Erdős #74 — almost-bipartite graph of infinite chromatic number

Statement

Let $f(n)\to\infty$ (possibly arbitrarily slowly). Is there a graph $G$ of infinite chromatic number such that every finite induced subgraph of $G$ on $n$ vertices can be made bipartite by deleting at most $f(n)$ edges?

Equivalently, in the notation of [EHS82] (also used in the DeepMind Lean formalization): define $h_G(n)$ = the maximum, over $n$-vertex subgraphs $A$ of $G$, of the minimum number of edges whose deletion makes $A$ bipartite. The question is whether $h_G(n) = o(g(n))$ is achievable simultaneously for *every* unbounded $g$, i.e. whether $\chi(G)=\infty$ is compatible with $h_G(n)\to\infty$ arbitrarily slowly.

Facts

- Prize \$500 for a proof, but only \$250 for a counterexample (erdosproblems.com/74, direct fetch) — an explicit asymmetry signalling Erdős believed the answer is "yes" (existence) and viewed a resolving *construction* as the harder, more valuable direction. - Falsifiable: no — the statement is a $\forall f\,\exists G$ claim over infinite objects; no finite computation can decide it (site tag falsifiability: not-finite, confirmed by the "OPEN … cannot be resolved with a finite computation" tooltip on the live page). - Origin: conjectured by Erdős, Hajnal, Szemerédi, "On almost bipartite large chromatic graphs," *Theory and Practice of Combinatorics* (Ann. Discrete Math. 12), 1982, 117–123 [EHS82] (erdosproblems.com/bibs/EHS82, MR 806975). Restated in [Er87], [Er90], [Er93,p.342], [Er94b], [Er95], [Er95d,p.62], [Er96], [Er97b], [Er97c], [Er97d], [Er97f] — i.e. Erdős kept repeating it through the 1990s, a signal it stayed open and he considered it important. - Known partial result (the only progress ever recorded): Rödl, "Nearly bipartite graphs with large chromatic number," *Combinatorica* 2 (1982), 377–383 [Ro82] (erdosproblems.com/bibs/Ro82, MR 708152): (i) proves the hypergraph analogue of the conjecture in full (erdosproblems.com/74, direct text); (ii) for ordinary graphs, constructs, for every fixed constant $\epsilon>0$, a graph of chromatic number $\aleph_0$ in which every $n$-vertex subgraph can be made bipartite by deleting $\leq \epsilon n$ edges — i.e. settles the *linear* case $f(n)=\epsilon n$ affirmatively. Per a Google-Scholar-indexed abstract snippet, Rödl's note was explicitly answering a prior Erdős–Hajnal question ("is there $\epsilon>0$ such that every subgraph makeable-bipartite by deleting $\leq\epsilon|H|$ edges has $\chi(H)\leq 3$?") negatively, and the hypergraph result is a byproduct. - The exact construction technique in [Ro82] could not be verified (paper is paywalled, no open-access copy found via Semantic Scholar/Unpaywall); do not assume it is probabilistic — 1982 predates the Rödl-nibble semi-random method (1985), so it is more likely an explicit/algebraic (e.g. Kneser-graph- or shift-graph-style) construction. Flagged unverified rather than guessed. - What is still open: the sub-linear regime, i.e. any $f(n)=o(n)$. The site explicitly states: *"It is open even for $f(n)=\sqrt{n}$."* This is the frontier — going from Rödl's $\epsilon n$ down to anything growing slower than linear, all the way to arbitrarily slow $f(n)\to\infty$. - Sharp dichotomy with the uncountable case (erdosproblems.com/111): the conjecture is false if "infinite chromatic number" is strengthened to "chromatic number $\aleph_1$", *even allowing $f(n)\gg n$* (erdosproblems.com/74, cross-linking Erdős, Hajnal & Szemerédi (1982) — an $\\aleph_1$-chromatic graph with $h_G(n)=O(n^{3/2})$). Reason (erdosproblems.com/111, direct text): any graph $G$ with $\chi(G)=\aleph_1$ must contain, for some fixed odd length $2r+1$, $\aleph_1$-many vertex-disjoint odd cycles of that length, forcing $h_G(n)\gg n$ for the union of $\Theta(n)$ of those disjoint cycles (each odd cycle needs $\geq 1$ deleted edge to bipartite-ify, and they're vertex-disjoint so the deletions don't share). So $\chi(G)=\aleph_0$ (countable) is essential to any hoped-for "yes" construction — the countable case is the *only* regime where sub-linear-$f$ constructions are even conceivable. - Related problems: Erdős, Hajnal & Szemerédi (1982) — an $\\aleph_1$-chromatic graph with $h_G(n)=O(n^{3/2})$ — the $\aleph_1$/quantitative dual: EHS82 themselves constructed a $\chi(G)=\aleph_1$ graph with $h_G(n)\ll n^{3/2}$, and Erdős [Er81] conjectured this improves to $n^{1+\epsilon}$ for every $\epsilon>0$ — also still open, per direct fetch of erdosproblems.com/111.

Literature state

Not resolved. Direct fetch of erdosproblems.com/74 confirms live status = OPEN with "no solutions, partial or complete, claimed in the comments" (0 forum comments as of this fetch, 2026-07-02) and last page edit 25 January 2026 — i.e. actively maintained but with no new mathematical content added recently.

Multi-source check for silent/independent resolution came back empty: - Semantic Scholar citation graph for Rödl's paper (DOI 10.1007/BF02579434) returns only 6 citing works, all 1990–2011 (Erdős's own problem-list restatements, and Jensen–Toft's *Graph Coloring Problems* book, 2011) — zero citations since 2011, and none of the 6 claims any improvement on the $\epsilon n$ bound. - arXiv full-text/abstract API queries for "nearly bipartite" AND "chromatic number" and for "infinite chromatic number" AND "bipartite" both return zero results — no modern arXiv preprint engages with this exact question. - No mention found of GPT/DeepMind/Aristotle-style AI-assisted progress. The DeepMind formal-conjectures repo (github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/ErdosProblems/74.lean, fetched directly) has formalized *both* the general statement (erdos_74) and the explicit $f(n)=\sqrt n$ variant (erdos_74.variants.sqrt) as Lean 4 theorems, each answer(sorry) ↔ ... with proof body sorry and tag category research open — confirming the statement is precisely formalized but genuinely unproved, consistent with the site. - Peripheral but thematically adjacent recent work exists and could plausibly be mined for technique, though none addresses erdos/74 directly: Illingworth, "The chromatic profile of locally bipartite graphs," arXiv:2012.10409 / JCTB 156 (2022) 343–388 (finite, dense-graph chromatic thresholds for locally-bipartite graphs — different regime: dense not sparse, finite not infinite); and the July-2026 preprint "The Erdős–Hajnal High-Girth Subgraph Conjecture Holds in the Polynomial Chromatic-Sparsity Regime," arXiv:2606.17901 (a *different* Erdős–Hajnal conjecture, about forcing a high-girth *subgraph* of prescribed chromatic number out of a globally high-chromatic sparse graph — same "sparse-vs-chromatic" tension as erdos/74 but not the same object; its technique — "chromatic-defect random extraction" + "sparse-core bootstrapping" + degree-peeling/thinning — is the closest modern methodological analog found).

Net: this is a genuine 44-year-old unaddressed gap between Rödl's 1982 linear upper bound and Erdős's belief that arbitrarily-slow $f$ should suffice; no literature-resolution was found.

Attack surface

- Mode: derivation+formalization (not finite-search — the statement is a $\forall f\,\exists G$ over infinite structures, so no counterexample search applies; a "yes" resolution needs an explicit or probabilistic *construction* of a single countably-chromatic $G$ working for every $f\to\infty$, or at minimum for $f(n)=\sqrt n$; a "no" resolution needs a structural lower-bound argument in the style of the erdos/111 odd-cycle-disjointness argument, adapted to rule out sub-linear $f$ for $\chi=\aleph_0$). - Concrete first experiment (feasible sub-goal, not the full problem): reproduce Rödl's $\epsilon n$ construction from [EHS82]/[Ro82] on paper/in Lean (their def of $h_G(n)$ is already formalized in FormalConjectures/ErdosProblems/74.lean), then attempt the standard "sparsify a known $\aleph_0$-chromatic graph" moves — e.g. take a countable increasing union of finite graphs of growing chromatic number and *randomly thin* each finite piece à la the Erdős 1959 probabilistic high-girth/high-chromatic-number method (delete one edge from each short odd cycle while union-bounding that chromatic number survives) — to see whether the thinning-cost can be pushed from $\Theta(n)$ to $O(\sqrt n)$ or $o(n)$ on a specific concrete family (e.g. iterated Kneser graphs, Zykov/Mycielski-style constructions, or Erdős–Hajnal shift graphs, which are the standard building blocks for explicit unbounded-chromatic sparse-ish graphs). - Oracle: none mechanical for the full statement (infinite object, not finite-checkable); for the sub-goal above, a candidate finite-graph *family* $\{G_k\}$ can be checked computationally for a stated $n\mapsto$ edges-to-bipartite bound via ILP/exact bipartite-edge-deletion (a known-hard but small-instance-tractable problem, e.g. via networkx/OR-tools max-cut-style formulation) to validate the claimed $f(n)$ envelope empirically before attempting the infinite limit argument. - Feasibility: famous-and-hard, but not obviously beyond reach for a partial improvement. Full resolution (all $f\to\infty$, or even just $f(n)=\sqrt n$) has resisted 44 years untouched (zero post-2011 citations, zero modern arXiv hits). This is exactly the kind of "no one has looked recently" gap where a targeted derivation pass (transferring 1959-era Erdős alteration-method machinery, or the 2026 "chromatic-defect random extraction / sparse-core bootstrapping" machinery from the sibling high-girth Erdős–Hajnal conjecture) could plausibly either (a) push Rödl's $\epsilon n$ down to $n/\log n$ or similar (a genuine, citable, non-full-resolution result) or (b) at minimum produce a clean formalized/verified restatement plus a structured literature-gap writeup, which is itself a legitimate deliverable given the total absence of modern engagement.

Related

- Rödl 1982 — the hypergraph analogue of Erdős–Hajnal–Szemerédi's almost-bipartite large-chromatic-number problem, SOLVED (the graph case, erdos/74, remains open) — dedicated technique-focused page on Rödl's [Ro82] hypergraph solution and linear-graph sub-case (the material summarized in the Facts bullet above), including the sibling erdos/1092 disproof and a flagged reconstruction of the likely proof schema. - Erdős, Hajnal & Szemerédi (1982) — an $\\aleph_1$-chromatic graph with $h_G(n)=O(n^{3/2})$ — the $\aleph_1$-chromatic quantitative analogue: EHS82 built a $\chi=\aleph_1$ graph with $h_G(n)\ll n^{3/2}$, Erdős conjectured $\ll n^{1+\epsilon}$; also open; the disjoint-odd-cycles lower-bound argument there is the reason erdos/74 is restricted to *countable* chromatic number. - Erdős #63 — infinite chromatic number ⇒ cycles of length $2^n$ infinitely often — sibling infinite-chromatic-number/cycle-structure problem ("does $\chi(G)=\infty$ force cycles of length $2^n$ for infinitely many $n$?"), PROVED by Liu–Montgomery arXiv:2010.15802 via de Bruijn–Erdős + a degree-forcing cycle-length theorem — a concrete precedent that "$\chi=\infty$ + de Bruijn–Erdős compactness" arguments can crack this family of problems; worth checking whether the same compactness reduction (infinite chromatic $\Rightarrow$ some finite subgraph already has the needed property, by De Bruijn–Erdős) applies here. - De Bruijn–Erdős compactness theorem — infinite chromatic number is determined by finite subgraphs — the finite/infinite chromatic-number transfer theorem that resolved the sibling erdos/63; candidate tool for reducing erdos/74 to a finite statement. - The alteration (deletion) method — probabilistic existence proofs that build an almost-good random structure, then delete its blemishes; canonical instance: Erdős's 1959 high-girth/high-chromatic-number graphs — the 1959 probabilistic construction of high-girth, high-chromatic-number graphs (delete an edge from each bad short cycle, union-bound survival of chromatic number); the closest known technique-shape to "sparsify a highly-chromatic graph while preserving chromatic number," i.e. the reverse-engineering target for pushing Rödl's $\epsilon n$ bound down. - Erdős–Hajnal shift graphs (explicit high-chromatic, controlled-odd-girth construction) — Erdős–Hajnal's explicit high-chromatic, controlled-odd-girth graph family; standard building block for constructions in this literature, candidate base object for a sub-linear $f(n)$ construction. - Minimum edge-deletion to bipartite: β(G)/h_G(n), the Max-Cut complement, and the Edwards–Erdős bound — the general "minimum edges to delete to bipartite-ify" (odd-cycle transversal / max-cut complement) parameter $h_G(n)$ that is Definition 3.1 of [EHS82] and the formalized core of FormalConjectures/ErdosProblems/74.lean. - Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings — semi-random/nibble method (post-1985, so NOT what [Ro82] itself used, but the standard modern tool for pushing probabilistic sparsification bounds below linear); candidate for a genuine sub-linear improvement attempt. - Chromatic-defect random extraction + sparse-core bootstrapping (the Erdős–Hajnal high-girth subgraph technique) — technique from the July-2026 "Erdős–Hajnal High-Girth Subgraph Conjecture" paper (arXiv:2606.17901): combines forced-coloring defect analysis with sparse-core bootstrapping and degree peeling/thinning to trade edge-density for guaranteed high-girth/high-chromatic subgraphs; same sparse-vs-chromatic tension as erdos/74, structurally the closest 2020s machinery found.

PRIOR-ART SCAN (2026-07-03)

Verdict: HARD-OPEN. No resolution, no active work, no hidden progress found anywhere — a genuine 44-year gap (EHS82 1982 → today) between Rödl's [Ro82] linear ($f(n)=\epsilon n$) upper bound and the full conjecture (down to arbitrarily slow $f$, open even at $f(n)=\sqrt n$). This scan specifically re-checked the failure mode from erdos/64 (novelty falsely claimed for something already sitting in a public repo, incl. in an unindexed branch/data file) and found no analog here.

Checks performed and results: - erdosproblems.com/74 (direct curl fetch, HTTP 200, re-verified 2026-07-03): live status OPEN, "cannot be resolved with a finite computation," 0 forum comments, no "Partial Solution" text beyond Rödl's [Ro82], last edit 25 Jan 2026. No "See also" section beyond the inline cross-link to Erdős, Hajnal & Szemerédi (1982) — an $\\aleph_1$-chromatic graph with $h_G(n)=O(n^{3/2})$ already captured above. - teorth/erdosproblems GitHub repo (github.com/teorth/erdosproblems) — the #64 lesson applied directly: checked all branches (main, revert-326-fix/887-lean-companion-comment — latter is an unrelated Lean-companion-comment revert, nothing to do with #74), fetched data/problems.yaml in full (13,452 lines) and pulled the number: "74" entry directly: status.state: open, last_update: 2025-08-31, formalized.state: yes, formalized.last_update: 2025-09-25 — pure metadata, no hidden result. Searched repo issues/PRs for "74" (GitHub code/issue search API): 0 relevant hits (the only matches were unrelated issue/PR numbers containing the substring "74"). Fetched the AI-contributions-to-Erdős-problems wiki page (github.com/teorth/erdosproblems/wiki/AI-contributions-to-Erdős-problems) in full: problem 74 is not listed in any of the AI-standalone / AI-alongside-literature / AI-collaborating-with-humans tables. - google-deepmind/formal-conjectures FormalConjectures/ErdosProblems/74.lean (re-fetched current main + full commit history for that file): both erdos_74 (general $f$) and erdos_74.variants.sqrt are still answer(sorry) with proof body sorry, tagged category research open. All 5 commits touching the file (2025-09-25 → 2026-01-07) are formalization bookkeeping (quantifier-scope fix, answer(sorry) style change, Lean version bump) — zero mathematical progress. - Citation graph for Rödl's paper (Combinatorica 2 (1982) 377–383, DOI 10.1007/BF02579434): OpenAlex work W2037617500, cited_by_count = 5, and all 5 citing works are dated 1990–1997 (Erdős's own problem-list restatements + one Pisier-type-problems paper) — i.e. the citation trail goes completely cold after 1997, even starker than the "zero since 2011" found in the earlier pass via Semantic Scholar/Jensen–Toft. - arXiv API (export.arxiv.org, re-run 2026-07-03): abs:"infinite chromatic number" AND "bipartite" → 0 hits; abs:"nearly bipartite" AND "chromatic" → 0 hits; abs:"almost bipartite large chromatic" → 0 hits. No modern preprint engages this statement directly. - arXiv:2606.17901 ("The Erdős–Hajnal High-Girth Subgraph Conjecture Holds in the Polynomial Chromatic-Sparsity Regime," confirmed real via arXiv API, abstract read in full) — a *different* Erdős–Hajnal conjecture (forcing a high-girth subgraph out of a sparse high-chromatic graph), but the closest 2020s methodological analog (chromatic-defect random extraction + sparse-core bases + peeling/thinning bootstrap); does not touch #74 but is a candidate technique donor for the attack surface below. - Legacy mirror mathweb.ucsd.edu/~erdosproblems/.../AlmostBipartiteInfiniteGraphs1.html (re-fetched via curl -k, cert issue bypassed): identical content to the live site, no additional facts. - Terence Tao, Mathstodon, 2025-12-26 (fetched via ActivityPub JSON, https://mathstodon.xyz/@tao/115788262274999408): explicitly names three Erdős problems (#897, #333, #481) where an AI tool claimed a "solution" that turned out to already exist in obscure literature — i.e. this is the documented, named instance of exactly the #64 failure mode. #74 is not among the three — no evidence anyone (human or AI) has recently claimed progress on it that would need re-checking.

Net: every independent channel (live site, community GitHub repo incl. all branches and data files, Lean formalization repo incl. full commit history, citation graph, arXiv, legacy mirror, Tao's own public commentary on AI false-novelty cases) agrees — the gap between Rödl 1982 and the full EHS82 conjecture is real, confirmed untouched, and not a repeat of the erdos/64 mistake.

No change to the Attack surface / Feasibility assessment above — it remains the right target: not full resolution, but a genuine sub-linear improvement on Rödl's $\epsilon n$ bound (or a clean, citable partial result / formalized negative argument) is a legitimate, currently-unclaimed deliverable.