High degrees in random recursive trees. Issue 4 (26th December 2017) - Addario‐Berry, Louigi; Eslava, Laura
Abstract: For n ≥ 1, let Tn be a random recursive tree (RRT) on the vertex set [ n ] = 1, …, n . Let deg ⁡ T n ( v ) be the degree of vertex v in Tn, that is, the number of children of v in Tn . Devroye and Lu showed that the maximum degree Δ n of Tn satisfies Δ n / ⌊ log ⁡ 2 n ⌋ → 1 almost surely; Goh and Schmutz showed distributional convergence of Δ n − ⌊ log ⁡ 2 n ⌋ along suitable subsequences. In this work we show how a version of Kingman's coalescent can be used to access much finer properties of the degree distribution in Tn . For any i ∈ ℤ, let X i ( n ) = | v ∈ [ n ] : deg ⁡ T n ( v ) = ⌊ log ⁡ n ⌋ + i | . Also, let P be a Poisson point process on ℝ with rate function λ ( x ) = 2 − x · ln ⁡ 2 . We show that, up to lattice effects, the vectors ( X i ( n ), i ∈ ℤ ) converge weakly in distribution to ( P [ i, i + 1 ), i ∈ ℤ ) . We also prove asymptotic normality of X i ( n ) when i = i ( n ) → − ∞ slowly, and obtain precise asymptotics for P ( Δ n − log ⁡ 2 n > i ) when i ( n ) → ∞ and i ( n ) / log ⁡ n is not too large. Our results recover and extends the previous distributional convergence results on maximal and near‐maximal degrees in RRT.