Loading Events

« All Events

  • This event has passed.

Brett Leroux, Expansion of random 0/1 polytopes

August 25 Thursday @ 10:00 AM - 11:00 AM KST

Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]


Brett Leroux
UC Davis

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 $\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 random $0/1$ polytope in $\mathbb{R}^d$ is at least $\frac{1}{12d}$ with high probability.

After discussing this result and the proof, we will mention some possible extensions. To conclude, we will discuss some related questions about the combinatorics of random polytopes, including the diameter problem.

This is joint work with Luis Rademacher.


August 25 Thursday
10:00 AM - 11:00 AM KST
Event Category:
Event Tags:


Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]


Joonkyung Lee (이준경)
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.