Worst-case variance conjecture for the chromatic number of random graphs

About 7 years old · traced to

Let Gn,pG_{n,p} be the binomial random graph with constant p∈(0,1−1/e2]p\in(0,1-1/e^2], let Yn=χ(Gn,p)Y_n=\chi(G_{n,p}), and let σn2=Var⁡(Yn)\sigma_n^2=\operatorname{Var}(Y_n). Define

wn=nlog⁡log⁡nlog⁡3n.w_n=\frac{\sqrt n\log\log n}{\log^3 n}.

Worst-case variance conjecture. One has

0<lim sup⁡σnwn<∞.0<\limsup\frac{\sigma_n}{w_n}<\infty.

Moreover, for every constant c>0c>0 there is a constant d>0d>0 such that, along every sequence of integers nn satisfying μα(n)(n)∼cn/log⁡2n\mu_{\alpha(n)}(n)\sim c n/\log^2 n, one has σn∼dwn\sigma_n\sim d w_n. 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

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.