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

DOI10.1002/RSA.21046zbMATH Open1522.05413arXiv2003.12018OpenAlexW3199358134MaRDI QIDQ6074697FDOQ6074697

Authors: Gabriel Berzunza, Cecilia Holmgren 

Publication date: 12 October 2023

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

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.

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

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

zbMATH Keywords

Poisson processescluster sizerandom treessplit treessupercritical bond-percolation

Mathematics Subject Classification ID

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

Cites Work

• Quicksort
• Title not available (Why is that?)
• Title not available (Why is that?)
• Combinatorial stochastic processes. Ecole d'Eté de Probabilités de Saint-Flour XXXII -- 2002.
• Random Trees
• Quad trees: A data structure for retrieval by composite keys
• Random graphs.
• Random graph dynamics
• Probability: a graduate course
• Locally balanced binary trees
• Sizes of the largest clusters for supercritical percolation on random recursive trees
• Cutting down random trees
• Coalescent random forests
• Title not available (Why is that?)
• File structures using hashing functions
• Digital trees and memoryless sources: from arithmetics to analysis
• 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
• Novel characteristics of split trees by use of renewal theory
• Percolation on random recursive trees
• A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree
• Analysis of the space of search trees under the random insertion algorithm
• Universal Limit Laws for Depths in Random Trees
• The total path length of split trees
• On the expected height of fringe-blanced trees
• Supercritical percolation on large scale-free 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)