On the edge expansion of random polytopes
Abstract
A 0/1-polytope in \(\mathbb R^n\) is the convex hull of a subset of \(\{0,\, 1\}^n\). The graph of a polytope \(P\) is the graph whose vertices are the zero-dimensional faces of \(P\) and whose edges are the one-dimensional faces of \(P\). A conjecture of Mihail and Vazirani states that the edge expansion of the graph of every 0/1-polytope is at least one. We study a random version of the problem, where the polytope is generated by selecting vertices of \(\{0,\, 1\}^n\) independently at random with probability \(p \in (0; 1)\). Improving earlier results, we show that, for any \(p \in (0; 1)\), with high probability the edge expansion of the random 0/1-polytope is bounded from below by an absolute constant.
Fields of Study & Subjects
Point processes and geometric inequalities
Stochastic processes and statistical mechanics
Limits and Structures in Graph Theory
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Publisher
- Society for Industrial and Applied Mathematics
- Pages
- 3022–3035
- Publication date
- 1 January 2026
- Language
- EN