Asymptotics of trees with a prescribed degree sequence and applications

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 $\ds$; we write $`P_\ds$ for the corresponding distribution. Let $\ds(κ)=(n_i(κ),i\geq 0)$ be a list of degree sequences indexed by $κ$ 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.

No reviews yet.

No comments yet.