Random 0/1-polytopes expand rapidly
2026-04-10 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors study shapes called 0/1-polytopes, which come from points with coordinates only 0 or 1. They focus on a property called edge-expansion, which measures how well-connected the shape's graph is. While a famous idea suggested the edge-expansion should always be at least 1, the authors show that if you pick points randomly, the connection strength is actually much higher, growing with the dimension. Their work improves on earlier results by showing these typical random shapes are very well connected.
0/1-polytopeconvex hulledge-expansiongraph connectivityrandom samplingcombinatorial geometryprobabilityMihail-Vazirani conjecture
Authors
He Guo, István Tomon
Abstract
A 0/1-polytope is the convex hull of a subset $V\subseteq \{0,1\}^n$. A celebrated conjecture of Mihail and Vazirani asserts that the graph of every 0/1-polytope has edge-expansion at least 1. In this paper, we show that typical 0/1-polytopes have significantly stronger expansion. Specifically, if $V$ is formed by sampling each vertex of $\{0,1\}^n$ independently with constant probability $p$, then with high probability the edge-expansion is $Θ(n)$ for $p \in (1/2, 1)$, and $n^{Θ(\log \log n)}$ for $p \in (0, 1/2)$. This improves the previously best known bound $Ω(1)$ due to Ferber, Krivelevich, Sales and Samotij.