Sharp bounds for the chromatic number of random Kneser graphs

Main Article Content

Sergei Kiselev Andrey Kupavskii


Given positive integers $n\ge 2k$, a Kneser graph $KG_{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. A famous result due to L. Lov\'asz states that the chromatic number of $KG_{n,k}$ is equal to $n-2k+2$. In this paper, we study the {\it random Kneser graph} $KG_{n,k}(p)$, obtained from $KG_{n,k}$ by including each of the edges of $KG_{n,k}$ independently and with probability $p$.
We prove that, for any fixed $k\ge 3$, $\chi(KG_{n,k}(1/2)) = n-\Theta(\sqrt[2k-2]{\log_2 n})$. We also provide new bounds for the case of growing $k$. This significantly improves previous results on the subject, obtained by Kupavskii and by Alishahi and Hajiabolhassan. We also discuss an interesting connection to an extremal problem on embeddability of complexes.

Article Details

How to Cite
Kiselev, S., & Kupavskii, A. (2019). Sharp bounds for the chromatic number of random Kneser graphs. Acta Mathematica Universitatis Comenianae, 88(3), 861-865. Retrieved from