Expansion of random 0/1 polytopes and the Mihail and Vazirani conjecture.

Abstract: 

A 0/1 polytope is the convex hull of a set of 0/1 d-dimensional vectors. A conjecture of Milena Mihail and Umesh Vazirani says that the graph of vertices and edges of every 0/1 polytope is highly connected. Specifically, it 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 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 random 0/1 polytope in R^d is at least 1/12d with high probability. This is joint work with Brett Leroux.

Posted on Jan 19, 2026 in ACGO, Seminars