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

DOI10.1002/RSA.21046MaRDI QIDQ6074697zbMATH OpenOpenAlexFDO

Authors Gabriel Berzunza, Cecilia Holmgren

Publication date 12 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.12018

zbMATH Keywords

Poisson processescluster sizerandom treessplit treessupercritical bond-percolation

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80)

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.

Recommendations

• The fluctuations of the giant cluster for percolation on random split trees
• Supercritical percolation on large scale-free random trees
• Sizes of the largest clusters for supercritical percolation on random recursive trees
• Almost giant clusters for percolation on large trees with logarithmic heights
• The existence of a giant cluster for percolation on large Crump–Mode–Jagers trees

Cites work

• scientific article; zbMATH DE number 4030574 (Why is no real title available?)
• scientific article; zbMATH DE number 1354815 (Why is no real title available?)
• scientific article; zbMATH DE number 3233336 (Why is no real title available?)
• A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree
• Almost giant clusters for percolation on large trees with logarithmic heights
• Analysis of the space of search trees under the random insertion algorithm
• Coalescent random forests
• Combinatorial stochastic processes. Ecole d'Eté de Probabilités de Saint-Flour XXXII -- 2002.
• Cutting down random trees
• Digital trees and memoryless sources: from arithmetics to analysis
• File structures using hashing functions
• Locally balanced binary trees
• Novel characteristics of split trees by use of renewal theory
• On the expected height of fringe-blanced trees
• Percolation on random recursive trees
• Probability: a graduate course
• Quad trees: A data structure for retrieval by composite keys
• Quicksort
• Random Trees
• Random graph dynamics
• Random graphs.
• Sizes of the largest clusters for supercritical percolation on random recursive trees
• Supercritical percolation on large scale-free random trees
• The existence of a giant cluster for percolation on large Crump–Mode–Jagers trees
• The total path length of split trees
• Universal Limit Laws for Depths in Random Trees

Cited in

(8)

• Sizes of the largest clusters for supercritical percolation on random recursive trees
• Voronoi cells in random split trees
• Finite size percolation in regular trees
• Random graphs: combinatorics, complex networks and disordered systems. Abstracts from the workshop held March 26--31, 2023
• The fluctuations of the giant cluster for percolation on random split trees
• Asymptotic behaviors for percolation clusters with uncorrelated weights
• Supercritical percolation on large scale-free random trees
• Almost giant clusters for percolation on large trees with logarithmic heights

This page was built for publication: The asymptotic distribution of cluster sizes for supercritical percolation on random split trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6074697)