Non-concentration of the chromatic number of the random graph $G(n,1/2)$ (Erdős #1156)
Statement
Let $G$ be a random graph on $n$ vertices, in which every edge is included independently with probability $1/2$. Is there some constant $C$ such that the chromatic number $\chi(G)$ is, almost surely, concentrated on at most $C$ values? Is it true that, if $\omega(n)\to\infty$ sufficiently slowly, then for every function $f(n)$ $$\mathbb{P}(\lvert \chi(G)-f(n)\rvert<\omega(n))<1/2$$ for all sufficiently large $n$?
Acceptance. FULLY RESOLVES: a complete proof or disproof of the second statement — that for every sufficiently slowly growing $\omega(n)\to\infty$ and every function $f(n)$, $\mathbb{P}(\lvert\chi(G)-f(n)\rvert<\omega(n))<1/2$ for all sufficiently large $n$. This is proof-shaped (no finite certificate exists): a machine-checkable (Lean 4) proof is preferred, else a complete written proof with all probabilistic estimates. A disproof must exhibit $f$ and an unbounded $\omega$ for which the concentration probability is $\geq 1/2$ for infinitely many $n$, with proof. ADVANCES: strictly improving the non-concentration frontier stated in the background — e.g. upgrading 'infinitely many $n$' to 'all sufficiently large $n$' for some explicit unbounded width, raising the exponent range beyond every $c<1/2$, or proving the probability-$1/2$ statement for some explicit unbounded $\omega(n)$; or narrowing the gap from the concentration side below the Shamir–Spencer/Alon–Spencer width stated in the background. Deliver the proof file.
Background
An Erdős problem on the concentration of the chromatic number of the dense random graph $G(n,1/2)$, appearing in Alon–Spencer [AlSp92] and catalogued from [Va99, 3.6]; listed as open on erdosproblems.com/1156 (fetched 2026-07-13, status 'open', tagged 'graph theory | chromatic number'). The asymptotics are classical: Bollobás [Bo88] proved $\chi(G)\sim n/(2\log_2 n)$ with high probability. On the concentration side, Shamir and Spencer [ShSp87] proved that for any $\omega(n)$ with $\omega(n)/\sqrt{n}\to\infty$ there is a centering $f(n)$ with $\mathbb{P}(\lvert\chi(G)-f(n)\rvert<\omega(n))\to 1$; the refinement requiring only $\omega(n)\log n/\sqrt{n}\to\infty$ appears as Exercise 3 of Section 7.9 of Alon–Spencer [AlSp16], with a proof also given by Scott [Sc17]. On the non-concentration side, Heckel [He21] proved that any $(f,\omega)$ achieving concentration probability $\to 1$ must have $\omega(n)>n^c$ for infinitely many $n$, for every $c<1/4$; Heckel and Riordan [HeRi23] improved this to every $c<1/2$. In particular the first question above is already answered in the negative by [He21] — bounded-width concentration is impossible — and the concentration width is pinned near $n^{1/2}$ up to the infinitely-often quantifier and lower-order factors. The live open problem is the second, stronger statement: that every sufficiently slowly growing width $\omega(n)\to\infty$ fails, for every centering $f(n)$, even at the probability-$1/2$ threshold and for all large $n$. The attacker's tool: sharpening the Heckel–Riordan coupling and second-moment machinery for colourings of $G(n,1/2)$ to upgrade infinitely-often non-concentration to all-large-$n$ non-concentration at constant probability; simulation of $\chi(G(n,1/2))$ supplies heuristic evidence only, not resolution.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1156 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.