Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees

DOI10.1214/11-AOP686zbMATH Open1259.60033arXiv1003.3632MaRDI QIDQ693717FDOQ693717

Authors: Bénédicte Haas, Grégory Miermont 

Publication date: 10 December 2012

Published in: The Annals of Probability (Search for Journal in Brave)

Abstract: We consider a family of random trees satisfying a Markov branching property. Roughly, this property says that the subtrees above some given height are independent with a law that depends only on their total size, the latter being either the number of leaves or vertices. Such families are parameterized by sequences of distributions on partitions of the integers that determine how the size of a tree is distributed in its different subtrees. Under some natural assumption on these distributions, stipulating that "macroscopic" splitting events are rare, we show that Markov branching trees admit the so-called self-similar fragmentation trees as scaling limits in the Gromov-Hausdorff-Prokhorov topology. The main application of these results is that the scaling limit of random uniform unordered trees is the Brownian continuum random tree. This extends a result by Marckert-Miermont and fully proves a conjecture by Aldous. We also recover, and occasionally extend, results on scaling limits of consistent Markov branching models and known convergence results of Galton-Watson trees toward the Brownian and stable continuum random trees.

Full work available at URL: https://arxiv.org/abs/1003.3632

Recommendations

• Scaling Limits of Markov-Branching Trees and Applications
• Scaling limits of Markov branching trees and Galton-Watson trees conditioned on the number of vertices with out-degree in a given set
• Scaling limits of multi-type Markov branching trees
• Scaling limits of tree-valued branching random walks
• A note on the scaling limits of contour functions of Galton-Watson trees
• A uniform limit law for the branching measure on a Galton-Watson tree
• Limit theorems for Markov processes indexed by continuous time Galton-Watson trees
• On scaling limits of multitype Galton-Watson trees with possibly infinite variance
• Scaling limit of random \(k\)-trees
• Scaling limits of random trees and random graphs

zbMATH Keywords

scaling limitsself-similar fragmentationsrandom treescontinuum random treesMarkov branching property

Mathematics Subject Classification ID

Functional limit theorems; invariance principles (60F17) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Cites Work

• Analytic combinatorics
• Title not available (Why is that?)
• Continuum tree asymptotics of discrete fragmentations and applications to phylogenetic mod\-els
• Title not available (Why is that?)
• Combinatorial stochastic processes. Ecole d'Eté de Probabilités de Saint-Flour XXXII -- 2002.
• Title not available (Why is that?)
• Random Trees
• Tessellations of random maps of arbitrary genus
• Title not available (Why is that?)
• Title not available (Why is that?)
• Random Fragmentation and Coagulation Processes
• Self-similar fragmentations
• Probabilistic and fractal aspects of Lévy trees
• Title not available (Why is that?)
• A note on the height of binary search trees
• Title not available (Why is that?)
• The number of trees
• Ranked Fragmentations
• The continuum random tree. III
• The continuum random tree. I
• Rayleigh processes, real trees, and root growth with re-grafting
• Regenerative tree growth: binary self-similar continuum random trees and Poisson-Dirichlet compositions
• A new family of Markov branching trees: the alpha-gamma model
• The genealogy of self-similar fragmentations with negative index as a continuum random tree
• Spinal partitions and invariance under re-rooting of continuum random trees
• Branching processes in Lévy processes: The exploration process
• Title not available (Why is that?)
• A limit theorem for the contour process of conditioned Galton-Watson trees
• The shape of unlabeled rooted random trees
• The distribution of height and diameter in random non-plane binary trees
• The CRT is the scaling limit of unordered binary trees
• Self-similar scaling limits of non-increasing Markov chains
• The height of increasing trees
• Subtree prune and regraft: a reversible real tree-valued Markov process

Cited In (67)

• Multicritical continuous random trees
• Scaling limit of critical random trees in random environment
• Tail asymptotics for extinction times of self-similar fragmentations
• Invariance principle for fragmentation processes derived from conditioned stable Galton-Watson trees
• Almost sure convergence of vertex degree densities in the vertex splitting model
• On random trees and forests
• Simply generated unrooted plane trees
• Surprising identities for the greedy independent set on Cayley trees
• A down‐up chain with persistent labels on multifurcating trees
• Cutoff on trees is rare
• Scaling limits of slim and fat trees
• Sizes of the largest clusters for supercritical percolation on random recursive trees
• The CRT is the scaling limit of random dissections
• Poisson point process limits in size-biased Galton-Watson trees
• Cutting edges at random in large recursive trees
• Limits of random tree-like discrete structures
• Scaling limits for a family of unrooted trees
• The dual tree of a recursive triangulation of the disk
• On the Wiener index of random trees
• Sub-exponential tail bounds for conditioned stable Bienaymé-Galton-Watson trees
• Bivariate Markov chains converging to Lamperti transform Markov additive processes
• The shape of unlabeled rooted random trees
• Inverting the cut-tree transform
• Scaling Limits of Markov-Branching Trees and Applications
• Recursive construction of continuum random trees
• The CRT is the scaling limit of unordered binary trees
• Zooming in at the root of the stable tree
• Forward-backward stochastic differential equations and controlled McKean-Vlasov dynamics
• An asymptotic analysis of labeled and unlabeled \(k\)-trees
• Dissecting the circle, at random
• The scaling limit of a critical random directed graph
• Scaling limits of multi-type Markov branching trees
• Self-similar scaling limits of non-increasing Markov chains
• The cut-tree of large Galton-Watson trees and the Brownian CRT
• Cutting down trees with a Markov chainsaw
• Scaling limits of Markov branching trees and Galton-Watson trees conditioned on the number of vertices with out-degree in a given set
• Consistent Markov branching trees with discrete edge lengths
• Graphon convergence of random cographs
• Generalized Markov branching trees
• A binary embedding of the stable line-breaking construction
• Self-similar growth fragmentations as scaling limits of Markov branching processes
• The degree profile of random Pólya trees
• Global regime for general additive functionals of conditioned Bienaymé-Galton-Watson trees
• Scaling limits of stochastic processes associated with resistance forms
• Scaling limits of \(k\)-ary growing trees
• Probability, trees and algorithms. Abstracts from the workshop held November 2--8, 2014.
• Scaling limits and influence of the seed graph in preferential attachment trees
• Local limits of Markov branching trees and their volume growth
• Graph limits of random graphs from a subset of connected \(k\)-trees
• Stable graphs: distributions and line-breaking construction
• Scaling limits of random Pólya trees
• Fires on trees
• Scaling limits for some random trees constructed inhomogeneously
• Cutting down \(\mathbf{p}\)-trees and inhomogeneous continuum random trees
• The continuum random tree. III
• The gap between Gromov-Vague and Gromov-Hausdorff-vague topology
• Schröder's problems and scaling limits of random trees
• Growing random graphs with a preferential attachment structure
• Tree limits and limits of random trees
• The cut-tree of large recursive trees
• A symmetric entropy bound on the non-reconstruction regime of Markov chains on Galton-Watson trees
• Gromov-Hausdorff-Prokhorov convergence of vertex cut-trees of \(n\)-leaf Galton-Watson trees
• Excursion theory for Brownian motion indexed by the Brownian tree
• Random enriched trees with applications to random graphs
• The stable trees are nested
• The distribution of height and diameter in random non-plane binary trees
• Scaling limits for simple random walks on random ordered graph trees

This page was built for publication: Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q693717)