UW Combinatorics and Geometry Seminar: Shira Zerbib

We discuss several new results on Kneser graphs. First, we define the Kneser Ramsey number $R_r^{KG}(s,t)$RrKGst to be the minimum integer $n$n such that every red/blue edge-coloring of the Kneser graph $KG(n,r)$KGnr contains a red $s$s-clique or a blue $t$t-clique. We obtain general bounds on these numbers and make progress on two related Ramsey-type problems, one raised by Holmsen, Hrusak, and Roldan-Pensado, and the other posted by Palvolgyi. Next, we discuss the chromatic number of $s$s-stable Kneser graphs. Meunier conjectured in 2011 that the chromatic number of these graphs is $n-sk+s$nsks. The conjecture was previously proven for even $s$s or $s\ge 4$s and $n$n large enough. We prove the conjecture for $s=3$s and $n$n large enough, or when $k=s=3$ks. To this end, we prove a version of the Hilton–Milner theorem for $s$s-stable sets. We also present a topological approach towards Meunier's conjecture.