On random subgraphs of Kneser and Schrijver graphs

A Kneser graph KGn,kKGn,k is a graph whose vertices are in one-to-one correspondence with k  -element subsets of [n][n], with two vertices connected if and only if the corresponding sets do not intersect. A famous result due to Lovász states that the chromatic number of a Kneser graph KGn,kKGn,k is equal to n−2k+2n−2k+2. In this paper we study the chromatic number of a random subgraph of a Kneser graph KGn,kKGn,k as n   grows. A random subgraph KGn,k(p)KGn,k(p) is obtained by including each edge of KGn,kKGn,k with probability p  . For a wide range of parameters k=k(n)k=k(n), p=p(n)p=p(n) we show that χ(KGn,k(p))χ(KGn,k(p)) is very close to χ(KGn,k)χ(KGn,k), w.h.p. differing by at most 4 in many cases. Moreover, we obtain the same bounds on the chromatic numbers for the so-called Schrijver graphs, which are known to be vertex-critical induced subgraphs of Kneser graphs.