Depth of vertices with high degree in random recursive trees

Let Tn be a random recursive tree with n nodes. List vertices of Tn in decreasing order of degree as v1,ldots,vn, and write di and hi for the degree of vi and the distance of vi from the root, respectively. We prove that, as n → ∞ along suitable subsequences, [ bigg(di - lfloor log2 n rfloor, frachi - μln n√σ2ln nbigg) → ((Pi,i ≥ 1),(Ni,i ≥ 1)), , ] where μ=1-(log2 e)/2, σ2=1-(log2 e)/4, (Pi,i ≥ 1) is a Poisson point process on mathbbZ and (Ni,i ≥ 1) is a vector of independent standard Gaussians. We additionally establish joint normality for the depths of uniformly random vertices in Tn, 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.