{"id":"d8535350-440b-4287-8e4c-cd88b18686e0","arxiv_id":"2607.18201","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A uniform random recursive tree polluted by an Erdős–Rényi graph with p=o(log n/n) still admits a root confidence set of size depending only on ε, not on n.","lead":"A noisy family tree built by one-node-at-a-time growth, plus extra random connections, can still be traced back to its origin: the paper proves that for very sparse noise, a small list of candidate roots—whose size depends only on the desired confidence, not on tree size—contains the true root. This confirms an open conjecture and gives a route for rumor or virus source detection.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"The reader's weakest-assumption identification points to Lemma 2.5 and the positivity of γ(α), but that step is proved in Lemma 2.4 and used correctly; it is not the soft spot. The reader's conditional verdict is motivated by an unproved explicit rate and by omitted auxiliary proofs. Those are real presentation weaknesses but not load-bearing for the main existence theorem, which only needs some finite K(ε). My independent pass through the noisy-reduction core—especially the μ-operator's off-by-one, the neighborhood coupling, and the Jordan-centrality concentration—did not reveal a fatal gap. Hence I do not request a change to the reader's verdict; the paper remains conditional but for addressable, non-central reasons.","tokens_in":44914,"tokens_out":30453,"duration_ms":272842,"concrete_test":"Re-derive Proposition 4.13 from Definition 4.9 by computing c_{t'}(u) after adding the extra leaves X_v for both the root and non-root vertices of the subtree, and check that the pruning threshold ℓ=(1−α)log n−1 yields exactly the inclusion rule d_{T_n}(u)+Z_u > (1−α)log n. If the off-by-one offset is wrong, the exchangeability step would fail; if it matches, the central ER-noise reduction stands.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I read the proof as an existence argument for a finite confidence set K(ε), and I could not find a soundness gap in that central claim. The reduction chain is: Lemma 2.5/Corollary 3.23 put the early URRT chunk T_{n^{γ-ε}} inside the root component; Propositions 3.11 and 3.21 pin the root-component size between n^{α−o(1)} and n^{α+o(1)}; Proposition 3.24 shows all non-root components are smaller than any n^{α−γ/4+o(1)}; and the exchangeability/negative-correlation machinery (Lemma 3.29, Propositions 3.30, 4.13, 4.16) shows that ranking by Jordan centrality in the root component recovers the root with probability tending to 1. I specifically checked the places where a hidden assumption could enter: the off-by-one accounting in the operator μ (Definition 4.11) versus the actual condition d_{T_n}(u)+Z_u > (1−α)log n, the coupling of G-neighborhoods on the random set D_{T_n}(α+δ) (Lemma 4.8, Proposition 4.10), and the exponent bookkeeping in Propositions 3.24 and 3.30. These are consistent. The reader's conditional concerns—the claimed O(log(1/ε)/ε) rate, omitted proofs of auxiliary lemmas, and the citation mismatch—are presentation issues and do not undermine the existence of a finite K(ε).","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies root recovery in a uniform random recursive tree T_n observed together with independent noise. The main result (Theorem 1.7) proves the Crane–Xu conjecture: when the noise is an Erdős–Rényi graph G(n, λ_n/n) with λ_n=o(log n), then for every ε>0 there is a confidence set K(ε) whose cardinality is bounded uniformly in n and which contains the root with probability at least 1−ε. The construction filters the observed graph by vertex degree, identifies the largest connected component of the resulting forest, and ranks vertices by Jordan centrality. A parallel theorem is proved for random perfect matching noise (Theorem 1.8), and an informal extension to d_n-regular noise is discussed in Section 6. The proof is by reduction: the noisy problem is reduced to root-finding in an α-forest, then to an exchangeable/Pólya-urn limit in which Jordan-centrality comparisons are controlled by Dirichlet limits.","tokens_in":45284,"tokens_out":10445,"duration_ms":107207,"significance":"If correct, the main theorem resolves an open conjecture and identifies a nearly sharp noise threshold: root recovery with bounded-size confidence sets is possible up to p=o(log n/n). The proof strategy is substantial and original, combining degree-threshold filtering, component-size identification, Jordan centrality, and exchangeability/negative-correlation arguments. The reduction chain is coherent: Lemmas 2.5 and Corollary 3.23 place an early URRT chunk inside the root component; Propositions 3.11, 3.21, and 3.24 pin its size and distinguish it from other components; Propositions 3.30, 4.13, 4.16, and 4.18 handle the Jordan-centrality step. I checked the places where a hidden assumption could enter—off-by-one accounting in the operator μ, coupling of G-neighborhoods on D_{T_n}(α+δ), and exponent bookkeeping in Propositions 3.24 and 3.30—and found them consistent. The paper also gives credit to the noiseless base result [12] and presents the extension to matching noise. The main weaknesses are local: several auxiliary lemmas are stated without proof, and the advertised O(log(1/ε)/ε) rate is not actually derived. These do not undermine the existence theorem.","major_comments":[],"minor_comments":[{"comment":"The abstract and Theorem statements only claim a finite K(ε) with size independent of n, but the introduction and Remarks 1.5 and 1.9 claim the stronger quantitative bound |K|=O(log(1/ε)/ε). I could not find this rate derived anywhere. The proofs of Theorem 3.26 and Proposition 4.18 use weak convergence to a Dirichlet vector and then choose M=M(ε) large enough; this gives existence, not the stated rate. The cited noiseless bound from [12] does not directly apply to the random component C_α(1). Please either supply the rate calculation or soften the claim to 'finite, depending only on ε'.","section":"§1, Remarks 1.5 and 1.9"},{"comment":"Lemma 2.12 (conditionally independent subtrees) is stated without proof and is used in the proof of Proposition 2.11, a central exchangeability tool. The statement is standard for random recursive trees, but because the exchangeability machinery is load-bearing for the whole paper, a proof or a precise reference should be included.","section":"§2.2, Lemma 2.12"},{"comment":"Lemma 4.2 is asserted with 'straightforward proof omitted', but it underpins Proposition 4.1 and hence the filtering step for Theorem 1.7. The proof is an elementary union bound, but it should be written out or explicitly referenced, since without it the key claim that noise edges do not survive among high-degree vertices is unsupported.","section":"§4.1, Lemma 4.2"},{"comment":"Theorem 1.8 reduces the matching-noise problem to the noiseless α-forest entirely through Proposition 5.1, whose proof is omitted ('may be easily proved'). This proposition is load-bearing for the matching theorem; the proof should be supplied (the high-degree set has size n^{o(1)} on the relevant scale, making matching edges inside it unlikely).","section":"§5, Proposition 5.1"},{"comment":"In the final display of the proof, the exponent of n in the first error term appears to be -γ+2ε+6δ+2δ', not -γ−2ε+6δ+2δ'. The sign of the ε term should be corrected. The conclusion still holds when ε,δ,δ' are taken sufficiently small, so this is a local typo, but it should be fixed.","section":"§4.2, proof of Proposition 4.16"},{"comment":"The notation F_n(α) is used both for the degree-based α-forest (Definition 1.2) and again for the offspring-based α-offspring forest (Definition 3.1). This is confusing, especially in Lemma 3.3 and the surrounding text. Please use distinct notation, e.g., F_n(α) and F_n^off(α).","section":"§3.1, Definitions 1.2 and 3.1"},{"comment":"The abstract says the approach works in 'other noise models as well'. The only other model proved formally is random perfect matching noise. The random regular graph extension in §6.3 is informal and is not stated as a theorem; I suggest softening the abstract or promoting the regular-graph claim to a clearly stated conditional result.","section":"§6.3"}],"recommendation":"minor_revision","confidential_remarks":"I am fairly confident the central theorem is correct: the reduction chain is coherent and I found no internal inconsistency. The issues are local—unproved auxiliary lemmas, a notational clash, and an unsupported O(log(1/ε)/ε) rate claim. If the authors supply the small missing arguments and adjust the quantitative claims, I would support acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague — this paper is the real thing. It proves the open conjecture that, when p=o(log n/n), you can build a root confidence set of size depending only on ε for a uniform random recursive tree observed with Erdős–Rényi noise. I read the main reduction chain carefully and did not find a load-bearing gap. The sandwiching of the noisy high-degree subgraph between α-forests, the identification of the root component by size, and the Jordan-centrality argument on that component all cohere. The extension to random matching noise is a genuine bonus, and the informal treatment of d_n-regular noise in Section 6 looks sensible.\n\nWhat is actually new: previous work only gave n^γ-sized sets for p<log n/n, and the o(log n/n) question was open. The degree-threshold-plus-Jordan-centrality reduction is a clean idea that should be reusable. The noiseless bound is imported from Bubeck–Devroye–Lugosi, which is published and independent, so I see no circularity.\n\nThe soft spots are real but presentation-level. The abstract and Remark 1.5 claim the explicit K(ε)=O(log(1/ε)/ε) bound, and Remark 1.9 repeats it, but the proofs as written establish only the existence of a finite K(ε) with no derived rate. That mismatch should be fixed — either derive the rate or state the theorem as an existence result. Several supporting lemmas that carry weight have proofs omitted (Lemma 2.12, Lemma 4.2, Proposition 5.1); for a paper this technical, those omissions are worth filling. The conjecture attribution also shifts between the abstract and the body (Crane–Xu 2021 vs 2023). These are all addressable.\n\nWhere the condition λ_n=o(log n) is used is made explicit in Section 6.1, which I appreciate; it is exactly where the maximum noise degree starts competing with the tree degrees. That is an honest statement of the method's limit.\n\nThis paper belongs in the network-archaeology conversation and deserves a serious referee. I would send it out, with the rate-claim caveat flagged for the authors to resolve before acceptance.","headline":"Solid proof of the Crane–Xu conjecture for bounded confidence sets in uniform attachment trees with sparse Erdős–Rényi noise; presentation gaps, not proof gaps, keep it from being cleanly acceptable as-is.","tokens_in":45770,"tokens_out":1684,"would_cite":true,"duration_ms":31890,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","60C05","62F99"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that the root of a uniform random recursive tree can be enclosed in a confidence set of size depending only on the error tolerance, even when the tree is corrupted by sparse Erdős–Rényi edges.","keywords":["random recursive trees","root finding","network archaeology","Erdős–Rényi noise","Jordan centrality","confidence sets","uniform attachment","robust inference"],"falsifier":"Simulate a urrt of size n = 10^6 with added Erdős–Rényi noise of p = 2 log n / n; for alpha = 0.5, compute the largest component of the subgraph induced by vertices of degree above (1-alpha) log n. If vertex 1 is not in that largest component in a non-negligible fraction of runs, the sandwiching step fails for this p. A sharper test: prove that for p = c log n / n with c > 1, any confidence set for the root must have size tending to infinity with n.","tokens_in":44804,"feed_emoji":"🌳","tokens_out":4608,"duration_ms":46974,"temperature":0.7,"pith_summary":"The paper proves that the origin of a uniform random recursive tree can still be identified up to a constant-size set of candidates even when the observed graph is the tree plus a sparse independent random noise graph: as long as the noise has mean degree o(log n), for any error tolerance epsilon there is a confidence set of O(log(1/epsilon)/epsilon) vertices that contains the root with probability at least 1-epsilon. This settles a conjecture from the network-archaeology literature. The method is to discard all vertices of degree below a threshold, show that the surviving high-degree subgraph is a forest whose largest component is the root component, and then rank vertices in that component by Jordan centrality. The same strategy succeeds for noise given by a random perfect matching and, informally, for random regular graphs of degree o(log n).","feed_headline":"Root of noisy tree found with constant-size confidence set","feed_subtitle":"Sparse noise up to o(log n/n) cannot hide Adam in uniform recursive trees","key_machinery":"The driving device is the 'high-degree forest sandwich.' The noisy graph's subgraph H_n(alpha) of edges whose endpoints both have degree above (1-alpha) log n satisfies F_n(alpha) subset H_n(alpha) subset F_n(alpha+delta) with high probability, where F_n(alpha) is the forest obtained from the clean tree by cutting all edges incident to a vertex of degree at most (1-alpha) log n. This ensures H_n(alpha) is a forest, its largest component is the root component, and the root component can be analyzed as a pruned uniform random recursive tree. Exchangeability of subtree functionals (a Pólya-urn-like property) then transfers the known Jordan-centrality bounds for clean urrts to the pruned compone","core_discovery":"The central claim is that the root component of a uniform random recursive tree is recognizable and self-similar in the presence of o(log n)-average-degree noise. For any fixed alpha below 1 - (1/2)log 2, the subgraph induced by vertices with degree at least (1-alpha) log n is with high probability a forest; its component containing vertex 1 is the unique component of size at least n^{alpha - gamma/4} (where gamma = gamma(alpha) is defined by a rate-function zero), and it contains the initial segment {1,...,n^{gamma-epsilon}}. Inside this component, the sizes of branches hanging off the first M vertices concentrate around their conditional means, so the M vertices with smallest Jordan centra","pith_inferences":["If the threshold is sharp, then for noise of constant multiple of log n/n the root is information-theoretically confounded; a lower-bound proof would likely require coupling two urrts with swapped first two vertices that are indistinguishable under the noise.","The sandwiching-plus-exchangeability recipe may extend to other growing-tree models (e.g., preferential attachment with bounded degree variance) as long as a high-degree forest with a unique giant root component can be constructed.","Swapping Jordan centrality for rumor centrality within the same framework may shrink the confidence set to exp(O(sqrt(log(1/epsilon)))), matching the best noiseless rates.","Practically, the theorem implies that in networks generated by uniform attachment with spurious edges from measurement error, one can pinpoint the seed with a fixed-size suspect list regardless of network size, so long as the average number of spurious edges per vertex grows slower than log n."],"forward_implications":["For any epsilon > 0, a confidence set of size O(log(1/epsilon)/epsilon) containing the root exists under Erdős–Rényi noise with p = o(log n/n), resolving a previously open conjecture.","The result is robust: the same construction works when the noise is a random perfect matching and extends to d_n-regular noise with d_n = o(log n).","The proof yields an explicit algorithm: threshold degrees, take the largest component of the high-degree subgraph, and return the most central vertices by Jordan centrality.","The paper identifies p = o(log n/n) as a sufficient condition and leaves open whether the exact threshold for feasibility lies elsewhere."],"fun_headline_variants":["Constant-size set finds root in noisy random trees","Sparse noise can't hide Adam: root found with fixed-size set","Jordan centrality beats o(log n/n) noise to locate tree root","Tree root recovered despite sparse Erdős–Rényi noise","Fixed-size confidence set identifies root in attachment trees"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The argument's load-bearing step is that all early vertices up to index n^{gamma-epsilon} have degree above (1-alpha) log n with high probability (Lemma 2.5); if that failed, the root component would not contain a recognizable urrt chunk, and size-based identification and Jordan-centrality ranking would both break.","fun_headline_variants_meta":{"raw":{"variants":["Constant-size set finds root in noisy random trees","Sparse noise can't hide Adam: root found with fixed-size set","Jordan centrality beats o(log n/n) noise to locate tree root","Tree root recovered despite sparse Erdős–Rényi noise","Fixed-size confidence set identifies root in attachment trees"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00017,"raw_usage":{"total_tokens":1064,"prompt_tokens":660,"completion_tokens":404,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":404,"completion_tokens_details":{"reasoning_tokens":321}},"tokens_in":404,"tokens_out":404,"duration_ms":5205,"temperature":1.0,"reasoning_tokens":321,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T15:42:23.551915+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate a urrt of size n = 10^6 with added Erdős–Rényi noise of p = 2 log n / n; for alpha = 0.5, compute the largest component of the subgraph induced by vertices of degree above (1-alpha) log n. If vertex 1 is not in that largest component in a non-negligible fraction of runs, the sandwiching step fails for this p. A sharper test: prove that for p = c log n / n with c > 1, any confidence set for the root must have size tending to infinity with n.","supporting_citations":[],"review_version":1}