pith. machine review for the scientific record. sign in

arxiv: 2604.20589 · v1 · submitted 2026-04-22 · 🧮 math.CO · math.PR

Recognition: unknown

The Mihail-Vazirani conjecture and strong edge-expansion in random 0/1 polytopes

Micha Christoph , Sahar Diskin , Lyuben Lichev , Benny Sudakov
Authors on Pith no claims yet

Pith reviewed 2026-05-10 00:13 UTC · model grok-4.3

classification 🧮 math.CO math.PR
keywords random 0/1 polytopesedge expansionMihail-Vazirani conjecturehypercube verticesphase transitionconvex hull1-skeleton graph
0
0 comments X

The pith

For fixed p bounded away from 1, the graph of a random 0/1 polytope has edge-expansion linear in dimension d, confirming the Mihail-Vazirani conjecture.

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

The paper examines the edge-expansion of the 1-skeleton graph of random 0/1 polytopes, formed as the convex hull of a random subset of hypercube vertices where each vertex is kept independently with probability p. For any fixed ε > 0 and p in (0, 1 − ε], the authors prove that this expansion is Θ(d) with high probability as d grows. This strengthens earlier lower bounds and verifies the Mihail-Vazirani conjecture in a strong form for the random model. They further establish a phase transition at p = 1/2: when p ≤ 1/2 − ε, the expansion jumps to Ω(d^k) for every fixed k ≥ 2. The results rely on probabilistic control over the random subset and the resulting faces and edges.

Core claim

We prove that, for every fixed ε > 0 and every p ∈ (0, 1 − ε], with high probability the graph of P^d_p has edge-expansion Θ(d). This improves the previously best known bound and verifies, in a strong form, the celebrated Mihail-Vazirani conjecture for random 0/1 polytopes. Although the expansion factor Θ(d) is typically best possible for p ≥ 1/2 + ε, for every fixed ε > 0 and every integer k ≥ 2, if p ≤ 1/2 − ε, then with high probability the graph of P^d_p has edge-expansion Ω(d^k). Thus, random 0/1 polytopes exhibit an interesting phase transition at p = 1/2.

What carries the argument

The graph of the random 0/1 polytope P^d_p (its 1-skeleton) and the edge-expansion of that graph, which counts the minimum cut size relative to the smaller side for subsets of vertices.

If this is right

  • The Mihail-Vazirani conjecture holds for this random model of 0/1 polytopes.
  • Edge-expansion grows linearly with dimension for all p bounded away from 1.
  • A sharp phase transition occurs at p = 1/2, after which expansion is superlinear to any polynomial degree.
  • Previous weaker expansion bounds are improved to the optimal linear rate.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The linear expansion implies that the 1-skeleton mixes rapidly under random walks, which could aid uniform sampling from the polytope.
  • The phase transition suggests that the geometry of random subsets changes qualitatively around half the hypercube vertices.
  • Similar expansion techniques may apply to other random convex bodies or to deterministic polytopes with comparable vertex distributions.

Load-bearing premise

Each point of the d-dimensional hypercube is included independently with fixed probability p bounded away from 1, and concentration holds for the random polytope as d becomes large.

What would settle it

A concrete random instance in dimension d = 100 with p = 0.7 whose 1-skeleton graph has edge-expansion o(d) would falsify the Θ(d) claim.

Figures

Figures reproduced from arXiv: 2604.20589 by Benny Sudakov, Lyuben Lichev, Micha Christoph, Sahar Diskin.

Figure 1
Figure 1. Figure 1: Illustration of the proof of Lemma 5.4. Here, the set Vq ′ = V (Cl)∪V (Cs) is drawn in red. Vertices landing there are black, and the vertices outside are white. The set S is depicted in blue, and edges in the figure belong to Eq ′ . The large subset S ′ of S is at distance 1 from Cl in Eq ′ . Note that the set A might ‘miss’ some of the vertices in S ′ ∩ V (Cl), since some components in Cl may be only par… view at source ↗
read the original abstract

We study the edge-expansion of the graph of a random $0/1$ polytope $P^d_p$, defined as the convex hull of a random subset of the points in $\{0,1\}^d$ where every point is retained independently and with probability $p$. This problem was introduced more than twenty years ago in a work of Gillmann and Kaibel, and has been extensively studied ever since. We prove that, for every fixed $\varepsilon>0$ and every $p\in(0,1-\varepsilon]$, with high probability the graph of $P^d_p$ has edge-expansion $\Theta(d)$. This improves the previously best known bound due to Ferber, Krivelevich, Sales and Samotij, and verifies, in a strong form, the celebrated Mihail-Vazirani conjecture for random $0/1$ polytopes. Although the expansion factor $\Theta(d)$ is typically best possible for $p\ge 1/2+\varepsilon$, we also show that the behaviour changes drastically at $p=1/2$. Namely, for every fixed $\varepsilon>0$ and every integer $k\ge 2$, if $p\le 1/2-\varepsilon$, then with high probability the graph of $P^d_p$ has edge-expansion $\Omega(d^k)$. Thus, random $0/1$ polytopes exhibit an interesting phase transition at $p=1/2$.

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.

Referee Report

0 major / 2 minor

Summary. The paper studies the edge-expansion of the graph of random 0/1 polytopes P^d_p, the convex hull of a random subset of {0,1}^d with each point included independently with probability p. It proves that for every fixed ε>0 and p∈(0,1-ε], the edge-expansion is Θ(d) with high probability, improving prior bounds and verifying the Mihail-Vazirani conjecture in this model. It further shows a phase transition: for p≤1/2-ε the expansion is Ω(d^k) for any fixed k≥2.

Significance. If the proofs hold, this constitutes a substantial advance: it establishes the optimal Θ(d) expansion (typically best possible for p≥1/2+ε) via direct probabilistic arguments in the random model, supplies a strong form of the Mihail-Vazirani conjecture for random 0/1 polytopes, and identifies an interesting phase transition at p=1/2. The explicit parameters and high-probability statements are strengths.

minor comments (2)
  1. [Abstract] The abstract states the high-probability claims but does not indicate the precise probability (e.g., 1-o(1) or 1-exp(-d^Ω(1))); this should be made explicit in the statements of the main theorems.
  2. [Introduction] Notation for the random polytope P^d_p and its graph should be introduced with a short formal definition in the introduction to aid readers unfamiliar with the model.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment and recommendation to accept the manuscript. The referee's summary accurately captures the main results: the proof that random 0/1 polytopes have edge-expansion Θ(d) whp for p ≤ 1-ε, which verifies the Mihail-Vazirani conjecture in strong form, together with the stronger Ω(d^k) bound for any k when p ≤ 1/2-ε and the resulting phase transition at p=1/2.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper presents a direct probabilistic proof establishing high-probability edge-expansion bounds Θ(d) (and stronger Ω(d^k) for p ≤ 1/2 - ε) in the random 0/1 polytope model with independent point inclusion probability p. No derivation step reduces by construction to a fitted parameter, self-definition, or load-bearing self-citation; the argument relies on the stated random model and improves external prior bounds without invoking the Mihail-Vazirani conjecture as an assumption. The result is self-contained against the random geometric setting.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on standard high-dimensional probabilistic combinatorics; no free parameters are fitted, no new entities are postulated, and the axioms are background facts from probability and convex geometry.

axioms (2)
  • standard math Standard concentration and union-bound arguments apply to the random subset model with independent inclusions.
    Invoked implicitly to obtain 'with high probability' statements for large d.
  • domain assumption The edge-expansion definition and its relation to the Mihail-Vazirani conjecture are taken from prior literature.
    The conjecture itself is cited as background.

pith-pipeline@v0.9.0 · 5571 in / 1436 out tokens · 39445 ms · 2026-05-10T00:13:09.008230+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

66 extracted references · 28 canonical work pages

  1. [1]

    2001 , PAGES =

    Bollob\'as, B\'ela , TITLE =. 2001 , PAGES =. doi:10.1017/CBO9780511814068 , URL =

    work page doi:10.1017/cbo9780511814068 2001

  2. [2]

    Polytopes—combinatorics and computation , pages=

    Lectures on 0/1-polytopes , author=. Polytopes—combinatorics and computation , pages=. 2000 , organization=

    2000

  3. [3]

    Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    On the edge expansion of random polytopes , author=. Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2026 , organization=

    2026

  4. [4]

    and Ruci\'nski, A

    Karo\'nski, M. and Ruci\'nski, A. , TITLE =. Graph theory ( ag\'ow, 1981) , SERIES =. 1983 , ISBN =. doi:10.1007/BFb0071616 , URL =

    work page doi:10.1007/bfb0071616 1981

  5. [5]

    2017 , publisher=

    Markov chains and mixing times , author=. 2017 , publisher=

    2017

  6. [6]

    Combinatorica , volume=

    Isoperimetric inequalities and supercritical percolation on high-dimensional graphs , author=. Combinatorica , volume=. 2024 , publisher=

    2024

  7. [7]

    arXiv preprint arXiv:2505.04436 , year=

    Nearly spanning cycle in the percolated hypercube , author=. arXiv preprint arXiv:2505.04436 , year=

    work page arXiv

  8. [8]

    Hamiltonicity of expanders: optimal bounds and applications , year =

    Dragani. Hamiltonicity of expanders: optimal bounds and applications , year =

  9. [9]

    1981 , Publisher =

    M. 1981 , Publisher =

    1981

  10. [10]

    arXiv preprint arXiv:2311.07210 , year=

    Component sizes in the supercritical percolation on the binary cube , author=. arXiv preprint arXiv:2311.07210 , year=

    work page arXiv

  11. [11]

    1998 , Publisher =

    A. 1998 , Publisher =

    1998

  12. [12]

    Harper, L. H. Optimal assigments of numbers to vertices. SIAM J. Appl. Math. 1964

    1964

  13. [13]

    Lindsey, J. H. Assigment of numbers to vertices. Am. Math. Mon. 1964

    1964

  14. [14]

    Bernstein, A. J. Maximally connected arrays on the n -cube. SIAM J. Appl. Math. 1967

    1967

  15. [15]

    A note on the edges of the n -cube

    Hart, S. A note on the edges of the n -cube. Discrete Math. 1976

    1976

  16. [16]

    and Krivelevich, M

    Diskin, S. and Krivelevich, M. , TITLE =. Combin. Probab. Comput. , FJOURNAL =. 2023 , NUMBER =. doi:10.1017/s0963548322000323 , URL =

    work page doi:10.1017/s0963548322000323 2023

  17. [17]

    Harper, L. H. , TITLE =. J. Comb. Theory , FJOURNAL =. 1966 , PAGES =

    1966

  18. [18]

    , TITLE =

    Fernandez de la Vega, W. , TITLE =. Studia Sci. Math. Hungar. , FJOURNAL =. 1979 , NUMBER =

    1979

  19. [19]

    and Krivelevich, M

    Alon, Y. and Krivelevich, M. and Lubetzky, E. , TITLE =. Random Structures Algorithms , FJOURNAL =. 2022 , NUMBER =. doi:10.1002/rsa.21067 , URL =

    work page doi:10.1002/rsa.21067 2022

  20. [20]

    , TITLE =

    Anastos, M. , TITLE =. Electron. J. Combin. , FJOURNAL =. 2023 , NUMBER =. doi:10.37236/11471 , URL =

    work page doi:10.37236/11471 2023

  21. [21]

    and Diskin, S

    Anastos, M. and Diskin, S. and Elboim, D. and Krivelevich, M. , Title =. Electron. Commun. Probab. , ISSN =. 2024 , Language =. doi:10.1214/24-ECP639 , Keywords =

    work page doi:10.1214/24-ecp639 2024

  22. [22]

    Proceedings of the London Mathematical Society , volume=

    Some theorems on abstract graphs , author=. Proceedings of the London Mathematical Society , volume=. 1952 , publisher=

    1952

  23. [23]

    Ore, Oystein , TITLE =. Amer. Math. Monthly , FJOURNAL =. 1960 , PAGES =. doi:10.2307/2308928 , URL =

    work page doi:10.2307/2308928 1960

  24. [24]

    Chv\'. On. J. Combinatorial Theory Ser. B , FJOURNAL =. 1972 , PAGES =. doi:10.1016/0095-8956(72)90020-2 , URL =

    work page doi:10.1016/0095-8956(72)90020-2 1972

  25. [25]

    Bondy, J. A. and Chv\'. A method in graph theory , JOURNAL =. 1976 , NUMBER =. doi:10.1016/0012-365X(76)90078-9 , URL =

    work page doi:10.1016/0012-365x(76)90078-9 1976

  26. [26]

    Hamiltonian circuits in random graphs , JOURNAL =

    P\'. Hamiltonian circuits in random graphs , JOURNAL =. 1976 , NUMBER =. doi:10.1016/0012-365X(76)90068-6 , URL =

    work page doi:10.1016/0012-365x(76)90068-6 1976

  27. [27]

    Solution of a problem of

    Kor. Solution of a problem of. Diskret. Analiz , FJOURNAL =. 1977 , Volume =

    1977

  28. [28]

    The evolution of sparse graphs , BOOKTITLE =

    Bollob\'. The evolution of sparse graphs , BOOKTITLE =. 1984 , MRCLASS =

    1984

  29. [29]

    Lee, Choongbum and Samotij, Wojciech , TITLE =. J. Graph Theory , FJOURNAL =. 2012 , NUMBER =. doi:10.1002/jgt.20638 , URL =

    work page doi:10.1002/jgt.20638 2012

  30. [30]

    Krivelevich, Michael and Lee, Choongbum and Sudakov, Benny , TITLE =. SIAM J. Discrete Math. , FJOURNAL =. 2010 , NUMBER =. doi:10.1137/090761148 , URL =

    work page doi:10.1137/090761148 2010

  31. [31]

    Krivelevich, Michael and Sudakov, Benny , TITLE =. J. Graph Theory , FJOURNAL =. 2003 , NUMBER =. doi:10.1002/jgt.10065 , URL =

    work page doi:10.1002/jgt.10065 2003

  32. [32]

    Limit distribution for the existence of

    Koml\'. Limit distribution for the existence of. Discrete Math. , FJOURNAL =. 1983 , NUMBER =. doi:10.1016/0012-365X(83)90021-3 , URL =

    work page doi:10.1016/0012-365x(83)90021-3 1983

  33. [33]

    and Koml\'

    Ajtai, M. and Koml\'. Largest random component of a. Combinatorica , FJOURNAL =. 1982 , NUMBER =. doi:10.1007/BF02579276 , URL =

    work page doi:10.1007/bf02579276 1982

  34. [34]

    The evolution of random subgraphs of the cube , JOURNAL =

    Bollob\'. The evolution of random subgraphs of the cube , JOURNAL =. 1992 , NUMBER =. doi:10.1002/rsa.3240030106 , URL =

    work page doi:10.1002/rsa.3240030106 1992

  35. [35]

    On the evolution of random graphs , JOURNAL =

    Erd. On the evolution of random graphs , JOURNAL =. 1960 , PAGES =

    1960

  36. [36]

    and Espuny D\'

    Condon, P. and Espuny D\'. Hamiltonicity of random subgraphs of the hypercube , JOURNAL =. 2024 , NUMBER =. doi:10.1090/memo/1534 , URL =

    work page doi:10.1090/memo/1534 2024

  37. [37]

    and Frieze, A

    Cooper, C. and Frieze, A. M. , TITLE =. Random graphs '87 (. 1990 , MRCLASS =

    1990

  38. [38]

    Hamiltonicity of expanders: optimal bounds and applications.arXiv preprint arXiv:2402.06603, 2024

    Hamiltonicity of expanders: optimal bounds and applications , author=. arXiv preprint arXiv:2402.06603 , year=

    work page arXiv

  39. [39]

    and Chayes, J

    Borgs, C. and Chayes, J. T. and van der Hofstad, R. and Slade, G. and Spencer, J. , TITLE =. Combinatorica , FJOURNAL =. 2006 , NUMBER =. doi:10.1007/s00493-006-0022-1 , URL =

    work page doi:10.1007/s00493-006-0022-1 2006

  40. [40]

    and Nachmias, A

    van der Hofstad, R. and Nachmias, A. , TITLE =. J. Eur. Math. Soc. (JEMS) , FJOURNAL =. 2017 , NUMBER =. doi:10.4171/JEMS/679 , URL =

    work page doi:10.4171/jems/679 2017

  41. [41]

    Karp, R. M. , title =. Complexity of computer computations. Proceedings of a symposium on the complexity of computer computations. , isbn =. 1972 , publisher =. doi:10.1007/978-1-4684-2001-2_9 , keywords =

    work page doi:10.1007/978-1-4684-2001-2_9 1972

  42. [42]

    and Krivelevich, M

    Friedman, L. and Krivelevich, M. , title =. Combinatorica , issn =. 2021 , language =. doi:10.1007/s00493-020-4434-0 , keywords =

    work page doi:10.1007/s00493-020-4434-0 2021

  43. [43]

    and Krivelevich, M

    Hefetz, D. and Krivelevich, M. and Szab. Hamilton cycles in highly connected and expanding graphs , fjournal =. Combinatorica , issn =. 2009 , language =. doi:10.1007/s00493-009-2362-0 , keywords =

    work page doi:10.1007/s00493-009-2362-0 2009

  44. [44]

    and Krivelevich, M

    Diskin, S. and Krivelevich, M. , title =. Random Structures Algorithms , issn =. 2024 , language =. doi:10.1002/rsa.21225 , keywords =

    work page doi:10.1002/rsa.21225 2024

  45. [45]

    and Liu, K

    Anari, N. and Liu, K. and Oveis Gharan, S. and Vinzant, C. , TITLE =. Ann. of Math. (2) , FJOURNAL =. 2024 , NUMBER =. doi:10.4007/annals.2024.199.1.4 , URL =

    work page doi:10.4007/annals.2024.199.1.4 2024

  46. [46]

    and Diskin, S

    Anastos, M. and Diskin, S. and Lichev, L. and Zhukovskii, M. , title =. , note =

  47. [47]

    , author=

    On random 2 -adjacent 0/1 -polyhedra. , author=. Discrete Math. Appl. , volume=

  48. [48]

    and Elling, T

    Babecki, C. and Elling, T. and Ferber, A. , title =. , eprint =

  49. [49]

    and Mihail, M

    Feder, T. and Mihail, M. , title =. Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC) , year =

  50. [50]

    Gillmann , title =

    R. Gillmann , title =

  51. [51]

    Harper, L. H. , title =. J. Comb. Theory , volume =

  52. [52]

    and Linial, N

    Hoory, S. and Linial, N. and Wigderson, A. , title =. Bull. Am. Math. Soc. , volume =

  53. [53]

    and Sinclair, A

    Jerrum, M. and Sinclair, A. and Vigoda, E. , title =. J. ACM , volume =

  54. [54]

    , title =

    Kaibel, V. , title =. The Sharpest Cut: The Impact of Manfred Padberg and His Work , series =

  55. [55]

    and Remshagen, A

    Kaibel, V. and Remshagen, A. , title =. Approximation, Randomization, and Combinatorial Optimization (APPROX-RANDOM) , series =

  56. [56]

    , title =

    Krivelevich, M. , title =. Surveys in Combinatorics 2019 , series =

    2019

  57. [57]

    and Rademacher, L

    Leroux, B. and Rademacher, L. , title =. Random Struct. Algorithms , volume =. 2024 , eprint =

    2024

  58. [58]

    and Vazirani, U

    Mihail, M. and Vazirani, U. , title =. Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC) , pages =

  59. [59]

    , title =

    Mihail, M. , title =. Mathematical Foundations of Computer Science (MFCS) , series =

  60. [60]

    , title =

    Mihail, M. , title =

  61. [61]

    , title =

    Schrijver, A. , title =

  62. [62]

    Israel J

    Galvin, David , TITLE =. Israel J. Math. , FJOURNAL =. 2003 , PAGES =. doi:10.1007/BF02783426 , URL =

    work page doi:10.1007/bf02783426 2003

  63. [63]

    Probability Theory and Related Fields , volume=

    Faster mixing and small bottlenecks , author=. Probability Theory and Related Fields , volume=. 2007 , publisher=

    2007

  64. [64]

    Proceedings of the thirty-first annual ACM symposium on Theory of computing , pages=

    Faster mixing via average conductance , author=. Proceedings of the thirty-first annual ACM symposium on Theory of computing , pages=

  65. [65]

    On the method of typical bounded differences , author=. Comb. Probab. Comput. , volume=. 2016 , publisher=

    2016

  66. [66]

    Random 0/1-polytopes expand rapidly , author=