Random 0/1-polytopes expand rapidly

He Guo, István Tomon · 2026

Read Random 0/1-polytopes expand rapidly by He Guo, István Tomon (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-09520.txt.

Introduction

Guo and Tomon prove that typical 0/1-polytopes expand far more strongly than the celebrated Mihail-Vazirani conjecture requires. They sample each vertex of the n-dimensional cube independently with fixed probability p. With high probability, edge-expansion is of order n when p lies between one half and one. When p lies below one half, it is of order n raised to log log n. Both bounds beat the previous best of constant order, due to Ferber, Krivelevich, Sales, and Samotij.

Catalog record

CREATORHe Guo, István Tomon
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE61839
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.09520

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Random 0/1-polytopes expand rapidly He Guo, István Tomon Abstract A 0/1-polytope is the convex hull of a subset V ⊆ { 0 , 1 } n 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 V is formed by sampling each vertex of { 0 , 1 } n \{0,1\}^{n} independently with constant probability p p , then with high probability the edge-expansion is Θ ⁡ ( n ) \Theta(n) for p ∈ ( 1 / 2 , 1 ) p\in(1/2,1) , and n Θ ⁡ ( log ⁡ log ⁡ n ) n^{\Theta(\log\log n)} for p ∈ ( 0 , 1 / 2 ) p\in(0,1/2) . This improves the previously best known bound Ω ⁡ ( 1 ) \Omega(1) due to Ferber, Krivelevich, Sales and Samotij. 1 Introduction A 0/1-polytope in \mathbb{R}^{n} is the convex hull of a subset of the n -dimensional hypercube \{0,1\}^{n} . These polytopes play a central role in polyhedral combinatorics and combinatorial optimization. Their significance stems from the fact that many algorithmic problems require finding an optimal subset of items from a finite universe, which can be naturally formulated as an integer linear program minimizing a linear cost function c^{T}x over a feasible set V\subseteq\{0,1\}^{n} . Because minimizing a linear function over a discrete set is mathematically equivalent to minimizing it over its convex hull, understanding the geometric structure of \conv(V) is crucial for designing efficient algorithms. Consequently, much of polyhedral combinatorics is dedicated to identifying the exact facet descriptions of specific 0/1-polytopes, such as the matching, matroid, and independent set polytopes. The graph (or 1-skeleton) of a polytope P is the graph whose vertices are the 0-dimensional faces of P , and whose edges are its 1-dimensional faces. The classical Simplex algorithm solves linear programs by traversing the edges of this graph until reaching an optimal vertex. To guarantee that such path-following algorithms can be fast, the graph of the polytope must have a small diameter. For 0/1-polytopes, a celebrated theorem by Naddef [ 18 ] establishes that the diameter is bounded by its dimension, and is therefore at most n . Geometrically, this guarantees that an optimal solution is never more than n steps away from any starting point. While the diameter governs worst-case path lengths, the edge-expansion (or Cheeger constant) characterizes the global connectivity. For a graph G , the edge-expansion is defined as h(G)=\min\left\{\frac{|\partial(U)|}{|U|}:U\subseteq V(G),\;1\leq|U|\leq\frac{1}{2}|V(G)|\right\}, where \partial(U) is the set of edges with exactly one endpoint in U . The edge-expansion of 0/1-polytopes plays a key role in the theory of approximate counting and sampling. Large edge-expansion ensures the rapid mixing of Markov chain random walks, a property utilized to generate elements of combinatorial objects uniformly at random. For instance, analyzing random walks on the matching polytope allowed Jerrum, Sinclair, and Vigoda [ 10 , 11 ] to design a polynomial-time randomized approximation scheme (FPRAS) for computing the permanent of nonnegative matrices. Motivated by these connections, Mihail and Vazirani [ 4 , 17 ] famously conjectured that h(G)\geq 1 for the graph of every 0/1-polytope. The classical result of Harper [ 7 ] shows that h(G)=1 if V=\{0,1\}^{n} is the entire hypercube. The conjecture of Mihail and Vazirani remains a major open problem, though it has been established for several specific classes: stable set polytopes, perfect matching polytopes [ 12 ] , order ideal polytopes, matching polytopes, independent set polytopes [ 16 ] and balanced matroid base polytopes [ 4 ] . In a recent breakthrough, Anari, Liu, Gharan, and Vinzant [ 1 ] proved the conjecture for matroid base polytopes. However, the conjecture remained open even for random 0/1-polytopes , whose study was proposed by Kaibel and Remshagen [ 13 ] and Gillmann [ 6 ] . Let V be generated by sampling each vertex of \{0,1\}^{n} independently with probability p , and let G be the graph of \conv(V) . Leroux and Rademacher [ 15 ] proved that h(G)=\Omega(1/n) with high probability (w.h.p.). Here and later, an event, or more precisely a sequence of events \{A_{n}\}_{n\in\mathbb{N}} happens w.h.p. if \lim_{n\rightarrow\infty}\mathbb{P}(A_{n})=1 . This was improved by Ferber, Krivelevich, Sales and Samotij [ 5 ] , who established that w.h.p. h(G)=\Omega(1) . In this paper, we significantly improve these results. We show that when p is bounded away from 1, the edge-expansion is much larger, and we determine the correct order of magnitude of h(G) across a wide range of probabilities p=p(n) . This resolves questions posed in [ 5 ] in a strong form, and it shows that the Mihail-Vazirani conjecture is true for random 0/1-polytopes. Theorem 1.1 . For every \varepsilon>0 the following holds. Let V be formed by sampling each vertex of \{0,1\}^{n} independently with probability p=p(n) , and let G be the graph of \conv(V) . Then w.h.p.: (a) h(G)=\Theta(n) if p\in(1/2+\varepsilon,1-\varepsilon) , (b) h(G)=n^{\Theta(\log\log n+\log(1/p))} for p\in(n^{-0.05},1/2-\varepsilon) . The constant hidden by \Theta(\cdot) may depend on \varepsilon . The upper bounds on h(G) follow from the degrees in G , as we show in Section 2.3 . For p\in(1/2+\varepsilon,1] , w.h.p. there exist vertices whose hypercube neighbors are all contained in V , ensuring a degree of n and thus h(G)\leq n . Conversely, for p\in(0,1/2) , G contains few edges connecting vertices of Hamming-distance much greater than \log\log n+\log(1/p) , which limits the average degree and implies the corresponding upper bound in ( b ). Our main contributions are the matching lower bounds, whose proof we outline at the end of this section. We remark that in the case p\in[1/2-\varepsilon,1/2+\varepsilon] , which is not covered by Theorem 1.1 , our proof shows that h(G)=\Omega(n) , and the only obstacle of larger expansion is the existence of vertices whose hypercube neighbors are almost all sampled. Theorem 1.1 only applies when p>n^{-O(1)} . However, our results extend to smaller values of p as well via a projection argument introduced in [ 15 ] , and strengthened in [ 5 ] . Theorem 1.2 . Let c>0 , then there exists C>0 such that the following holds. Let p=p(n)\in(2^{-0.9n},n^{-c}) , and let V be formed by sampling each vertex of \{0,1\}^{n} independently with probability p . Then w.h.p. the graph G of \conv(V) satisfies h(G)\geq n^{C\log n}. For exponentially small p , even tighter characterizations exist. In case p\leq 2^{-5n/6} , Bondarenko and Brodskii [ 3 ] proved that G is w.h.p. a clique. Babecki, Elling, and Ferber [ 2 ] refined this, identifying a threshold \delta\approx 0.8295 such that G is a clique if p\leq 2^{-(\delta+\epsilon)n} . They also showed that for p<2^{-n(1/2+\epsilon)} , every vertex has degree (1-o(1))|V| , implying h(G)=\Omega(|V|) . Collectively, these results show that random 0/1-polytopes exhibit super-polynomial edge-expansion for all p<1/2-\varepsilon as long as the size of V permits. 1.1 Proof outline To establish that a graph G has large edge-expansion, it is sufficient to construct a multicommodity flow with low maximum congestion (see Section 2.2 ). Specifically, for every pair of vertices x,y\in V(G) , we distribute a unit of flow across the paths connecting x and y such that the congestion of

Read the complete text