Random 0/1-polytopes expand rapidly

He Guo; Istv\'an Tomon

arxiv: 2604.09520 · v1 · submitted 2026-04-10 · 🧮 math.CO · cs.DM· math.PR

Random 0/1-polytopes expand rapidly

He Guo , Istv\'an Tomon This is my paper

Pith reviewed 2026-05-10 16:56 UTC · model grok-4.3

classification 🧮 math.CO cs.DMmath.PR

keywords 0/1-polytopeedge expansionrandom subsethypercubeMihail-Vazirani conjecturegraph expansion

0 comments

The pith

Random 0/1-polytopes have edge-expansion Θ(n) for dense sampling and n^Θ(log log n) for sparser sampling.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that a random subset V of the n-dimensional hypercube, formed by keeping each of the 2^n points independently with fixed probability p, produces a convex hull whose 1-skeleton graph expands much faster than the constant lower bound conjectured for all 0/1-polytopes. For p above 1/2 the expansion reaches linear order in n with high probability; for p below 1/2 it is still a superpolynomial n raised to a power that grows with log log n. This strengthens the earlier guarantee of constant expansion and indicates that the typical case is far from the worst case.

Core claim

If V is formed by sampling each vertex of {0,1}^n independently with constant probability p, then with high probability the edge-expansion of the graph of the convex hull conv(V) is Θ(n) for p ∈ (1/2, 1), and n^Θ(log log n) for p ∈ (0, 1/2).

What carries the argument

The edge-expansion of the 1-skeleton graph of conv(V), defined as the minimum over nonempty proper subsets S of the number of edges leaving S divided by the size of the smaller of S and its complement.

Load-bearing premise

Vertices are included independently with a probability p that stays fixed as dimension n grows.

What would settle it

An explicit construction or numerical check for sufficiently large n and p=0.6 that exhibits a cut whose crossing-edge density is o(n).

read the original abstract

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 $\Theta(n)$ for $p \in (1/2, 1)$, and $n^{\Theta(\log \log n)}$ for $p \in (0, 1/2)$. This improves the previously best known bound $\Omega(1)$ due to Ferber, Krivelevich, Sales and Samotij.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper's claimed expansion rates for p above and below 1/2 contradict the symmetry of the random model under coordinate complementation.

read the letter

The main thing to know is that the quantitative claims cannot both be correct. The abstract states that random 0/1-polytopes have edge-expansion Θ(n) with high probability when the sampling probability p is in (1/2, 1), but only n^Θ(log log n) when p is in (0, 1/2). This split is impossible under the model as written. Sampling each vertex independently with probability p produces the same distribution of polytopes as sampling with probability 1-p after applying the map x to 1-x to every point. That map is an automorphism of the hypercube, preserves edges in the 1-skeleton, and therefore preserves edge-expansion exactly. The distribution of expansion must be identical for p and 1-p. The earlier Ω(1) bound from Ferber et al. respected the symmetry; the new bounds do not. This is a direct contradiction, not a minor technical point. The paper attempts to strengthen the known lower bound on expansion from constant to growing with n in the random case of the Mihail-Vazirani conjecture. That direction is reasonable, since the conjecture concerns all 0/1-polytopes and typical instances are a natural place to look for stronger guarantees. The abstract presents the probabilistic statement cleanly. The soft spot is the symmetry violation. It suggests an error either in the derivation of the rates or in how the two regimes are stated. Without seeing the full proof I cannot locate the exact step, but the abstract alone already shows the inconsistency. The citation pattern is standard and does not introduce circularity. This work would interest people studying expansion properties of polytopes and random methods toward the Mihail-Vazirani conjecture. A reader looking for ideas on typical behavior could extract the overall approach, but the stated rates need correction before they are usable. The paper does not deserve a serious referee report in its current form because the central claim has this internal inconsistency with the model. I recommend against sending it to peer review until the authors resolve the symmetry issue.

Referee Report

1 major / 0 minor

Summary. The manuscript claims that if V is a random subset of the vertices of the n-cube obtained by including each point independently with constant probability p, then with high probability the edge-expansion of the 1-skeleton of conv(V) is Θ(n) for p ∈ (1/2,1) and n^Θ(log log n) for p ∈ (0,1/2). This is presented as an improvement over the Ω(1) lower bound of Ferber et al. for the Mihail-Vazirani conjecture on 0/1-polytopes.

Significance. A correct proof of super-constant expansion for random 0/1-polytopes would be of interest in discrete geometry and expanders. The manuscript contains no machine-checked proofs or reproducible code. The central probabilistic claim is falsifiable in principle via sampling, but the stated result is internally inconsistent.

major comments (1)

[Abstract] Abstract: The claimed high-probability expansion rates Θ(n) for p ∈ (1/2,1) and n^Θ(log log n) for p ∈ (0,1/2) cannot both hold. The model is invariant under the affine map x ↦ 1-x, a bijection on {0,1}^n. If V is sampled with parameter p then 1-V has the same distribution as a sample with parameter 1-p. This map induces a graph isomorphism between the 1-skeletons of conv(V) and conv(1-V), preserving edge-expansion exactly. Hence the distribution of the expansion is identical for p and 1-p, contradicting the distinct asymptotic regimes asserted.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their thorough review of the manuscript. The main objection concerns an alleged internal inconsistency in the abstract regarding the expansion rates for p above and below 1/2, based on a symmetry argument. We explain below why this does not indicate an inconsistency in our claims.

read point-by-point responses

Referee: [Abstract] Abstract: The claimed high-probability expansion rates Θ(n) for p ∈ (1/2,1) and n^Θ(log log n) for p ∈ (0,1/2) cannot both hold. The model is invariant under the affine map x ↦ 1-x, a bijection on {0,1}^n. If V is sampled with parameter p then 1-V has the same distribution as a sample with parameter 1-p. This map induces a graph isomorphism between the 1-skeletons of conv(V) and conv(1-V), preserving edge-expansion exactly. Hence the distribution of the expansion is identical for p and 1-p, contradicting the distinct asymptotic regimes asserted.

Authors: We appreciate the referee bringing this to our attention. However, the proposed symmetry does not map the parameter p to 1-p. Specifically, let φ(x) = 1 − x. For a random set V where each vertex of the hypercube is included independently with probability p, the probability that a fixed point y belongs to φ(V) is equal to the probability that φ(y) belongs to V, which is p. Therefore, φ(V) is distributed identically to V with the same p. While φ is indeed an automorphism of the hypercube preserving the edge structure, this symmetry preserves the sampling parameter and does not equate the distributions for p and 1-p. The distributions for p > 1/2 and p < 1/2 differ, for instance in the typical cardinality of V, allowing for potentially different expansion properties. We therefore see no contradiction with the stated results and do not plan to revise the abstract on this basis. revision: no

Circularity Check

0 steps flagged

No circularity; probabilistic expansion bounds derived independently from sampling model

full rationale

The paper's central claim is a direct probabilistic statement: random sampling of vertices from {0,1}^n with fixed p yields high-probability edge-expansion bounds that depend on whether p exceeds 1/2. No step reduces a derived quantity to a fitted parameter or self-referential definition by construction, nor does any load-bearing premise rest on a self-citation chain. The derivation relies on standard probabilistic method and graph-expansion arguments applied to the 1-skeleton, remaining self-contained against external benchmarks. The noted symmetry under coordinate complementation (p vs 1-p) raises a potential correctness issue but does not create circularity in the logical chain.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Based solely on the abstract, the claim rests on standard definitions of convex hulls, 1-skeleton graphs, and edge-expansion in graph theory, plus basic probabilistic concentration; no free parameters, invented entities, or non-standard axioms are visible.

axioms (2)

standard math Edge-expansion is defined as the minimum over nonempty proper subsets S of the number of edges leaving S divided by |S|.
Standard definition in expander graphs and polytope theory invoked implicitly by the claim.
domain assumption A 0/1-polytope is the convex hull of a subset of the vertices of the unit hypercube.
Core definition stated in the abstract.

pith-pipeline@v0.9.0 · 5449 in / 1533 out tokens · 69060 ms · 2026-05-10T16:56:55.356709+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

[1]

Anari, K

N. Anari, K. Liu, S. O. Gharan, and C. Vinzant. Log-concave polynomials II: High-dimensional walks and an FPRAS for counting bases of a matroid.Ann. of Math.199(1) (2024), 259–299

work page 2024
[2]

Babecki, T

C. Babecki, T. Elling, and A. Ferber. Sharp Threshold for Cliques in Random 0/1 Polytope Graphs.preprint, arXiv:2507.03212

work page arXiv
[3]

V. A. Bondarenko and A. G. Brodskii. On random 2-adjacent 0/1-polyhedra.Discrete Math. Appl.18(2) (2008), 181–186

work page 2008
[4]

Feder and M

T. Feder and M. Mihail. Balanced matroids. STOC92: Proc. 24th Annu. ACM Symp. Theory Comput. (Victoria BC Canada), S. R. Kosaraju, M. Fellows, A. Wigderson, and J. A. Ellis (eds.), ACM, New York NY USA (1992), 26–38

work page 1992
[5]

Ferber, M

A. Ferber, M. Krivelevich, M. Sales, and W. Samotij. On the edge expansion of random polytopes.preprint, arXiv:2509.09831. 20

work page arXiv
[6]

Gillmann

R. Gillmann. 0/1-Polytopes: Typical and Extremal Properties. Doctoral thesis, Technische Universit¨ at Berlin, Fakult¨ at II- Mathematik und Naturwissenschaften, Berlin, 2007

work page 2007
[7]

L. H. Harper. Optimal assignments of numbers to vertices.J. Soc. Indust. Appl. Math.12(1) (1964), 131–135

work page 1964
[8]

H˚ astad and T

J. H˚ astad and T. Leighton. Fast computation using faulty hypercubes. STOC89: Proc. 21st Annu. ACM Symp. Theory Comput. (Seattle WA USA), D. S. Johnson (eds.) ACM, New York NY USA (1989), 251–263

work page 1989
[9]

S. Janson. Large deviations for sums of partly dependent random variables.Random Structures Algorithms 24(3) (2004), 234–248

work page 2004
[10]

Jerrum and A

M. Jerrum and A. Sinclair. Approximating the permanent.SIAM J. Comput.18(6) (1989), 1149–1178

work page 1989
[11]

Jerrum and A

M. Jerrum and A. Sinclair. The markov chain monte carlo method: an approach to approximate counting and integration. PWS Publishing Co., USA, 1996

work page 1996
[12]

V. Kaibel. On the expansion of graphs of 0/1-polytopes. In The Sharpest Cut: The Impact of Manfred Padberg and His Work (pp. 199-216). Society for Industrial and Applied Mathematics (2004)

work page 2004
[13]

Kaibel and A

V. Kaibel and A. Remshagen. On the graph-density of random 0/1-polytopes. In International Workshop on Randomization and Approximation Techniques in Computer Science (pp. 318-328). Berlin, Heidelberg: Springer Berlin Heidelberg (2003)

work page 2003
[14]

Leighton and S

T. Leighton and S. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms.J. ACM46(6) (1999), 787–832

work page 1999
[15]

Leroux and L

B. Leroux and L. Rademacher. Expansion of random 0/1 polytopes.Random Structures Algorithms64(2) (2024), 309–319

work page 2024
[16]

M. Mihail. Combinatorial Aspects of Expanders. Doctoral thesis, Aiken Laboratory, Harvard University, July 1989

work page 1989
[17]

M. Mihail. On the expansion of combinatorial polytopes. Mathematical foundations of computer science 1992, Lecture Notes in Computer Science, Vol 629, I. M. Havel and V. Koubek (eds.), Springer, Berlin, (1992), 37–49

work page 1992
[18]

D. Naddef. The Hirsch conjecture is true for (0,1)-polytopes.Math. Program.45(1) (1989), 109–110. 21

work page 1989

[1] [1]

Anari, K

N. Anari, K. Liu, S. O. Gharan, and C. Vinzant. Log-concave polynomials II: High-dimensional walks and an FPRAS for counting bases of a matroid.Ann. of Math.199(1) (2024), 259–299

work page 2024

[2] [2]

Babecki, T

C. Babecki, T. Elling, and A. Ferber. Sharp Threshold for Cliques in Random 0/1 Polytope Graphs.preprint, arXiv:2507.03212

work page arXiv

[3] [3]

V. A. Bondarenko and A. G. Brodskii. On random 2-adjacent 0/1-polyhedra.Discrete Math. Appl.18(2) (2008), 181–186

work page 2008

[4] [4]

Feder and M

T. Feder and M. Mihail. Balanced matroids. STOC92: Proc. 24th Annu. ACM Symp. Theory Comput. (Victoria BC Canada), S. R. Kosaraju, M. Fellows, A. Wigderson, and J. A. Ellis (eds.), ACM, New York NY USA (1992), 26–38

work page 1992

[5] [5]

Ferber, M

A. Ferber, M. Krivelevich, M. Sales, and W. Samotij. On the edge expansion of random polytopes.preprint, arXiv:2509.09831. 20

work page arXiv

[6] [6]

Gillmann

R. Gillmann. 0/1-Polytopes: Typical and Extremal Properties. Doctoral thesis, Technische Universit¨ at Berlin, Fakult¨ at II- Mathematik und Naturwissenschaften, Berlin, 2007

work page 2007

[7] [7]

L. H. Harper. Optimal assignments of numbers to vertices.J. Soc. Indust. Appl. Math.12(1) (1964), 131–135

work page 1964

[8] [8]

H˚ astad and T

J. H˚ astad and T. Leighton. Fast computation using faulty hypercubes. STOC89: Proc. 21st Annu. ACM Symp. Theory Comput. (Seattle WA USA), D. S. Johnson (eds.) ACM, New York NY USA (1989), 251–263

work page 1989

[9] [9]

S. Janson. Large deviations for sums of partly dependent random variables.Random Structures Algorithms 24(3) (2004), 234–248

work page 2004

[10] [10]

Jerrum and A

M. Jerrum and A. Sinclair. Approximating the permanent.SIAM J. Comput.18(6) (1989), 1149–1178

work page 1989

[11] [11]

Jerrum and A

M. Jerrum and A. Sinclair. The markov chain monte carlo method: an approach to approximate counting and integration. PWS Publishing Co., USA, 1996

work page 1996

[12] [12]

V. Kaibel. On the expansion of graphs of 0/1-polytopes. In The Sharpest Cut: The Impact of Manfred Padberg and His Work (pp. 199-216). Society for Industrial and Applied Mathematics (2004)

work page 2004

[13] [13]

Kaibel and A

V. Kaibel and A. Remshagen. On the graph-density of random 0/1-polytopes. In International Workshop on Randomization and Approximation Techniques in Computer Science (pp. 318-328). Berlin, Heidelberg: Springer Berlin Heidelberg (2003)

work page 2003

[14] [14]

Leighton and S

T. Leighton and S. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms.J. ACM46(6) (1999), 787–832

work page 1999

[15] [15]

Leroux and L

B. Leroux and L. Rademacher. Expansion of random 0/1 polytopes.Random Structures Algorithms64(2) (2024), 309–319

work page 2024

[16] [16]

M. Mihail. Combinatorial Aspects of Expanders. Doctoral thesis, Aiken Laboratory, Harvard University, July 1989

work page 1989

[17] [17]

M. Mihail. On the expansion of combinatorial polytopes. Mathematical foundations of computer science 1992, Lecture Notes in Computer Science, Vol 629, I. M. Havel and V. Koubek (eds.), Springer, Berlin, (1992), 37–49

work page 1992

[18] [18]

D. Naddef. The Hirsch conjecture is true for (0,1)-polytopes.Math. Program.45(1) (1989), 109–110. 21

work page 1989