Non-concentration of the chromatic number of G(n,1/2) (Heckel 2021)

Statement

For the binomial random graph $G_{n,1/2}$ (each of the $\binom n2$ possible edges present independently with probability $1/2$), the celebrated Shamir–Spencer / Bollobás theory pins down the chromatic number $\chi(G_{n,1/2})$ to within a window of width $O(\sqrt n)$ around $\frac{n}{2\log_2 n}$, whp. This left a large gap: is $\chi(G_{n,1/2})$ in fact concentrated far more sharply than that — e.g. on an interval of length $o(\sqrt n)$, or even on just one or two values, as it is known to be for other random-graph parameters like the independence number?

Erdős asked how accurately $\chi(G_{n,1/2})$ can be estimated, and Bollobás (2004), reporting having "discussed the question frequently with Erdős," explicitly requested *any* non-trivial proof of a lack of concentration — i.e. any genuine lower bound on how wide the true concentration window must be — remarking that "even the weakest results claiming lack of concentration would be of interest." No such result existed for over 30 years after Shamir–Spencer (1987).

The solved problem: prove a non-trivial *non-concentration* result — a lower bound on the width of any interval that contains $\chi(G_{n,1/2})$ whp.

Facts

- Classical baseline (pre-existing, not itself in question): - Shamir & Spencer, *Combinatorica* 7 (1987), 121–129, "Sharp concentration of the chromatic number on random graphs $G_{n,p}$": using the vertex-exposure martingale (the first application of martingale concentration to random graph theory), $\chi(G_{n,p})$ lies whp in an interval of width $O(\omega\sqrt n)$ for any $\omega=\omega(n)\to\infty$. - Alon (unpublished, cited in later papers) slightly sharpened this to width $O(\sqrt n/\log n)$ for constant $p$, adapting a Bollobás colouring argument. - Bollobás, *Combinatorica* 8 (1988), 49–55, "The chromatic number of random graphs": a refined martingale argument pins down the leading-order value $\chi(G_{n,1/2}) \sim \frac{n}{2\log_2 n}$ whp — but says nothing about how tight the true concentration window is beyond the $O(\sqrt n)$ bound above. - Before 2019, it was open (and widely believed possible) that concentration could be far sharper than $O(\sqrt n)$ — folklore even entertained near-rigidity / two-point concentration, by analogy with parameters like the independence number, which genuinely is two-point concentrated. - Status: SOLVED. Annika Heckel, "Non-concentration of the chromatic number of a random graph," arXiv:1906.11808 (2019); published *J. Amer. Math. Soc.* 34 (2021), no. 1, 245–260. Theorem: for any constant $c<\tfrac14$, $\chi(G_{n,1/2})$ is not contained in any sequence of intervals of length $n^c$ with high probability — equivalently, along an infinite sequence of $n$, no interval of length $n^{1/4-\varepsilon}$ can capture $\chi(G_{n,1/2})$ whp, for any fixed $\varepsilon>0$. This was the first non-trivial non-concentration result, directly answering Erdős's/Bollobás's question. - Announced as "sensational" by Gil Kalai (blog, June 2019); the underlying line of work later received a 2024 Frontiers of Science Award in Mathematics at the International Congress of Basic Science. - Improved by Heckel & Riordan, "How does the chromatic number of a random graph vary?", arXiv:2103.14014, *J. London Math. Soc.* 108(5) (2023), 1769–1815: - Unconditionally, the concentration width is at least $n^{1/2-o(1)}$ for *some* values of $n$ — matching the Shamir–Spencer/Alon upper bound up to the error term, i.e. essentially closing the gap for those $n$. - Conditionally (on a plausible structural hypothesis about maximum independent sets), width $\gtrsim \sqrt n\,\log\log n/\log^3 n$ for a *positive density* of $n$. - They conjecture the true fluctuation of $\chi(G_{n,1/2})$ is of order $\sqrt n$ with an asymptotically Gaussian limiting shape (after rescaling) — i.e. that no sharper concentration than the Shamir–Spencer window is possible, essentially closing the qualitative question even though the fully general quantitative statement (for *all* $n$, unconditionally) remains open. - Machinery further generalized in Heckel & Panagiotou, "Colouring random graphs: Tame colourings," arXiv:2306.07253, into a reusable "tame colouring profile" second-moment framework. - This result later served as the load-bearing input for a second, independent problem: Heckel (arXiv:2408.13839, 2024) and Steiner (arXiv:2408.02400, 2024) independently showed that Erdős–Gimbel's open \$1000 question of whether $\chi(G_{n,1/2})-\zeta(G_{n,1/2})\to\infty$ (cochromatic number gap, Erdős #625 — does χ(G)−ζ(G)→∞ for random G(n,1/2)?) reduces via a Harris–FKG argument to exactly this non-concentration quantity — plugging in Heckel's and Heckel–Riordan's bounds gives the current best partial progress on that still-open problem.

Solution

Answer: YES — non-concentration holds. $\chi(G_{n,1/2})$ is *not* concentrated on any interval of length $n^{1/4-\varepsilon}$ (Heckel 2021), later strengthened to $n^{1/2-o(1)}$ for some $n$ (Heckel–Riordan 2023) — matching the classical $O(\sqrt n)$ upper bound and showing that, at least along a subsequence, the Shamir–Spencer window cannot be improved much further.

**The transferable technique — an explicit coupling that transports the fluctuation of a *secondary* extremal statistic (independent-set counts) into a proof of non-concentration of the *primary* statistic (chromatic number), by comparing two different values of $n$.**

1. Find a secondary statistic with large, well-understood relative fluctuation. Fix $a$ near the scale of the independence number (so $\varepsilon<x<\tfrac12-\varepsilon$ where $\mu := \mathbb E[X_a] = n^x$, $X_a$ = number of independent $a$-sets). While the independence number itself is essentially rigid, the *count* $X_a$ of independent sets of that near-extremal size is not concentrated relative to its mean: its standard deviation is of order $\sqrt\mu = n^{x/2}$, a genuine, provable fluctuation in a quantity that is otherwise easy to compute exactly. 2. Build an explicit coupling linking $G_{n,1/2}$ to $G_{n',1/2}$ for a nearby $n' = n + ra$ ($r\approx n^{x/2}$). Condition $G_{n,1/2}$ on $X_a = A$ and $G_{n',1/2}$ on $X_a = A+r$; construct both simultaneously so that $G_{n,1/2}$ sits as an induced subgraph of $G_{n',1/2}$, with the extra $ra$ vertices splitting into exactly $r$ disjoint new independent $a$-sets. This is possible precisely because both target counts ($A$ and $A+r$) are typical values for their respective $n,n'$, by the fluctuation established in step 1. 3. Turn the coupling into an inequality between the two chromatic numbers. Colour the $r$ new independent blocks with $r$ fresh colours to get $\chi(G_{n',1/2}) \le \chi(G_{n,1/2}) + r$. If both chromatic numbers were confined to their "typical" windows $[s_n,t_n]$ and $[s_{n'},t_{n'}]$ of width $\ell_n, \ell_{n'}$, this forces a relation between $s_{n'}, s_n$, and $r$. 4. Compare against the known deterministic asymptotic formula. Bollobás's asymptotic $f(n) = \frac{n}{2\log_2 n - 2\log_2\log_2 n - 2}(1+o(1))$ is a smooth, essentially deterministic function of $n$; a direct calculus computation of $f(n')-f(n)$ for the specific $n'=n+ra$ shows it exceeds the "budget" $r$ that the typical-window inequality from step 3 would allow — *unless* the window widths $\ell_n,\ell_{n'}$ are themselves large enough to absorb the discrepancy. Iterating this comparison across a sequence of $n$ forces $\ell_{n^*} \gtrsim n^{1/4-\varepsilon}$ (later sharpened to $n^{1/2-o(1)}$) for some $n^*$ in the sequence — a contradiction with any assumed tighter concentration. 5. The reusable idea, stated abstractly: whenever a quantity's *expectation* is governed by a smooth, essentially deterministic formula in a parameter $n$, but some *auxiliary* combinatorial count feeding into that quantity has demonstrably large relative fluctuation (not concentrated around its own mean), build an explicit coupling across two nearby values of $n$ that exploits the auxiliary count's fluctuation to produce two graphs, one an induced subgraph of the other, differing by a controlled, colourable "patch." Comparing the resulting inequality against the deterministic asymptotic formula for the primary quantity converts fluctuation in the auxiliary statistic into a non-concentration proof for the primary one. This "parameter-interpolation coupling" is exactly the engine later reused (via the Harris–FKG correlation-inequality variant, comparing $\chi(G)$ and $\chi(\bar G)$ instead of $\chi(G_n)$ and $\chi(G_{n'})$) to attack the Erdős–Gimbel cochromatic-number gap in Erdős #625 — does χ(G)−ζ(G)→∞ for random G(n,1/2)?.

Related

- Erdős #625 — does χ(G)−ζ(G)→∞ for random G(n,1/2)? — open Erdős–Gimbel \$1000 question ($\chi(G_{n,1/2})-\zeta(G_{n,1/2})\to\infty$?) whose best current partial results (Heckel 2024, Steiner 2024) are built directly on top of this non-concentration result, via a Harris–FKG argument comparing $\chi(G)$ and $\chi(\bar G)$. - Erdős #762 — is χ(G)≤ζ(G)+2 when ω(G)<5 and ζ(G)≥4? (Erdős–Gimbel–Straight 1988) — sibling, already-solved problem from the same Erdős–Gimbel cochromatic-number literature (disproved by Steiner 2024 via an unrelated gadget/blow-up construction, not this coupling technique). - Vertex-exposure martingale + Azuma–Hoeffding concentration for graph parameters — the classical Shamir–Spencer / Bollobás martingale machinery this result contrasts with (establishes the $O(\sqrt n)$ upper bound on concentration width that Heckel–Riordan's non-concentration bound nearly matches from below). - Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs — the variance/fluctuation estimate on $X_a$ (number of independent $a$-sets) that step 1 of the coupling technique relies on. - Tame colouring profiles — smoothness/tail conditions making second-moment analysis of random-graph colourings tractable — Heckel–Panagiotou's (arXiv:2306.07253) generalization of this coupling machinery into a reusable second-moment framework for both ordinary and co-colourings. - Harris–FKG correlation inequality for increasing/decreasing events (random graphs, percolation) — the correlation-inequality variant of this technique (comparing $G$ and its complement $\bar G$ rather than $G_n$ and $G_{n'}$) used to derive Erdős #625 — does χ(G)−ζ(G)→∞ for random G(n,1/2)?'s partial results from this result. - Ramsey-type concentration of the independence/clique number of G(n,1/2) — Bollobás–Erdős / Matula's result that the independence number itself *is* essentially two-point concentrated, the contrasting fact that makes non-concentration of $\chi$ surprising and non-trivial to prove. - Non-concentration of the chromatic number of a random graph (Heckel / Heckel–Riordan / Heckel–Panagiotou) — concept-level pointer to this whole result line (Heckel 2021; Heckel–Riordan 2023; Heckel–Panagiotou arXiv:2306.07253), of which this page is the detailed solved-problem writeup.