Gyarfas's conjecture on covering edge-colored complete graphs by r-1 monochromatic trees
Color each edge of a finite complete graph with one of colors. A monochromatic tree cover is a family of monochromatic trees (overlaps and single vertices allowed) whose vertex sets cover the graph. The monochromatic stars at any vertex always give a cover by trees. Gyarfas conjectured that trees always suffice; Erdos, Gyarfas and Pyber recorded that this covering formulation is equivalent to the intersecting case of Ryser's conjecture. Can the vertices of every -edge-colored complete graph be covered by at most monochromatic trees?
- Result
- Disproved(see note)
- Status
- Candidate (review pending)
- AI contribution
- AI-discovered
- Method
- Construction
- Field
- Ramsey-type covering problems; monochromatic trees
- Posed by
- Andras Gyarfas; recorded by Erdos, Gyarfas and Pyber (J. Combin. Theory Ser. B 51, 1991)
- Year posed
- 1991
- Years open
- 35y
- Solved
- 2026-09-23
- Model
- Unreleased internal OpenAI model
- Vendor
- OpenAI
- Collaborators
- —
- Verification
- Lean-checked, statement unaudited
- Publication
- Announced
- Collection
- OpenAI math release (October 2026), version adc7f12
- Significance
- 32 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
For every sufficiently large prime (September 27 paper), and for with a large prime and large odd (September 23 paper), there is a finite complete graph with an -edge-coloring whose vertices need exactly monochromatic trees to cover them; the same holds for connected monochromatic subgraphs. Built from the Ryser counterexamples by coloring each pair of hyperedges by a part where they meet. Not addressed: small , or the distinct vertex-disjoint tree-partition conjecture of Erdos-Gyarfas-Pyber.
What the AI did
The release README says the results were produced by an unreleased internal OpenAI model with a fixed procedure, on average about three hours of ChatGPT Pro thinking compute per result, and that some outputs build on earlier model results. This result is not among the README's exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region). The manuscript is authored 'OpenAI' and names no human author. Two manuscripts: the extension-field construction (September 23, 2026) and the balanced prime-order construction (September 27, 2026); the later paper says its proof is independent, and the earlier imports only three elementary lemmas from it.
Verification
No independent mathematician has checked this yet. Checked here: the tree-cover corollary in both manuscripts was read against the conjecture as stated by Milicevic (Conjecture 1) and Erdos-Gyarfas-Pyber. The Lean main results for the September 23 paper (RyserCovering, RyserOddExtensions; and BalancedRyser for the companion, not in the formalization catalogue) were read; they state the hypergraph counterexamples only. The transfer to edge-colored complete graphs is a short standard argument proved in the papers and not formalised. Not rebuilt here.
Sources
- PaperCompanion: Balanced counterexamples to Ryser's conjecture at prime orders (September 27, 2026)
- Lean proofLean proof: OAI/Combinatorics/Ryser/Construction/Main.leanLean proof: OAI/Combinatorics/Ryser/OddExtensions.lean
- CodeOpenAI math release: A counterexample to Ryser's covering conjecture
- Problem recordErdos, Gyarfas, Pyber, Vertex coverings by monochromatic cycles and trees (JCTB 1991)