Paperlane

no. 8 · Wednesday 4 November 2026

$0/1$-Polytopes with Exponentially Small Edge Expansion

Xiongxin Yang

math.CO · v2 · 12 pp

Abstract

We present a simple construction of a family of $0/1$-polytopes whose edge expansion decreases exponentially with the dimension, which disproves the Mihail-Vazirani conjecture that the graph of every $0/1$-polytope has edge expansion at least one.

comments
12 pages
fields
Combinatorics
pdf ↗ page arXiv:2608.01870 ↗