REVIEW 3 minor 5 references
$0/1$-Polytopes with Exponentially Small Edge Expansion
T0 review · 0 major / 3 minor · reviewed 2026-08-04 · deepseek-v4-flash
Pith's one-line read A new family of 0/1-polytopes has edge expansion decaying exponentially in dimension, disproving the Mihail–Vazirani conjecture.
desk verdict Clean, self-contained counterexample to the Mihail–Vazirani conjecture; core lemmas hold under inspection. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
Key machinery: the Cayley sum P_n = X_n ∗ Y_n, i.e., conv((X_n×{0}) ∪ (Y_n×{1})) with X_n=C^n×D^n and Y_n=D^n×C^n, together with the one-block compatibility relation R={(00,00),(10,10),(01,01),(11,10),(11,01)}⊆C×D that exactly characterizes which cross-layer segments are edges. The active-block sets I(u), J(u) record which blocks are nonzero; Lemma 11 shows they are invariant along every cross-layer edge, so the cut S_n={|I|<|J|} has no cross-layer boundary. The boundary computation converts the expansion ratio into the diagonal binomial sum Σ_r binom(n,r)^2 6^r, bounded by 12^n β^n, which gives the exponential decay.
What would settle it
Exhaustively test Lemma 9: for each of the 12 pairs (c,d)∈C×D, decide whether some w∈R^2 uniquely maximizes over C at c and over D at d. The paper claims exactly the five pairs in R; a single counterexample outside R would break the active-block invariant and hence the boundary estimate. Independently, for n beyond the threshold (4n+1)β^n<1, evaluating |δ(S_n)|/|S_n| from the explicit formulas should confirm the exponential bound.
Extended reading notes
Core claim
The central claim is Theorem 1: there exist c>0 and an infinite sequence of full-dimensional 0/1-polytopes with dim(P_n)→∞ such that h(G(P_n))≤exp(−c dim(P_n)). The proof gives the explicit bound h(G_n)≤4n β^n/(1−β^n) with β=(1+√6)^2/12, which is below 1 once (4n+1)β^n<1. The polytope is P_n = conv((C^n×D^n)×{0} ∪ (D^n×C^n)×{1}), with C={0,1}² and D={0,e1,e2}. The graph-theoretic heart is a cut S_n containing all vertices whose second-group active-block count exceeds their first-group count; cross-layer edges never leave S_n because every compatible block pair in the relation R matches zero with zero and nonzero with nonzero. Counting same-layer boundary edges gives a diagonal binomial sum t
Load-bearing premise
The construction's validity hinges on Lemma 11, which claims that cross-layer edges preserve the active-block sets—i.e., a block is nonzero in one layer exactly when the matching block is nonzero in the other; if any compatible pair violated this zero/nonzero matching, the cut's boundary would gain cross-layer edges and the exponential bound would break.
Editorial extensions
If this is right
- The Mihail–Vazirani conjecture is false: no constant lower bound holds for all 0/1-polytopes.
- The weaker inverse-polynomial version is also false, since the expansion can be exponentially small in the dimension.
- Random-walk and Markov-chain sampling algorithms that require expansion at least one cannot be justified unconditionally for all 0/1-polytopes.
- The bound is explicit: h(G_n)≤4n β^n/(1−β^n) with β=(1+√6)^2/12, so the failure is quantitative, not just qualitative.
- Full-dimensionality shows the counterexample is not an artifact of degenerate low-dimensional embedding.
Reading between the lines
- Following the paper's remark, the same layered construction with C={0,1}^m and D={0,e1,...,em} likely yields a sharper decay rate; computing the analogue of the diagonal sum would make this explicit.
- The active-block invariant suggests a general recipe: any Cayley sum whose cross-layer adjacency relation preserves a monotone statistic will have a cut with only same-layer boundary, potentially yielding other small-expansion polytopes.
- The contrast with the random-polytope results cited in the paper points to a sharp worst-case versus typical-case separation: expansion is not guaranteed by the class of 0/1-polytopes, only typical in random models.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper gives an explicit construction of full-dimensional 0/1-polytopes (P_n) in dimension 4n+1 whose 1-skeleta have exponentially small edge expansion. The polytope is P_n = conv(C^n × D^n × {0} ∪ D^n × C^n × {1}), where C={0,1}^2 and D={0,e1,e2}. The proof classifies all edges: same-layer edges are Cartesian-product edges (Lemma 8), and cross-layer edges are governed by a five-pair compatibility relation R (Lemma 9, Corollary 10). It then defines S_n = {u: |I(u)|<|J(u)|} using active-block sets, proves each V_{K,L} is a connected component of the cross-layer graph (Lemma 11), and shows that the edge boundary of S_n is counted exactly by the diagonal profiles (Lemma 13). Combined with the Cauchy-Schwarz bound on the diagonal binomial sum, this yields h(G(P_n)) ≤ 4n β^n/(1-β^n) with β=(1+√6)^2/12<1, hence h<1 and exponential decay in dim(P_n). Since dim(P_n)=4n+1, this disproves the Mihail-Vazirani conjecture in full generality.
Significance. This is a significant resolution of a longstanding open problem. The construction is simple and fully explicit; the proof is self-contained and has no fitted parameters. The derived bound is quantitative, including an explicit exponential decay constant. I independently checked the three delicate steps: the compatibility relation, the connectivity/invariance of V_{K,L}, and the boundary count in Lemma 13; all are valid. The result also rules out inverse-polynomial lower bounds for general 0/1-polytopes. The paper is well-written and the related-work discussion is accurate.
minor comments (3)
- [Section 3, Lemma 11] The connectivity argument is terse but valid. I recommend expanding it by explicitly noting that in every unchanged block the chosen compatible partner is 00 for an inactive block and nonzero for an active block, so the intermediate upper-layer vertex indeed lies in the same V_{K,L}; and that first-group changes between 10 and 01 are realized in two steps via 11. This would remove a common source of reader hesitation.
- [Section 4, Lemma 13] The boundary count is correct, but the sentence 'Starting from this diagonal endpoint' may confuse because the diagonal endpoint is the outside endpoint of the boundary edge. A short clarification that the inside endpoint has profile (r-1,r) or (r,r+1) would improve readability.
- [Introduction, Statement of AI use] The disclosure that the construction was generated with GPT-5.6 Sol is transparent and the author states that the proof was independently verified. This does not affect mathematical correctness, but the editor should ensure it complies with the journal's AI-use policy.
Circularity Check
No significant circularity: the construction and bound are explicit and self-contained.
full rationale
The paper's central claim (Theorem 1 / Theorem 14) is derived from an explicit construction: P_n = X_n * Y_n with X_n = C^n × D^n and Y_n = D^n × C^n. No parameter is fitted to the target quantity, and no prior result by the author (or anyone else) is invoked as a load-bearing premise. The edge-expansion upper bound is obtained by (i) classifying same-layer edges via the standard Cartesian-product edge characterization (Fact 5), (ii) classifying cross-layer edges via the compatibility relation R, which is proven from first principles in Lemma 9 with explicit witness vectors, (iii) proving an invariant of cross-layer edges (Lemma 11) that motivates the cut S_n, and (iv) counting the boundary of S_n exactly in Lemma 13, followed by a Cauchy–Schwarz bound on the diagonal sum ∑ A_{r,r}. All steps are proven in the paper with elementary arguments; the final exponential decay follows from β < 1 and dim(P_n) = 4n+1, also proven. The self-citations and references to related work (Mihail, Kaibel, etc.) are contextual and do not supply the construction or the bound. The AI-generation disclosure is a statement about provenance, not a mathematical input. Therefore there is no circular step and the score is 0.
Assumptions & free parameters
assumptions (3)
- standard math Every nonempty face of a polytope is exposed by some linear functional.
- standard math The graph of a polytope is its 1-skeleton, and edges are one-dimensional faces; a face exposed by a functional is a closed segment with two vertices.
- standard math Cauchy-Schwarz inequality and the binomial theorem.
Cite this review
Pith. "Pith review of $0/1$-Polytopes with Exponentially Small Edge Expansion." pith.science (2026). https://pith.science/paper/RBV7EYB5
@misc{pith2026260801870,
author = {Pith},
title = {Pith review of: $0/1$-Polytopes with Exponentially Small Edge Expansion},
year = {2026},
howpublished = {\url{https://pith.science/paper/RBV7EYB5}},
note = {Machine review of arXiv:2608.01870}
}
abstract
We present a construction of a family of $0/1$-polytopes whose edge expansion decreases exponentially with the dimension, which disproves the Mihail-Vazirani conjecture that the graph of every $0/1$-polytope has edge expansion at least one.
Reference graph
Works this paper leans on
-
[1]
Log-concave poly- nomials II: High-dimensional walks and an FPRAS for counting bases of a matroid
[ALOV24] Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant. “Log-concave poly- nomials II: High-dimensional walks and an FPRAS for counting bases of a matroid”.Annals of Mathematics199.1 (2024), pp. 259–299.doi:10.4007/annals.2024.199.1.4. [CDLS26] Micha Christoph, Sahar Diskin, Lyuben Lichev, and Benny Sudakov. “The Mihail-Vazirani conject...
-
[89]
The expansion of half-integral polytopes
[CP24] Jean Cardinal and Lionel Pournin. “The expansion of half-integral polytopes” (2024). arXiv: 2402.14343. [FKSS26] Asaf Ferber, Michael Krivelevich, Marcelo Sales, and Wojciech Samotij. “On the edge expansion of random polytopes”.International Mathematics Research Notices2026.11 (2026). doi:10.1093/imrn/rnag114. [FM92] Tom´as Feder and Milena Mihail....
arXiv 2024
-
[1992]
37–49.doi:10.1007/3-540-55808-x_4
1992, pp. 37–49.doi:10.1007/3-540-55808-x_4. 9
-
[2017]
Expansion of random 0/1 polytopes
[LR24] Brett Leroux and Luis Rademacher. “Expansion of random 0/1 polytopes”.Random Struc- tures & Algorithms64.2 (2024), pp. 309–319.doi:10.1002/rsa.21184. [Mih89] Milena Mihail. “Combinatorial Aspects of Expanders”. PhD thesis. Harvard University,
-
[9520]
Optimal numberings and isoperimetric problems on graphs
[Har66] L.H. Harper. “Optimal numberings and isoperimetric problems on graphs”.Journal of Combinatorial Theory1.3 (1966), pp. 385–393.doi:10.1016/s0021-9800(66)80059-5. [Jer03] Mark Jerrum.Counting, Sampling and Integrating: Algorithms and Complexity. Birkh ¨auser Basel, 2003.doi:10.1007/978-3-0348-8005-3. [Kai04] Volker Kaibel. “On the Expansion of Graph...
Reviewed August 4, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.