Sharp bounds for the chromatic number of random Kneser graphs

Given positive integers n >= 2k, the {\it Kneser graph} KG(n,k) is a graph whose vertex set is the collection of all k-element subsets of the set {1, horizontexpressionl ellipsis ,n}, with edges connecting pairs of disjoint sets. One of the classical results in combinatorics, conjectured by Kneser and proved by Lovasz, states that the chromatic number of KG(n,k) is equal to n-2k+2. In this paper, we study the chromatic number of the random Kneser graph} KG(n,k)(p), that is, the graph 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 >= 3, chi(KG(n,k)(1/2))=n-theta((2k-2)root log(2)n), as well as chi(KG(n,2)(1/2))=n-theta((2)root log(2)n center dot log(2)log(2)n). We also prove that, for k >=(1+epsilon)log log n, we have chi(KG(n,k)(1/2))>= n-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. (C) 2022 Elsevier Inc. All rights reserved.