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

preprint2013arXivOpen access

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

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.