Asymptotics of trees with a prescribed degree sequence and applications. Issue 3 (5th September 2012) - Broutin, Nicolas
Abstract Let t be a rooted tree and nbi(t) the number of nodes in t having i children. The degree sequence (ni(t), i≥0) of t satisfies ∑i≥0ni(t)=1+∑i≥0ini(t)=|t|, where |t| denotes the number of nodes in t. In this paper, we consider trees sampled uniformly among all plane trees having the same degree sequence s; we write ℙs for the corresponding distribution. Let s(κ)=(ni(κ), i≥0) be a list of degree sequences indexed by κ corresponding to trees with size nκ→+∞. We show that under some simple and natural hypotheses on (s(κ), κ>0) the trees sampled under ℙs(κ) converge to the Brownian continuum random tree after normalisation by nκ1/2. Some applications concerning Galton–Watson trees and coalescence processes are provided.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 290‐316, 2014