Premium
The asymptotic distribution of cluster sizes for supercritical percolation on random split trees
Author(s) -
Berzunza Gabriel,
Holmgren Cecilia
Publication year - 2022
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.21046
Subject(s) - bernoulli's principle , mathematics , percolation (cognitive psychology) , statistical physics , tree (set theory) , supercritical fluid , logarithm , percolation threshold , limit (mathematics) , cluster (spacecraft) , central limit theorem , distribution (mathematics) , combinatorics , continuum percolation theory , bernoulli distribution , percolation critical exponents , scaling , random variable , statistics , computer science , critical exponent , physics , mathematical analysis , geometry , quantum mechanics , neuroscience , biology , programming language , electrical resistivity and conductivity , thermodynamics
We consider the model of random trees introduced by Devroye, 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 also study the case of d ‐regular trees.