Mihail–Vazirani edge-expansion conjecture for 0/1-polytopes

Must the edge graph of a full-dimensional 0/1-polytope have a universal, or at least inverse-polynomial, expansion lower bound? The counterexample target has dimension 4n+1 and exponentially decreasing expansion.

Why it matters and what counts as progress

Why it matters: It tests a proposed combinatorial expansion property across all binary-coordinate polytopes.

What counts as progress: Explicit 0/1-polytopes with expansion below the proposed universal or inverse-polynomial bound, or a lower bound for an additional polytope class.

How the problem developed

3 Aug 2026 · Counterexample [1]
Xiongxin Yang Constructed a family of 0/1-polytopes with exponentially small edge expansion, disproving the Mihail–Vazirani conjecture.