Id: arxiv/2607.18201 Url: https://arxiv.org/abs/2607.18201 Tags: math.PR Score: 0 Title: Finding Adam in noisy trees Domain: math.PR Source: arxiv Authors: Luc Devroye, Gábor Lugosi, Neeladri Maitra Reviews: 0 Subject: math.PR Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-20 Page: https://delphi.science/r/arxiv/2607.18201 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ős-Rényi 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…