Asymptotics of trees with a prescribed degree sequence and applications

Abstract

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\ge 0)$ of $t$ satisfies ${\sum }_{i\ge 0}{n}_i(t)=1+{\sum }_{i\ge 0}i{n}_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 $\ds$; we write $`P_\ds$ for the corresponding distribution. Let $\ds(κ)=(n_i(κ),i\geq 0)$ be a list of degree sequences indexed by $\kappa$ corresponding to trees with size $\nk\to+\infty$. We show that under some simple and natural hypotheses on $(\ds(κ),κ>0)$ the trees sampled under $`P_{\ds(κ)}$ converge to the Brownian continuum random tree after normalisation by $\nk^{1/2}$. Some applications concerning Galton--Watson trees and coalescence processes are provided.

References in corpus (1)

• Tail bounds for the height and width of a random tree with a given degree sequence