Abstract:
We discuss several new results on Kneser graphs. First, we define the Kneser Ramsey number \$R^{KG}_r(s, t)\$ to be the minimum integer \$n\$ such that every red/blue edge-coloring of the Kneser graph \$KG(n, r)\$ contains a red \$s\$-clique or a blue \$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\$-stable Kneser graphs. Meunier conjectured in 2011 that the chromatic number of these graphs is \$n - sk +s\$. The conjecture was previously proven for even \$s\$ or \$s\geq 4\$ and \$n\$ large enough. We prove the conjecture for \$s=3\$ and \$n\$ large enough, or when \$k=s=3\$. To this end, we prove a version of the Hilton–Milner theorem for \$s\$-stable sets. We also present a topological approach towards Meunier's conjecture.
Note: This talk begins with a pre-seminar (aimed at graduate students) at 3:30–4:00. The main talk starts at 4:10.
Join Zoom Meeting: https://washington.zoom.us/j/
Meeting ID: 915 4733 5974