Random 0/1-polytopes expand rapidly

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 $\hat{I}˜(n)$ for $p\in (1/2,1)$, and $n^{\hat{I}˜(\log \log n)}$ for $p\in (0,1/2)$. This improves the previously best known bound $\hat{I}\text{c◯}(1)$ due to Ferber, Krivelevich, Sales and Samotij.

21 pages