Subscribe to Events

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. In this talk, 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 $pin (0,1)$. Improving earlier results, we show that, for any $pin (0,1)$, with high probability the edge expansion of the random $0/1$-polytope is bounded from below by an absolute constant.

This is joint work with Asaf Ferber, Michael Krivelevich, and Wojciech Samotij.