Local Convergence of Large Critical Multi-type Galton–Watson Trees and Applications to Random Maps

We show that large critical multi-type Galton–Watson trees, when conditioned to be large, converge locally in distribution to an infinite tree which is analogous to Kesten’s infinite monotype Galton–Watson tree. This is proven when we condition on the number of vertices of one fixed type, and with an extra technical assumption if we count at least two types. We then apply these results to study local limits of random planar maps, showing that large critical Boltzmann-distributed random maps converge in distribution to an infinite map.     

Asymptotic normality of fringe subtrees and additive functionals in conditioned Galton–Watson trees

We consider conditioned Galton–Watson trees and show asymptotic normality of additive functionals that are defined by toll functions that are not too large. This includes, as a special case, asymptotic normality of the number of fringe subtrees isomorphic to any given tree, and joint asymptotic normality for several such subtree counts. Another example is the number of protected nodes. The offspring distribution defining the random tree is assumed to have expectation 1 and finite variance; no further moment condition is assumed. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 48, 57–101, 2016     

Rayleigh processes, real trees, and root growth with re-grafting

The real trees form a class of metric spaces that extends the class of trees with edge lengths by allowing behavior such as infinite total edge length and vertices with infinite branching degree. Aldous's Brownian continuum random tree, the random tree-like object naturally associated with a standard Brownian excursion, may be thought of as a random compact real tree. The continuum random tree is a scaling limit as N→∞ of both a critical Galton-Watson tree conditioned to have total population size N as well as a uniform random rooted combinatorial tree with N vertices. The Aldous–Broder algorithm is a Markov chain on the space of rooted combinatorial trees with N vertices that has the uniform tree as its stationary distribution. We construct and study a Markov process on the space of all rooted compact real trees that has the continuum random tree as its stationary distribution and arises as the scaling limit as N→∞ of the Aldous–Broder chain. A key technical ingredient in this work is the use of a pointed Gromov–Hausdorff distance to metrize the space of rooted compact real trees. Berkeley Statistics Technical Report No. 654 (February 2004), revised October 2004. To appear in Probability Theory and Related Fields. SNE supported in part by NSF grants DMS-0071468 and DMS-0405778, and a Miller Institute for Basic Research in Science research professorship JP supported in part by NSF grants DMS-0071448 and DMS-0405779 AW supported by a DFG Forchungsstipendium     

Conditioning Galton–Watson Trees on Large Maximal Outdegree

We propose a new way to condition random trees, that is, conditioning random trees to have large maximal outdegree. Under this conditioning, we show that conditioned critical Galton–Watson trees converge locally to size-biased trees with a unique infinite spine. For the subcritical case, we obtain the local convergence to size-biased trees with a unique infinite node. We also study the tail of the maximal outdegree of subcritical Galton–Watson trees, which is essential for the proof of the local convergence.     

Random tree recursions: Which fixed points correspond to tangible sets of trees?

Let be the set of rooted trees containing an infinite binary subtree starting at the root. This set satisfies the metaproperty that a tree belongs to it if and only if its root has children u and v such that the subtrees rooted at u and v belong to it. Let p be the probability that a Galton‐Watson tree falls in . The metaproperty makes p satisfy a fixed‐point equation, which can have multiple solutions. One of these solutions is p, but what is the meaning of the others? In particular, are they probabilities of the Galton‐Watson tree falling into other sets satisfying the same metaproperty? We create a framework for posing questions of this sort, and we classify solutions to fixed‐point equations according to whether they admit probabilistic interpretations. Our proofs use spine decompositions of Galton‐Watson trees and the analysis of Boolean functions.     

Random self-similar trees and a hierarchical branching process

We study self-similarity in random binary rooted trees. In a well-understood case of Galton–Watson trees, a distribution on a space of trees is said to be self-similar if it is invariant with respect to the operation of pruning, which cuts the tree leaves. This only happens for the critical Galton–Watson tree (a constant process progeny), which also exhibits other special symmetries. We extend the prune-invariance setup to arbitrary binary trees with edge lengths. In this general case the class of self-similar processes becomes much richer and covers a variety of practically important situations. The main result is construction of the hierarchical branching processes that satisfy various self-similarity definitions (including mean self-similarity and self-similarity in edge-lengths) depending on the process parameters. Taking the limit of averaged stochastic dynamics, as the number of trajectories increases, we obtain a deterministic system of differential equations that describes the process evolution. This system is used to establish a phase transition that separates fading and explosive behavior of the average process progeny. We describe a class of critical Tokunaga processes that happen at the phase transition boundary. They enjoy multiple additional symmetries and include the celebrated critical binary Galton–Watson tree with independent exponential edge length as a special case. Finally, we discuss a duality between trees and continuous functions, and introduce a class of extreme-invariant processes, constructed as the Harris paths of a self-similar hierarchical branching process, whose local minima has the same (linearly scaled) distribution as the original process.     

Noncrossing trees are almost conditioned Galton–Watson trees

A noncrossing tree (NC‐tree) is a tree drawn on the plane having as vertices a set of points on the boundary of a circle, and whose edges are straight line segments that do not cross. In this article, we show that NC‐trees with size n are conditioned Galton–Watson trees. As corollaries, we give the limit law of depth‐first traversal processes and the limit profile of NC‐trees. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 115–125, 2002     

Hereditary tree growth and Lévy forests

We introduce the notion of a hereditary property for rooted real trees and we also consider reduction of trees by a given hereditary property. Leaf-length erasure, also called trimming, is included as a special case of hereditary reduction. We only consider the metric structure of trees, and our framework is the space $\mathbb{T}$ of pointed isometry classes of locally compact rooted real trees equipped with the Gromov–Hausdorff distance. We discuss general tightness criteria in $\mathbb{T}$ and limit theorems for growing families of trees. We apply these results to Galton–Watson trees with exponentially distributed edge lengths. This class is preserved by hereditary reduction. Then we consider families of such Galton–Watson trees that are consistent under hereditary reduction and that we call growth processes. We prove that the associated families of offspring distributions are completely characterised by the branching mechanism of a continuous-state branching process. We also prove that such growth processes converge to Lévy forests. As a by-product of this convergence, we obtain a characterisation of the laws of Lévy forests in terms of leaf-length erasure and we obtain invariance principles for discrete Galton–Watson trees, including the super-critical cases.     

Recursive functions on conditional Galton‐Watson trees

A recursive function on a tree is a function in which each leaf has a given value, and each internal node has a value equal to a function of the number of children, the values of the children, and possibly an explicitly specified random element U. The value of the root is the key quantity of interest in general. In this study, all node values and function values are in a finite set S. In this note, we describe the limit behavior when the leaf values are drawn independently from a fixed distribution on S, and the tree T_n is a random Galton‐Watson tree of size n.     

On family trees and subtrees of simple branching processes

We study the probability of occurrence of certain subtrees of the family tree of a Galton Watson branching process.     

The Wiener Index of simply generated random trees

Asymptotics are obtained for the mean, variance, and higher moments as well as for the distribution of the Wiener index of a random tree from a simply generated family (or, equivalently, a critical Galton–Watson tree). We also establish a joint asymptotic distribution of the Wiener index and the internal path length, as well as asymptotics for the covariance and other mixed moments. The limit laws are described using functionals of a Brownian excursion. The methods include both Aldous' theory of the continuum random tree and analysis of generating functions. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 22: 337–358, 2003     

Infinitely Many Trees Have Non-Sperner Subtree Poset

Let C(T) denote the poset of subtrees of a tree T with respect to the inclusion ordering. Jacobson, Kézdy and Seif gave a single example of a tree T for which C(T) is not Sperner, answering a question posed by Penrice. The authors then ask whether there exist an infinite family of trees T such that C(T) is not Sperner. This paper provides such a family.     

Random cutting and records in deterministic and random trees

We study random cutting down of a rooted tree and show that the number of cuts is equal (in distribution) to the number of records in the tree when edges (or vertices) are assigned random labels. Limit theorems are given for this number, in particular when the tree is a random conditioned Galton–Watson tree. We consider both the distribution when both the tree and the cutting (or labels) are random and the case when we condition on the tree. The proofs are based on Aldous' theory of the continuum random tree. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

A Ramsey theorem for trees

We prove a Ramsey theorem for trees. The infinite version of this theorem can be stated: if T is a rooted tree of infinite height with each node of T having at least one but finitely many immediate successors, if n is a positive integer, and if the collection of all strongly embedded, height-n subtrees of T is partitioned into finitely many classes, then there must exist a strongly embedded subtree S of T with S having infinite height and with all the strongly embedded, height-n subtrees of S in the same class.     

And/or trees: A local limit point of view

We present here a new and universal approach for the study of random and/or trees, unifying in one framework many different models, including some novel ones not yet understood in the literature. An and/or tree is a Boolean expression represented in (one of) its tree shapes. Fix an integer k, take a sequence of random (rooted) trees of increasing size, say , and label each of these random trees uniformly at random in order to get a random Boolean expression on k variables. We prove that, under rather weak local conditions on the sequence of random trees , the distribution induced on Boolean functions by this procedure converges as n tends to infinity. In particular, we characterize two different behaviors of this limit distribution depending on the shape of the local limit of : a degenerate case when the local limit has no leaves; and a non‐degenerate case, which we are able to describe in more details under stronger conditions. In this latter case, we provide a relationship between the probability of a given Boolean function and its complexity. The examples covered by this unified framework include trees that interpolate between models with logarithmic typical distances (such as random binary search trees) and other ones with square root typical distances (such as conditioned Galton–Watson trees).     

Large deviations for random walks on Galton–Watson trees: averaging and uncertainty

 In the study of large deviations for random walks in random environment, a key distinction has emerged between quenched asymptotics, conditional on the environment, and annealed asymptotics, obtained from averaging over environments. In this paper we consider a simple random walk {X _n } on a Galton–Watson tree T, i.e., on the family tree arising from a supercritical branching process. Denote by |X _n | the distance between the node X _n and the root of T. Our main result is the almost sure equality of the large deviation rate function for |X _n |/n under the “quenched measure” (conditional upon T), and the rate function for the same ratio under the “annealed measure” (averaging on T according to the Galton–Watson distribution). This equality hinges on a concentration of measure phenomenon for the momentum of the walk. (The momentum at level n, for a specific tree T, is the average, over random walk paths, of the forward drift at the hitting point of that level). This concentration, or certainty, is a consequence of the uncertainty in the location of the hitting point. We also obtain similar results when {X _n } is a λ-biased walk on a Galton–Watson tree, even though in that case there is no known formula for the asymptotic speed. Our arguments rely at several points on a “ubiquity” lemma for Galton–Watson trees, due to Grimmett and Kesten (1984). Received: 15 November 2000 / Revised version: 27 February 2001 / Published online: 19 December 2001     

Weighted enumeration of spanning subgraphs in locally tree‐like graphs

Using the theory of negative association for measures and the notion of unimodularity for random weak limits of sparse graphs, we establish the validity of the cavity method for counting spanning subgraphs subject to local constraints in asymptotically tree‐like graphs. Specifically, the normalized logarithm of the associated partition function (free energy) is shown to converge along any sequence of graphs whose random weak limit is a tree, and the limit is directly expressed in terms of the unique solution to a limiting cavity equation. On a Galton–Watson tree, the latter simplifies into a recursive distributional equation which can be solved explicitly. As an illustration, we provide a new asymptotic formula for the maximum size of a b‐matching in the Erd?s–Rényi random graph with fixed average degree and diverging size, for any $b\in\mathbb{N}Using the theory of negative association for measures and the notion of unimodularity for random weak limits of sparse graphs, we establish the validity of the cavity method for counting spanning subgraphs subject to local constraints in asymptotically tree‐like graphs. Specifically, the normalized logarithm of the associated partition function (free energy) is shown to converge along any sequence of graphs whose random weak limit is a tree, and the limit is directly expressed in terms of the unique solution to a limiting cavity equation. On a Galton–Watson tree, the latter simplifies into a recursive distributional equation which can be solved explicitly. As an illustration, we provide a new asymptotic formula for the maximum size of a b‐matching in the Erd?s–Rényi random graph with fixed average degree and diverging size, for any $b\in\mathbb{N}$. To the best of our knowledge, this is the first time that correlation inequalities and unimodularity are combined together to yield a general proof of uniqueness of Gibbs measures on infinite trees. We believe that a similar argument is applicable to other Gibbs measures than those over spanning subgraphs considered here. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

A Note on “State Spaces of the Snake and Its Tour—Convergence of the Discrete Snake” by J.-F. Marckert and A. Mokkadem

In State spaces of the snake and its tour—Convergence of the discrete snake the authors showed a limit theorem for Galton–Watson trees with geometric offspring distribution. In this note it is shown that their result holds for all Galton–Watson trees with finite offspring variance.