Depth of vertices with high degree in random recursive trees

Abstract

Let $T_n$ be a random recursive tree with $n$ nodes. List vertices of $T_n$ in decreasing order of degree as $v^1,\dots ,v^n$, and write $d^i$ and $h^i$ for the degree of $v^i$ and the distance of $v^i$ from the root, respectively. We prove that, as $n\to \infty$ along suitable subsequences, \[ \bigg(d^i - \lfloor \log_2 n \rfloor, \frac{h^i - μ\ln n}{\sqrt{σ^2\ln n}}\bigg) \to ((P_i,i \ge 1),(N_i,i \ge 1))\, , \] where $\mu =1-({\log }_{2}e)/2$, ${\sigma }^2=1-({\log }_{2}e)/4$, $(P_i,i\ge 1)$ is a Poisson point process on $\mathbb{Z}$ and $(N_i,i\ge 1)$ is a vector of independent standard Gaussians. We additionally establish joint normality for the depths of uniformly random vertices in $T_n$, which extends results for the case of a single random vertex. The joint limit holds even if the random vertices are conditioned to have large degree, provided the normalizing constants are adjusted accordingly; however, both the mean and variance of the conditinal depths remain of orden $\ln n$. Our results are based on a simple relationship between random recursive trees and Kingman's $n$-coalescent; a utility that seems to have been largely overlooked.

arXiv comment19 pages, 2 figures