On the profile of trees with a given degree sequence

Abstract

A degree sequence is a sequence $\mathbf{s}=(N_i,i\ge 0)$ of non-negative integers satisfying $1+{\sum }_{i}i{N}_i={\sum }_i{N}_i<\infty$. We are interested in the uniform distribution ${\mathbb{P}}_{\mathbf{s}}$ on rooted plane trees whose degree sequence equals $\mathbf{s}$, giving conditions for the convergence of the profile (sequence of generation sizes) as the size of the tree goes to infinity. This provides a more general formulation and a probabilistic proof of a conjecture due to Aldous (1991). Our formulation contains and extends results in this direction obtained previously by Drmota and Gittenberger (1997) and Kersting (2011). A technical result is needed to ensure that trees with law ${\mathbb{P}}_{\mathbf{s}}$ have enough individuals in the first generations, and this is handled through novel path transformations and fluctuation theory of exchangeable increment processes. As a consequence, we obtain a boundedness criterion for the inhomogeneous continuum random tree introduced by Aldous, Miermont and Pitman (2004).

32 pages, 7 figures

References in corpus (4)

• The exploration process of inhomogeneous continuum random trees, and an extension of Jeulin's local time identity
• On the Height Profile of a Conditioned Galton-Watson Tree
• Limits of multiplicative inhomogeneous random graphs and Lévy trees: Limit theorems
• Invariance principles for local times in regenerative settings