Erdős–Hajnal high-girth problem (Erdős #108) disproved with ChatGPT/Codex help and a Lean proof, via the Conjectures.io bounty; experts sharpen it with GPT-6 Astra
Result confirmed
Importance: major (4 of 5)Status
- Claim
Result confirmed
- Our reporting
- High confidence
- Verification
- Lean-verified
- Importance
- Major (4 of 5)
- Last verified
- 7 October 2026
Your AI and this story
- GPT-6.2 Astra107 days after its cutoff
- Claude Opus 5.577 days after its cutoff
- Gemini 4 Hydrogen168 days after its cutoff
- Grok 4.7107 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 77 days before it.
Key facts
- Problem: for every r ≥ 4 and k ≥ 2, is there f(k,r) such that every graph with chromatic number ≥ f(k,r) has a subgraph of girth ≥ r and chromatic number ≥ k? (Erdős–Hajnal; Rödl proved r = 4). The answer is no already at girth 5 and k = 7
- Construction: arc graphs over an ordered multipartite random base graph (the Janzer–Steiner–Sudakov model); every C4-free subgraph splits into a bounded-degree-controlled part (4-colourable) and a forest (2 colours)
- Verification: the main theorem and the negation of Google DeepMind’s pinned Formal Conjectures statement (ErdosProblems/108.lean) were proved in Lean 4 (v4.33.1) using only standard axioms; Conjectures.io lists it as Lean-verified and approved in human review, with a $3,833 reward paid
- AI disclosure (Kohlmeyer & Kruer): ‘This work was developed with substantial assistance from OpenAI ChatGPT/Codex, including mathematical exploration, the preparation and checking of estimates, construction and debugging of the Lean proofs, and drafting and typesetting of the manuscript.’ Conjectures.io’s own write-up was ‘prepared by Conjectures with Codex assistance from the accepted Lean submission’
- Nguyen & Walczak (arXiv 2609.40192, Oct 1): improved 6-colourable to 3-colourable. ‘ChatGPT-6 Astra discovered a proof of Theorem 2.1, in particular proposing Lemma 5.1 as a suitable extension of Lemma 4.3.’ The step from 6 to 4 was done ‘entirely by the authors … with no AI tools involved’
- Nguyen & Walczak note that both earlier manuscripts ‘lack any references to the literature except for’ Janzer–Steiner–Sudakov, and that the Lean-derived write-up ‘may not be readily accessible to researchers in graph theory’
- Platform: Conjectures.io (Bittensor subnet 66) pays for Lean-verified proofs of formalised open problems. By Oct 5 its results page listed 26 problems solved and $127,713 paid; JenW1N also has accepted solves of Erdős #859, #18(b), #1062(ii) and Green’s open problems 24 and 40 (Sept 15–25)
- erdosproblems.com still showed #108 as OPEN with one proof claim on Oct 5, 2026
What happened
Erdős and Hajnal asked whether a graph with enormous chromatic number must contain a subgraph that has both large girth and large chromatic number. Rödl settled girth 4 (triangle-free subgraphs), and the general question stayed open as Erdős Problem #108. Google DeepMind’s Formal Conjectures project had pinned it as a Lean statement. Conjectures.io, a Bittensor subnet that pays for Lean-checked proofs, offered a bounty for it.
On Sept 15, 2026 the solver “JenW1N”, identified in the manuscripts as Purdue’s Jensen Kohlmeyer with Liam Kruer, submitted a Lean proof of the negation. They take arc graphs of a carefully sized random multipartite graph. In these graphs any subgraph without a four-cycle is 6-colourable, yet the whole graph has arbitrarily large chromatic number. The platform verified the proof and approved it in human review. It paid the bounty and published an explanatory PDF that Codex prepared from the Lean code.
Graph theorists Tung Nguyen and Bartosz Walczak learned of the result from the Conjectures.io announcement. On Oct 1 they posted an exposition on arXiv that ties each step to the literature. Working without AI, they observed that the construction already gives 4 colours. They then asked ChatGPT-6 Astra for a 2-degenerate version of the key lemma. Astra found the proof, which brings the bound down to 3 colours.
Why it matters
This is a well-known problem from Erdős’s list, and the counterexample comes with a machine-checked proof. Independent experts have checked it and improved on it. It also shows a new route for AI-assisted mathematics: paid, Lean-gated bounties outside arXiv, where the first write-up was itself machine-generated. Nguyen and Walczak’s note criticises the lack of literature context in those write-ups. We found no Hacker News thread about the result, and we did not locate the original Conjectures.io announcement post on X.
Sources
7 sources from 5 sites. Numbers match the chips in the text.
7 sources: 7 primary
Primary
- Kohlmeyer & Kruer: A counterexample to Erdős problem 108 via arc graphs (dated Sept 15, 2026)jenwin.io, paper
- Conjectures.io write-up: Erdős Problem 108, high chromatic number with six-colour C4-free subgraphs (Sept 17)conjectures.io, paper
- Conjectures.io problem page: Erdős 108conjectures.io, official
- Conjectures.io results (bounties paid)conjectures.io, official
- arXiv 2609.40192: Nguyen & Walczak, On the solution to the Erdős–Hajnal problem on high-girth high-chromatic subgraphsarxiv.org, paper
- Erdős Problems #108erdosproblems.com, docs
- Google DeepMind Formal Conjectures repositorygithub.com, code
Changes
- Science block: normalised label “Erdős problem #108”
- Linked the new entry on the platform’s other bounty solves
- Filed (found via the AI disclosure in arXiv 2609.40192)