On random subgraphs of Kneser graphs and their generalizations

DOI10.1134/S106456241605015XzbMath1357.05139MaRDI QIDQ512505

M. M. Pyaderkin, Andrei M. Raigorodskii

Publication date: 27 February 2017

Published in: Doklady Mathematics (Search for Journal in Brave)

zbMATH Keywords

independence number of random subgraphs of distance graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (13)

Sharp bounds for the chromatic number of random Kneser graphs ⋮ Independence numbers of random subgraphs of some distance graph ⋮ On the number of edges of a uniform hypergraph with a range of allowed intersections ⋮ A generalization of Kneser graphs ⋮ On the stability of the independence number of a random subgraph ⋮ On the random version of the Erdős matching conjecture ⋮ On stability of the independence number of a certain distance graph ⋮ Random Kneser graphs and hypergraphs ⋮ On the chromatic number of a random subgraph of the Kneser graph ⋮ On threshold probability for the stability of independent sets in distance graphs ⋮ Clique numbers of random subgraphs of some distance graphs ⋮ Degree versions of theorems on intersecting families via stability ⋮ Asymptotics of the independence number of a random subgraph of the graph \(G(n,r,<s)\)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Independence numbers of random subgraphs of a distance graph
• Independence numbers of random subgraphs of distance graphs
• Independence numbers and chromatic numbers of random subgraphs in some sequences of graphs
• On the stability of the Erdős-Ko-Rado theorem
• Intersection theorems with geometric consequences
• Coloring Distance Graphs and Graphs of Diameters
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Independence numbers and chromatic numbers of the random subgraphs of some distance graphs
• Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler

This page was built for publication: On random subgraphs of Kneser graphs and their generalizations