{"id":"0550a37f-e623-4cea-8c97-c3bb1060ebcb","arxiv_id":"2506.16858","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"With high probability, the percolated hypercube Q^d_{c/d} contains cycles of every even length between 4 and (1-epsilon)2^d.","lead":"Randomly keep each edge of a d-dimensional hypercube with probability c/d. The paper proves that with high probability the resulting graph contains cycles of every even length from 4 up to almost all of its 2^d vertices, strengthening a recent result that only guaranteed one very long cycle.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The I3/I4 interval split in Section 3 is internally inconsistent: the I3 construction only uses three (d-2)-subcubes with 3·2^{d-2} vertices, so it cannot yield cycles of length 2^d-4 as printed, while the I4 proof actually starts at 2^{d-3}.","rationale":"The strongest claim is plausible, and the four-regime strategy is coherent once the interval boundaries are corrected. The paper's main new input beyond the companion paper [7] is the I1–I3 machinery and the I4 shortening/lengthening argument. I checked the most delicate steps: the I2 induction via Lemma 3.2 is acceptable after minor interpretation; the I3 path selection relies on paths in C of length 2ℓ−d^2, which forces 2ℓ ≤ |C| + d^2 ≈ 2^{d−2}+d^2; the I4 argument fixes 2ℓ ∈ [2^{d−3}, |C|] and correctly shortens a nearly spanning cycle. The q mismatch in Lemma 3.4 is real but repairable: applying Theorem 2.4 with q = 1−δ/2 and the appropriate epsilon parameter yields (P1'). The reversed Chernoff inequality in the I4 step is a typo, since the subsequent union bound uses the correct failure probability exp(−Ω(2^d/d^6)). The central unresolved issue is the mismatched I3/I4 interval split, which would leave a gap between 2^{d−3} and 2^d−4 if not corrected. This does not change the CONDITIONAL verdict, as the fix is local and the intended argument is sound; it strengthens the case for a conditional rather than unconditional acceptance.","tokens_in":15025,"tokens_out":19246,"duration_ms":158915,"concrete_test":"Check whether the I3 construction can produce a cycle of length 2^d−4: any such cycle must lie in Q_{0,0}∪Q_{1,0}∪Q_{0,1}, which has only 3·2^{d−2} vertices; since 3·2^{d−2} < 2^d−4 for all d ≥ 4, this is impossible. Separately, with the corrected range I3 = [d^10, 2^{d−3}], verify the path-selection step: for every even 2ℓ ≤ 2^{d−3}, the demanded path length 2ℓ−d^2 satisfies 2ℓ−d^2 ≤ 2^{d−3} ≤ |C|, so the greedy selection of P_i(ℓ) inside C is feasible, and Lemma 3.3 plus the 3-path replacement completes the length adjustment. This distinguishes a boundary typo from a structural gap.","verdict_should_be":"UNCHANGED","load_bearing_attack":"At the start of Section 3 the proof splits the target range into I3 = [d^10, 2^d−4] and I4 = [2^d−4, (1−ε)2^d]. The I3 construction is confined to Q_{0,0} ∪ Q_{1,0} ∪ Q_{0,1}: it starts from a cycle C ⊆ Q_{0,0} of length at least 2^{d−3}, takes subpaths P_i of length 2ℓ−d^2 inside C, extends through Q_{1,0}, and adjusts length using 3-paths through Q_{0,1}. Since Q_{0,0} is a (d−2)-cube, |V(Q_{0,0})| = 2^{d−2}, so C cannot contain any path of length exceeding 2^{d−2}; already for 2ℓ ≈ 2^d−4 the required path length 2ℓ−d^2 ≈ 2^d is impossible. Moreover, the union of the three subcubes used has 3·2^{d−2} vertices, which is less than 2^d−4 for d ≥ 4, so no cycle of length 2^d−4 can exist in this construction. The I4 proof, however, fixes 2ℓ ∈ [2^{d−3}, |C|], showing the intended I4 lower bound is 2^{d−3} and the intended I3 upper bound should be 2^{d−3}, not 2^d−4. As printed, the proofs either leave the range (2^{d−3}, 2^d−4) uncovered or demand an impossible construction. This internal inconsistency is load-bearing for the theorem's claim that all even lengths up to (1−ε)2^d are present.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":15421,"tokens_out":18817,"duration_ms":179688,"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":[{"comment":"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.","section":"Section 3, Lemma 3.4, property (P1')"},{"comment":"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.","section":"Section 3, final Chernoff bound in the I4 proof"},{"comment":"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.","section":"Section 3, induction in the I2 proof"}],"minor_comments":[{"comment":"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.","section":"Section 3, I1 definition and Lemma 3.1"},{"comment":"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.","section":"Throughout Section 3"},{"comment":"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.","section":"Section 2 and Section 3 notation"}],"recommendation":"major_revision","confidential_remarks":"The paper depends essentially on Theorem 2.4 from the companion paper [7], including for the upper end of the cycle spectrum. Since that theorem is not reproved here, the editor may wish to confirm the status of [7] before final acceptance. The number of Lemma/Theorem cross-reference errors and arithmetic slips suggests that the manuscript would benefit from a careful revision before a final decision; none of the identified issues appears to require abandoning the proof strategy."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe headline: this paper does what it says — proves that for p=c/d with c large, the percolated hypercube whp contains every even cycle length from 4 up to (1−ε)2^d. That is a real strengthening of the authors' earlier near-spanning cycle result, and it is the hypercube analogue of Alon–Krivelevich–Lubetzky for G(n,c/n). The proof is a four-regime construction, with an inductive local-to-global lengthening lemma (Lemma 3.2) and a final stage that strings a long cycle through a second giant component and uses V3 4-cycles to adjust lengths. I found no fatal mathematical error in the central mechanisms.\n\nCredit where due: the paper is not a routine application of known theorems. The inductive extension in Section 3.2 is new and looks sound; the mixed percolation setup (Theorem 2.4 from the companion paper) is used cleverly to get the long cycle and then trimmed/extended. The dependency on companion preprints is real but not circular — those are separate results, not restatements of Theorem 1.\n\nNow the soft spots, mostly presentation, but one is structural. The I3 interval as printed is [d^10, 2^d−4], and the construction cannot produce cycles anywhere near that. The starting cycle C lives in Q_{0,0}, a (d−2)-cube, so |C| ≤ 2^{d−2}. Since the paths P_i(ℓ) have length 2ℓ−d^2, you need 2ℓ−d^2 ≤ |C|, which forces 2ℓ ≤ 2^{d−2}+d^2. The stress-test note is right. Fortunately I4 starts at 2^{d−3}, so the fix is simply to cut I3 at 2^{d−3} (or at 2^{d−2} if you can force a Hamiltonian cycle in Q_{0,0}, which is not needed). The union still covers all even lengths. So this is a genuine error in the write-up, but not a theorem-killer.\n\nOther slips: I1 is [4,d/5] while Lemma 3.1 proves [4,d/8]; adjust the split. Lemma 3.4 invokes Theorem 2.4 with q=1−δ, should be q=1−δ/2 (with ε'=δ). The last Chernoff bound in I4 has the inequality direction wrong (should be ≤ exp{...}, not 1−exp{...}). All repairable.\n\nThe citation pattern is fine. The paper deserves a serious referee. I'd send it back for minor revisions, mostly to correct the interval definitions and typos. The core proof is coherent and the result is likely correct as stated after these fixes.","headline":"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.","tokens_in":16008,"tokens_out":5772,"would_cite":true,"duration_ms":50482,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","05C38"],"pacs":[],"model":"deepseek-v4-flash","headline":"The percolated hypercube simultaneously contains cycles of every even length from 4 up to a near-spanning length.","keywords":["percolated hypercube","cycle spectrum","pancyclicity","even cycles","random subgraphs of the hypercube","supercritical percolation","probabilistic combinatorics"],"falsifier":"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.","tokens_in":14813,"feed_emoji":"🔄","tokens_out":11698,"duration_ms":106353,"temperature":0.7,"pith_summary":"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.","feed_headline":"Percolated hypercube has every even cycle length up to near-spanning","feed_subtitle":"Sparse random cube: all even cycle lengths from 4 to almost the whole cube appear together.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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)$."],"supporting_citations":[{"why":"Supplies the nearly spanning cycle in the percolated hypercube (Theorem 2.4) that the medium- and long-cycle constructions extend.","marker":"[7]"},{"why":"Gives the existence of maximal monotone paths in supercritical percolation on subcubes (Theorem 2.2), used to assemble very short and short cycles.","marker":"[6]"},{"why":"Provides the classical giant-component result for bond percolation on the hypercube, cited as part of Theorem 2.5(a).","marker":"[2]"},{"why":"Provides the companion giant-component result for the hypercube used together with [2] for Theorem 2.5(a).","marker":"[11]"},{"why":"Supplies the diameter bound for the giant component (Theorem 2.5(b)) used to route medium cycles through the component.","marker":"[17]"},{"why":"Gives the vertex-isoperimetric inequality (Lemma 2.8) used to prove constant expansion of small connected sets.","marker":"[24]"},{"why":"Bounds the number of rooted $k$-vertex trees in a bounded-degree graph (Lemma 2.7), used in the expansion proof.","marker":"[8]"}],"fun_headline_variants":["Random hypercube gains every even cycle length","All even cycle lengths in percolated hypercube","Sparse random cube has every even cycle","Percolated hypercube: all even cycles to near-full","From 4 to near-spanning: all even cycles in random cube"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Random hypercube gains every even cycle length","All even cycle lengths in percolated hypercube","Sparse random cube has every even cycle","Percolated hypercube: all even cycles to near-full","From 4 to near-spanning: all even cycles in random cube"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001315,"raw_usage":{"total_tokens":5321,"prompt_tokens":876,"completion_tokens":4445,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":492,"completion_tokens_details":{"reasoning_tokens":4367}},"tokens_in":492,"tokens_out":4445,"duration_ms":28257,"temperature":1.0,"reasoning_tokens":4367,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T19:19:23.026208+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Anastos, S","cited_arxiv_id":null,"evidence_quote":"Gives the existence of maximal monotone paths in supercritical percolation on subcubes (Theorem 2.2), used to assemble very short and short cycles."},{"cited_title":"Ajtai, J","cited_arxiv_id":null,"evidence_quote":"Provides the classical giant-component result for bond percolation on the hypercube, cited as part of Theorem 2.5(a)."},{"cited_title":"Bollob´ as, Y","cited_arxiv_id":null,"evidence_quote":"Provides the companion giant-component result for the hypercube used together with [2] for Theorem 2.5(a)."},{"cited_title":"Diskin, J","cited_arxiv_id":null,"evidence_quote":"Supplies the diameter bound for the giant component (Theorem 2.5(b)) used to route medium cycles through the component."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the vertex-isoperimetric inequality (Lemma 2.8) used to prove constant expansion of small connected sets."}],"review_version":2}