Sharp bounds for the chromatic number of random Kneser graphs

DOI10.1016/J.JCTB.2022.05.010MaRDI QIDQ2171013zbMATH OpenOpenAlexFDO

Authors Sergei Kiselev, Andrey B. Kupavskii

Publication date 23 September 2022

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.01161

zbMATH Keywords

coloringsKneser graphsErdős-Ko-Rado theorem

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Extremal set theory (05D05)

Abstract: Given positive integers $nge2k$, the {it Kneser graph} $K{G}_{n,k}$ is a graph whose vertex set is the collection of all $k$-element subsets of the set $1,ldots,n$, with edges connecting pairs of disjoint sets. One of the classical results in combinatorics, conjectured by Kneser and proved by Lov'asz, states that the chromatic number of $K{G}_{n,k}$ is equal to $n-2k+2$. In this paper, we study the chromatic number of the {it random Kneser graph} $K{G}_{n,k}(p)$, that is, the graph obtained from $K{G}_{n,k}$ by including each of the edges of $K{G}_{n,k}$ independently and with probability $p$. We prove that, for any fixed $kge3$, $chi(K{G}_{n,k}(1/2))=n-Theta(sqrt[2k-2]lo{g}_{2}n)$, as well as $chi(K{G}_{n,2}(1/2))=n-Theta(sqrt[2]lo{g}_{2}ncdotlo{g}_{2}lo{g}_{2}n)$. We also prove that, for $kge(1+varepsilon)loglogn$, we have $chi(K{G}_{n,k}(1/2))gen-2k-10$. This significantly improves previous results on the subject, obtained by Kupavskii and by Alishahi and Hajiabolhassan. The bound on $k$ in the second result is also tight up to a constant. We also discuss an interesting connection to an extremal problem on embeddability of complexes.

Recommendations

• On random subgraphs of Kneser and Schrijver graphs
• Random Kneser graphs and hypergraphs
• On some topological and combinatorial lower bounds on the chromatic number of Kneser type hypergraphs
• Chromatic number of random Kneser hypergraphs
• On the chromatic number of the general Kneser-graph

Cites work

• scientific article; zbMATH DE number 3672329 (Why is no real title available?)
• scientific article; zbMATH DE number 3561377 (Why is no real title available?)
• scientific article; zbMATH DE number 3221072 (Why is no real title available?)
• A combinatorical proof of Kneser's conjecture
• Chromatic number of random Kneser hypergraphs
• Diversity of uniform intersecting families
• Edge-critical subgraphs of Schrijver graphs. II: The general case
• Extremal problems concerning Kneser-graphs
• Families with no s pairwise disjoint sets
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Improved bounds for Erdős' matching conjecture
• Independence numbers and chromatic numbers of random subgraphs in some sequences of graphs
• Independence numbers and chromatic numbers of the random subgraphs of some distance graphs
• Kneser's conjecture, chromatic number, and homotopy
• On ``stability in the Erdős-Ko-Rado theorem
• On chromatic numbers of nearly Kneser distance graphs
• On random subgraphs of Kneser and Schrijver graphs
• On random subgraphs of Kneser graphs and their generalizations
• On the chromatic number of a random subgraph of the Kneser graph
• On the stability of some Erdős-Ko-Rado type results
• On the stability of the Erdős-Ko-Rado theorem
• On the union of intersecting families
• Random Kneser graphs and hypergraphs
• Removal and stability for Erdős-Ko-Rado
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Stability versions of Erdős-Ko-Rado type theorems via isoperimetry
• The Chromatic Number of Kneser Hypergraphs
• The Erdős matching conjecture and concentration inequalities
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Transference for the Erdős-Ko-Rado theorem
• Two problems on matchings in set families -- in the footsteps of Erdős and Kleitman
• 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

Cited in

(12)

• Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
• On random subgraphs of Kneser and Schrijver graphs
• Kneser ranks of random graphs and minimum difference representations
• On the Hadwiger number of Kneser graphs and their random subgraphs
• Kneser ranks of random graphs and minimum difference representations
• scientific article; zbMATH DE number 1420986 (Why is no real title available?)
• Random Kneser graphs and hypergraphs
• A note on the sharp concentration of the chromatic number of random graphs
• Trivial colors in colorings of Kneser graphs
• Chromatic numbers of Kneser-type graphs
• Fixed-Parameter Algorithms for the Kneser and Schrijver Problems
• Sharp bounds for the chromatic number of random Kneser graphs

This page was built for publication: Sharp bounds for the chromatic number of random Kneser graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2171013)