The almost-stable Kneser hypergraph colorability bound

Let [n]={1,,n}[n]=\{1,\ldots,n\}, let G\mathcal G be a hypergraph over the ground set [n][n], and let rs2r\geq s\geq 2. Write G{s-stable}~\mathcal G_{\widetilde{\{s\text{-stable}\}}} for the corresponding almost-stable restriction, let KGr(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 cdr(G)\operatorname{cd}^r(\mathcal G) denote the rr-colorability defect. The almost-stable Kneser hypergraph conjecture. Every such hypergraph satisfies

χ(KGr(G{s-stable}~))cdr(G)r1.\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.

Sources & referencesView supporting material

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.