Pith. sign in

REVIEW 7 minor 1 cited by

Finding Adam in noisy trees

T0 review · 0 major / 7 minor · reviewed 2026-08-01 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2607.18201 v1 pith:N3ZKLAIM submitted 2026-07-20 math.PR

Luc Devroye , Gábor Lugosi , Neeladri Maitra This is my paper · ORCID
classification math.PR MSC 05C8060C0562F99
keywords randomrecursivetreesrootfindingnetworkarchaeologyErdős–RényinoiseJordancentralityconfidencesetsuniformattachmentrobustinference
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

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).

What carries the argument

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

What would settle it

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.

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 7 minor

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.

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.

minor comments (7)
  1. [§1, Remarks 1.5 and 1.9] 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 ε'.
  2. [§2.2, Lemma 2.12] 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.
  3. [§4.1, Lemma 4.2] 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.
  4. [§5, Proposition 5.1] 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).
  5. [§4.2, proof of Proposition 4.16] 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.
  6. [§3.1, Definitions 1.2 and 3.1] 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(α).
  7. [§6.3] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the noisy root-finding result is reduced to independent noiseless forest/Jordan-centrality arguments with no fitted parameters and no self-citation chain carrying the proof.

full rationale

The paper proves the Crane–Xu conjecture by a reduction chain: Lemma 2.5/Corollary 3.23 show the early URRT chunk lies in the root component; Propositions 3.11, 3.21, 3.24 and Lemma 3.25 identify the root component by size; Theorem 3.26 then shows that ranking by Jordan centrality in that component yields a bounded confidence set. The noisy case (Theorem 1.7) is handled by filtering high-degree vertices (Proposition 4.1, Lemma 4.4), a coupling/sandwich reduction to the forest H^(3)_n (Propositions 4.10 and 4.13), and a Jordan-centrality argument (Propositions 4.16 and 4.18) that mirrors the noiseless case. No parameter is fitted to data or to the target event; the constants α, δ, ε, γ and M are free algorithmic choices. The only self-citations are to Bubeck–Devroye–Lugosi [12] and Coll Josifov–Devroye–Lugosi [15] for the noiseless Jordan-centrality benchmark. These are published, parameter-free, externally falsifiable results, and the proof in this paper does not rely on a uniqueness theorem or an unverified self-citation; the Jordan-centrality step is re-derived via exchangeability and the Dirichlet limit. No 'prediction' is equivalent to an input by construction: the target confidence-set property is never assumed in the proof. I therefore find no circular step and assign score 0.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

No fitted constants or invented physical/mathematical entities are added. The only hand-chosen quantity is the pruning threshold α, which is universal over its stated range. Several auxiliary structural facts (Lemma 2.12, Lemma 4.2, Proposition 5.1) are stated with proofs omitted and are treated as domain assumptions here.

free parameters (1)
  • α (degree-threshold exponent)
    The algorithms prune at degree >(1−α)log n. The theorems hold for every α in (0,1) (and α<1−1/(2log2) for the noise results), so no value is fitted to data; but the construction and proof constants depend on α.
assumptions (5)
  • standard math Standard probabilistic tools: Chernoff bounds, Latała's moment inequality, Wald's identity, Hölder/Markov inequalities, Gamma-function bounds, Riemann-sum approximations, Pólya-urn/Dirichlet limits.
    Invoked throughout Sections 2–4; they are background results, not part of the claim.
  • domain assumption Model definitions: the uniform random recursive tree and independence of the noise graph G from T_n (Definition 1.1, Section 1.1).
    The theorems are stated for this model; no empirical justification is provided, which is normal for a math paper.
  • domain assumption Lemma 2.12 (conditionally independent subtrees given sizes) is taken as given with proof omitted and underpins the exchangeability Proposition 2.11.
    Stated as a 'straightforward consequence' of the construction in Section 2.3; it is load-bearing for all later exchangeability arguments.
  • standard math Maximum degree of G(n,λ/n) is o(log n) when λ=o(log n) (Bollobás [9]), and maximum degree of a random d_n-regular graph is o(log n) when d_n=o(log n).
    Used in Lemma 4.4 and Section 6.3 to guarantee the noise graph cannot pass the high-degree filter.
  • domain assumption Lemma 4.2 and Proposition 5.1 assert that the high-degree vertex set is small enough that no ER/matching edge joins two high-degree vertices; proofs are sketched or omitted.
    These are structural facts about the urrt degree distribution coupled with sparse noise; if false, the filter would retain noise edges.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Finding Adam in noisy trees." pith.science (2026). https://pith.science/paper/N3ZKLAIM

@misc{pith2026260718201,
  author       = {Pith},
  title        = {Pith review of: Finding Adam in noisy trees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/N3ZKLAIM}},
  note         = {Machine review of arXiv:2607.18201}
}
abstract

We consider the problem of finding the root vertex of a random uniform attachment tree, when the union of the unlabeled tree and an Erd\H{o}s-R\'enyi random graph $\mathbb{G}(n,p)$ is observed. We prove that, as long as $p=o(\log n /n)$, for any $\varepsilon>0$, one can construct a confidence set of vertices of size $K(\varepsilon)$ that depends only on $\varepsilon$ and not on $n$, such that it contains the root with probability at least $1-\varepsilon$. This affirms a conjecture of Crane and Xu (2021). Our approach ranks vertices by their Jordan centrality in the largest component of the subgraph spanned by high-degree vertices. We show that the same approach works in other noise models as well.

Figures

Figures reproduced from arXiv: 2607.18201 by the authors.

Figure 1
Figure 1. The problem of root finding with Erdős-Rényi noise. Upon observing the graph at the [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. The problem of root finding with an added perfect matching. [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. The function gα(x) = x + fα(x) versus x ∈ [0, 1) is shown in red, while fα(x) is drawn in black. The parameter γ = γ(α) is the leftmost point x with gα(x) = 0. Lemma 2.4. For all α ∈ (0, 1), gα(x) = x + fα(x) is a continuous strictly concave function on [0, 1), attaining a unique maximum value of 1 − (1 − α) log 2 at (1 + α)/2. The unique solution on [0,(1 + α)/2] of gα(x) = 0, denoted by γ(α), satisfies γ(α) < α/2.… view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: A rooted tree (t, o) with the operators χ>5 and ψ 5 off applied to it. The red vertices are the vertices other than the root that have at least 5 offspring. Note that the edges of ψ 5 off(t, o) form a subset of the edges of χ>5(t, o). Remark 3.9. The edge set of ψ r of…
Figure 5
Figure 5. Figure 5: Tn is the graph on the left and Cα(1) ∩ [bn α1 c] is on the right. The orange vertices have several offspring > (1 − α) log n (= 5, say, for this illustrative example) in Tn. The green vertices have label > bn α1 c, so are not part of Cα(1) ∩ [bn α1 c]. The red vertice…
Figure 6
Figure 6. Figure 6: Grafting, from top to bottom: the black subtree is [PITH_FULL_IMAGE:figures/full_fig_p047_6.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Subcritical percolation and network archaeology on random recursive tree substrate networks

    math.PR 2026-07 accept novelty 5.0 of 10

    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.

Reference graph

Works this paper leans on

30 extracted references · 2 canonical work pages · cited by 1 Pith paper

  1. [12]

    Bubeck, L

    S. Bubeck, L. Devroye, and G. Lugosi. Finding Adam in random growing trees. Random Structures & Algorithms , 50(2):158–172, 2017

    2017

  2. [1]

    Addario-Berry and L

    L. Addario-Berry and L. Eslava. High degrees in random recursive trees. Random Structures & Algorithms , 52(4):560–575, 2018

    2018

  3. [2]

    Addario-Berry, L

    L. Addario-Berry, L. Devroye, G. Lugosi, and V. Velona. Broadcasting on random recursive trees. Annals of Applied Probability , 32(1):497–528, 2022

    2022

  4. [3]

    Addario-Berry, C

    L. Addario-Berry, C. Fontaine, R. Khanfir, L.-R. Langevin, and S. Têtu. Optimal root recovery for uniform attachment trees and d-regular growing trees. arXiv preprint arXiv:2411.18614 , 2024

    arXiv 2024

  5. [4]

    Addario-Berry, A

    L. Addario-Berry, A. Brandenberger, S. Briend, N. Broutin, and G. Lugosi. Leaf strip- ping on uniform attachment trees. Random Structures & Algorithms , 67(1):e70023, 2025. doi:https://doi.org/10.1002/rsa.70023

    work page doi:10.1002/rsa.70023 2025

  6. [5]

    D. J. Aldous. Exchangeability and related topics. In École d’Été de Probabilités de Saint-Flour XIII1983, pages 1–198. Springer, 2006. 54

    2006

  7. [6]

    Banerjee and S

    S. Banerjee and S. Bhamidi. Root finding algorithms and persistence of Jordan centrality in growing random trees. The Annals of Applied Probability , 32(3):2180–2210, 2022

    2022

  8. [7]

    Banerjee and X

    S. Banerjee and X. Huang. Degree centrality and root finding in growing random networks. Electronic Journal of Probability , 28:1–39, 2023

    2023

Show all 30 references
  1. [8]

    Biau and L

    G. Biau and L. Devroye. Lectures on the Nearest Neighbor Method . Springer, 2015

    2015

  2. [9]

    Bollobás

    B. Bollobás. Modern Graph Theory . Springer, 2011

    2011

  3. [10]

    Briend, C

    S. Briend, C. Giraud, G. Lugosi, and D. Sulem. Estimating the history of a random recursive tree. Bernoulli, 31(4):3260–3284, 2025

    2025

  4. [11]

    Bubeck, E

    S. Bubeck, E. Mossel, and M. Rácz. On the influence of the seed graph in the preferential attachment model. IEEE Transactions on Network Science and Engineering , 2(1):30–39, 2015

    2015

  5. [13]

    Bubeck, R

    S. Bubeck, R. Eldan, E. Mossel, and M. Rácz. From trees to seeds: on the inference of the seed from large trees in the uniform attachment model. Bernoulli, 23(4A):2887–2916, 2017

    2017

  6. [14]

    Bäumler, S

    J. Bäumler, S. Briend, and J. Jorritsma. History estimation in random recursive trees: Pointwise approach via iterated Jordan centralities. arXiv preprint arXiv:2606.24465 , 2026

    2026 arXiv

  7. [15]

    Coll Josifov, L

    R. Coll Josifov, L. Devroye, and G. Lugosi. A study of centrality measures in random recursive trees. arXiv preprint arXiv:2603.19493 , 2026

    2026

  8. [16]

    Contat, N

    A. Contat, N. Curien, P. Lacroix, E. Lasalle, and V. Rivoirard. Eve, Adam and the preferential attachment tree. Probability Theory and Related Fields , 190:321–336, 2024

    2024

  9. [17]

    Crane and M

    H. Crane and M. Xu. Inference on the history of a randomly growing tree. Journal of the Royal Statistical Society: Series B (Statistical Methodology) , 83(4):639–668, 2021

    2021

  10. [18]

    Crane and M

    H. Crane and M. Xu. Root and community inference on latent network growth processes using noisy attachment models. Journal of the Royal Statistical Society Series B: Statistical Methodology, page qkad102, 2023

    2023

  11. [19]

    Curien, T

    N. Curien, T. Duquesne, I. Kortchemski, and I. Manolescu. Scaling limits and influence of the seed graph in preferential attachment trees. Journal de l’École Polytechnique–Mathématiques , 2:1–34, 2015

    2015

  12. [20]

    Devroye and J

    L. Devroye and J. Lu. The strong convergence of maximal degrees in uniform random recursive trees and dags. Random Structures & Algorithms , 7(1):1–14, 1995

    1995

  13. [21]

    Devroye and T

    L. Devroye and T. Reddad. On the discovery of the seed in uniform attachment trees. Internet Mathematics, pages 75–93, 2019. doi: https://doi.org/10.24166/im.02.2019. 55

    2019 doi

  14. [22]

    L. Eslava. Depth of vertices with high degree in random recursive trees. ALEA, Latin American Journal of Probability and Mathematical Statistics , 19(1):839–857, 2022

    2022

  15. [23]

    J. Haigh. The recovery of the root of a tree. Journal of Applied Probability , 7(1):79–88, 1970

    1970

  16. [24]

    Jog and P.-L

    V. Jog and P.-L. Loh. Analysis of centrality in sublinear preferential attachment trees via the crump-mode-jagers branching process. IEEE Transactions on Network Science and Engineering , 4(1):1–12, 2016

    2016

  17. [25]

    Jog and P.-L

    V. Jog and P.-L. Loh. Persistence of centrality in random growing trees. Random Structures and Algorithms , 52(1):136–157, 2018

    2018

  18. [26]

    Khim and P.-L

    J. Khim and P.-L. Loh. Confidence sets for the source of a diffusion in regular trees. IEEE Transactions on Network Science and Engineering , 4(1):27–40, 2016

    2016

  19. [27]

    R. Latała. Estimation of moments of sums of independent real random variables. The Annals of Probability, 25(3):1502–1513, 1997

    1997

  20. [28]

    Lugosi and A

    G. Lugosi and A. S. Pereira. Finding the seed of uniform attachment trees. Electronic Journal of Probability, 24:1–15, 2019

    2019

  21. [29]

    Shah and T

    D. Shah and T. Zaman. Finding rumor sources on random trees. Operations Research, 64(3): 736–755, 2016

    2016

  22. [30]

    Shah and T

    D. Shah and T. R. Zaman. Rumors in a network: Who’s the culprit? IEEE Transactions on Information Theory , 57(8):5163–5181, 2011. 56

    2011

Pith tools

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