On the edge expansion of random polytopes
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918139772534784 |
|---|---|
| author | Ferber, Asaf Krivelevich, Michael Sales, Marcelo Samotij, Wojciech |
| author_facet | Ferber, Asaf Krivelevich, Michael Sales, Marcelo Samotij, Wojciech |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_09831 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the edge expansion of random polytopes Ferber, Asaf Krivelevich, Michael Sales, Marcelo Samotij, Wojciech Combinatorics Discrete Mathematics 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. |
| title | On the edge expansion of random polytopes |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2509.09831 |