Erdős Problem #1091
Erdős problem #1091 · erdosproblems.com/1091
- Result
- Proved
- Status
- Resolved
- AI contribution
- AI-discovered
- Method
- Argument
- Field
- Graph Theory, Chromatic Number
- Posed by
- Paul Erdős
- Year posed
- 1976
- Years open
- 50y
- Solved
- 2026-04-09
- Model
- OpenAI internal model
- Vendor
- —
- Collaborators
- Boris Alexeev, Moe Putterman, Mehtaab Sawhney, Mark Sellke, Gregory Valiant
- Verification
- Site-confirmed
- Publication
- Announced
- Significance
- 10 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What the AI did
From "Short proofs in combinatorics, probability and number theory II": "The proofs in this manuscript are due to an internal model at OpenAI... The role of the human authors was simply to digest the proofs and modify the write-ups for clarity and elegance." This is the one place in the paper where the humans changed the mathematics: the model's original proof gave the same family of example graphs but deduced colour-criticality from a presentation the authors reworked.
Verification
Marked solved by erdosproblems.com's official status. Solve credited via Terence Tao's AI-contributions wiki.
Sources
- PaperShort proofs II (Section 4)
- Problem recorderdosproblems.com