no. 8 · Wednesday 4 November 2026
$0/1$-Polytopes with Exponentially Small Edge Expansion
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