2026-07-24T18:00:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12036 2024-03-06T10:49:14Z ddc:004 open_access

Largest Clusters for Supercritical Percolation on Split Trees Berzunza, Gabriel Holmgren, Cecilia Split trees random trees supercritical bond-percolation cluster size Poisson measures We consider the model of random trees introduced by Devroye [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. The approach we develop may be useful for studying percolation on other classes of trees with logarithmic height, for instance, we have also studied the case of complete d-regular trees. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gabriel Berzunza and Cecilia Holmgren 2020 Is Part Of LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AofA.2020.6 urn:nbn:de:0030-drops-120361 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.6 eng https://creativecommons.org/licenses/by/3.0/legalcode