On the edge expansion of random polytopes

A $0/1$-polytope in Rⁿ is the convex hull of a subset of \0,1\ⁿ. 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\ⁿ independently at random with probability p∈ (0,1). Improving earlier results, we show that, for any p∈ (0,1), with high probability the edge expansion of the random $0/1$-polytope is bounded from below by an absolute constant.