For $n\ge 1$, let $T_n$ be a random recursive tree on the vertex set $[n]=\{ 1,\ldots,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.
Categories: math.CO math.PR