{"id":"arxiv/2604.20589","url":"https://arxiv.org/abs/2604.20589","tags":["math.CO","math.PR"],"score":0,"title":"The Mihail-Vazirani conjecture and strong edge-expansion in random $0/1$ polytopes","domain":"math.CO","source":"arxiv","authors":["Micha Christoph","Sahar Diskin","Lyuben Lichev","Benny Sudakov"],"reviews":0,"subject":"math.CO","summary":"We study the edge-expansion of the graph of a random $0/1$ polytope $P^d_p$, defined as the convex hull of a random subset of the points in $\\{0,1\\}^d$ where every point is retained independently and with probability $p$. This problem was introduced more than twenty years ago in a work of Gillmann and Kaibel, and has been extensively studied ever since. We prove that, for every fixed $\\varepsilon>0$ and every $p\\in(0,1-\\varepsilon]$, with high probability the graph of $P^d_p$ has edge-expansion $Θ(d)$. This improves the previously best known bound due to Ferber, Krivelevich, Sales and…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-22","reactions":{}}