Conjecture on random Kneser graph chromatic number
Conjecture on random Kneser graph chromatic number
Let be the Kneser graph on the -element subsets of , and let be its random subgraph obtained by retaining each edge independently with probability . Write for chromatic number. Random Kneser graph conjecture. For every fixed ,
whenever . 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
Sign in to submit a solution.
No solutions have been posted yet.