Combinatorics Seminar

When: Sunday, April 12, 10am Where: Schreiber 309 Speaker: Andrey Kupavskii, EPFL Title: Random subgraphs of Kneser and Schrijver graphs

Abstract:

A Kneser graph KG_{n,k} is a graph whose vertices are in one-to-one correspondence with k-element subsets of [n], with two vertices connected if and only if the corresponding sets do not intersect. A famous result due to Lovasz states that the chromatic number of a Kneser graph KG_{n,k} is equal to n-2k+2. We discuss the chromatic number of random subgraphs of KG_{n,k}(p), obtained by including each edge of KG_{n,k} with probability p. For a wide range of parameters k, p we show that \chi(KG_{n,k}(p)) is very close to \chi(KG_{n,k}), a.a.s. 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.