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.
Type de document :
Article dans une revue
Random Structures and Algorithms, Wiley, 2014, 44, pp.290-316. 〈10.1002/rsa.20463〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01220797
Contributeur : Nicolas Broutin <>
Soumis le : mardi 27 octobre 2015 - 00:44:48
Dernière modification le : vendredi 25 mai 2018 - 12:02:03

Lien texte intégral

Identifiants

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〉

Partager

Métriques

Consultations de la notice

252