Asymptotics of trees with a prescribed degree sequence and applications. Issue 3 (5th September 2012) - Broutin, Nicolas; Marckert, Jean‐François
Abstract: Let t be a rooted tree and n bi ( t ) the number of nodes in t having i children. The degree sequence ( n i ( t ), i ≥ 0 ) of t satisfies ∑ i ≥ 0 n i ( t ) = 1 + ∑ i ≥ 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 plane trees having the same degree sequence s ; we write ℙ s for the corresponding distribution. Let s ( κ ) = ( n i ( κ ), 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