{"id":"arxiv/2604.09520","url":"https://arxiv.org/abs/2604.09520","tags":["math.CO","cs.DM","math.PR"],"score":0,"title":"Random 0/1-polytopes expand rapidly","domain":"math.CO","source":"arxiv","authors":["He Guo","István Tomon"],"reviews":0,"subject":"math.CO","summary":"A 0/1-polytope is the convex hull of a subset $V\\subseteq \\{0,1\\}^n$. A celebrated conjecture of Mihail and Vazirani asserts that the graph of every 0/1-polytope has edge-expansion at least 1. In this paper, we show that typical 0/1-polytopes have significantly stronger expansion. Specifically, if $V$ is formed by sampling each vertex of $\\{0,1\\}^n$ independently with constant probability $p$, then with high probability the edge-expansion is $Θ(n)$ for $p \\in (1/2, 1)$, and $n^{Θ(\\log \\log n)}$ for $p \\in (0, 1/2)$. This improves the previously best known bound $Ω(1)$ due to Ferber,…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-10","reactions":{}}