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 $n\to\infty$ 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é Probab. Stat. (2012) 48 909–921] obtained in the special case of Cayley trees.
Citation
Jean Bertoin. Grégory Miermont. "The cut-tree of large Galton–Watson trees and the Brownian CRT." Ann. Appl. Probab. 23 (4) 1469 - 1493, August 2013. https://doi.org/10.1214/12-AAP877
Information