  A conjecture of Mihail and Vazirani states that the edge expansion of the
graph of every $0/1$ polytope is at least one. Any lower bound on the edge
expansion gives an upper bound for the mixing time of a random walk on the
graph of the polytope. Such random walks are important because they can be used
to generate an element from a set of combinatorial objects uniformly at random.
A weaker form of the conjecture of Mihail and Vazirani says that the edge
expansion of the graph of a $0/1$ polytope in $\mathbb{R}^d$ is greater than 1
over some polynomial function of $d$. This weaker version of the conjecture
would suffice for all applications. Our main result is that the edge expansion
of the graph of a $\textit{random}$ $0/1$ polytope in $\mathbb{R}^d$ is at
least $\frac{1}{12d}$ with high probability.
