The Mihail-Vazirani Conjecture
Mihail and Vazirani conjectured that the graph of every -polytope has edge expansion at least one. Disproved by a family of -polytopes whose edge expansion decreases exponentially in the dimension.
- Result
- Disproved
- Status
- Resolved
- AI contribution
- AI-discovered
- Method
- Construction
- Field
- Polyhedral combinatorics
- Posed by
- Milena Mihail, Umesh Vazirani
- Year posed
- —
- Years open
- —
- Solved
- 2026-08-03
- Model
- GPT-5.6 Sol
- Vendor
- OpenAI
- Collaborators
- Xiongxin Yang
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 30 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What the AI did
The AI use section states that the construction and its analysis were generated by GPT-5.6 Sol in a one-shot manner, from a prompt adapted from OpenAI's cycle double cover prompt by replacing the problem statement. The author verified the result independently.
Verification
arXiv preprint, not yet peer-reviewed.
Source
arXiv:2608.01870 - 0/1-Polytopes with Exponentially Small Edge Expansion