The Mihail-Vazirani Conjecture

Precise statement

Mihail and Vazirani conjectured that the graph of every $0/1$-polytope has edge expansion at least one. Disproved by a family of $0/1$-polytopes whose edge expansion decreases exponentially in the dimension.

The source statement is reproduced for indexing with attribution. Mathematical correctness requires domain-expert or mechanical review. VibeMath has not independently audited statement fidelity, correctness, priority, or novelty.

What AI did

GPT-5.6 Sol

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.

Provider: OpenAI · Prompt public: unknown · Independence: unknown

Verification boundary

unreviewed

arXiv preprint, not yet peer-reviewed.

Correctness: unknown · statement fidelity: unaudited · peer review: none

Timeline

1. 2026-08-03

   arXiv:2608.01870 - 0/1-Polytopes with Exponentially Small Edge Expansion

   VibeMathed reports this item as resolved. VibeMath preserves that report as a source assertion and has not independently authored a plain-language mathematical explanation.

Known method families

construction (source-reported)

Source-reported tools: construction.

Independent: unknown · difference confidence: 0

What remains uncertain

VibeMath has not independently audited the mathematical statement, proof, or novelty claim.

• VibeMath has not independently verified the mathematical claim.
• AI-attempt independence and training-data exposure are unknown unless explicitly documented.
• VibeMath has not independently audited the mathematical statement, proof, or novelty claim.