The exponential deficit conjecture for near-optimal Kneser graph colorings
The exponential deficit conjecture for near-optimal Kneser graph colorings
Let be the Kneser graph on the -element subsets of , with edges joining disjoint sets. Consider a subset of its vertices that is properly colorable with colors. Exponential deficit conjecture. The largest possible size of such a subset is at most
where is an absolute constant. This would strengthen the Lovász lower bound by asserting that deleting exponentially many vertices is necessary before an -coloring becomes possible. The corresponding edge version is posed immediately beforehand as a separate minimization problem.
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
Sergei Kiselev and Andrey Kupavskii, “Sharp bounds for the chromatic number of random Kneser graphs”, arXiv:1810.01161 (2021).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.