On the edge expansion of random polytopes
International Mathematics Research Notices · 09.06.2026 · 2026 (11)
DOI: 10.1093/imrn/rnag114 ↗Kurz gefasst
Fachartikel in der Zeitschrift International Mathematics Research Notices, online erschienen am 09.06.2026. Verfasst von Asaf Ferber und 3 weiteren Autor:innen. Die Arbeit nennt 25 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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.
Zitieren
APA
Ferber, A., Krivelevich, M., Sales, M., & Samotij, W. (2026). On the edge expansion of random polytopes. International Mathematics Research Notices, 2026(11). https://doi.org/10.1093/imrn/rnag114
Vancouver
Ferber A, Krivelevich M, Sales M, Samotij W. On the edge expansion of random polytopes. International Mathematics Research Notices. 2026;2026(11). doi:10.1093/imrn/rnag114
BibTeX
@article{Ferber2026,
author = {Ferber, Asaf and Krivelevich, Michael and Sales, Marcelo and Samotij, Wojciech},
title = {On the edge expansion of random polytopes},
journal = {International Mathematics Research Notices},
year = {2026},
volume = {2026},
number = {11},
doi = {10.1093/imrn/rnag114}
}
EUVIMED