{"id":"609fc78e-5c62-40c5-b36f-0ec6feffb42a","arxiv_id":"2607.21428","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"low","formal_verification":"none","parameter_count":1,"one_line_summary":"For random recursive trees with independent Erdős–Rényi shortcut edges, subcritical bond percolation exposes a decorated tree structure on which Jordan centrality recovers the root within a deterministic-size confidence set.","lead":"This paper gives a root-finding algorithm for a random recursive tree augmented with random shortcut edges, using an auxiliary percolation step to turn the cyclic graph back into a tree-like object. The result is a proof that a constant-size candidate set can contain the first vertex with high probability, even though the observed graph is no longer a tree.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the only soft spot is the explicitly acknowledged q<1/3 moment restriction, and it is not a gap.","rationale":"The reader's weakest assumption is q<1/3, and I agree that this is the most delicate condition in the proof. However, it is an explicit hypothesis of the theorem, not a hidden assumption, and the paper clearly remarks it is not expected to be sharp. I checked the main proof steps for circularity and internal consistency: the q-percolation analysis treats retained tree and shortcut edges symmetrically, Lemma 5.13 correctly derives the conditional uniform-attachment skeleton, Lemma 5.16's raw weights are conditionally independent with controlled moments, and Lemma 5.17's weighted-to-unweighted Jordan transfer is deterministic and valid on the high-probability single-attachment event. The possible exact-tie issue in component ranking is handled by the strictly positive asymptotic gaps among the top blob sizes. I therefore find no concrete failure mode that would change the ACCEPT verdict, and I propose an independent re-derivation of the key moment recursion as a worthwhile verification step.","tokens_in":33556,"tokens_out":46377,"duration_ms":462273,"concrete_test":"Independently re-derive Lemma 5.14: verify that for q<1/3, (1/n)Σ_i W_{n,i}^3 = O_P(1) follows from Lemma 5.3(b), and that the dominating branching-process second moment satisfies M2 ≤ C E[(W*)^2] + ρ M2 with ρ<1, yielding M2 = O_P(1). If the recursion or the size-biased third-moment bound fails at q close to 1/3, the decoration-moment step would need revisiting; otherwise the central claim stands.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I find no load-bearing flaw in the central claim. Theorem 3.2's proof requires q<1/3 in Lemma 5.14 to make (1/n)Σ W_i^3 = O_P(1), i.e. finite second moment of the size-biased blob law; this is the weakest assumption, but the paper flags it as non-sharp and uses it cleanly. The chain—Theorem 3.1 for component identification, Lemma 5.13 for the uniform-attachment skeleton, Lemmas 5.14–5.16 for singly-attached decorations with controlled moments, Lemma 5.12 for weighted-Jordan root finding, Lemma 5.17 for transfer to ordinary Jordan—has no circular step. The conditional independence statements check: conditional on A, internal parents factor; conditional on F_n, raw weights are independent and independent of the skeleton. The constants K,L depend on (ε,q,λ) only. The only way the argument could fail is if Lemma 5.14's branching-process domination or its M2 recursion were wrong for q<1/3, but the computations are explicit and internally consistent. I would not adjust the reader's verdict.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper treats network archaeology for the unlabeled cyclic observed graph G_n = T_n ∪ H_n, where T_n is a random recursive tree and H_n is an independent Erdős–Rényi shortcut layer with edge probability λ/n. The main tool is auxiliary subcritical bond percolation. Retaining edges with probability p < 1/(λ+2), the retained tree edges form heavy-tailed Yule–Simon blobs, while retained shortcuts contract to a subcritical rank-one inhomogeneous random graph with susceptibility ρ(p,λ)=pλ/(1−2p). Theorem 3.1 shows that, to first order, the largest full percolation components are the largest backbone blobs amplified by (1−ρ)^{-1}. Theorem 3.2 then proves that for auxiliary retention probability q < min{1/(λ+2), 1/3}, the root-finding rule H_{K,L}, which takes the K largest q-percolated components and the L best graph-Jordan vertices inside each, contains vertex 1 with probability tending to 1−ε, with K,L depending only on ε,q,λ. The proof chain includes Yule-embedding blob asymptotics, a subcritical rank-one comparison theorem, a decorated-skeleton reduction of the root component, a robust weighted-Jordan theorem for uniform attachment trees, and a deterministic transfer from weighted to ordinary Jordan centrality. The restriction q<1/3 is explicitly acknowledged as not sharp and is used only to keep the third empirical blob moment O_P(1).","tokens_in":33749,"tokens_out":31897,"duration_ms":300958,"significance":"If the result holds, it extends deterministic-size root-confidence-set theory from growing trees to sparse graphs with cycles, and does so through a genuinely new percolative coarse graining rather than posterior sampling or high-degree filtering. The paper is unusually self-contained: the Yule-process blob limits, the subcritical shortcut exploration, the conditional rank-one comparison, and the decorated-skeleton Jordan transfer are all proved in detail. Theorem 3.1's subcritical component picture is of independent interest. The main limitation, q<1/3, is clearly flagged as non-sharp and does not appear to conceal a gap. The relation to the very recent [DLM26] result is disclosed and discussed honestly; the percolation method and the structural theorem distinguish the contribution.","major_comments":[],"minor_comments":[{"comment":"The weighted Jordan comparison lemma is proved in detail but is never cited in the subsequent proof: Lemma 5.12 proceeds by direct branch-size estimates rather than invoking this lemma. Either cite Lemma 5.11 where it is used or remove it to avoid a dangling statement.","section":"Section 5.4.1, Lemma 5.11"},{"comment":"Several OCR-style artifacts appear in the text, e.g. 'PERCOLA TION' and 'SUBSTRA TE' in the running header and 'o P' in place of o_P in some displays. Figure 4 refers to 'teal' and 'orange' regions; if the figure is printed in grayscale, the description should be made color-independent.","section":"Global / typesetting"},{"comment":"The reduction from external-component moments to full q-percolated component moments is correct, but the sentence 'deleting the root blob and incident shortcut edges only partitions components and removes vertices' is terse. One additional sentence explaining that for r≥1 the r-th power masses of the pieces are dominated by the original component's r-th power would improve readability.","section":"Section 5.4.2, Lemma 5.14"},{"comment":"Lemma 5.12 is stated for a fixed tree size m, while Proposition 5.18 applies it at the random size |B_root^n|. The explanation in the text is sufficient, but a formal random-size corollary of Lemma 5.12 with the same uniform constants would make the application cleaner.","section":"Section 5.4.3, Proposition 5.18"}],"recommendation":"minor_revision","confidential_remarks":"For the editor: the proximity to [DLM26] should be weighed. The present paper's percolative renormalization and Theorem 3.1 are distinct structural contributions, and the related-work section is transparent about the overlap; I do not regard the overlap as disqualifying. My recommendation is driven by the local presentation issues listed in the report."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a careful, almost unusually self-contained paper, and the structural result is new. The root-finding theorem itself, for fixed λ, is already in [DLM26] over a broader noise regime, and the paper openly says that. That makes the contribution methodological and structural rather than endpoint-breaking. It is still worth a serious referee.\n\nWhat is new: Theorem 3.1 gives a subcritical component picture for percolated random recursive trees with ER shortcuts: after thinning, the retained tree clusters are heavy-tailed blobs, the retained shortcuts form a subcritical rank-one graph on them, and the largest full components are leading blobs amplified by the factor (1-ρ)^{-1}. That is a clean, nontrivial statement. The proof is unusually detailed: the Yule embedding, blob asymptotics, the subcritical rank-one bound, the decorated-skeleton reduction, and the weighted-to-ordinary Jordan transfer are all proved in line. There is no circular step; the conditional independence structure is checked explicitly. The machinery is genuinely different from the high-degree filtering in [DLM26], and the idea of using auxiliary percolation to expose a tree-like skeleton in a cyclic graph should have legs beyond this specific model.\n\nSoft spots: the q < 1/3 condition is not sharp and the authors know it. It comes from the third empirical moment of blob sizes, i.e., a finite second moment of the size-biased blob law. This is a real restriction, but it is clearly flagged, and the subcritical comparison itself only needs q < 1/(λ+2). The paper also does not claim optimal confidence-set sizes; the budgets K and L are finite but quantitative efficiency is left open. The overlap of Theorem 3.2 with [DLM26] is real, and no amount of methodological novelty changes that the endpoint for fixed λ was already known. The authors handle this honestly in Section 4, where they say the DLM26 method covers a broader noise regime. That is the right way to do it.\n\nI don't see a load-bearing flaw. The proof chain from Theorem 3.1 through Lemma 5.17 is clear. The moment restriction is the weakest point, but it is a proof-technical limitation, not a gap. The paper is a solid contribution to the network-archaeology literature, especially for people working on percolation-based strategies for cyclic graphs.\n\nRecommendation: yes, send this to peer review. It deserves referee time. Ideally get one referee who knows the inhomogeneous-random-graph literature and one who knows [DLM26], so the comparison is assessed fairly. The paper will likely need only modest revision.","headline":"A careful, genuinely self-contained paper whose structural result is new but whose root-finding endpoint is already known; the authors say so, the proof holds up, and it deserves a serious referee.","tokens_in":34298,"tokens_out":1842,"would_cite":true,"duration_ms":18772,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","60K35","60C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that even when a random recursive tree is obscured by an Erdős–Rényi shortcut layer that creates cycles, the original root can be enclosed in a confidence set whose size depends on the error tolerance but not on the networ","keywords":["random recursive tree","network archaeology","root finding","bond percolation","Jordan centrality","inhomogeneous random graph","subcritical regime","confidence sets"],"falsifier":"Simulate the model with, say, λ=1 and q=0.3 for increasing n, and measure the rank of the root blob among all percolated components along with the Jordan-based budget needed to contain the root. If for any fixed K the probability that the root blob ranks above K fails to stay high, or if the required budget grows with n, the deterministic-size claim is false; the paper predicts that the required (K, L) stabilizes as n grows.","tokens_in":33382,"feed_emoji":"🎯","tokens_out":5265,"duration_ms":53566,"temperature":0.7,"pith_summary":"Network archaeology asks whether a single unlabeled snapshot of a growing network still contains enough information to locate the first vertex. For trees, Jordan (centroid) centrality gives deterministic-size confidence sets, but cycles destroy the clean tree decomposition. This paper shows the signal survives a sparse Erdős–Rényi shortcut layer over a random recursive tree substrate. The device is auxiliary subcritical percolation: thinning the observed graph splits it into heavy-tailed tree-blobs wired by a subcritical rank-one random graph, so the largest components look like one large blob decorated by small shortcut pieces. Jordan centrality inside the largest percolated components then yields a root confidence set of size bounded by constants depending only on the error tolerance and model parameters, not on the network size.","feed_headline":"Root finding survives cycles in random networks","feed_subtitle":"Subcritical percolation exposes the tree skeleton, so the first vertex gets a confidence set whose size does not grow with the network.","key_machinery":"Auxiliary subcritical bond percolation on the observed graph, followed by a blob-and-shortcut renormalization. The retained recursive-tree edges form Yule–Simon blobs with sizes of order n^q and susceptibility (1−2q)^(−1); conditional on these blob sizes, the retained shortcut edges contract to a rank-one inhomogeneous random graph with effective offspring mean ρ(q,λ)=qλ/(1−2q). Subcriticality ρ<1 (equivalently q<1/(λ+2)) makes the largest full components equal to leading blobs amplified by (1−ρ)^(−1) plus o_P(n^q), and the root blob's rank among blobs is tight. Inside the root component, the root blob is a uniform attachment tree skeleton with singly attached shortcut decorations, so a weig","core_discovery":"The central discovery is that the cyclic observed graph G_n = T_n ∪ H_n admits the same root-finding guarantee as the tree alone. With retention parameter q < min{1/(λ+2), 1/3}, the retained tree edges partition the latent recursive tree into blobs whose sizes follow a Yule–Simon law; conditional on blob sizes, retained shortcuts form a rank-one inhomogeneous random graph. Because the effective branching factor ρ(q,λ)=qλ/(1−2q) is below 1, the shortcut layer is subcritical: the K largest full percolated components are exactly the components seeded by the K largest blobs, and the root blob sits among them with tight rank. Inside the root component the root blob is a uniform attachment tree ca","pith_inferences":["If the sketched extension to preferential attachment substrates holds, auxiliary subcritical percolation could become a general reduction from cyclic network archaeology to tree root-finding, with each substrate contributing its own blob law and susceptibility.","The authors flag q<1/3 as a technical, likely non-sharp restriction; if it can be removed, the admissible root-finding range would widen to the full subcritical window and the budget constants could improve.","The auxiliary parameter q creates an algorithmic tradeoff between subcriticality and fragmentation; optimizing q and the resulting budgets is an open problem the paper leaves for future work.","A natural stress test is to replace the homogeneous shortcut layer with a community-structured or heavier-tailed shortcut graph; observing whether the rank-one subcritical mechanism is essential would delimit the method's scope."],"forward_implications":["A single unlabeled snapshot of a sparse cyclic network can be rooted with a confidence set of size bounded independently of the network size.","The structural theorem gives a precise subcritical component picture: largest percolated components are leading blobs amplified by a deterministic factor (1−ρ)^(−1), analogous to subcritical power-law random graphs.","Tree-based centrality arguments transfer to cyclic networks through percolation coarse-graining, rather than through posterior sampling or high-degree filtering.","The required budgets K and L depend only on ε, q, and λ, so the guarantee is uniform across network sizes.","The proof isolates the recursive-tree inputs, suggesting the same percolate-and-decorate pipeline can be rerun for other attachment mechanisms once the blob law, susceptibility, and root estimate are known."],"fun_headline_variants":["Percolation cracks root in cyclic random networks","Cycles don't stop root detection in random trees","Subcritical percolation reveals the first vertex","Root confidence set for cyclic random graphs"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The shortcut layer after percolation must be subcritical: the effective branching factor ρ(q,λ)=qλ/(1−2q) must stay below 1, and additionally q<1/3 so the size-biased blob law has finite second moment; if either fails, the decorated-skeleton analysis collapses.","fun_headline_variants_meta":{"raw":{"variants":["Percolation cracks root in cyclic random networks","Cycles don't stop root detection in random trees","Subcritical percolation reveals the first vertex","Root confidence set for cyclic random graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000324,"raw_usage":{"total_tokens":1625,"prompt_tokens":688,"completion_tokens":937,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":432,"completion_tokens_details":{"reasoning_tokens":879}},"tokens_in":432,"tokens_out":937,"duration_ms":9896,"temperature":1.0,"reasoning_tokens":879,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T07:27:49.214091+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate the model with, say, λ=1 and q=0.3 for increasing n, and measure the rank of the root blob among all percolated components along with the Jordan-based budget needed to contain the root. If for any fixed K the probability that the root blob ranks above K fails to stay high, or if the required budget grows with n, the deterministic-size claim is false; the paper predicts that the required (K, L) stabilizes as n grows.","supporting_citations":[],"review_version":1}