{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-20","reactions":{}}