Abstract A 0/1-polytope in 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 (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.
Ferber et al. (Sat,) studied this question.