Asymptotics of trees with a prescribed degree sequence

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\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 $\mathbf s$; we write $\mathbb P_{\bf s}$ for the corresponding distribution. Let $\mathbf s(\kappa)=(n_i(\kappa),i\geq 0)$ be a list of degree sequences indexed by $\kappa$ corresponding to trees with size ${\sf n}_\kappa\to+\infty$. We show that under some simple and natural hypotheses on $(\mathbf s(\kappa),\kappa>0)$ the trees sampled under $\mathbb P_{\mathbf s(\kappa)}$ converge to the Brownian continuum random tree after normalisation by $\sqrt{{\sf n}_\kappa}$. Some applications concerning Galton--Watson trees and coalescence processes are provided.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/hal-01220797
Contributor : Nicolas Broutin <>
Submitted on : Tuesday, October 27, 2015 - 12:44:48 AM
Last modification on : Friday, May 25, 2018 - 12:02:03 PM

Links full text

Identifiers

Collections

Citation

Nicolas Broutin, Jean-François Marckert. Asymptotics of trees with a prescribed degree sequence. Random Structures and Algorithms, Wiley, 2014, 44, pp.290-316. ⟨10.1002/rsa.20463⟩. ⟨hal-01220797⟩

Share

Metrics

Record views

350