Erdős #625 — does χ(G)−ζ(G)→∞ for random G(n,1/2)?

Statement

The cochromatic number of $G$, denoted $\zeta(G)$, is the minimum number of colours needed to colour the vertices of $G$ such that each colour class induces either a complete graph or an empty graph (i.e. is a clique or an independent set). Let $\chi(G)$ denote the chromatic number.

If $G$ is a random graph on $n$ vertices with each edge included independently with probability $1/2$ (i.e. $G \sim G_{n,1/2}$), is it true that, almost surely (with high probability, whp), $$\chi(G) - \zeta(G) \to \infty$$ as $n \to \infty$?

Facts

- Prize: Erdős offered \$100 for a proof the answer is "yes" and \$1000 for a proof it is "no" — at a conference on random graphs in Poznań (most likely 1991), though Erdős later told Gimbel that \$1000 was perhaps too much. Status open per erdosproblems.com/625 (site-owner belief, fetched 2026-07-02). - Falsifiable: not by finite computation — this is an asymptotic whp statement about $n\to\infty$, so no finite counterexample search can settle it either way; it needs a genuine proof (of "yes", "no", or of a quantitative rate). - Origin: Erdős, P. and Gimbel, J., "Some problems and results in cochromatic theory", *Annals of Discrete Mathematics* (1993) [ErGi93]; see also Gimbel, "Some of my favorite coloring problems for graphs and digraphs" (2016) [Gi16]. - Trivially, always $\zeta(G) \le \chi(G)$. Classical result: whp $\zeta(G_{n,1/2}) \sim \chi(G_{n,1/2}) \sim \frac{n}{2\log_2 n}$ (upper bound on $\chi$ due to Bollobás, *Combinatorica* 1988 [Bo88]; lower bound on $\zeta$ from the fact that whp clique number and independence number of $G_{n,1/2}$ are both $< 2\log_2 n$, Bollobás–Erdős 1976 / Matula 1970/1972). So the *ratio* $\chi/\zeta \to 1$ whp — the question is only about the (much smaller) additive gap. - Best current partial results (both 2024, independent): - Heckel (arXiv:2408.13839, published *Electron. J. Combin.* 31:P4.72, 2024) and, independently, Steiner (arXiv:2408.02400) both discovered that if $\chi(G)-\zeta(G) \le g(n)$ whp for some function $g$, then $g(n)$ must be at least the *concentration-interval length* of $\chi(G_{n,1/2})$ itself — because $\zeta(\bar G)=\zeta(G)$ for the complement $\bar G$ (same distribution as $G$), so $g(n)$-boundedness of $\chi-\zeta$ forces $\chi(G)$ and $\chi(\bar G)$ (two "correlated but oppositely-monotone" copies of the same distribution, linked via the Harris/FKG inequality) to be within $g(n)$ of each other. Plugging in the best known chromatic-number non-concentration lower bounds (Heckel, *JAMS* 2021; Heckel–Panagiotou, arXiv:2306.07253) gives: for an infinite sequence of $n$, any such $g(n) \ge c\sqrt{n}\log\log n/\log^3 n$ — so $\chi-\zeta$ is *not* whp $O(n^{1/2-o(1)})$-bounded, at least along a subsequence. This does not resolve the original question for all $n$. - Steiner (arXiv:2408.02400, Thm 1.7) separately proves, via the Harris–FKG inequality directly, that for infinitely many $n$, $\mathbb P(\chi(G_n)-\zeta(G_n) \ge n^{1/2-\epsilon}) \ge c > 0$ for an absolute constant $c$, hence $\mathbb E[\chi-\zeta] = \Omega(n^{1/2-\epsilon})$ along that subsequence — positive-probability, not whp. - Heckel (arXiv:2409.17614, Feb 2025 revision) gives the strongest result to date: for roughly 95% of all values of $n$ (those $n$ where the expected number $\mu_\alpha$ of maximum independent sets satisfies $n^{0.05+\epsilon}\le \mu_\alpha \le n^{1-\epsilon}$), whp $\chi(G)-\zeta(G) \ge n^{1-\epsilon}$ — i.e. essentially the full first-moment gap, not just $\sqrt n$. The remaining ~5% of $n$ (where $\mu_\alpha$ is near a "jump" of the independence number) are explicitly left open; Heckel conjectures the same bound holds there too. - Heckel further conjectures (both papers) that whp $\chi(G)-\zeta(G) = \Theta(n/\log^3 n)$, based on a first-moment heuristic (the cochromatic first-moment threshold should sit $n/\log^3 n$ colours below the chromatic one). - Directly related, already-resolved sibling problem from the same Erdős–Gimbel 1993 paper: Erdős #762 — is χ(G)≤ζ(G)+2 when ω(G)<5 and ζ(G)≥4? (Erdős–Gimbel–Straight 1988) (a 1988 Erdős–Gimbel–Straight conjecture that $\omega(G)<5,\ \zeta(G)\ge 4 \Rightarrow \chi(G)\le\zeta(G)+2$) was disproved by Steiner in the same paper (arXiv:2408.02400, Thm 1.4): infinitely many graphs with $\omega(G)<5$, $\zeta(G)=4$, $\chi(G)=7$. - Related problems: Erdős #762 — is χ(G)≤ζ(G)+2 when ω(G)<5 and ζ(G)≥4? (Erdős–Gimbel–Straight 1988), erdos/761, Erdős #760 — large χ(G) forces a subgraph of large cochromatic number ζ(H) ≫ χ(G)/log χ(G), erdos/759, erdos/758.

Literature state

Not resolved — genuinely open, but very actively worked in 2024–2025 with substantial partial progress; the field converged on the *same* proof idea independently within weeks (Heckel and Steiner, both August 2024). As of this research pass (checked 2026-07-02 via arXiv API sorted-by-date search for "cochromatic": no paper newer than Heckel's Feb-2025 revision of arXiv:2409.17614 touches this problem), the state of the art is exactly Heckel's 95%-of-$n$ result above; nobody has closed the remaining 5% or proven the full whp statement for all $n$.

Key papers, in order of the technique's development: 1. A. Heckel, "On a question of Erdős and Gimbel on the cochromatic number", arXiv:2408.13839 (Aug 2024, rev. Feb 2025), *Electron. J. Combin.* 31:P4.72 (2024). Introduces the complement-graph + Harris's-lemma trick connecting $\chi-\zeta$ boundedness to chromatic-number concentration-interval length. 2. R. Steiner, "On the difference between the chromatic and cochromatic number", arXiv:2408.02400 (Aug 2024). Independently finds the same connection; separately disproves Erdős–Gimbel–Straight's 1988 conjecture (Erdős #762 — is χ(G)≤ζ(G)+2 when ω(G)<5 and ζ(G)≥4? (Erdős–Gimbel–Straight 1988)) and Erdős–Gimbel's related finiteness problem; gives a Harris-FKG argument for $\Omega(n^{1/2-\epsilon})$ gap with positive probability for infinitely many $n$. 3. A. Heckel, "The difference between the chromatic and the cochromatic number of a random graph", arXiv:2409.17614 (Sep 2024, rev. Feb 2025). The main advance: transfers the "tame colouring profile" second-moment machinery of Heckel–Panagiotou (arXiv:2306.07253) from ordinary colourings to cocolourings, proving $\chi-\zeta \ge n^{1-\epsilon}$ whp for ~95% of $n$.

The underlying machinery this whole line rests on is the recent (2021–2023) breakthrough on *non-concentration of the chromatic number of $G_{n,1/2}$* itself: Heckel, *JAMS* 34(1):245–260 (2021); Heckel–Riordan, *J. London Math. Soc.* 108(5):1769–1815 (2023, "How does the chromatic number of a random graph vary?"); Heckel–Panagiotou, arXiv:2306.07253 ("Colouring random graphs: Tame colourings"). Before ~2020 the folklore expectation (Shamir–Spencer / Bollobás two-point-style concentration results notwithstanding) was that $\chi(G_{n,1/2})$ was essentially rigid; the discovery that it actually *fluctuates* by as much as $\sqrt n$-ish amounts along subsequences is precisely what supplies the "yes"-leaning evidence for #625, since $\zeta$ inherits much less of that fluctuation (it can "absorb" cliques and independent sets symmetrically).

No AI/LLM involvement found: the github.com/teorth/erdosproblems wiki "AI contributions to Erdős problems" page (fetched and searched in full) does not mention #625 or "cochromatic" at all.

Attack surface

- Mode: derivation (extend Heckel's second-moment/tame-profile machinery) — this is not a finite-search problem; it is a research-mathematics extension of an active, well-documented, very recent (2024–2025) technique with a named remaining gap. - Concrete first target: close Heckel's stated 5% gap (arXiv:2409.17614, §5) — the values of $n$ where $\mu_\alpha < n^{0.05}$ or $\mu_\alpha$ is near-integer-jump for $\alpha_0(n)$, i.e. where the independence-number "profile" $k^*$ from Lemma 7.20 of Heckel–Panagiotou (arXiv:2306.07253) is not directly available. Heckel explicitly says this "should be straightforward" to push from 95%→97% by relaxing the exponent from $0.05$ to $x_0\approx 0.02905$ in that lemma, and flags the true obstruction for the rest as needing a more careful analysis of the optimal cocolouring profile $k^*$ when $\mu_\alpha < n^{x_0}$. This is a well-scoped, technically legible extension of someone else's stated open sub-lemma — a strong candidate for LLM-assisted derivation (adapting Heckel–Panagiotou Lemma 7.20's proof to the boundary regime), not a from-scratch attack. - A second, more ambitious target: prove Conjecture 19 (Heckel, both papers) that $\chi(G)-\zeta(G) = \Theta(n/\log^3 n)$ whp for *all* $n$ — this requires either (a) removing the "tame profile" constraint $\mathbb E_m[X_{\mathbf k}] \ge \exp(-n^{1-c})$ from Heckel–Panagiotou's Definition 2.3, or (b) redoing the second-moment analysis for cocolourings directly at the smaller profile $k^* = k_{\alpha-1}-\Theta(n/\log^3 n)$ rather than at $k_{\alpha-1}-n^{1-\epsilon/2}$. Heckel explicitly identifies this as "a lot more work" — full-strength research mathematics, not a quick derivation. - Oracle: not mechanically checkable — no finite computation can verify a whp asymptotic statement about $n\to\infty$; correctness can only be checked by a human/AI reviewer verifying the proof against the existing lemma statements in arXiv:2306.07253 (Heckel–Panagiotou) and arXiv:2409.17614 (Heckel), i.e. formal/semi-formal proof-checking against the cited lemmas, not empirical testing. (A sanity-check simulation of $\chi(G_{n,1/2})-\zeta(G_{n,1/2})$ for small-to-moderate $n$ via ILP/SAT-based exact chromatic/cochromatic-number computation could give supporting numerical evidence but cannot prove or disprove an asymptotic claim.) - Feasibility: famous-and-hard for full resolution (this is Erdős's own \$1000 problem, actively worked by two independent research groups in 2024–2025 using genuinely deep machinery — non-concentration of $\chi(G_{n,1/2})$ took Heckel + Heckel–Riordan + Heckel–Panagiotou multiple papers over 2021–2023 to build). But the 95%→97% gap-closing sub-task is realistically in reach for a careful derivation effort that reads Heckel–Panagiotou's Lemma 7.20 proof closely and adapts the exponent bound — this is exactly the kind of "extend a named, explicitly-flagged technical lemma in a very recent paper" task where LLM-assisted derivation has shown traction (per this project's own SekaiCTF finding that *derivation* from research papers, not raw problem-solving, is where the real capability edge is).

Related

- Erdős #762 — is χ(G)≤ζ(G)+2 when ω(G)<5 and ζ(G)≥4? (Erdős–Gimbel–Straight 1988) — same Erdős–Gimbel(–Straight) 1993/1988 problem family; the bounded-clique-number ($\omega(G)<5$) analogue, disproved by Steiner in the very same paper (arXiv:2408.02400) that supplies the Harris-FKG technique used on #625. - erdos/761 — cochromatic number vs. dichromatic number analogue; still open. - Erdős #760 — large χ(G) forces a subgraph of large cochromatic number ζ(H) ≫ χ(G)/log χ(G) — "large $\chi$ implies subgraph with large $\zeta$" — proved (a resolved structural cousin using $\zeta$ vs $\chi$). - erdos/759 — cochromatic number extremal growth rate on genus-$n$ surfaces — solved. - erdos/758 — extremal $\zeta(G)$ over all $n$-vertex graphs, small cases (e.g. $z(12)=4$?) — solved. - Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs — Paley-Zygmund-based existence proofs for cocolourings (Heckel, arXiv:2409.17614, Prop. 5); core technique transferring first/second-moment colouring-count bounds to cocolourings via the $2^k$ clique/independent-set choice factor (Prop. 6 in that paper). - Harris–FKG correlation inequality for increasing/decreasing events (random graphs, percolation) — correlation inequality used by both Heckel and Steiner to compare $\chi(G)$ and $\chi(\bar G)$ (increasing vs. decreasing functions of the same edge set) and derive lower bounds on $\chi-\zeta$. - Non-concentration of the chromatic number of a random graph (Heckel / Heckel–Riordan / Heckel–Panagiotou) — the Heckel (JAMS 2021) / Heckel–Riordan (JLMS 2023) / Heckel–Panagiotou (arXiv:2306.07253) result line proving $\chi(G_{n,1/2})$ is *not* concentrated on an interval much shorter than $\sqrt n\,\mathrm{polylog}(n)$ along a subsequence of $n$ — the entire evidentiary basis for expecting #625's answer to be "yes". - Tame colouring profiles — smoothness/tail conditions making second-moment analysis of random-graph colourings tractable — Heckel–Panagiotou's technical device (bounded profiles with smoothness/tail conditions) that makes the second-moment method tractable for both ordinary and co-colourings; the stated obstruction to closing the 5%/proving Conjecture 19. - Vertex-exposure martingale + Azuma–Hoeffding concentration for graph parameters — Azuma–Hoeffding concentration argument (Frieze's trick) used to upgrade a positive-probability existence bound on $\zeta$ into a whp upper bound. - Ramsey-type concentration of the independence/clique number of G(n,1/2) — Bollobás–Erdős (1976) / Matula (1970/72) result that $\alpha(G_{n,1/2}) = \lfloor \alpha_0+o(1)\rfloor$; underlies both the $n/(2\log_2 n)$ scale of $\chi,\zeta$ and the 95%-of-$n$ condition in Heckel's main theorem.