Asymptotics of trees with a prescribed degree sequence and applications. Issue 3 (5th September 2012)

• Record Type: Journal Article
• Authors: Broutin, Nicolas; Marckert, Jean‐François
• Is Part Of: Random structures & algorithms. Volume 44:Issue 3(2014)
• Page Start: 290
• Page End: 316
• Publication Date: 2012-09-05
• Subjects: continuum random tree -- Brownian excursion -- real tree -- invariance principle -- coalescence; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20463
• Languages: English
• ISSNs: 1042-9832

Abstract

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