Random trees and applications

By Jean-François Le Gall. 2005

408 citations recorded by the source corpus.

We discuss several connections between discrete and continuous random trees. In the discrete setting, we focus on Galton-Watson trees under various conditionings. In particular, we present a simple approach to Aldous' theorem giving the convergence in distribution of the contour process of conditioned Galton-Watson trees towards the normalized Brownian excursion. We also briefly discuss applications to combinatorial trees. In the continuous setting, we use the formalism of real trees, which yields an elegant formulation of the convergence of rescaled discrete trees towards continuous objects. We explain the coding of real trees by functions, which is a continuous version of the well-known coding of discrete trees by Dyck paths. We pay special attention to random real trees coded by Brownian excursions, and in a particular we provide a simple derivation of the marginal distributions of the CRT. The last section is an introduction to the theory of the Brownian snake, which combines the genealogical structure of random real trees with independent spatial motions. We introduce exit measures for the Brownian snake and we present some applications to a class of semilinear partial differential equations.

Subfields: Artificial Intelligence, Condensed Matter Physics, Mathematical Physics

View Paper: https://www.semanticscholar.org/paper/6b656e5d42d36dfcc56069734a9ac9511f1c0914

How researchers see this paper

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

In Artificial Intelligence

In Condensed Matter Physics

In Mathematical Physics

Citations in the corpus

The local weak limit of the minimum spanning tree of the complete graph (2013, background): “1 i3k 3) induced by the graph structure of K, by viewing x i;x 0 i as the extremities of the edge i. Here we should recall some of the basic properties of the CRT T , referring the reader to, e.g., [43] for more details. If "= ("(s);0 s1) is a standard normalized Brownian excursion then T ”
The continuum limit of critical random graphs (2009, methodology): “, dGH(G , G) ≤ 12 supx,y |d (x, y)−d(x, y)| (see, for example, [33]).”
Rescaled bipartite planar maps converge to the Brownian map (2013, background): “6 in [8] for a precise justification in a slightly different setting.”
Scaling Limit of Random Planar Quadrangulations with a Boundary (2011, background): “We will also need basic facts on real trees (see for example [26]).”
Scaling Limits of Random Graphs from Subcritical Classes (2014, background): “erplanar graphs. 2. Galton-Watson Trees and the CRT We brie y summarize required notions and results related to the Brownian Continuum Random Tree (CRT) and refer the reader to Aldous [5] and Le Gall [34] for a thorough treatment. 2.1. Graphs and (Plane) Trees. All graphs considered in this paper ar”
The topological structure of scaling limits of large planar maps (2006, background): “Given an integer p ≥ 2, a 2p-angulation is a planar map where each face has degree 2p, that is 2p adjacent edges (one should count edge sides, so that if an edge lies entirely inside a face it is counted twice).”
Scaling limits of random trees and planar maps (2011, background): “All these results can be derived from a general statement of convergence of conditioned Galton-Watson trees due to Aldous [2] (see also [29]).”
Itô’s excursion theory and random trees (2010, background): “Note that, although we formulate our limit theorems in terms of contour processes, these results immediately imply analogous limit theorems for the trees viewed as compact metric spaces, in the sense of the Gromov-Hausdorff distance: The point is that a (discrete or continuous) tree can be viewed as”
Scaling limits of random planar maps with large faces (2011, background): “2, or [18], Section 1) and we leave the proof as an exercise for the reader.”
Random stable looptrees (2013, neutral): “…) on u n 0 , . . . , u n | τ n |− 1 can be recovered from W n in a similar way to the continuous setting (see the proof of Proposition 1.2 in [24] for details): Furthermore, when u ni ≺ u nj , that is when u ni u nj and i = j , the quantity informally gives the “position” of the ancestral…”
Cutting down trees with a Markov chainsaw (2011, neutral): “ for the R-tree coded by e. (We recall that the points of Te are equivalence classes {[x],0 ≤ x≤ 1}, where points x,y∈ [0,1] are equivalent if e(x) = e(y) = inf{e(z):x≤ z≤ y}, and refer the reader to [34] for more details of this standard construction.) Next, let Ae={(s,y)∈[0,1]×R+:0≤y≤e(s)} be the ”
Some families of increasing planar maps (2007, methodology): “We borrow some considerations from Le Gall & Weill [31] and Le Gall [28].”
The Brownian limit of separable permutations (2016, background): “to X1; ;X k). Lemma 6.1. Let ebe the Brownian excursion, then a.s. ehas the distinct minima property. Proof. This can be seen as a consequence of Lemma A.4, but since this lemma uses a deep result of [26], let us give a more elementary proof. If eis the Brownian excursion, and X1 < <X kis the ”
Scaling limits of random planar maps with a unique large face (2012, background): “) Aldous [3] proved that the contour function of such a random rooted tree, after rescaling, converges in distribution to e, which implies convergence of the tree to Te in Gromov–Hausdorff distance; see [38], Theorem 2.”
Simply generated trees, conditioned Galton–Watson trees, random allocations and condensation (2011, background): “Duquesne [34] and Le Gall [80, 81]; the limit is now a different random metric space called a stable tree.”