Sharp bounds for the chromatic number of random Kneser graphs
share
Given positive integers n> 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,..., n}, with edges connecting pairs of disjoint sets. One of the classical results in combinatorics, conjectured by M. Kneser and proved by L. Lovász, states that the chromatic number of KG_n,k is equal to n-2k+2. In this paper, we study 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, χ(KG_n,k(1/2)) = n-Θ(√(_2 n)) and, for k=2, χ(KG_n,k(1/2)) = n-Θ(√(_2 n ·_2_2 n)). We also prove that, for any fixed l> 6 and k> C√( n), we have χ(KG_n,k(1/2))> n-2k+2-2l, where C=C(l) is an absolute constant. 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.
READ FULL TEXT