Header

UZH-Logo

Maintenance Infos

The cut-tree of large galton-watson trees and the brownian crt


Bertoin, Jean; Miermont, Grégory (2013). The cut-tree of large galton-watson trees and the brownian crt. Annals of Applied Probability, 23(4):1469-1493.

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 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.

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 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.

Statistics

Citations

13 citations in Web of Science®
10 citations in Scopus®
Google Scholar™

Altmetrics

Downloads

30 downloads since deposited on 22 Nov 2013
7 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Journal Article, refereed, original work
Communities & Collections:07 Faculty of Science > Institute of Mathematics
Dewey Decimal Classification:510 Mathematics
Language:English
Date:2013
Deposited On:22 Nov 2013 11:34
Last Modified:05 Apr 2016 17:10
Publisher:Institute of Mathematical Statistics
ISSN:1050-5164
Free access at:Publisher DOI. An embargo period may apply.
Publisher DOI:https://doi.org/10.1214/12-AAP877

Download

Download PDF  'The cut-tree of large galton-watson trees and the brownian crt'.
Preview
Content: Published Version
Language: English
Filetype: PDF
Size: 207kB
View at publisher