pith. sign in

arxiv: 2510.13348 · v4 · submitted 2025-10-15 · 🧮 math.PR · math.CO

Diameter and mixing time of the giant component in the percolated hypercube

Michael Anastos , Sahar Diskin , Lyuben Lichev , Maksim Zhukovskii This is my paper

Pith reviewed 2026-05-18 06:37 UTC · model grok-4.3

classification 🧮 math.PR math.CO
keywords hypercube percolationgiant componentdiametermixing timerandom walksupercritical regimebond percolationstability
0
0 comments X

The pith

In bond percolation on the d-dimensional hypercube at p = c/d for fixed c > 1, the giant component has diameter of order Θ(d) and the lazy random walk on it mixes in time of order Θ(d²).

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

The paper studies bond percolation on the binary hypercube where each edge survives independently with probability p = c/d and c > 1 is fixed. It establishes that the largest connected piece, the giant component L_1, has diameter that is linear in the dimension d with high probability. It further shows that a lazy random walk on L_1 requires a number of steps quadratic in d to reach equilibrium. These scalings resolve two specific open questions posed in the 1990s and early 2000s. The arguments rest on a new large-deviation bound for the size of L_1 together with structural control on the complement and a stability result that prevents large sets from falling apart under small random deletions.

Core claim

For bond percolation on the d-dimensional hypercube with edge-retention probability p = c/d where c > 1 is a fixed constant, the giant component L_1 satisfies diam(L_1) = Θ(d) with high probability, and the mixing time of the lazy random walk on L_1 is Θ(d²). The proof proceeds by establishing a tight large-deviation estimate on |L_1|, which in turn relies on a structural description of the small components left after sprinkling, a quantitative bound on the spread of L_1 across the hypercube, and a stability principle that controls the survival of large connected sets after mild thinning; the same toolkit yields optimal expansion bounds inside L_1.

What carries the argument

A tight large-deviation estimate for the number of vertices in the giant component L_1, built from a structural description of the residue after sprinkling, a quantitative spread bound for the giant, and a stability principle under thinning.

If this is right

  • Optimal vertex and edge expansion bounds hold inside the giant component.
  • Large connected sets remain connected after an additional small random thinning with high probability.
  • The complement of the giant component after sprinkling consists of components whose sizes are tightly controlled.
  • The giant component spreads across the hypercube at a linear rate in every direction.

Where Pith is reading between the lines

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

  • The same stability and spread arguments may extend to percolation on other highly symmetric graphs such as the torus or expander-based models.
  • The quadratic mixing time suggests that the giant component behaves like a d-dimensional object with constant speed diffusion.
  • One could test whether the diameter and mixing scales remain Θ(d) and Θ(d²) when c grows slowly with d.

Load-bearing premise

The retention probability is fixed exactly at p = c/d for some constant c greater than 1.

What would settle it

For large d, exhibiting a realization in which the giant component has diameter o(d) or ω(d), or in which the lazy random walk mixes in o(d²) or ω(d²) steps.

Figures

Figures reproduced from arXiv: 2510.13348 by Lyuben Lichev, Maksim Zhukovskii, Michael Anastos, Sahar Diskin.

Figure 1
Figure 1. Figure 1: Illustration of some of the sets from the last proof. The family M10 is represented by a rectangle with a thick black border, and the family M− 2 is represented by a light-blue shape with a dashed border. The family C of components in M− 2 which are not part of L ′ 1 and the set of vertices in SC attached to it through edges of Qd p2 are both represented in red. The family S of components which are in M10 … view at source ↗
read the original abstract

We consider bond percolation on the $d$-dimensional binary hypercube with $p=c/d$ for fixed $c>1$. We prove that the typical diameter of the giant component $L_1$ is of order $\Theta(d)$, and the typical mixing time of the lazy random walk on $L_1$ is of order $\Theta(d^2)$. This resolves long-standing open problems of Bollob\'as, Kohayakawa and {\L}uczak from 1994, and of Benjamini and Mossel from 2003. A key component in our approach is a new tight large deviation estimate on the number of vertices in $L_1$ whose proof includes several novel ingredients: a structural description of the residue outside the giant component after sprinkling, a tight quantitative estimate on the spread of the giant in the hypercube, and a stability principle which rules out the disintegration of large connected sets under thinning. This toolkit further allows us to obtain optimal bounds on the expansion in $L_1$.

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 / 3 minor

Summary. The manuscript considers bond percolation on the d-dimensional binary hypercube with retention probability p = c/d for fixed c > 1. It proves that the typical diameter of the giant component L_1 is of order Θ(d) and the typical mixing time of the lazy random walk on L_1 is of order Θ(d²). This resolves open problems of Bollobás, Kohayakawa and Łuczak (1994) and Benjamini and Mossel (2003). The proof centers on a new tight large-deviation estimate for |L_1| that incorporates a structural description of the residue outside the giant component after sprinkling, a quantitative spread estimate for the giant in the hypercube, and a stability principle ruling out disintegration of large connected sets under thinning; the same toolkit yields optimal expansion bounds in L_1.

Significance. If the central claims hold, the work supplies the first sharp determination of diameter and mixing-time scales for the giant component in this supercritical regime, quantities that have remained open for three decades. The novel ingredients—a structural residue description, spread estimate, and stability principle—constitute a methodological advance that strengthens the analysis of connectivity and expansion in high-dimensional percolated graphs and may extend to related models. The argument flow from the model definition through these estimates to the matching Θ(d) and Θ(d²) bounds is internally consistent and directly targets the claimed scales.

minor comments (3)
  1. [Introduction / Theorem statements] The statements of the main theorems should explicitly define the meaning of 'typical' (e.g., with high probability or in probability) and clarify the dependence on the constant c.
  2. [Section on structural residue description] Notation for the sprinkling parameter and the residue set after sprinkling could be introduced earlier and used consistently throughout the structural arguments.
  3. [Proof of diameter result] A short remark on how the stability principle interacts with the quantitative spread estimate would help readers follow the combination step that yields the diameter bound.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and for the positive assessment, including the recommendation of minor revision. The report correctly identifies the resolution of the open problems posed by Bollobás, Kohayakawa and Łuczak (1994) and by Benjamini and Mossel (2003). No specific major comments appear in the report, so we have no individual points to address.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained via new estimates

full rationale

The paper establishes its main results on the diameter Θ(d) and mixing time Θ(d²) of the giant component in supercritical bond percolation on the hypercube by introducing and proving several new ingredients: a tight large-deviation estimate for |L_1|, a structural description of the residue after sprinkling, a quantitative spread estimate for the giant, and a stability principle against disintegration under thinning. These tools are developed internally from the model definition (p = c/d, c > 1 fixed) and are combined to control expansion and connectivity without reducing any target quantity to a fitted parameter, self-citation chain, or definitional tautology. The argument resolves external open problems from 1994 and 2003 and contains no load-bearing steps that collapse to the claimed outputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work relies on standard background from percolation theory, random walks on graphs, and large-deviation principles for binomial random variables. No free parameters are fitted to data, and no new entities are postulated.

axioms (2)
  • standard math Standard results on the existence and size of the giant component in supercritical bond percolation on the hypercube (p = c/d, c > 1).
    Invoked to set the regime in which the diameter and mixing-time statements are proved.
  • standard math Basic properties of lazy random walks and their mixing times on finite graphs.
    Used to define the mixing-time claim.

pith-pipeline@v0.9.0 · 5719 in / 1454 out tokens · 40233 ms · 2026-05-18T06:37:24.240357+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

56 extracted references · 56 canonical work pages

  1. [1]

    Ajtai, J

    M. Ajtai, J. Koml´ os, and E. Szemer´ edi. Largest random component of ak-cube.Combinatorica, 2(1):1–7, 1982

    work page 1982

  2. [2]

    Alon and J

    N. Alon and J. H. Spencer.The probabilistic method. Hoboken, NJ: John Wiley & Sons, fourth edition, 2016

    work page 2016

  3. [3]

    Anastos, S

    M. Anastos, S. Diskin, D. Elboim, and M. Krivelevich. Climbing up a random subgraph of the hypercube.Electronic Communications in Probability, to appear

    work page

  4. [4]

    Anastos, S

    M. Anastos, S. Diskin, D. Ignasiak, L. Lichev, and Y. Sha. Spanning trees of bounded degree in random geometric graphs.arXiv:2505.1681, 2025

    work page arXiv 2025

  5. [5]

    Andreis, W

    L. Andreis, W. K¨ onig, H. Langhammer, and R. I. A. Patterson. A large-deviations principle for all the components in a sparse inhomogeneous random graph.Probability Theory and Related Fields, 186(1):521–620, 2023

    work page 2023

  6. [6]

    Andreis, W

    L. Andreis, W. K¨ onig, and R. I. A. Patterson. A large-deviations principle for all the cluster sizes of a sparse Erd˝ os– R´ enyi graph.Random Structures & Algorithms, 59(4):522–553, 2021

    work page 2021

  7. [7]

    Benjamini, N

    I. Benjamini, N. Berger, and A. Yadin. Long-range percolation mixing time.Combin. Probab. Comput., 17(4):487–494, 2008

    work page 2008

  8. [8]

    Benjamini, G

    I. Benjamini, G. Kozma, and N. Wormald. The mixing time of the giant component of a random graph.Random Struct. Algorithms, 45(3):383–407, 2014

    work page 2014

  9. [9]

    Benjamini and E

    I. Benjamini and E. Mossel. On the mixing time of a simple random walk on the super critical percolation cluster. Probab. Theory Related Fields, 125(3):408–420, 2003

    work page 2003

  10. [10]

    A. J. Bernstein. Maximally connected arrays on then-cube.SIAM J. Appl. Math., 15:1485–1489, 1967

    work page 1967

  11. [11]

    Beveridge, A

    A. Beveridge, A. Frieze, and C. McDiarmid. Random minimum length spanning trees in regular graphs.Combinatorica, 18(3):311–333, 1998

    work page 1998

  12. [12]

    Blanc-Renaudie, N

    A. Blanc-Renaudie, N. Broutin, and A. Nachmias. The scaling limit of critical hypercube percolation.arXiv preprint arXiv:2401.16365, 2024

    work page arXiv 2024

  13. [13]

    Bollob´ as, Y

    B. Bollob´ as, Y. Kohayakawa, and T. Luczak. The evolution of random subgraphs of the cube.Random Struct. Algo- rithms, 3(1):55–90, 1992

    work page 1992

  14. [14]

    Bollob´ as, Y

    B. Bollob´ as, Y. Kohayakawa, and T. Luczak. On the diameter and radius of random subgraphs of the cube.Random Struct. Algorithms, 5(5):627–648, 1994

    work page 1994

  15. [15]

    Borgs, J

    C. Borgs, J. T. Chayes, R. van der Hofstad, G. Slade, and J. Spencer. Random subgraphs of finite graphs. III. The phase transition for then-cube.Combinatorica, 26(4):395–410, 2006

    work page 2006

  16. [16]

    Ju. D. Burtin. The probability of connectedness of a random subgraph of ann-dimensional cube.Problemy Peredaˇ ci Informacii, 13(2):90–95, 1977

    work page 1977

  17. [17]

    Chung and L

    F. Chung and L. Lu. The diameter of sparse random graphs.Adv. Appl. Math., 26(4):257–279, 2001

    work page 2001

  18. [18]

    Cipriani and M

    A. Cipriani and M. Salvi. Scale-free percolation mixing time.Stochastic Process. Appl., 167:Paper No. 104236, 40, 2024

    work page 2024

  19. [19]

    R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, and D. E. Knuth. On the Lambert W function.Advances in Computational Mathematics, 5(1):329–359, 1996

    work page 1996

  20. [20]

    J. Ding, J. H. Kim, E. Lubetzky, and Y. Peres. Anatomy of a young giant component in the random graph.Random Structures Algorithms, 39(2):139–178, 2011

    work page 2011

  21. [21]

    Diskin, J

    S. Diskin, J. Erde, M. Kang, and M. Krivelevich. Isoperimetric inequalities and supercritical percolation on high- dimensional graphs.Combinatorica, 44(4):741–784, 2024

    work page 2024

  22. [22]

    Diskin, M

    S. Diskin, M. Kang, and L. Lichev. Universality of the matching number in percolated regular graphs. arXiv:2503.11242, 2025

    work page arXiv 2025

  23. [23]

    Durrett.Probability: theory and examples

    R. Durrett.Probability: theory and examples. Cambridge University Press, Cambridge, 2019

    work page 2019

  24. [24]

    M. Dwass. The total progeny in a branching process and a related random walk.J. Appl. Probab., 6(3):682–686, 1969

    work page 1969

  25. [25]

    J. Erde, M. Kang, and M. Krivelevich. Expansion in supercritical random subgraphs of the hypercube and its conse- quences.Ann. Probab., 51:127–156, 2023

    work page 2023

  26. [26]

    Erd˝ os and A

    P. Erd˝ os and A. R´ enyi. On the evolution of random graphs.Magyar Tud. Akad. Mat. Kutat´ o Int. K¨ ozl., 5:17–61, 1960

    work page 1960

  27. [27]

    Erd˝ os and J

    P. Erd˝ os and J. Spencer. Evolution of then-cube.Comput. Math. Appl., 5(1):33–39, 1979

    work page 1979

  28. [28]

    Fernholz and V

    D. Fernholz and V. Ramachandran. The diameter of sparse random graphs.Random Struct. Algorithms, 31(4):482–516, 2007

    work page 2007

  29. [29]

    Fountoulakis and B

    N. Fountoulakis and B. A. Reed. Faster mixing and small bottlenecks.Probab. Theory Related Fields, 137(3-4):475–486, 2007

    work page 2007

  30. [30]

    Fountoulakis and B

    N. Fountoulakis and B. A. Reed. The evolution of the mixing rate of a simple random walk on the giant component of a random graph.Random Struct. Algorithms, 33(1):68–86, 2008

    work page 2008

  31. [31]

    Frieze and M

    A. Frieze and M. Karo´ nski.Introduction to random graphs. Cambridge University Press, Cambridge, 2016

    work page 2016

  32. [32]

    L. H. Harper. Optimal assigments of numbers to vertices.SIAM J. Appl. Math., 12:131–135, 1964

    work page 1964

  33. [33]

    S. Hart. A note on the edges of then-cube.Discrete Math., 14:157–163, 1976

    work page 1976

  34. [34]

    van der Hofstad.Random graphs and complex networks, volume 1

    R. van der Hofstad.Random graphs and complex networks, volume 1. Cambridge university press, 2017

    work page 2017

  35. [35]

    van der Hofstad and A

    R. van der Hofstad and A. Nachmias. Hypercube percolation.J. Eur. Math. Soc., 19(3):725–814, 2017

    work page 2017

  36. [36]

    van der Hofstad and G Slade

    R. van der Hofstad and G Slade. Expansion inn −1 for percolation critical values on then-cube andZ n: the first three terms.Combin. Probab. Comput., 15(5):695–713, 2006

    work page 2006

  37. [37]

    Hulshof and A

    T. Hulshof and A. Nachmias. Slightly subcritical hypercube percolation.Random Structures Algorithms, 56(2):557– 593, 2020. 32 ANASTOS, DISKIN, LICHEV, AND ZHUKOVSKII

    work page 2020

  38. [38]

    Janson, T

    S. Janson, T. Luczak, and A. Ruci´ nski.Random graphs. Wiley-Interscience Series in Discrete Mathematics and Opti- mization. Wiley-Interscience, 2000

    work page 2000

  39. [39]

    Jorritsma, J

    J. Jorritsma, J. Komj´ athy, and D. Mitsche. Large deviations of the giant in supercritical kernel-based spatial random graphs.arXiv:2404.02984, 2024

    work page arXiv 2024

  40. [40]

    Kiwi and D

    M. Kiwi and D. Mitsche. Spectral gap of random hyperbolic graphs and related parameters.Ann. Appl. Probab., 28(2):941–989, 2018

    work page 2018

  41. [41]

    M. Kiwi, M. Schepers, and J. Sylvester. Cover and hitting times of hyperbolic random graphs.Random Structures Algorithms, 65(4):915–978, 2024

    work page 2024

  42. [42]

    D. E. Knuth.The art of computer programming. Vol. 3. Addison-Wesley, Reading, MA, second edition, 1998. Sorting and searching

    work page 1998

  43. [43]

    Krivelevich

    M. Krivelevich. Expanders — how to find them, and what to find in them. InSurveys in combinatorics 2019, volume 456 ofLondon Math. Soc. Lecture Note Ser., pages 115–142. Cambridge Univ. Press, Cambridge, 2019

    work page 2019

  44. [44]

    Krivelevich

    M. Krivelevich. Component sizes in the supercritical percolation on the binary cube.arXiv:2311.07210, 2023

    work page arXiv 2023

  45. [45]

    D. A. Levin, Y. Peres, and E. L. Wilmer.Markov chains and mixing times. Providence, RI: American Mathematical Society, 2017

    work page 2017

  46. [46]

    J. H. Lindsey. Assigment of numbers to vertices.Amer. Math. Monthly, 71:508–516, 1964

    work page 1964

  47. [47]

    McDiarmid

    C. McDiarmid. Concentration. InProbabilistic methods for algorithmic discrete mathematics, pages 195–248. Berlin: Springer, 1998

    work page 1998

  48. [48]

    O’Connell

    N. O’Connell. Some large deviation results for sparse random graphs.Probability theory and related fields, 110(3):277– 285, 1998

    work page 1998

  49. [49]

    R. Otter. The multiplicative process.Ann. Math. Stat., pages 206–224, 1949

    work page 1949

  50. [50]

    Y. Peres. Markov chains and mixing times.https://www.yuval-peres-books.com/ markov-chains-and-mixing-times/. Accessed: October 2025

    work page 2025

  51. [51]

    J. Pitman. Enumerations of trees and forests related to branching processes and random walks.Microsurveys in discrete probability, 41:163–180, 1997

    work page 1997

  52. [52]

    Riordan and N

    O. Riordan and N. Wormald. The diameter of sparse random graphs.Combin. Probab. Comput., 19(5-6):835–926, 2010

    work page 2010

  53. [53]

    A. A. Sapoˇ zenko. Metric properties of almost all functions of the algebra of logic.Diskret. Analiz, 10:91–119, 1967

    work page 1967

  54. [54]

    Spivak.Calculus on manifolds: a modern approach to classical theorems of advanced calculus

    M. Spivak.Calculus on manifolds: a modern approach to classical theorems of advanced calculus. Addison-Wesley Publishing Company, 2018

    work page 2018

  55. [55]

    L. Warnke. On the method of typical bounded differences.Combin. Probab. Comput., 25(2):269–299, 2016

    work page 2016

  56. [56]

    N. C. Wormald. Models of random regular graphs.London mathematical society lecture note series, pages 239–298, 1999. Institute of Science and Technology Austria (ISTA), Klosterneurburg 3400, Austria Email address:michael.anastos@ist.ac.at D-MATH ETH Z ¨urich, R ¨amistrasse 101, 8092 Z ¨urich, Switzerland Email address:sahardiskinmail@gmail.com Institute o...

    work page 1999