The chromatic number of 3-stable Kneser graphs

Abstract

For an integer $s\ge 2$, a subset $S\subseteq [n]$ is {\em $s$-stable} if $\min \{j-i,n+i-j\}\ge s$ for every $i,j\in S$ with $i<j$. Denote the set of all $s$-stable subsets of size $k$ of $[n]$ by ${\left(\genfrac{}{}{0ex}{}{[n]}{k}\right)}_{s\text{-stable}}$. Schrijver proved in 1978 that whenever $n\ge 2k$, the chromatic number of the Kneser graph $\mathrm{KG}\left({\left(\genfrac{}{}{0ex}{}{[n]}{k}\right)}_{2\text{-stable}}\right)$ is $n-2k+2$. Generalizing this result, Meunier conjectured in 2011 that $\chi \left(\mathrm{KG}\left({\left(\genfrac{}{}{0ex}{}{[n]}{k}\right)}_{s\text{-stable}}\right)\right)=n-sk+s$ for all $n\ge sk$. This conjecture was previously proven for all even $s$, for $s\ge 4$ and large enough $n$, and for $k=2$. We prove the conjecture in the cases $s=3$ and $n$ large enough, or $k=s=3$. To this end, we prove versions of the Hilton-Milner theorem for $s$-stable sets. We also present a topological approach towards Meunier's conjecture.