Random 0/1-polytopes expand rapidly
This addresses a conjecture in combinatorial geometry and polytope theory, providing strong expansion results for random 0/1-polytopes, which is an incremental advance over prior work.
The paper tackles the problem of edge-expansion in 0/1-polytopes, showing that typical random 0/1-polytopes have significantly stronger expansion than previously known, with edge-expansion of Θ(n) for p ∈ (1/2, 1) and n^{Θ(log log n)} for p ∈ (0, 1/2), improving the prior bound of Ω(1).
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.