Asymptotics of trees with a prescribed degree sequence
Résumé
Let $t$ be a rooted tree and $n_i(t)$ the number of nodes in $t$ having $i$ children. The degree sequence $(n_i(t),i\geq 0)$ of $t$ satisfies $\sum_{i\ge 0} n_i(t)=1+\sum_{i\ge 0} in_i(t)=|t| $, where $|t|$ denotes the number of nodes in $t$. In this paper, we consider trees sampled uniformly among all trees having the same degree sequence $\mathbf s$; we write $\mathbb P_{\bf s}$ for the corresponding distribution. Let $\mathbf s(\kappa)=(n_i(\kappa),i\geq 0)$ be a list of degree sequences indexed by $\kappa$ corresponding to trees with size ${\sf n}_\kappa\to+\infty$. We show that under some simple and natural hypotheses on $(\mathbf s(\kappa),\kappa>0)$ the trees sampled under $\mathbb P_{\mathbf s(\kappa)}$ converge to the Brownian continuum random tree after normalisation by $\sqrt{{\sf n}_\kappa}$. Some applications concerning Galton--Watson trees and coalescence processes are provided.