The cut-tree of large Galton-Watson trees and the Brownian CRT

DOI10.1214/12-AAP877zbMATH Open1279.60035arXiv1201.4081OpenAlexW3100171672MaRDI QIDQ363853FDOQ363853

Authors: Jean Bertoin, Grégory Miermont 

Publication date: 5 September 2013

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Abstract: Consider the edge-deletion process in which the edges of some finite tree T are removed one after the other in the uniform random order. Roughly speaking, the cut-tree then describes the genealogy of connected components appearing in this edge-deletion process. Our main result shows that after a proper rescaling, the cut-tree of a critical Galton-Watson tree with finite variance and conditioned to have size n, converges as $noinfty$ to a Brownian continuum random tree (CRT) in the weak sense induced by the Gromov-Prokhorov topology. This yields a multi-dimensional extension of a limit theorem due to Janson [Random Structures Algorithms 29 (2006) 139-179] for the number of random cuts needed to isolate the root in Galton-Watson trees conditioned by their sizes, and also generalizes a recent result [Ann. Inst. Henri Poincar'{e} Probab. Stat. (2012) 48 909-921] obtained in the special case of Cayley trees.

Full work available at URL: https://arxiv.org/abs/1201.4081

Recommendations

• The cut-tree of large trees with small heights
• Gromov-Hausdorff-Prokhorov convergence of vertex cut-trees of \(n\)-leaf Galton-Watson trees
• The vertex-cut-tree of Galton-Watson trees converging to a stable tree
• The \(k\)-cut model in deterministic and random trees
• \(k\)-cut model for the Brownian continuum random tree

zbMATH Keywords

Brownian continuum random treecut-treeGalton-Watson tree

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Cites Work

• Random Fragmentation and Coagulation Processes
• Self-similar fragmentations
• Conceptual proofs of \(L\log L\) criteria for mean behavior of branching processes
• Metric structures for Riemannian and non-Riemannian spaces. Transl. from the French by Sean Michael Bates. With appendices by M. Katz, P. Pansu, and S. Semmes. Edited by J. LaFontaine and P. Pansu
• The continuum random tree. III
• Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees
• Fires on trees
• Random cutting and records in deterministic and random trees
• Cutting down very simple trees
• Cutting down random trees
• Coalescent random forests
• The standard additive coalescent
• Convergence in distribution of random metric measure spaces (\(\Lambda \)-coalescent measure trees)
• Cauchy's principal value of local times of Lévy processes with no negative jumps via continuous branching processes
• A continuum-tree-valued Markov process
• Total progeny in killed branching random walk

Cited In (24)

• A view from the bridge spanning combinatorics and probability
• Cutting edges at random in large recursive trees
• A new combinatorial representation of the additive coalescent
• The vertex-cut-tree of Galton-Watson trees converging to a stable tree
• Record process on the continuum random tree
• Reversing the cut tree of the Brownian continuum random tree
• The distance profile of rooted and unrooted simply generated trees
• Inverting the cut-tree transform
• Scaling Limits of Markov-Branching Trees and Applications
• A note on the probability of cutting a Galton-Watson tree
• Percolation on random recursive trees
• On moment sequences and mixed Poisson distributions
• Convergence of bi-measure \(\mathbb{R}\)-trees and the pruning process
• Cutting down trees with a Markov chainsaw
• The \(k\)-cut model in deterministic and random trees
• Models of random subtrees of a graph
• Coupling Bertoin's and Aldous-Pitman's representations of the additive coalescent
• The cut-tree of large trees with small heights
• Probability, trees and algorithms. Abstracts from the workshop held November 2--8, 2014.
• \(k\)-cut model for the Brownian continuum random tree
• The forest associated with the record process on a Lévy tree
• Cutting down \(\mathbf{p}\)-trees and inhomogeneous continuum random trees
• The cut-tree of large recursive trees
• Gromov-Hausdorff-Prokhorov convergence of vertex cut-trees of \(n\)-leaf Galton-Watson trees

This page was built for publication: The cut-tree of large Galton-Watson trees and the Brownian CRT

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q363853)