Pith. sign in

REVIEW 3 major objections 3 minor 36 references

Cycle lengths in the percolated hypercube

T0 review · 3 major / 3 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 The percolated hypercube simultaneously contains cycles of every even length from 4 up to a near-spanning length.

desk verdict A genuine strengthening of the near-spanning cycle theorem for percolated hypercubes; the proof is repairable but the I3 interval as printed is impossible and needs to be redefined. read the letter →

arxiv 2506.16858 v1 pith:6JZZVOZO submitted 2025-06-20 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 05C8005C38
keywords percolatedhypercubecyclespectrumpancyclicityevencyclesrandomsubgraphsofthesupercriticalpercolationprobabilisticcombinatorics
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

This paper proves that, for every fixed $\varepsilon>0$, once the edge-retention probability of the $d$-dimensional hypercube is at least $c/d$ with $c$ a sufficiently large constant, the random subgraph typically contains cycles of every even length between $4$ and $(1-\varepsilon)2^d$ simultaneously. Because the hypercube is bipartite, no odd cycle can exist, so the result covers every parity-allowed length below a near-spanning bound. The paper thereby upgrades an earlier theorem that guaranteed only one nearly spanning cycle into a complete description of the cycle spectrum of the sparse percolated hypercube. This matters because it shows that the supercritical random hypercube, unlike a sparse random graph where a fixed small cycle length can be absent with probability bounded away from zero, has a cycle system in which short, medium, and near-spanning cycles all coexist.

What carries the argument

The engine of the proof is length adjustment by local detours: from a cycle that is already known to exist, one edge or a short segment is swapped for a path of controlled length through parts of the hypercube that were previously untouched. The detours are supplied by maximal monotone paths in subcubes (which exist with probability at least $(\rho D/(2e))^D$), by paths inside the giant component whose diameter is at most $2^d/d^8$, and by vertex-disjoint 4-cycles whose middle edges lie in a third vertex class. Independence across many disjoint subcubes makes the probability that any target length is missed exponentially small, so a union bound over all even lengths in the interval succeeds.

What would settle it

Compute the expected number of cycles of length $\ell$ in $Q^d_{c/d}$ for $\ell$ ranging over $[4,(1-\varepsilon)2^d]$; if for some fixed $c\ge c(\varepsilon)$ there is a length $\ell_d$ in that interval whose expected count tends to $0$ as $d\to\infty$, then with high probability that length is absent, contradicting Theorem 1. The expectation is huge for small $\ell$, so the decisive range is near the top, where the proof relies on the inherited nearly spanning cycle and on the diameter estimates for the giant component.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: for every $\varepsilon \in (0,1)$ there is a constant $c(\varepsilon)>0$ such that for all $c\ge c(\varepsilon)$, with $p=c/d$, with high probability $Q^d_p$ contains all cycles of even length between $4$ and $(1-\varepsilon)2^d$. The proof splits the target interval into four ranges — very short, short, medium, and long — and produces cycles in each range by a different construction. Very short cycles are found by threading maximal monotone paths through many disjoint small subcubes; short cycles are grown inductively by replacing edges of an existing cycle with longer detours through fresh subcubes; medium cycles come from taking the nearly spanning cycle supplied by a companion result and rerouting it through a neighbouring subcube, with vertex-disjoint 4-cycles used to adjust lengths; long cycles are fine-tuned by splicing a segment of the nearly spanning cycle to a path through the giant component of a second vertex class and using 4-cycles through a third class to add or remove individual units of length.

Load-bearing premise

The argument takes as a black box the companion theorem that, at the edge probabilities used here, the percolated hypercube (including a mixed version with vertex retention) contains a single cycle covering at least a $1-\varepsilon$ fraction of the vertices; if that nearly spanning cycle did not exist, the upper end of the cycle spectrum claimed here would fail.

Editorial extensions

If this is right

  • For every fixed $\varepsilon>0$ and all large enough $c$, the cycle spectrum of $Q^d_{c/d}$ contains every even integer from $4$ to $(1-\varepsilon)2^d$ with probability tending to one.
  • Because the hypercube is bipartite, this is the fullest possible cycle spectrum up to that length: no odd cycle can appear, so the only absent lengths below the longest cycle are odd numbers.
  • The constant $c(\varepsilon)$ can be taken inverse-polynomial in $\varepsilon$, so the statement covers the entire sparse supercritical regime $p=c/d$ for any fixed sufficiently large $c$.
  • The medium- and long-cycle constructions use the nearly spanning cycle from the companion theorem as a starting point, so any future improvement of that theorem to a spanning or Hamiltonian cycle would automatically extend the full even spectrum up to the new bound.
  • The proof leaves open whether the cube is weakly even-pancyclic, meaning whether every even length up to the actual longest cycle appears, in analogy with the open question for $G(n,c/n)$.

Reading between the lines

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

  • A testable extension is the mixed-percolated cube $Q^d_p(q)$, where vertices survive independently with probability $q$: since the companion nearly-spanning-cycle theorem holds for every $q\in(0,1]$, the same four-range construction should give all even cycle lengths up to $(1-\varepsilon)q 2^d$ with only notational changes.
  • The detour machinery suggests a local-resilience version: even after deleting a small proportion of edges adversarially, the percolated hypercube should retain cycles of every even length up to a near-spanning bound, in line with known resilience results for Hamiltonicity in expanders.
  • The bottleneck between $(1-\varepsilon)2^d$ and the true longest cycle is the inherited nearly-spanning-cycle theorem rather than the detour constructions themselves, so improving that companion result would be the most direct route to a stronger cycle spectrum.
  • Simulations for moderate $d$ could probe whether the four ranges already overlap comfortably for $c$ near the constant required by the companion theorem, which would indicate whether the inverse-polynomial dependence on $\varepsilon$ is an artifact of the proof or a genuine feature.
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

3 major / 3 minor

Summary. The paper studies the cycle spectrum of the percolated hypercube Q^d_p with p=c/d for a large constant c. The main result, Theorem 1, asserts that for every ε>0 there is c(ε)>0 such that, with high probability, Q^d_p contains cycles of every even length between 4 and (1−ε)2^d. The proof splits the target range into four intervals and treats them separately: very short cycles via maximal monotone paths in small subcubes, short cycles via an inductive extension lemma, medium cycles by replacing segments of a long cycle with detours through adjacent subcubes, and long cycles by splicing a nearly spanning cycle from a mixed-percolated subcube with the giant component of another mixed-percolated subcube. The argument relies substantially on a theorem from the companion paper [7] guaranteeing a nearly spanning cycle in the mixed percolated hypercube.

Significance. If the proof is corrected, the result is a substantial strengthening of the authors' earlier near-spanning-cycle theorem for the percolated hypercube and a natural analogue of pancyclicity results for sparse random graphs. The proof strategy is coherent and uses interesting tools: monotone paths in random subcubes, vertex expansion in mixed percolation, and a two-cube splicing construction. The modular division of the cycle-length range is appealing, and the high-level strategy appears viable. However, as printed, the manuscript contains several errors that affect load-bearing steps, most importantly an inconsistency between the stated medium/long interval split and the constructions actually proving those ranges. The errors appear repairable, but they must be fixed before the main theorem is established as stated.

major comments (3)
  1. [Section 3, Lemma 3.4, property (P1')] The proof of (P1') applies Theorem 2.4 'with q=1−δ', but the graph Q^d_p[V1] has vertex retention probability q1=1−δ/2, not 1−δ. To obtain a cycle of length (1−δ)(1−δ/2)2^d in Q^d_p[V1], Theorem 2.4 must be invoked with q=1−δ/2 and error parameter δ, or with q=1−δ only if one changes the definition of δ and the target length accordingly. As written, the cited theorem is applied to a mixed-percolated cube with the wrong vertex-retention probability, so the stated conclusion (P1') does not follow from the displayed argument. This is a local correction, but it is load-bearing because (P1') supplies the near-spanning cycle used for the whole I4 construction.
  2. [Section 3, final Chernoff bound in the I4 proof] The sentence 'the probability that there are less than 2^d/d^6 vertex-disjoint edges uv in P' such that there are u',v'∈V3 with uvv'u' forming a 4-cycle in Q^d_p is at most 1−exp{−2^d/d^6}' is written in the wrong direction: the displayed upper bound is close to 1, whereas the intended Chernoff tail is exp{−2^d/d^6}. In addition, the subsequent expression '2ℓ−|\hat C|≤3k' uses an undefined symbol \hat C; it should refer to the cycle C' constructed earlier in the same proof. These are presentation-level slips, but they occur in the final step that turns a cycle of length roughly 2ℓ into a cycle of exact length 2ℓ, so they should be corrected carefully.
  3. [Section 3, induction in the I2 proof] In the induction step, Lemma 3.2 is applied with D=2^{i−11}d and with 2L≈b_i d^{i+1}. The lemma guarantees cycles up to length 2^{-8} L D, which is approximately 2^{i−20} b_i d^{i+2}. The text instead claims the upper endpoint is 2^{i−19} b_i d^{i+2} and sets b_{i+1}=2^{i−19}b_i. This overstates the guaranteed upper endpoint by a factor of 2. The induction can be repaired by taking b_{i+1}=2^{i−20}b_i (or an even smaller positive constant), and the final b_{10} will still be positive, so the existence of a constant b_{10}>0 is not endangered. But the displayed interval inclusion as written is false, and the proof of the I2 claim relies on it.
minor comments (3)
  1. [Section 3, I1 definition and Lemma 3.1] The interval I1 is defined as [4,d/5]∩2N, but Lemma 3.1 is proved only for [4,D/8], and the proof application with D=d yields only [4,d/8]. This gap is not fatal for the theorem because the I2 induction actually proves a stronger statement covering all small cycles up to b_{10}d^{11}, but the stated proof of the I1 part is not correct as written and should be reconciled with the interval definitions.
  2. [Throughout Section 3] There are several inconsistent cross-references: Lemma 3.1 refers to 'Theorem 2.3' when it means Lemma 2.3, and the text refers to 'Theorem 3.2', 'Theorem 3.3', and 'Theorem 3.4' when the statements are Lemmas 3.2, 3.3, and 3.4. These should be corrected in a proofreading pass.
  3. [Section 2 and Section 3 notation] Some superscripts are missing in the plain text, for example 'k 2∈[2−6D,3·2 −6D]' should read k_2∈[2^{-6}D, 3·2^{-6}D], and '2i−16d' should read 2^{i−16}d. This makes the bounds harder to verify and should be fixed in typesetting.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the proof imports the authors' earlier, strictly weaker long-cycle theorem and extends it to all even lengths; the theorem's conclusion is not an input.

full rationale

Theorem 1 is not derived from itself. The long-cycle input is Theorem 2.4, a strictly weaker statement (existence of one cycle of length at least (1-epsilon)q*2^d in the mixed percolated cube), proved in the companion paper [7]; the present paper's contribution is to convert that single cycle into the full even cycle spectrum. Similarly, the I2 induction and Lemma 3.2 use Theorem 2.2 from [6] and Lemma 2.3, neither of which assumes the conclusion. No parameter is fitted and no 'prediction' coincides with an input. The self-citations are load-bearing in the sense that the proof would need a different source for a nearly spanning cycle, but they are independent theorems with stated assumptions that do not include 'all cycle lengths', so under the rules they do not constitute circularity. The score is set to 2 rather than 0 only because the key input is an unpublished companion preprint by the same authors. Caveat: the printed interval split is internally inconsistent: I3 is stated as [d^10, 2^d - 4] while the construction uses paths inside a (d-2)-dimensional subcube and hence cannot produce lengths beyond about 2^(d-3); the I4 proof begins at 2^(d-3). This is a correctness/typographical concern, not a circularity.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The paper introduces no ad hoc objects or fitted constants. All constants c, delta, b_i, and q are chosen in the proof and are not fitted to data. The real load-bearing input is a collection of prior probabilistic-combinatorics theorems, several from the same author group ([6] and [7]), which the paper treats as black boxes.

assumptions (6)
  • standard math Chernoff bound for binomial tails (Lemma 2.1)
    Used throughout for high-probability estimates; standard probabilistic tool, no independent support needed.
  • domain assumption Theorem 2.2 from [6]: for all sufficiently large D and rho>e/D, Q^D_rho contains a maximal monotone path with probability at least 1/2
    Imported from the authors' earlier paper; used in Lemmas 3.1 and 3.2 to find monotone paths inside percolated subcubes.
  • domain assumption Theorem 2.4 from [7]: for q in (0,1] and epsilon in (0,1) there is c0(q,epsilon) such that whp a longest cycle in Q^d_{c/d}(q) has length at least (1-epsilon) q 2^d
    Load-bearing for the medium and long cycle ranges I3 and I4; stated as Theorem 2.4 and Remark 1 of the companion preprint, not reproved here.
  • domain assumption Theorem 2.5: unique giant component of order y 2^d and diameter O(d log^2 d) in Q^d_{c/d} for constant c>1
    Used in Lemma 3.3 and the I4 proof to connect endpoints through the giant of mixed percolated subcubes; follows from [2], [11], and [17].
  • domain assumption Theorem 2.6: unique giant and diameter bound 2^d/d^8 for the mixed percolation Q^d_{c/d}(q)
    Proved partly in the paper, Section 2.2, using isoperimetric and expansion tools; still an assumption carrier because it imports Harper's inequality and tree counting bounds.
  • standard math Harper vertex-isoperimetric inequality (Lemma 2.8)
    Used in Lemma 2.9 to show expansion of small connected sets; classical result from the literature.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Cycle lengths in the percolated hypercube." pith.science (2026). https://pith.science/paper/6JZZVOZO

@misc{pith2026250616858,
  author       = {Pith},
  title        = {Pith review of: Cycle lengths in the percolated hypercube},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6JZZVOZO}},
  note         = {Machine review of arXiv:2506.16858}
}
abstract

Let $Q^d_p$ be the random subgraph of the $d$-dimensional binary hypercube obtained after edge-percolation with probability $p$. It was shown recently by the authors that, for every $\varepsilon > 0$, there is some $c = c(\varepsilon)>0$ such that, if $pd\ge c$, then typically $Q^d_p$ contains a cycle of length at least $(1-\varepsilon)2^d$. We strengthen this result to show that, under the same assumptions, typically $Q^d_p$ contains cycles of all even lengths between $4$ and $(1-\varepsilon)2^d$.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

36 extracted references · 26 canonical work pages

  1. [7]

    Anastos, S

    M. Anastos, S. Diskin, J. Erde, M. Kang, M. Krivelevich, and L. Lichev. Nearly spanning cycle in the percolated hypercube.arXiv preprint arXiv:2505.04436, 2025

    arXiv 2025

  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]

    Alon and J

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

    2016

  5. [4]

    Y. Alon, M. Krivelevich, and E. Lubetzky. Cycle lengths in sparse random graphs.Random Structures Algorithms, 61(3):444–461, 2022

    work page 2022

  6. [5]

    M. Anastos. A note on long cycles in sparse random graphs.Electron. J. Combin., 30(2):Pa- per No. 2.21, 24, 2023

    work page 2023

  7. [6]

    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

  8. [8]

    Beveridge, A

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

    1998

Show all 36 references
  1. [9]

    Bollob´ as

    B. Bollob´ as. The evolution of sparse graphs. InGraph theory and combinatorics (Cam- bridge, 1983), pages 35–57. Academic Press, London, 1984

    1983

  2. [10]

    Bollob´ as.Random graphs, volume 73 ofCambridge Studies in Advanced Mathematics

    B. Bollob´ as.Random graphs, volume 73 ofCambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, second edition, 2001

    2001

  3. [11]

    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

  4. [12]

    J. A. Bondy and V. Chv´ atal. A method in graph theory.Discrete Math., 15(2):111–135, 1976

    1976

  5. [13]

    Chv´ atal

    V. Chv´ atal. On Hamilton’s ideals.J. Combinatorial Theory Ser. B, 12:163–168, 1972. 12

    1972

  6. [14]

    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

    2024

  7. [15]

    Cooper and A

    C. Cooper and A. M. Frieze. Pancyclic random graphs. InRandom graphs ’87 (Pozna´ n, 1987), pages 29–39. Wiley, Chichester, 1990

    1987

  8. [16]

    G. A. Dirac. Some theorems on abstract graphs.Proceedings of the London Mathematical Society, 3(1):69–81, 1952

    1952

  9. [17]

    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

  10. [18]

    Diskin and M

    S. Diskin and M. Krivelevich. Supercritical site percolation on the hypercube: small com- ponents are small.Combin. Probab. Comput., 32(3):422–427, 2023

    2023

  11. [19]

    Diskin and M

    S. Diskin and M. Krivelevich. Expansion in supercritical random subgraphs of expanders and its consequences.Random Structures Algorithms, 65(3):576–600, 2024

    2024

  12. [20]

    Dragani´ c, R

    N. Dragani´ c, R. H. Montgomery, D. Munh´ a Correia, A. Pokrovskiy, and B. Sudakov. Hamil- tonicity of expanders: optimal bounds and applications.arXiv preprint arXiv:2402.06603, 2024

    2024 arXiv

  13. [21]

    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

  14. [22]

    Fernandez de la Vega

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

    1979

  15. [23]

    Friedman and M

    L. Friedman and M. Krivelevich. Cycle lengths in expanding graphs.Combinatorica, 41(1):53–74, 2021

    2021

  16. [24]

    D. Galvin. On homomorphisms from the Hamming cube toZ.Israel J. Math., 138:189–213, 2003

    2003

  17. [25]

    L. H. Harper. Optimal numberings and isoperimetric problems on graphs.J. Combinatorial Theory, 1:385–393, 1966

    1966

  18. [26]

    Hefetz, M

    D. Hefetz, M. Krivelevich, and T. Szab´ o. Hamilton cycles in highly connected and expand- ing graphs.Combinatorica, 29(5):547–568, 2009

    2009

  19. [27]

    Karo´ nski and A

    M. Karo´ nski and A. Ruci´ nski. On the number of strictly balanced subgraphs of a random graph. InGraph theory ( Lag´ ow, 1981), volume 1018 ofLecture Notes in Math., pages 79–83. Springer, Berlin, 1983

    1981

  20. [28]

    R. M. Karp. Reducibility among combinatorial problems. InComplexity of computer computations. Proceedings of a symposium on the complexity of computer computations., pages 85–103. New York-London: Plenum Press, 1972

    1972

  21. [29]

    Koml´ os and E

    J. Koml´ os and E. Szemer´ edi. Limit distribution for the existence of Hamiltonian cycles in a random graph.Discrete Math., 43(1):55–63, 1983

    1983

  22. [30]

    A. D. Korˇ sunov. Solution of a problem of P. Erd˝ os and A. R´ enyi on Hamiltonian cycles in nonoriented graphs.Diskret. Analiz, (31):17–56, 90, 1977

    1977

  23. [31]

    Krivelevich

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

    2023 arXiv

  24. [32]

    Krivelevich, C

    M. Krivelevich, C. Lee, and B. Sudakov. Resilient pancyclicity of random and pseudoran- dom graphs.SIAM J. Discrete Math., 24(1):1–16, 2010

    2010

  25. [33]

    Krivelevich and B

    M. Krivelevich and B. Sudakov. Sparse pseudo-random graphs are Hamiltonian.J. Graph Theory, 42(1):17–33, 2003

    2003

  26. [34]

    Lee and W

    C. Lee and W. Samotij. Pancyclic subgraphs of random graphs.J. Graph Theory, 71(2):142–158, 2012

    2012

  27. [35]

    O. Ore. Note on Hamilton circuits.Amer. Math. Monthly, 67:55, 1960

    1960

  28. [36]

    L. P´ osa. Hamiltonian circuits in random graphs.Discrete Math., 14(4):359–364, 1976. 14

    1976

Pith tools

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