The almost-stable Kneser hypergraph colorability bound

About 4 years old · traced to

Let [n]={1,…,n}[n]=\{1,\ldots,n\}, let G\mathcal G be a hypergraph over the ground set [n][n], and let r≥s≥2r\geq s\geq 2. Write G{s-stable}~\mathcal G_{\widetilde{\{s\text{-stable}\}}} for the corresponding almost-stable restriction, let KG⁡r(G{s-stable}~)\operatorname{KG}^r(\mathcal G_{\widetilde{\{s\text{-stable}\}}}) be its rr-uniform Kneser hypergraph, let χ\chi denote chromatic number, and let cd⁡r(G)\operatorname{cd}^r(\mathcal G) denote the rr-colorability defect. The almost-stable Kneser hypergraph conjecture. Every such hypergraph satisfies

χ(KG⁡r(G{s-stable}~))≥⌈cd⁡r(G)r−1⌉.\chi\left(\operatorname{KG}^r\left(\mathcal G_{\widetilde{\{s\text{-stable}\}}}\right)\right)\geq\left\lceil\frac{\operatorname{cd}^r(\mathcal G)}{r-1}\right\rceil.

This conjecture is proposed in the paper as a partial answer to a problem concerning how large the gap between the colorability-defect bound and the chromatic number can be. The supplied text gives no resolution.

References

Primary source

Saeed Shaebani, “Concerning Two Conjectures of Frick and Jafari”, arXiv:2206.00836 (2022).

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.