The cut‐tree of large trees with small heights1. Issue 3 (24th March 2017)

• Record Type: Journal Article
• Authors: Berzunza, Gabriel
• Is Part Of: Random structures & algorithms. Volume 51:Issue 3(2017)
• Page Start: 404
• Page End: 427
• Publication Date: 2017-03-24
• Subjects: random trees -- destruction of trees -- percolation -- Gromov‐Prokhorov convergence; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20711
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We destroy a finite tree of size n by cutting its edges one after the other and in uniform random order. Informally, the associated cut‐tree describes the genealogy of the connected components created by this destruction process. We provide a general criterion for the convergence of the rescaled cut‐tree in the Gromov‐Prohorov topology to an interval endowed with the Euclidean distance and a certain probability measure, when the underlying tree has branching points close to the root and height of order o ( n ) . In particular, we consider uniform random recursive trees, binary search trees, scale‐free random trees and a mixture of regular trees. This yields extensions of a result in Bertoin (Probab Stat 5 (2015), 478–488) for the cut‐tree of uniform random recursive trees and also allows us to generalize some results of Kuba and Panholzer (Online J Anal Combin (2014), 26) on the multiple isolation of vertices. The approach relies in the close relationship between the destruction process and Bernoulli bond percolation, which may be useful for studying the cut‐tree of other classes of trees. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 404–427, 2017