Erdos's Question on the Independence Ratio of Unit-Distance Graphs
Erdos asked whether a finite unit-distance graph in the plane can have independence ratio below . One exists, built on the geometric fractional chromatic number framework of Matolcsi, Ruzsa, Varga and Zsamboki plus a carefully chosen two-vertex augmentation.
- Result
- Proved
- Status
- Resolved
- AI contribution
- AI-assisted
- Method
- Computation
- Field
- Combinatorial geometry
- Posed by
- Paul Erdos
- Year posed
- 1986
- Years open
- 40y
- Solved
- 2026-06-26
- Model
- ChatGPT, Codex (GPT-5.5)
- Vendor
- OpenAI
- Collaborators
- Akos Ducz, Daniel Varga
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 20 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What the AI did
The models were used for software development including code drafting and debugging, plus improvement and formatting suggestions. The search that produces the graph is computational, so the tooling is load-bearing even though no mathematical step is attributed.
Verification
The result is a specific finite graph, so it is checkable by computation. arXiv preprint, not peer-reviewed.