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

By Bénédicte Haas, Grégory Miermont. 2010

120 citations recorded by the source corpus.

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. Applications include scaling limits of consistent Markov branching model, and convergence of Galton-Watson trees towards the Brownian and stable continuum random trees. We also obtain that random uniform unordered trees have the Brownian tree as a scaling limit, hence extending a result by Marckert-Miermont and fully proving a conjecture made by Aldous.

Subfields: Condensed Matter Physics, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/05fe5053caf3f02d039db112fc67bd3880d429e0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Condensed Matter Physics

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

Cutting down trees with a Markov chainsaw (2011, methodology): “We note that the terminology introduced in Sections 2.2 and 2.3 is not used until Section 5, and the reader may wish to correspondingly postpone their reading of these sections.”
The gap between Gromov-vague and Gromov–Hausdorff-vague topology (2014, methodology): “In such a situation, Gromov–Hausdorff convergence and Gromov-weak convergence are shown separately (for example, [24,12,3]), or the scaling results are stated either without the measure, using Gromov–Hausdorff convergence (for example, [30,33,25]), or only in the Gromov-weak topology (for example, [”
Scaling Limits of Random Graphs from Subcritical Classes (2014, background): “Since Aldous’s pioneering work, the CRT has been identified as the limiting object of many different classes of discrete structures, in particular trees, see e.g. Haas and Miermont [16] and references therein, and planar maps, see e.g. Albenque and Marckert [2], Bettinelli [8], Caraceni [9], Curien,”
Scaling limits of Markov branching trees and Galton-Watson trees conditioned on the number of vertices with out-degree in a given set (2011, methodology): “More recently, techniques for handling Markov branching trees that don’t necessarily satisfy consistency relations and whose size is their number of leaves (or vertices) were developed in [5].”
Scaling limits of random trees and planar maps (2011, background): “ing) towards the CRT. All these results can be derived from a general statement of convergence of conditioned Galton-Watson trees due to Aldous [2] (see also [29]). A recent work of Haas and Miermont [23] provides further extensions of Theorem 3.9 to Po´lya trees (unordered rooted trees). 4. Labeled”