Casselgren–Häggkvist conjecture on random list coloring of balanced complete-bipartite line graphs

Let DD be an even natural number and let G=obreakL(KD2+1,D2+1)G= obreak\frac{}{}\mathcal{L}(K_{\frac{D}{2}+1,\frac{D}{2}+1}) be the line graph of a complete bipartite graph. Thus GG has n=(D2+1)2n=(\frac{D}{2}+1)^2 vertices and maximum degree DD. For each vertex vV(G)v\in V(G), choose L(v)([D2+1]k)L(v)\in\binom{[\frac{D}{2}+1]}{k} uniformly and independently. Casselgren–Häggkvist conjecture. There is a constant CC such that, whenever kClognk\geq C\log n,

\mathbbmP(G is L-colorable)=1on(1).\mathbbm{P}(G\text{ is }L\text{-colorable})=1-o_{n\to\infty}(1).

This conjecture was posed after Johansson asked for a threshold for random list coloring. It has since been proved by several papers, so the conjecture is solved.

Sources & referencesView supporting material

Primary source

Vikrant Ashvinkumar and Charles Kenney, “Palette Sparsification via FKNP”, arXiv:2408.12835 (2024).

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.