Sharp bounds for the chromatic number of random Kneser graphs

Abstract

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.