Ziegler's conjecture for r-stable Kneser hypergraphs

Let KGr(n,k)KG^r(n,k) be the Kneser hypergraph whose vertices are the kk-element subsets of [n][n], and call a subset S[n]S\subseteq[n] rr-stable when any two elements x,ySx,y\in S satisfy rxynrr\leq |x-y|\leq n-r. Let KGr(n,k)r-StabKG^r(n,k)_{r\text{-}\mathrm{Stab}} be the sub-hypergraph induced by the rr-stable vertices. Ziegler's conjecture. For all nrkn\geq rk and r2r\geq2, its chromatic number is

χ(KGr(n,k)r-Stab)=nr(k1)r1.\chi\bigl(KG^r(n,k)_{r\text{-}\mathrm{Stab}}\bigr)=\left\lceil\frac{n-r(k-1)}{r-1}\right\rceil.

This asserts that the Alon–Frankl–Lovász chromatic-number formula remains valid after restricting to rr-stable vertices. The source attributes the conjecture to Ziegler; no resolution status is supplied here.

Sources & referencesView supporting material

Primary source

Yufeng Shen, Zhiyu Song, Feneglin Yu, Leopold Wuhan Zhou and Jingqi Zhuang, “Neighborhood Complexes of induced k-independent graphs”, arXiv:2512.09674 (2025).

Additional references

4 papers in this index state this conjecture (2009–2025). The statement above is taken from the most recent of them; the others are arXiv:2509.22026, arXiv:1712.03456, arXiv:0912.4748.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.