High degrees of random recursive trees

Abstract

For $n\ge 1$, let $T_n$ be a random recursive tree on the vertex set $[n]=\{1,\dots ,n\}$. Let ${\mathrm{deg}}_{T_n}(v)$ be the degree of vertex $v$ in $T_n$, that is, the number of children of $v$ in $T_n$. Devroye and Lu showed that the maximum degree ${\Delta }_n$ of $T_n$ satisfies ${\Delta }_n/\lfloor {\log }_{2}n\rfloor \to 1$ almost surely; Goh and Schmutz showed distributional convergence of ${\Delta }_n-\lfloor {\log }_{2}n\rfloor$ 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 $T_n$. For any $i\in \mathbb{Z}$, let $X_i^{(n)}=|\{v\in [n]:{\mathrm{deg}}_{T_n}(v)=\lfloor \log n\rfloor +i\}|$. Also, let $\mathcal{P}$ be a Poisson point process on $\mathbb{R}$ with rate function $\lambda (x)=2^{-x}\cdot \ln 2$. We show that, up to lattice effects, the vectors $(X_i^{(n)},i\in \mathbb{Z})$ converge weakly in distribution to $(\mathcal{P}[i,i+1),i\in \mathbb{Z})$. We also prove asymptotic normality of $X_i^{(n)}$ when $i=i(n)\to -\infty$ slowly, and obtain precise asymptotics for $\mathbb{P}({\Delta }_n-{\log }_{2}n>i)$ when $i(n)\to \infty$ and $i(n)/\log n$ is not too large. Our results recover and extends the previous results on maximal and near-maximal degrees in random recursive trees.

15 pages, 3 figures. Revised proof of Proposition 4.5, results unchanged

References in corpus (1)

• Recent progress in coalescent theory

Cited by in corpus (4)

• Fine asymptotics for the maximum degree in weighted recursive trees with bounded random weights
• A non-increasing tree growth process for recursive trees and applications
• The location of high-degree vertices in weighted recursive graphs with bounded random weights
• Root and community inference on the latent growth process of a network