Chromatic concentration lower bound in G(n,p)

Open problem on lower bound for concentration interval · arXiv:0806.0178

arXiv Informal medium confidence— first stated 2017-10-18

Author: Alex Scott

Status solved high confidence

Heckel (2019, arXiv:1906.11808) proved that the chromatic number of G(n,1/2) is not concentrated on fewer than n^{1/4-epsilon} consecutive values, directly resolving the open problem by showing chi(G) cannot be confined to any constant-length interval. Heckel (2021, arXiv:2103.14014, JLMS) further improved the lower bound to at least n^{1/2-o(1)}, nearly matching the Alon-Scott upper bound of O(sqrt(n)/log n).

Cited literature (2)

proof Non-concentration of the chromatic number of a random graph (2019)

Annika Heckel · arXiv preprint · arXiv:1906.11808

Proves that the chromatic number of G(n,1/2) is not concentrated on fewer than n^{1/4-epsilon} consecutive values, establishing the first non-trivial lower bound on the concentration width and settling the open problem that no such lower bound was known.
partial How does the chromatic number of a random graph vary? (2021)

Annika Heckel · Journal of the London Mathematical Society · arXiv:2103.14014 · doi:10.1112/jlms.12794

Strengthens the lower bound on the concentration width to at least n^{1/2-o(1)}, nearly matching the upper bound, and under additional assumptions improves to approximately sqrt(n) log log n / log^3 n.

Reviewer notes. The open problem asked whether one could show chi(G(n,p)) for fixed p is not concentrated on a constant number of values; Heckel (2019) settled this decisively by proving a non-concentration result of n^{1/4-epsilon}, far stronger than the minimum needed. The 2021 follow-up essentially closes the gap with the Alon-Scott upper bound. The doi 10.1112/jlms.12794 was inferred from the JLMS direct-PDF URL in search results and not independently verified via WebFetch.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. For $p$ fixed, nothing is known from below concerning concentration: it has not even been shown that the chromatic number cannot be concentrated in an interval of constant length.

Context

After establishing that $\chi(G)$ for $G \in \mathcal{G}(n,p)$ with $p$ fixed is concentrated in an interval of length $\omega(n)\sqrt{n}/\log n$, the author notes that all known results give only upper bounds on the concentration width. Whether $\chi(G)$ could in fact be concentrated on a bounded (or even constant) number of values remains completely open. Bollobás [4, 6] is cited for further discussion of this question.

Notes. Stated as a prose observation without a labelled theorem environment. The precise open question is whether one can rule out constant-length concentration of chi(G(n,p)) for fixed p.

Source paper

On the concentration of the chromatic number of random graphs
Alex Scott · 2017-10-18
https://arxiv.org/abs/0806.0178 PDF source