Cochromatic gap of the random graph: is $\chi(G)-\zeta(G)\to\infty$ almost surely? (Erdős #625)
Statement
The cochromatic number $\zeta(G)$ is the least number of colours needed to colour the vertices of a graph $G$ so that each colour class induces either a complete graph or an empty (independent) graph; the chromatic number $\chi(G)$ is the least number of colours with each class independent, so $\zeta(G)\le\chi(G)$ always. Let $G=G(n,1/2)$ be the random graph on $n$ vertices in which each edge is present independently with probability $1/2$. Is it true that, almost surely, $$\chi(G)-\zeta(G)\to\infty$$ as $n\to\infty$?
Acceptance. FULLY RESOLVES: a proof that almost surely $\chi(G(n,1/2))-\zeta(G(n,1/2))\to\infty$ (Erdős's \$100 direction), OR a proof that this fails (the \$1000 direction); ideally accompanied by the true asymptotic order, e.g. a proof of Heckel's $\chi-\zeta\asymp n/(\log n)^3$ with matching bounds. Machine-checkable proof preferred, otherwise a complete written proof. ADVANCES, any of, each with a full proof and stated relative to the records in the background: (a) upgrade Heckel's '$\chi-\zeta\ge n^{1-\epsilon}$ for about $95\%$ of $n$' to hold for a density-1 set of $n$ (or all sufficiently large $n$); (b) improve the '$\ge n^{1/2-o(1)}$ along a sequence' lower bound to a larger exponent, or to a with-high-probability statement; (c) establish any nontrivial upper bound $o(n)$ on $\chi-\zeta$ beyond what the trivial $\chi\le(1+o(1))n/(2\log_2 n)$ gives. Deliver the proof (or disproof) with explicit bounds tied to the stated frontier.
Background
A problem of Erdős and Gimbel [ErGi93] (see also Gimbel [Gi16]). At a random-graphs conference in Poznań, Poland (most likely 1989) Erdős offered \$100 for a proof that the statement is true and \$1000 for a proof that it is false (later telling Gimbel that \$1000 was perhaps too much). Known frontier: almost surely $\frac{n}{2\log_2 n}\le\zeta(G)\le\chi(G)\le(1+o(1))\frac{n}{2\log_2 n}$ — the upper bound is Bollobás [Bo88], and the lower bound follows because $G(n,1/2)$ almost surely has clique number and independence number below $2\log_2 n$. More recently, Heckel [He24] and independently Steiner [St24b] showed that $\chi(G)-\zeta(G)$ is NOT bounded with high probability: if $\chi(G)-\zeta(G)\le f(n)$ with high probability then $f(n)\ge n^{1/2-o(1)}$ along an infinite sequence of $n$. Heckel conjectures that with high probability $\chi(G)-\zeta(G)\asymp \frac{n}{(\log n)^3}$, and Heckel [He24c] further proved that for every $\epsilon>0$, $\chi(G)-\zeta(G)\ge n^{1-\epsilon}$ for roughly $95\%$ of all $n$. Despite this strong progress the exact statement — that the gap tends to infinity along the whole sequence — and the true asymptotic order remain open per erdosproblems.com/625 (fetched 2026-07-21, status 'open', tagged 'graph theory | chromatic number'). Venue neighbour: the non-concentration of $\chi(G(n,1/2))$ is Erdős #1156, a related but distinct random-graph chromatic question. Attacker's tool: martingale/second-moment concentration for $\chi$ and $\zeta$ of $G(n,1/2)$, sharp control of clique- and independence-number fluctuations, and the recent Heckel–Steiner machinery; simulation of $\chi$ and $\zeta$ at moderate $n$ can probe the conjectured $n/(\log n)^3$ order but cannot settle the limit.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #625 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #1156 — non-concentration of the chromatic number of G(n,1/2) (venue neighbour) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.