BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Discrete Mathematics Group
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20210101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220825T100000
DTEND;TZID=Asia/Seoul:20220825T110000
DTSTAMP:20260419T075443
CREATED:20220825T010000Z
LAST-MODIFIED:20240707T075527Z
UID:6007-1661421600-1661425200@dimag.ibs.re.kr
SUMMARY:Brett Leroux\, Expansion of random 0/1 polytopes
DESCRIPTION: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. \nAfter 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. \nThis is joint work with Luis Rademacher.
URL:https://dimag.ibs.re.kr/event/2022-08-25/
LOCATION:Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
END:VCALENDAR