The exponential deficit conjecture for near-optimal Kneser graph colorings

From papers

Let KGn,kKG_{n,k} be the Kneser graph on the kk-element subsets of [n][n], with edges joining disjoint sets. Consider a subset of its vertices that is properly colorable with n2k+1n-2k+1 colors. Exponential deficit conjecture. The largest possible size of such a subset is at most

(nk)ck,\binom{n}{k}-c^k,

where c>1c>1 is an absolute constant. This would strengthen the Lovász lower bound χ(KGn,k)n2k+2\chi(KG_{n,k})\geqslant n-2k+2 by asserting that deleting exponentially many vertices is necessary before an (n2k+1)(n-2k+1)-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

No solutions have been posted yet.