Conjecture on random Kneser graph chromatic number

About 10 years old · traced to

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 k≫log⁡nk\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.

References

Primary source

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

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.