On the Chromatic Number of Stable Kneser Hypergraphs: Verifying the Conjecture for New Families

Abstract

One of the key unsolved conjectures in hypergraph coloring is about the chromatic number of $s$-stable $r$-uniform Kneser hypergraphs ${\mathrm{KG}}^r(n,k{)}_{s\text{-stab}}$. The problem remains largely open, particularly in the case where $s>r\ge 3$. To the best of our knowledge, no information is available except a limited number of computations conducted for the instances when $r=3,4$, $s=4,5$, $k=2,3$ with some $n$ does not exceed 14. In this study, we verify the conjecture for infinity many values of the parameters $n$ and $k$. In particular, we demonstrate: (i) the validity of the conjecture for $r=4$, $s=6$ under the condition that $3\mid n$ or $k=2$, and (ii) for $r=4$, $k=2$, $s=5$ given $3\nmid n$. As far as we are aware, this provides the first rigorous theoretical proof of the conjecture (for the case $s>r\ge 3$) for infinitely many parameter values, extending beyond finite computational verification. Furthermore, our methods rely on a detailed study of vector-stable Kneser graphs, an approach that not only yields these results but also provides a deeper understanding of their chromatic numbers.