Worst-case variance conjecture for the chromatic number of random graphs
Let be the binomial random graph with constant , let , and let . Define
Worst-case variance conjecture. One has
Moreover, for every constant there is a constant such that, along every sequence of integers satisfying , one has . This conjecture proposes that the polylogarithmic lower bound for the variance has the correct order in the worst case; the paper notes that one inequality is already implied by a theorem subject to an announced result.
References
Primary source
Annika Heckel and Oliver Riordan, “How does the chromatic number of a random graph vary?”, arXiv:2103.14014 (2023).
Additional references
2 papers in this index state this conjecture (2019–2021). The statement above is taken from the most recent of them; the others are arXiv:1903.08247.
Progress summary
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.