Percolation on random recursive trees1. Issue 4 (3rd August 2015)

• Record Type: Journal Article
• Authors: Baur, Erich
• Is Part Of: Random structures & algorithms. Volume 48:Issue 4(2016)
• Page Start: 655
• Page End: 680
• Publication Date: 2015-08-03
• Subjects: random recursive tree -- percolation -- cluster; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20603
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We study Bernoulli bond percolation on a random recursive tree of size n with percolation parameter p ( n ) converging to 1 as n tends to infinity. The sizes of the percolation clusters are naturally stored in a tree structure. We prove convergence in distribution of this tree‐indexed process of cluster sizes to the genealogical tree of a continuous‐state branching process in discrete time. As a corollary we obtain the asymptotic sizes of the largest and next largest percolation clusters, extending thereby a recent work of Bertoin [5]. In a second part, we show that the same limit tree appears in the study of the tree components which emerge from a continuous‐time destruction of a random recursive tree. We comment on the connection to our first result on Bernoulli bond percolation. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 655–680, 2016