The asymptotic distribution of cluster sizes for supercritical percolation on random split trees
Preprint
Abstract
We consider the model of random trees introduced by Devroye (1999), the so-called random split trees. The model encompasses many important randomized algorithms and data structures. We then perform supercritical Bernoulli bond-percolation on those trees and obtain a precise weak limit theorem for the sizes of the largest clusters. We also show that the approach developed in this work may be useful for studying percolation on other classes of trees with logarithmic height, for instance, we study also the case of $d$-regular trees.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- The existence of a giant cluster for percolation on large Crump–Mode–Jagers treesAdvances in Applied Probability, 2020
- Sizes of the largest clusters for supercritical percolation on random recursive treesRandom Structures & Algorithms, 2012
- Coalescent Random ForestsJournal of Combinatorial Theory, Series A, 1999
- Universal Limit Laws for Depths in Random TreesSIAM Journal on Computing, 1998
- On the expected height of fringe-balanced treesActa Informatica, 1993
- Analysis of the space of search trees under the random insertion algorithmJournal of Algorithms, 1989
- Extreme Values, Regular Variation and Point Processes1987
- Locally balanced binary treesThe Computer Journal, 1976
- Quad trees a data structure for retrieval on composite keysActa Informatica, 1974
- Cutting down random treesJournal of the Australian Mathematical Society, 1970