Conjecture on random Kneser graph chromatic number

From papers

Let KGn,kKG_{n,k} be the Kneser graph on the kk-element subsets of [n][n], and let KGn,k(p)KG_{n,k}(p) be its random subgraph obtained by retaining each edge independently with probability pp. Write χ\chi for chromatic number. Random Kneser graph conjecture. For every fixed p>0p>0,

χ(KGn,k(p))χ(KGn,k)4\chi\bigl(KG_{n,k}(p)\bigr)\ge \chi\bigl(KG_{n,k}\bigr)-4

whenever klognk\gg\log n. This conjecture proposes that, in the indicated range, passing to a random subgraph lowers the chromatic number by at most an additive constant; the supplied passage states that the corresponding question is open and gives no resolution of this conjecture.

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

Andrey Kupavskii, “Random Kneser graphs and hypergraphs”, arXiv:1612.03868 (2018).

Solutions 0

No solutions have been posted yet.