0/1-Polytopes with Exponentially Small Edge Expansion

2026/08/03 by Xiongxin Yang
Mathematics · #math.CO

paper · pdf

9 pages

arxiv created 2026/08/03 · arxiv updated 2026/08/04

Abstract

We present a 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.

Citations

• On the edge expansion of random polytopes
• The expansion of half-integral polytopes
• Expansion of random 0/1 polytopes
• Expansion of random 0/1 polytopes
• Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid
• On the Expansion of Graphs of 0/1-Polytopes