Simply generated trees, conditioned Galton–Watson trees, random allocations and condensation

By Svante Janson. 2011

268 citations recorded by the source corpus.

We give a unified treatment of the limit, as the size tends to infinity, of simply generated random trees, including both the well-known result in the standard case of critical Galton–Watson trees and similar but less well-known results in the other cases (i.e., when no equivalent critical Galton–Watson tree exists). There is a well-defined limit in the form of an infinite random tree in all cases; for critical Galton–Watson trees this tree is locally finite but for the other cases the random limit has exactly one node of infinite degree. The proofs use a well-known connection to a random allocation model that we call balls-in-boxes, and we prove corresponding theorems for this model. This survey paper contains many known results from many different sources, together with some new results.

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

View Paper: https://www.semanticscholar.org/paper/6274bd01a7c5d50111e49479e9b005c3b1002d44

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

Scaling Limits of Random Graphs from Subcritical Classes (2014, background): “We also state some results given in [1, 28] that will be useful in our arguments.”
Fringe trees, Crump-Mode-Jagers branching processes and $m$-ary search trees (2016, result): “Note that the results are quite different from the results for fringe trees of conditioned Galton–Watson trees, where we also start with a branching process but instead of stopping it, we let it run until extinction and condition on its total size being a given finite number, see [1; 7; 76; 77].”
Local Convergence of Large Critical Multi-type Galton–Watson Trees and Applications to Random Maps (2014, methodology): “ formed by a unique innite spine to which many nite trees are grafted. This innite tree was rst indirectly mentioned in [15], Lemma 1.14, and many details about the convergence are given in [2] and [13]. One of its properties is that one can obtain its distribution from the distribution of the nite ”
Random stable looptrees (2013, unknown): “Janson [21, Formula (19.97)] gives the cumulative distribution function of ∆ ∗ ( X exc , ( α ) ) : where u ≥ 0 .”
Stable distributions (2011, methodology): “Introduction We give many explicit formulas for stable distributions, mainly based on Feller [3] and Zolotarev [14] and using several parametrizations; we give also some explicit calculations for convergence to stable distributions, mainly based on less explicit results in Feller [3].”
Scaling limits of random planar maps with a unique large face (2012, methodology): “Later it was established in full generality [covering cases (C1) and (C2)] in [29].”
Sub-Gaussian tail bounds for the width and height of conditioned Galton--Watson trees (2010, background): “(2.4) We will use a one-sided tail bound for Sn, which we take from Janson [16], that only requires our (weak) conditions.”