On the edge expansion of random polytopes

A 0/1-polytope in $\mathbb R^n$ is the convex hull of a subset of $\{0,\, 1\}^n$. The graph of a polytope $P$ is the graph whose vertices are the zero-dimensional faces of $P$ and whose edges are the one-dimensional faces of $P$. A conjecture of Mihail and Vazirani states that the edge expansion of the graph of every 0/1-polytope is at least one. We study a random version of the problem, where the polytope is generated by selecting vertices of $\{0,\, 1\}^n$ independently at random with probability $p \in (0; 1)$. Improving earlier results, we show that, for any $p \in (0; 1)$, with high probability the edge expansion of the random 0/1-polytope is bounded from below by an absolute constant.