The asymptotic distribution of cluster sizes for supercritical\n percolation on random split trees

2020/03/26 by Gabriel Berzunza, Berzunza, Gabriel, Cecilia Holmgren +1
Mathematics · Physics and Astronomy · #05C05 #05C80 #60C05 #60F05 #60K35 #68P05 #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics #Theoretical and Computational Physics

paper · pdf · doi:10.48550/arxiv.2003.12018

openalex publication_date 2020/03/26 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28

Abstract

We consider the model of random trees introduced by Devroye (1999), the\nso-called random split trees. The model encompasses many important randomized\nalgorithms and data structures. We then perform supercritical Bernoulli\nbond-percolation on those trees and obtain a precise weak limit theorem for the\nsizes of the largest clusters. We also show that the approach developed in this\nwork may be useful for studying percolation on other classes of trees with\nlogarithmic height, for instance, we study also the case of d-regular trees.\n

Related

• The fluctuations of the giant cluster for percolation on random split trees
• On the non-Gaussian fluctuations of the giant cluster for percolation on random recursive trees
• Size distribution of clusters in site-percolation on random recursive tree
• Almost giant clusters for percolation on large trees with logarithmic heights
• Large deviations of the giant in supercritical kernel-based spatial random graphs