Root finding algorithms and persistence of Jordan centrality in growing random trees (Q2170374)

Sequences of random trees are grown recursively, starting from the unique tree \(\mathcal{T}_f(1)\) of size \(1\), using the following procedure: define \(\mathcal{T}_f(n+1)\) by attaching a new vertex to a random vertex \(v\) of \(\mathcal{T}_f(n)\) chosen with a probability proportional to \(f(d_v)\), where \(d_v\) is the degree of \(v\) and \(f\) is a positive function on the integers. Given a tree \(\mathfrak{t}\) and an integer \(K\), the root-finding algorithm analyzed in the article outputs the \(K\) vertices \(v\) with the lowest Jordan centrality, which is defined as the maximal size of a connected component in the graph \(\mathfrak{t}\setminus\{v\}\). Under some natural assumptions on \(f\), the authors manage to (a) obtain fine bounds on \(K_\varepsilon\), the minimal number \(K\) such that the root of \(\mathcal{T}_f(n)\) is among the \(K\) vertices output by the algorithm with probability at least \(1-\varepsilon\) as \(n\to\infty\); (b) show that for all \(K\), there almost surely exists a rank \(n\) such that the output of the algorithm is the same for any tree \(\mathcal{T}_f(m)\), for all \(m\geq n\) -- a property called persistence. The results are obtained in great generality as they extend and substantially improve previous results in the more restrictive settings of uniform attachment trees, (affine) preferential attachment trees, and sublinear attachment trees. The methods used are original since they rely on a natural link between sequences of growing trees and particular Crump-Mode-Jagers processes (CMJ, i.e. general continuous-time branching processes). Estimates on the rate of convergence of a rescaled CMJ process to its limiting random variable and studying the tail of this limiting random variable are keys to the analysis; furthermore, these results are themselves interesting advances in the field of continuous-time branching processes.