Non-concentration of the chromatic number of a random graph (Heckel / Heckel–Riordan / Heckel–Panagiotou)

Statement

Non-concentration here means: proving a lower bound on the width of any interval that contains the chromatic number $\chi(G_{n,1/2})$ of the binomial random graph with high probability (whp) — the opposite direction from the classical concentration results, which give upper bounds on that width.

Classical background (Shamir–Spencer 1987, *Combinatorica* 7:121–129; Bollobás 1988, *Combinatorica* 8:49–55): $\chi(G_{n,1/2})$ lies whp in an interval of width $O(\sqrt n)$ around the deterministic asymptotic value $f(n) = \dfrac{n}{2\log_2 n - 2\log_2\log_2 n - 2}(1+o(1))$; Alon sharpened the width slightly to $O(\sqrt n/\log n)$. For over 30 years no non-trivial *lower* bound on the width was known, and it was open whether $\chi(G_{n,1/2})$ might in fact be far more sharply concentrated (even two-point concentrated, as the independence number is).

Theorem (Heckel 2019/2021). For any fixed $\varepsilon>0$, along an infinite sequence of $n$, no interval of length $n^{1/4-\varepsilon}$ contains $\chi(G_{n,1/2})$ whp. Equivalently: the true concentration width is $\ge n^{1/4-o(1)}$ for infinitely many $n$. (A. Heckel, "Non-concentration of the chromatic number of a random graph," arXiv:1906.11808; *J. Amer. Math. Soc.* 34(1) (2021), 245–260.)

Theorem (Heckel–Riordan 2021/2023). - Unconditionally, the width is $\ge n^{1/2-o(1)}$ for *some* values of $n$ — matching the Shamir–Spencer/Alon upper bound up to the error term. - Conditionally on a sharper explicit estimate for $\chi(G_{n,1/2})$ (announced but not fully published at the time), the width is $\ge \Omega\!\left(\sqrt n\,\log\log n/\log^3 n\right)$ for a positive density of $n$ — within a logarithmic factor of the upper bound. (A. Heckel, O. Riordan, "How does the chromatic number of a random graph vary?," arXiv:2103.14014; *J. London Math. Soc.* 108(5) (2023), 1769–1815.)

Zigzag Conjecture (attributed to Bollobás, Heckel, Morris, Panagiotou, Riordan, Smith; stated in Heckel–Riordan JLMS 2023): writing $\mu_\alpha = n^{\theta}$ for the (fluctuating, $n$-dependent) expected number of maximum independent sets and $\lambda = \max(\theta/2,(1-\theta)/2)$, the true width of the distribution of $\chi(G_{n,1/2})$ should be $n^{\lambda+o(1)}$ — a quantity that oscillates with $n$ between $\approx n^{1/4+o(1)}$ (best case) and $\approx n^{1/2+o(1)}$ (worst case) as $\log n$ varies, with a conjectured Gaussian limiting shape after rescaling. This conjecture remains open; the widest-case value matches Heckel–Riordan's unconditional lower bound.

Facts

- Origin of the question. Erdős asked how accurately $\chi(G_{n,1/2})$ can be estimated; Bollobás (2004) explicitly requested any non-trivial proof of a lack of concentration, remarking that "even the weakest results claiming lack of concentration would be of interest." This 30-year-open request is exactly what Heckel's 2019 paper answers. - Contrast with other random-graph parameters. The independence number $\alpha(G_{n,1/2})$ *is* essentially two-point concentrated (Bollobás–Erdős / Matula), which is what made it plausible before 2019 that $\chi(G_{n,1/2})$ could likewise be far more sharply concentrated than the $O(\sqrt n)$ martingale bound suggested — see Ramsey-type concentration of the independence/clique number of G(n,1/2). The non-concentration results show the two statistics behave qualitatively differently. - Heckel's result was called "sensational" by Gil Kalai on his blog (June 2019); the line of work (Heckel 2021 + Heckel–Riordan 2023) received a 2024 Frontiers of Science Award in Mathematics at the International Congress of Basic Science. - Heckel–Panagiotou generalization. "Colouring random graphs: Tame colourings" (arXiv:2306.07253, 2023) introduces the $t$-bounded chromatic number $\chi_t(G)$ (colourings restricted to colour classes of size $\le t$) and proves: (i) for $t=\alpha(G)-2$, $\chi_t(G_{n,m})$ *is* concentrated on at most two explicit values (a "tame colouring" second-moment result, unlike the ordinary chromatic number); (ii) for $t = \alpha(G_{n,1/2})-1$, an interval of length $n^{0.99}$ containing $\chi_t$ whp can be pinned down under mild conditions on independent-set counts. Result (ii) is stated as "an important ingredient in the proof of a non-concentration result for $\chi(G_{n,1/2})$." This generalizes the coupling machinery into a reusable second-moment "tame colouring profile" framework — see Tame colouring profiles — smoothness/tail conditions making second-moment analysis of random-graph colourings tractable. - Downstream application. This non-concentration result is the load-bearing input for the best current partial progress on the (still open) Erdős–Gimbel cochromatic-number question — whether $\chi(G_{n,1/2}) - \zeta(G_{n,1/2}) \to \infty$ — via Heckel (arXiv:2408.13839, 2024) and Steiner (arXiv:2408.02400, 2024) independently, using a Harris–FKG correlation-inequality variant comparing $\chi(G)$ and $\chi(\bar G)$. See Erdős #625 — does χ(G)−ζ(G)→∞ for random G(n,1/2)? and the sibling page Non-concentration of the chromatic number of G(n,1/2) (Heckel 2021).

Technique

When it applies. This is the right tool whenever you want to prove that a graph parameter of $G_{n,p}$ is not as tightly concentrated as a naive martingale/Lipschitz argument (e.g. vertex-exposure or edge-exposure martingale, giving $O(\sqrt n)$-type width bounds) would suggest, and you suspect the truth is close to that upper bound rather than far below it. It is specifically built for parameters like $\chi(G_{n,1/2})$ whose expectation/typical value is governed by a smooth, essentially deterministic asymptotic formula in $n$ (Bollobás's $f(n)$), while some auxiliary combinatorial count feeding into that parameter (here: the number $X_a$ of independent sets of size $a$ near the independence-number scale) has demonstrably large relative fluctuation around its own mean.

Why it works (the mechanism). 1. Find a fluctuating secondary statistic. Fix $a$ near the independence-number scale so that $\mu := \mathbb E[X_a] = n^x$ for suitable $x$. While $\alpha(G_{n,1/2})$ itself is nearly rigid (two-point concentrated), the *count* $X_a$ of independent $a$-sets is not concentrated relative to its mean — its standard deviation is of order $\sqrt\mu = n^{x/2}$, provable by a second-moment computation on the number of independent sets (see Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs). 2. Build an explicit coupling between two nearby $n$'s. Condition $G_{n,1/2}$ on $X_a=A$ and $G_{n',1/2}$ (with $n' = n+ra$, $r \approx n^{x/2}$) on $X_a = A+r$, and construct both simultaneously so $G_{n,1/2}$ sits as an induced subgraph of $G_{n',1/2}$, with the extra $ra$ vertices forming exactly $r$ new disjoint independent $a$-sets. This is possible precisely because both target counts are *typical* for their respective $n,n'$, using the fluctuation from step 1. 3. Convert the coupling into a chromatic-number inequality. Colour the $r$ new independent blocks with $r$ fresh colours: $\chi(G_{n',1/2}) \le \chi(G_{n,1/2}) + r$. If $\chi$ were confined to narrow typical windows $[s_n,t_n]$, $[s_{n'},t_{n'}]$, this constrains $s_{n'}-s_n$ to be $\le$ roughly $r$ plus the window widths. 4. Contradict via the deterministic asymptotic formula. Bollobás's smooth formula $f(n)$ gives an exact calculus value for $f(n')-f(n)$ that, for the specific $n'=n+ra$ chosen, *exceeds* the budget $r$ the coupling inequality allows — unless the window widths $\ell_n,\ell_{n'}$ are themselves large enough to absorb the discrepancy. Iterating across a sequence of $n$ forces $\ell_{n^*} \gtrsim n^{1/4-\varepsilon}$ (Heckel 2019), later sharpened to $n^{1/2-o(1)}$ (Heckel–Riordan 2023) for some $n^*$ — contradicting any assumed tighter concentration. 5. The reusable abstract pattern: whenever a statistic's expectation is a smooth deterministic function of a parameter $n$, but an *auxiliary* count feeding into it fluctuates by a provably large *relative* amount, plant that fluctuation via an explicit coupling across two nearby $n$'s (one graph an induced subgraph of the other, differing by a controlled, easily-colourable "patch"), then compare the resulting inequality against the deterministic formula for the primary statistic. This turns fluctuation of an auxiliary quantity into a non-concentration proof for the primary one — a "parameter-interpolation coupling." The same skeleton, with the correlation inequality swapped for Harris–FKG comparing $G$ and $\bar G$ instead of $G_n$ and $G_{n'}$, was later reused to attack the Erdős–Gimbel cochromatic-number gap (Erdős #625 — does χ(G)−ζ(G)→∞ for random G(n,1/2)?).

Caveats / current limits. The technique gives a lower bound on width only along a *subsequence* of $n$ (or, in Heckel–Riordan's unconditional result, "for some $n$"), not for all $n$ simultaneously — matching the conjectured "zigzag" oscillation rather than a uniform statement. Closing the gap to a full, unconditional, all-$n$ matching bound (and proving the Gaussian-limit conjecture) is open; the Zigzag Conjecture is the precise open target.

Related

- Non-concentration of the chromatic number of G(n,1/2) (Heckel 2021) — the detailed solved-problem writeup of exactly this result (history, precise theorem statements, full step-by-step proof sketch); this page is its technique-reference companion. - Erdős #625 — does χ(G)−ζ(G)→∞ for random G(n,1/2)? — the open Erdős–Gimbel cochromatic-number question whose best current partial results are built on top of this non-concentration result via a Harris–FKG argument. - Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs — the variance/fluctuation estimate on the count of near-maximum independent sets that step 1 of the coupling 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 bounded ("tame") colourings. - Harris–FKG correlation inequality for increasing/decreasing events (random graphs, percolation) — the correlation-inequality variant of the coupling technique (comparing $G$ and $\bar G$) 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) — the two-point concentration of the independence number, the contrasting classical fact that made non-concentration of $\chi$ surprising. - Vertex-exposure martingale + Azuma–Hoeffding concentration for graph parameters — the classical Shamir–Spencer/Bollobás martingale machinery giving the $O(\sqrt n)$ upper bound on concentration width that this line of work shows is nearly tight from below.