Ziegler's conjecture for r-stable Kneser hypergraphs

About 17 years old · traced to

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,y∈Sx,y\in S satisfy r≤∣x−y∣≤n−rr\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 n≥rkn\geq rk and r≥2r\geq2, its chromatic number is

χ(KGr(n,k)r-Stab)=⌈n−r(k−1)r−1⌉.\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.

References

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.