{"id":"cd657aae-61f3-4c2e-bf42-11696f732732","arxiv_id":"2505.04436","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"For every epsilon > 0 there is a C such that the percolated hypercube Q_d^p with p >= C/d contains, with high probability, a cycle of length at least (1-epsilon)2^d.","lead":"A long-standing conjecture about long cycles in percolated hypercubes is resolved: for any fixed small loss epsilon, once the edge probability reaches a large constant times 1/d, the random subgraph of the d-dimensional cube almost surely contains a cycle through a (1-epsilon) fraction of all vertices. The proof introduces a suite of new random-graph merging techniques that may transfer to other high-dimensional layered graphs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The Section 6 stitching paths P(k,u) lie inside already-exposed H1, not in the fresh H2; as written the final merge into a cycle has a gap, though a rerouting repair appears possible.","rationale":"The paper's central claim is well-supported by the detailed PEF/MOG machinery, and I agree with the reader's high confidence that the theorem is true and the proof is repairable. The reader's identified weakest assumption, the external giant-component estimate in a d/3-dimensional subcube at constant average degree, is standard and well-cited, and I do not regard it as the most acute risk. The more concrete gap is in Section 6: the connecting paths P(k,u) are claimed to have unexposed edges and to lie in H2, but their vertices u, u1, u2 all lie in L_{m1,m2}[Q0], hence inside V(H1). Moreover, during MOG on layer m1, the edges incident to u and u1 were necessarily exposed as part of the PEF construction, so they cannot be treated as fresh independent p^2 edges. This breaks the stated stitching argument as written. The gap is local and repairable by rerouting the connections downward below L_{m1} before entering the subcubes Q[uk;vk]; such a reroute does not affect the PEF or the interior-counting arguments. Therefore the verdict remains CONDITIONAL: the proof needs a technical correction in the final stitching step, but the architecture and central claim are not in doubt.","tokens_in":30968,"tokens_out":22692,"duration_ms":223423,"concrete_test":"Recompute the layers of the vertices in the path P(k,u) from Section 6: u ∈ L_{m1}, u1 ∈ L_{m1+1}, u2 ∈ L_{m1+2}, and observe that m1+2 ≤ m2, so all three lie in V(H1) = L_{m1,m2}[Q0] ∪ L_{m2+1,m4+1}. This directly falsifies the claim that P(k,u) is contained in H2 = Qd \\ (H1 ∪ {Q[uk;vk]}) and that its edges are yet to be exposed. A further check is whether a modified path descending from u to layer m1 − ⌈20 log d⌉ and then ascending through coordinates from J ∪ {1,k} into Q[uk;vk] can be made vertex-disjoint for all d^20 leaves; if so, the repair is feasible and the proof's architecture survives.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 6 attempts to stitch the at-most-six paths into a cycle using connecting paths P(k,u) = uu1u2, where u is a leaf in W*_P ⊆ L_{m1}[Q0], 1(u1)=1(u)∪{1}, and 1(u2)=1(u)∪{1,k}. The text asserts that these paths 'have edges yet to be exposed' and are contained in H2 = Qd \\ (H1 ∪ {Q[uk;vk]}). This is false. Since m1+2 ≤ m2 = d/2 − d^{0.7}, the vertices u1 and u2 lie in L_{m1,m2}[Q0], which is part of the vertex set of H1, so both edges uu1 and u1u2 are edges of H1. Moreover, during the MOG iteration on L_{m1,m1+1}, the set B_i equals L_{m1,m1+1}[Q0], so both u and u1 belong to B_i; the edges incident to them were therefore exposed and influenced the construction of the PEF. They cannot be treated as fresh, independent p^2 edges. The claimed connecting path with internal vertices outside V(H1) does not exist as written, so the final stitching step that turns the PEF into a cycle is incomplete. The gap is local and repairable by rerouting each connection downward from u to a layer below m1 before entering Q[uk;vk], and the interior-counting and PEF architecture are unaffected, but the proof as written has a concrete hole in its last step.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":31310,"tokens_out":18056,"duration_ms":183163,"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":[{"comment":"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.","section":"Section 6, proof of Theorem 1"},{"comment":"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.","section":"Section 4, construction of Aux and proof of Proposition 4.1"}],"minor_comments":[{"comment":"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.","section":"Section 6, proof of Theorem 1"},{"comment":"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.","section":"Section 5, paragraph before Definition 5.1"},{"comment":"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.","section":"Abstract and reference [11]"},{"comment":"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.","section":"Section 6, last paragraph"}],"recommendation":"major_revision","confidential_remarks":"The result is significant and the overall architecture is coherent. The two major issues are local: one concerns an independence/exposure statement in the final stitching step, and the other concerns the definition of the auxiliary percolation in Section 4. Both appear repairable without changing the strategy or the quantitative conclusions. I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this paper proves Conjecture 1.3 of [11] in strong quantitative form: for any constant epsilon, p = C/d suffices for a cycle that misses only epsilon 2^d vertices. That is a real advance. Previous work in the supercritical regime only got cycles of length 2^d/(d log d). The new machinery — the DFS-Aux algorithm on an auxiliary graph, the Merge-Or-Grow tree process, and the coupling with mixed percolation on the hypercube — is original and likely to be reused. I read the whole proof and the central architecture holds up.\n\nThe stress-test note about Section 6 does not land. The connecting paths P(k,u) start at u in L_{m1}[Q0], then flip coordinate 1, so u1 and u2 live in Q1 (first coordinate 1). H1 consists of L_{m1,m2}[Q0] on the Q0 side plus L_{m2+1,m4+1} in higher layers; u1 and u2 are in layers m1+1 and m1+2 with first coordinate 1, so they are in neither part. Their edges are unexposed, exactly as the paper says. No gap there.\n\nThe reader's three flags are minor and fixable. Section 4's statement that each Aux edge is retained with probability p is a conservative stand-in for the natural coupling probability 1-(1-p)^{C^{1/8}}; the DFS analysis remains valid as a lower bound. The Harris inequality application in the final stitching is not the cleanest justification for the 1/4 lower bound — for large C the bound holds directly from the giant component being large enough — but the stated reasoning is imprecise, not fatal. Lemma 5.7 has a couple of typos. None of these touches the load-bearing parts.\n\nThe only genuinely external input is the giant-component estimate for percolated subcubes at constant average degree, cited as [2,8]. That is standard and well-supported, and the proof cites it explicitly.\n\nWho this is for: anyone working on random subgraphs of high-dimensional graphs, Hamiltonicity thresholds, or percolation on the hypercube. It deserves a serious referee, and I expect acceptance after minor revisions. My recommendation: send it out.","headline":"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.","tokens_in":31893,"tokens_out":4845,"would_cite":true,"duration_ms":44564,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","05C38","05D40"],"pacs":[],"model":"deepseek-v4-flash","headline":"For any fixed $\\varepsilon$, keeping hypercube edges with probability at least $C/d$ yields a cycle through $(1-\\varepsilon)2^d$ vertices.","keywords":["percolated hypercube","random subgraph","nearly spanning cycle","long cycles","merge-or-grow","path-extension forest","mixed percolation","giant component"],"falsifier":"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.","tokens_in":30763,"feed_emoji":"🔁","tokens_out":11531,"duration_ms":110150,"temperature":0.7,"pith_summary":"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.","feed_headline":"A nearly spanning cycle survives percolation at constant average degree","feed_subtitle":"Keeping each hypercube edge with probability just C/d still leaves one cycle through almost all 2^d vertices, confirming a long-standing…","key_machinery":"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.","core_discovery":"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$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"States the conjecture that the paper confirms and supplies the Hamiltonicity threshold p=1/2 as the baseline for long cycles.","marker":"[11]"},{"why":"Supplies the giant-component estimate used in the final stitching step to connect endpoints inside dimension d/3 subcubes.","marker":"[2]"},{"why":"Gives the evolution of random subgraphs of the cube, supporting the component-structure and giant-component facts used at the end.","marker":"[8]"},{"why":"Lovasz's version of the Kruskal-Katona theorem, used to prove expansion from path segments and tree leaves into lower layers.","marker":"[24]"},{"why":"Provides the monotone-path lemma that Lemma 2.3 generalizes, used to find many monotone paths in mixed-percolated subcubes.","marker":"[5]"},{"why":"Konig's theorem, used to color the nearly regular bipartite graph between adjacent layers into two large matchings covering almost all vertices.","marker":"[28]"}],"fun_headline_variants":["Constant average degree still yields a nearly spanning hypercube cycle","Percolated hypercube: one cycle through almost every vertex at p~C/d","Near-perfect cycle in hypercube survives percolation at constant degree","Long-standing conjecture resolved: constant edge probability gives big cycle","Almost all 2^d vertices in a single cycle after sparse percolation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Constant average degree still yields a nearly spanning hypercube cycle","Percolated hypercube: one cycle through almost every vertex at p~C/d","Near-perfect cycle in hypercube survives percolation at constant degree","Long-standing conjecture resolved: constant edge probability gives big cycle","Almost all 2^d vertices in a single cycle after sparse percolation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000599,"raw_usage":{"total_tokens":2772,"prompt_tokens":887,"completion_tokens":1885,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":503,"completion_tokens_details":{"reasoning_tokens":1790}},"tokens_in":503,"tokens_out":1885,"duration_ms":13900,"temperature":1.0,"reasoning_tokens":1790,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T23:33:41.495565+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Condon, A","cited_arxiv_id":null,"evidence_quote":"States the conjecture that the paper confirms and supplies the Hamiltonicity threshold p=1/2 as the baseline for long cycles."},{"cited_title":"Ajtai, J","cited_arxiv_id":null,"evidence_quote":"Supplies the giant-component estimate used in the final stitching step to connect endpoints inside dimension d/3 subcubes."},{"cited_title":"Bollob´ as, Y","cited_arxiv_id":null,"evidence_quote":"Gives the evolution of random subgraphs of the cube, supporting the component-structure and giant-component facts used at the end."},{"cited_title":"Lov´ asz.Combinatorial problems and exercises","cited_arxiv_id":null,"evidence_quote":"Lovasz's version of the Kruskal-Katona theorem, used to prove expansion from path segments and tree leaves into lower layers."},{"cited_title":"Anastos, S","cited_arxiv_id":null,"evidence_quote":"Provides the monotone-path lemma that Lemma 2.3 generalizes, used to find many monotone paths in mixed-percolated subcubes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Konig's theorem, used to color the nearly regular bipartite graph between adjacent layers into two large matchings covering almost all vertices."}],"review_version":1}