Random trees and applications

Abstract

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.

Published at http://dx.doi.org/10.1214/154957805100000140 in the Probability Surveys (http://www.i-journals.org/ps/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (1)

• A limit theorem for the contour process of conditioned Galton-Watson trees

Cited by in corpus (118)

• Uniqueness and universality of the Brownian map
• The topological structure of scaling limits of large planar maps
• Invariance principles for Galton-Watson trees conditioned on the number of leaves
• Scaling limits of random trees and planar maps
• Random stable looptrees
• Scaling limits of random planar maps with a unique large face
• Mating of trees for random planar maps and Liouville quantum gravity: a survey
• Sub-Gaussian tail bounds for the width and height of conditioned Galton--Watson trees
• A simple proof of Duquesne's theorem on contour processes of conditioned Galton-Watson trees
• Cutting down trees with a Markov chainsaw
• The local weak limit of the minimum spanning tree of the complete graph
• Scaling limits of random bipartite planar maps with a prescribed degree sequence
• Random non-crossing plane configurations: A conditioned Galton-Watson tree approach
• The range of tree-indexed random walk in low dimensions
• Universality for critical heavy-tailed network models: Metric structure of maximal components
• Branching Feller diffusion for cell division with parasite infection
• Schnyder woods, SLE(16), and Liouville quantum gravity
• The topology of scaling limits of positive genus random quadrangulations
• Branching diffusions, superdiffusions and random media
• The scaling limit of random simple triangulations and random simple quadrangulations
• Field-theoretic approach to the universality of branching processes
• Probabilistic Models for the (sub)Tree(s) of Life
• Random stable laminations of the disk
• An invariance principle for branching diffusions in bounded domains
• Tokunaga and Horton self-similarity for level set trees of Markov chains
• Pruning Galton-Watson Trees and Tree-valued Markov Processes
• Triangulating stable laminations
• Recent progress in coalescent theory
• The distribution of height and diameter in random non-plane binary trees
• On scaling limits of planar maps with stable face-degrees
• Scaling limit of the invasion percolation cluster on a regular tree
• On the Brownian separable permuton
• On scaling limits of random trees and maps with a prescribed degree sequence
• The contour of splitting trees is a Lévy process
• The continuum random tree is the scaling limit of unlabelled unrooted trees
• Tree limits and limits of random trees
• The phase transition for parking on Galton--Watson trees
• Percolation on random triangulations and stable looptrees
• The dual tree of a recursive triangulation of the disk
• Convergence of odd-angulations via symmetrization of labeled trees
• On the Aldous diffusion on Continuum Trees. I
• The harmonic measure of balls in random trees
• Planar stochastic hyperbolic infinite triangulations
• Geometry of the vacant set left by random walk on random graphs, Wright's constants, and critical random graphs with prescribed degrees
• A representation of exchangeable hierarchies by sampling from real trees
• Dini derivatives for Exchangeable Increment processes and applications
• Scaling limits of discrete snakes with stable branching
• Percolation on trees as a Brownian excursion: from Gaussian to Kolmogorov-Smirnov to Exponential statistics
• The falling appart of the tagged fragment and the asymptotic disintegration of the Brownian height fragmentation
• Scaling limit for the ant in a simple labyrinth
• Mass-structure of weighted real trees
• The multiplicative coalescent, inhomogeneous continuum random trees, and new universality classes for critical random graphs
• Fires on large recursive trees
• On scaling limits of multitype Galton-Watson trees with possibly infinite variance
• Geometry of the minimal spanning tree of a random $3$-regular graph
• On the profile of trees with a given degree sequence
• Asymptotics for rooted planar maps and scaling limits of two-type spatial trees
• Uniform infinite half-planar quadrangulations with skewness
• Spectral dimension of trees with a unique infinite spine
• A branching process with coalescence to model random phylogenetic networks
• The continuum limit of critical random graphs
• Self avoiding walk on the seven regular triangulation
• Reversing the cut tree of the Brownian continuum random tree
• A Unified Framework for Generalizing the Gromov-Hausdorff Metric
• Large deviation Local Limit Theorems and limits of biconditioned Trees and Maps
• Critical Percolation on Random Networks with Prescribed Degrees
• Universality for the directed configuration model: metric space convergence of the strongly connected components at criticality
• On breadth-first constructions of scaling limits of random graphs and random unicellular maps
• Mean-field forest-fire models and pruning of random trees
• Limit of trees with fixed degree sequence
• Stable limit laws for randomly biased walks on supercritical trees
• SLE as a mating of trees in Euclidean geometry
• A new encoding of coalescent processes. Applications to the additive and multiplicative cases
• Total progeny in killed branching random walk
• Continuum limit of critical inhomogeneous random graphs
• Convergence of blanket times for sequences of random walks on critical random graphs
• Branching interlacements and tree-indexed random walks in tori
• Scaling limits of random looptrees and bipartite plane maps with prescribed large faces
• Markovian tricks for non-Markovian trees: contour process, extinction and scaling limits
• The heavy path approach to Galton-Watson trees with an application to Apollonian networks
• Fast Simulation of Size-Constrained Multitype Bienaymé-Galton-Watson Forests and Applications
• The Incipient Infinite Cluster of the Uniform Infinite Half-Planar Triangulation
• Limits of the boundary of random planar maps
• Sub-exponential tail bounds for conditioned stable Bienaymé-Galton-Watson trees
• A tree-valued Markov processes associated with an admissible family of branching mechanisms
• Predator-prey dynamics on infinite trees: a branching random walk approach
• Critical trees are neither too short nor too fat
• Thick points of 4D critical branching Brownian motion
• Random Lévy Looptrees and Lévy Maps
• On a ternary coalescent process
• Simply generated trees, conditioned Galton--Watson trees, random allocations and condensation
• On the growth of random planar maps with a prescribed degree sequence
• Tail bounds for the height and width of a random tree with a given degree sequence
• Uniform Hausdorff measure of the level sets of the Brownian tree
• The purely singular 1-D acoustic reflection problem
• Randomly biased walks on subcritical trees
• Marked metric measure spaces
• Enumeration of pyramids of one-dimensional pieces of arbitrary fixed integer length
• Encoding multitype Galton-Watson forests and a multitype Ray-Knight theorem
• The height of random binary unlabelled trees
• Continuum random tree as the scaling limit for a drainage network model: a Brownian web approach
• Critical random forests
• Small trees in supercritical random forests
• Random maps: proceeding of the Journ{é}es MAS 2014
• Scaling limits and universality: Critical percolation on weighted graphs converging to an $L^3$ graphon
• Height and diameter of brownian tree
• Noise Sensitivity of the Minimum Spanning Tree of the Complete Graph
• The Horton-Strahler number of Galton-Watson trees with possibly infinite variance
• Occupation densities of Ensembles of Branching Random Walks
• A View From The Bridge Spanning Combinatorics and Probability
• A random walk on Z with drift driven by its occupation time at zero
• Graphical Models: An Extension to Random Graphs, Trees, and Other Objects
• Rotating random trees with Skorokhod's $M_1$ topology
• Critical random graphs: limiting constructions and distributional properties
• $k$-cut model for the Brownian Continuum Random Tree
• The Brownian continuum random tree as the unique solution to a fixed point equation
• Scaling limits for a family of unrooted trees
• Epidemics on critical random graphs with heavy-tailed degree distribution