Videos

Expansion of random 0/1 polytopes

Presenter
September 30, 2022
Abstract
This talk will be about a type of discrete isoperimetric inequality and uses projections of polytopes in a fundamental way. A conjecture of Milena Mihail and Umesh 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 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.