## 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.