Chromatic number conjecture for powers of cycle Kneser hypergraphs

From papers

For integers ns2n\geqslant s\geqslant2 with n>ksn>ks, let Cns1C_n^{s-1} be the (s1)(s-1)-st power of the cycle of length nn, and let K(n,k,s)K(n,k,s) be the ss-uniform hypergraph whose vertices are the independent kk-sets of Cns1C_n^{s-1}, with an edge formed by every ss pairwise disjoint such sets. Chromatic number conjecture. For n>ksn>ks,

χ(K(n,k,s))=nks+ss1.\chi\bigl(K(n,k,s)\bigr)=\left\lceil\frac{n-ks+s}{s-1}\right\rceil.

The paper attributes this conjecture to Alon, Dol'nikov and collaborators and notes that it is proved when ss is a power of 22; the general case remains open.

Progress summary

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

Sources & referencesView supporting material

Primary source

Ron Aharoni, Noga Alon, Eli Berger, Maria Chudnovsky, Dani Kotlar, Martin Loebl and Ran Ziv, “Fair representation by independent sets”, arXiv:1611.03196 (2016).

Solutions 0

No solutions have been posted yet.