Pith. sign in

REVIEW 2 major objections 4 minor 1 cited by

Nearly spanning cycle in the percolated hypercube

T0 review · 2 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For any fixed $\varepsilon$, keeping hypercube edges with probability at least $C/d$ yields a cycle through $(1-\varepsilon)2^d$ vertices.

desk verdict This is a serious, largely correct proof of a folklore conjecture, and the stress-test's Section 6 concern is a misreading of which side of Q0 the connecting paths lie in. read the letter →

arxiv 2505.04436 v1 pith:WS6GYACA submitted 2025-05-07 math.CO math.PR

Michael Anastos , Sahar Diskin , Joshua Erde , Mihyun Kang , Michael Krivelevich , Lyuben Lichev This is my paper · ORCID
classification math.COmath.PR MSC 05C8005C3805D40
keywords percolatedhypercuberandomsubgraphnearlyspanningcyclelongcyclesmerge-or-growpath-extensionforestmixedpercolationgiantcomponent
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Randomly keeping each edge of the $d$-dimensional hypercube with probability $p \ge C/d$ produces, with high probability, a single cycle that visits all but an $\varepsilon$-fraction of the cube's $2^d$ vertices. This confirms a folklore conjecture from the study of random subgraphs of the hypercube, and it shows that nearly spanning cycles appear already at constant average degree, well below the $p = 1/2$ threshold needed for a Hamilton cycle. The proof slices the cube into layers, covers almost all vertices with short paths, and then repeatedly merges these paths through reserved vertices and expanding trees until only one cycle remains.

What carries the argument

The central device is a path-extension forest (PEF): a collection of vertex-disjoint paths, each carrying two endpoint segments, with a rooted tree attached to each segment and growing downward through the layers of the cube. The Merge-Or-Grow (MOG) algorithm processes layers from the middle outward: at each layer, a reserved set of vertices is exposed, and every such vertex either connects two trees belonging to different paths, merging the paths, or is absorbed as a leaf, growing the tree. The estimates keeping this going come from expansion bounds on hypercube subcubes (via a Kruskal-Katona-type inequality), a modified depth-first search that merges short paths into paths of length $\omega_C(d)$, and a coupling of tree growth with monotone paths in a mixed-percolated subcube. At the end at most six paths survive, and previously unexposed subcubes of dimension $d/3-1$ are used to stitch them into a single cycle.

What would settle it

A direct necessary check is the isolated-vertex obstruction: no cycle can contain an isolated vertex, so the theorem forces $e^{-C}\le \varepsilon$ up to lower-order terms for every claimed pair $(\varepsilon,C)$. One can compute this inequality immediately for the proof's $C(\varepsilon)$; if it ever failed, the quantitative claim would be false. A sharper test would simulate the proof's final stitching on $Q_d^p$ for moderate $d$ and large $C$ and verify that after the Merge-Or-Grow phase at most six paths survive, since six is the limit used to connect them through dimension $d/3-1$ subcubes.

Watch

Extended reading notes

Core claim

The paper establishes Theorem~1: for every constant $\varepsilon>0$ there is $C=C(\varepsilon)>0$ such that if $p=p(d)\ge C/d$, then with high probability $Q_d^p$ contains a cycle of length at least $(1-\varepsilon)2^d$. The dependence of $C$ on $\varepsilon$ is inverse polynomial. This resolves Conjecture 1.1 of [11] in a strong form: the conjectured condition $pd\to\infty$ implies the existence of a $(1-o(1))2^d$ cycle, and here a fixed constant average degree $pd\ge C$ already suffices, with the lost fraction $\varepsilon$ as small as one likes. The paper also records that the same proof works for mixed edge-and-vertex percolation, giving a cycle of length at least $(1-\varepsilon)\delta 2^d$ when vertices are retained with probability $\delta$.

Load-bearing premise

The load-bearing external premise is that in a percolated subcube of dimension $d/3$ with $p=C/d$, a fixed vertex lies in the largest component with probability at least $1/2$ once $C$ is large; the paper cites this from [2,8] instead of proving it, and without it the final step cannot join the remaining at most six paths into a single cycle.

Editorial extensions

If this is right

  • For any $p$ with $pd\to\infty$, the theorem gives with high probability a cycle of length $(1-o(1))2^d$, confirming the folklore conjecture.
  • The same proof extends to mixed percolation: with vertices kept with probability $\delta$, $Q_d^p(\delta)$ contains a cycle of length at least $(1-\varepsilon)\delta 2^d$ when $p\ge C/d$.
  • The theorem leaves open whether $p=(1+\varepsilon)/d$, the supercritical regime with small constant excess, already yields a linear cycle; currently only $\Omega(2^d/(d\log d))$ is known there.
  • The quantitative form suggests the optimal cycle length should be $(1-e^{-\Omega(pd)})2^d$, matching the isolated-vertex obstruction, but this strengthening is conjectured rather than proved.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The proof's constants are driven by reservoir sizes of order $C^{-1/80}$, so the $C(\varepsilon)$ guaranteed is very large; a natural extension is to optimize these exponents and approach the sharp $(1-e^{-pd})2^d$ form, though the paper only conjectures this.
  • The MOG/PEF machinery is not obviously tied to the hypercube's edge set and could serve as a template for sparse random subgraphs of other layered bipartite graphs; the paper itself asks whether it extends to the middle layer graph, so testing that family would be a direct next step.
  • The only ingredient imported from outside the proof is the giant-component estimate used in the final stitching; making that step self-contained, or replacing it with a direct expansion argument, could lower the required $C$ and possibly reach closer to the critical window.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper proves that for every constant epsilon > 0 there is C = C(epsilon) such that, if p >= C/d, then with high probability the percolated hypercube Q_d^p contains a cycle of length at least (1-epsilon)2^d. This confirms a folklore conjecture stated by Condon, Espuny Díaz, Girão, Kühn, and Osthus. The proof is a multi-stage construction: it partitions the cube into main and reservoir vertex sets, covers almost all vertices by short paths, repeatedly merges paths using a modified DFS on an auxiliary bipartite graph (Sections 3–4), grows extension trees via a Merge-Or-Grow process coupled with a mixed-percolation model on monotone paths (Section 5), and finally stitches the remaining at most six paths into one cycle using fresh disjoint subcubes (Section 6). The paper also states a mixed-percolation generalization in Remark 1 and discusses strengthenings and open problems.

Significance. If the proof is correct, Theorem 1 is a major result: it confirms a long-standing conjecture in a strong quantitative form and shows that a near-spanning cycle appears already at constant average degree, matching the behavior of the binomial random graph. The paper develops several potentially reusable tools: the path-extension forest framework, the Merge-Or-Grow process, the coupling with monotone paths in a mixed-percolated hypercube, and a fully written proof of the generalized monotone-path lemma (Lemma 2.3). The argument is detailed and the parameter choices are explicit, which is a significant strength. The main theorem gives a falsifiable quantitative prediction, and the conjectures in the introduction indicate natural next steps. The result is well within the scope of the journal and is likely to be influential.

major comments (2)
  1. [Section 6, proof of Theorem 1] The assertion that each path P(k,u) has 'edges yet to be exposed' and is contained in H2 is not accurate as written. For u in W*_P subset of L_{m1}[Q0], the first edge uu1 has one endpoint in B_{m1} = L_{m1,m1+1}[Q0], so it was already exposed during the MOG iteration on L_{m1,m1+1}; only the second edge u1u2 is genuinely unexposed. Note, however, that u1 and u2 have first coordinate 1 and lie in L_{m1+1},L_{m1+2}[Q1], so they are outside V(H1); the stronger version of this concern, that the connecting path lies inside H1, does not hold. The real gap is that the proof applies a Chernoff bound treating the two edges of P(k,u) as fresh independent p^2 events without justifying that the already exposed edge uu1 is independent of the PEF construction, or without restructuring the exposure. This is a load-bearing step in the final stitching, but it is locally repairable by a short independence argument.
  2. [Section 4, construction of Aux and proof of Proposition 4.1] The definition of Auxp is inconsistent with the coupling to Q_d^p that is claimed in the proof of Proposition 4.1. An edge of Aux between v in Li[V2] and P* in S1(i) is present in the natural coupling exactly when at least one of the roughly C^{1/8} Q^d edges from v to P* survives, so its probability is 1-(1-p)^{C^{1/8}} >> p, not p. Under an independent p-percolation on Aux, a present Aux edge does not by itself give a retained Q^d edge, so the passage from paths in Auxp to paths in Q_d^p needs the OR-coupling. Since the estimates in Lemmas 4.2–4.4 are monotone in the edge probability, replacing p by the larger OR probability, or explicitly declaring p a lower bound, repairs the argument; as written, however, the model and the path-lifting step are not rigorous.
minor comments (4)
  1. [Section 6, proof of Theorem 1] The sentence claiming that the family {P(k,u) : r in [s], k in K_r, u in W^-_{P_r} union W^+_{P_{r+1}}} is vertex-disjoint is false, because the same u is reused for different k; the later argument only needs to choose one k_r per r, so this should be reworded.
  2. [Section 5, paragraph before Definition 5.1] The phrase 'apply Proposition 4.1 to Q^d_p[L_{m1,m1-1}[V1 union V2]]' appears to be a typo for L_{m4,m4+1}, since the initialization of the PEF is described using the top layers.
  3. [Abstract and reference [11]] The abstract says the Condon et al. Memoir volume is 305 (2024), No. 1534, while reference [11] gives 304(1534):v+132; please correct the inconsistency.
  4. [Section 6, last paragraph] The statement that a fixed vertex in Q[uk;vk] lies in the largest component with probability at least 1/2 at p = C/d is cited to [2,8] without a precise formulation; since C/3 can be made arbitrarily large this is standard and plausible, but the exact consequence used should be stated.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular reasoning detected; the proof derives Theorem 1 from independent probabilistic and structural lemmas and external giant-component results.

full rationale

The derivation of Theorem 1 does not assume its conclusion. Lemma 2.3, although attributed to [5] as a generalization, is proved in full in the paper, so the self-citation is not load-bearing. The self-citations [12] and [14] appear only in the introduction and open problems and are not used in the proof of Theorem 1. The only external input that is genuinely load-bearing is the giant-component estimate for percolated subcubes, cited to [2,8], which are independent works and do not contain the target result. The main PEF/MOG construction is carried out inside the paper with internal lemmas (Lovász's Kruskal-Katona bound, König's theorem, Chernoff, Azuma-Hoeffding, Harris), and Proposition 5.2 is deduced from Propositions 5.4 and 5.5 rather than from the desired cycle. The Section 6 stitching does invoke a large-component fact from [2,8], but that fact is external and is not an input to the theorem. A separate issue is that the claim that the length-two connecting paths have 'edges yet to be exposed' may fail for the first edge uu1, since MOG exposes all edges from L_{m1}[Q0] to L_{m1+1} at the layer-m1 iteration; however, this is a potential correctness gap in the last step, not a circular reduction of the theorem to its own statement.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

No new postulated entities; the paper introduces no new forces, dimensions, or objects beyond the standard hypercube model. The free parameters are proof-construction constants, not fitted to experimental data.

free parameters (3)
  • C = unspecified; any sufficiently large constant
    The constant in the threshold p >= C/d. The proof requires C to be large enough for all union bounds and Chernoff estimates; it is not fitted to data.
  • q1, q2, q3 = q2 = q3 = C^{-1/80}, q1 = 1 - 2C^{-1/80}
    Partition probabilities for the vertex reservoir construction, chosen by hand to balance path merging and tree growth.
  • m1, m2, m3, m4 = m1 = 50 log d, m2 = d/2 - d^{0.7}, m3 = d/2 - d^{0.6}, m4 = d/2 + d^{0.6}
    Layer thresholds defining the main band of the cube and the region where MOG operates. These are chosen to make the layered proof work, not fitted to data.
assumptions (5)
  • standard math Lovasz's version of the Kruskal-Katona theorem (Theorem 2.1)
    Used to lower-bound neighborhood sizes of vertex sets between layers; invoked throughout Sections 5.1 and 5.3.
  • standard math Konig's theorem on edge-coloring bipartite graphs (Lemma 3.4)
    Used to decompose the percolated bipartite graph between two layers into matchings covering almost all vertices.
  • standard math Chernoff, Azuma-Hoeffding, and Harris inequalities
    Used throughout for concentration and correlation arguments; standard probabilistic tools.
  • domain assumption Giant component result for the percolated hypercube: for p = C/d with C large, a fixed vertex lies in the largest component with probability at least 1/2
    Cited [2,8]; load-bearing for the final stitching of the <= 6 paths in Section 6. Not proved in this paper.
  • domain assumption Random vertex partitions of each layer pair are well-spread with probability 1-o(1/d)
    Remark 3.2, proved by Chernoff and used throughout MOG to guarantee regular expansion properties.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Nearly spanning cycle in the percolated hypercube." pith.science (2026). https://pith.science/paper/WS6GYACA

@misc{pith2026250504436,
  author       = {Pith},
  title        = {Pith review of: Nearly spanning cycle in the percolated hypercube},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WS6GYACA}},
  note         = {Machine review of arXiv:2505.04436}
}
abstract

Let $Q^d$ be the $d$-dimensional binary hypercube. We form a random subgraph $Q^d_p\subseteq Q^d$ by retaining each edge of $Q^d$ independently with probability $p$. We show that, for every constant $\varepsilon>0$, there exists a constant $C=C(\varepsilon)>0$ such that, if $p\ge C/d$, then with high probability $Q^d_p$ contains a cycle of length at least $(1-\varepsilon)2^d$. This confirms a long-standing folklore conjecture, stated in particular by Condon, Espuny D\'iaz, Gir\~ao, K\"uhn, and Osthus [Hamiltonicity of random subgraphs of the hypercube, Mem. Amer. Math. Soc. 305 (2024), No. 1534].

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Cycle lengths in the percolated hypercube

    math.CO 2025-06 conditional novelty 7.0 of 10

    With high probability, the percolated hypercube Q^d_{c/d} contains cycles of every even length between 4 and (1-epsilon)2^d.

Reference graph

Works this paper leans on

28 extracted references · 25 canonical work pages · cited by 1 Pith paper

  1. [11]

    Condon, A

    P. Condon, A. Espuny D´ ıaz, A. Gir˜ ao, D. K¨ uhn, and D. Osthus. Hamiltonicity of random subgraphs of the hypercube. Mem. Amer. Math. Soc. , 304(1534):v+132, 2024

    work page 2024

  2. [1]

    Ajtai, J

    M. Ajtai, J. Koml´ os, and E. Szemer´ edi. The longest path in a random graph. Combina- torica, 1:1–12, 1981

    work page 1981

  3. [2]

    Ajtai, J

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

    work page 1982

  4. [3]

    Ajtai, J

    M. Ajtai, J. Koml´ os, and E. Szemer´ edi. First occurrence of Hamilton cycles in random graphs. North-Holland Mathematics Studies , 115(C):173–178, 1985

    work page 1985

  5. [4]

    Alon and J

    N. Alon and J. H. Spencer. The probabilistic method. Wiley Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., Hoboken, NJ, fourth edition, 2016

    work page 2016

  6. [5]

    Anastos, S

    M. Anastos, S. Diskin, D. Elboim, and M. Krivelevich. Climbing up a random subgraph of the hypercube. Electron. Commun. Probab., 29:13, 2024. Id/No 70

    work page 2024

  7. [6]

    Bollob´ as

    B. Bollob´ as. The evolution of random graphs. Trans. Am. Math. Soc., 286:257–274, 1984

    work page 1984

  8. [7]

    Bollob´ as

    B. Bollob´ as. Complete matchings in random subgraphs of the cube. Random Structures Algorithms, 1(1):95–104, 1990

    work page 1990

Show all 28 references
  1. [8]

    Bollob´ as, Y

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

    1992

  2. [9]

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

    1977

  3. [10]

    Collares, J

    M. Collares, J. Doolittle, and J. Erde. The evolution of the permutahedron. arXiv preprint arXiv:2404.17260, 2024

    2024

  4. [12]

    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

    2024

  5. [13]

    Diskin, J

    S. Diskin, J. Erde, M. Kang, and M. Krivelevich. Percolation on high-dimensional product graphs. Random Structures & Algorithms , 66(1):e21268, 2025. 27

    2025

  6. [14]

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

    2023

  7. [15]

    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

    1960

  8. [16]

    Erd˝ os and J

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

    1979

  9. [17]

    Fernandez de la Vega

    W. Fernandez de la Vega. Long paths in random graphs. Studia Sci. Math. Hungar. , 14(4):335–340, 1979

    1979

  10. [18]

    A. Frieze. On large matchings and cycles in sparse random graphs. Discrete Math. , 59(3):243–256, 1986

    1986

  11. [19]

    A. Frieze. Random structures and algorithms. In Proceedings of the International Congress of Mathematicians (ICM 2014), Seoul, Korea, August 13–21, 2014. Vol. I: Plenary lectures and ceremonies, pages 311–340. Seoul: KM Kyung Moon Sa, 2014

    2014

  12. [20]

    A. Frieze. Hamilton Cycles in Random Graphs: a bibliography. arXiv:1901.07139, 2019

    1901 arXiv

  13. [21]

    J. R. Johnson. Long cycles in the middle two layers of the discrete cube. J. Comb. Theory, Ser. A, 105(2):255–271, 2004

    2004

  14. [22]

    Krivelevich

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

    2023 arXiv

  15. [23]

    L. Lichev. The giant component after percolation of product graphs. J. Graph Theory , 99(4):651–670, 2022

    2022

  16. [24]

    Lov´ asz.Combinatorial problems and exercises

    L. Lov´ asz.Combinatorial problems and exercises . North-Holland Publishing Co., Amster- dam, second edition, 1993

    1993

  17. [25]

    T. M¨ utze. Proof of the middle levels conjecture. Proc. Lond. Math. Soc. (3) , 112(4):677– 713, 2016

    2016

  18. [26]

    T. M¨ utze. A book proof of the middle levels theorem.Combinatorica, 44(1):205–208, 2024

    2024

  19. [27]

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

    1967

  20. [28]

    D. B. West. Introduction to graph theory . Prentice Hall, Inc., Upper Saddle River, NJ, 1996. 28

    1996

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.