2026/07/20 by Luc Devroye, Gábor Lugosi, Neeladri Maitra · 1 citation
Mathematics · #math.PR
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 \mathbbG(n,p) is observed. We prove that, as long as p=o(log n /n), for any ε>0, one can construct a confidence set of vertices of size K(ε) that depends only on ε and not on n, such that it contains the root with probability at least 1-ε. 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.