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

At least 1 year old · documented by

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 v∈V(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 k≥Clog⁡nk\geq C\log n,

P(G is L-colorable)=1−on→∞(1).\mathbb{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.

References

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.