On the chromatic numbers of random subgraphs of Kneser graphs

A Kneser graph $KG_{n,k}$ is a graph whose vertices are all $k$-element subsets of $[n]$ and two vertices are connected if and only if the corresponding sets do not intersect. Kneser conjecture states that the chromatic number of such graph is $n - 2k + 2$. The conjecture was proved by Lov\'asz with the help of a topological approach.

A random subgraph $KG_{n,k}(p)$ is a spanning subgraph of $KG_{n,k}$ containing each edge of $KG_{n,k}$ with probability $p$. The chromatic numbers of random subgraphs of Kneser graphs and their generalizations were firstly studied by Bogoliubskiy, Gusev, Pyaderkin, and Raigorodskii. A related research was done by Bollob'\as, Narayanan, Raigorodskii and others. Kupavskii obtained the best known lower bounds for the chromatic numbers of $KG_{n,k}(p)$. He used a Lov\'asz type topological approach.

In this talk, I will give new upper and lower bounds for the chromatic numbers of $KG_{n,k}(p)$ using a purely combinatorial approach.