License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AofA.2020.6
URN: urn:nbn:de:0030-drops-120361
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12036/
Go to the corresponding LIPIcs Volume Portal

Berzunza, Gabriel ; Holmgren, Cecilia

Largest Clusters for Supercritical Percolation on Split Trees

pdf-format:
LIPIcs-AofA-2020-6.pdf (0.4 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{berzunza_et_al:LIPIcs:2020:12036,
  author =	{Gabriel Berzunza and Cecilia Holmgren},
  title =	{{Largest Clusters for Supercritical Percolation on Split Trees}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{6:1--6:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-147-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{159},
  editor =	{Michael Drmota and Clemens Heuberger},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12036},
  URN =		{urn:nbn:de:0030-drops-120361},
  doi =		{10.4230/LIPIcs.AofA.2020.6},
  annote =	{Keywords: Split trees, random trees, supercritical bond-percolation, cluster size, Poisson measures}
}

Keywords: Split trees, random trees, supercritical bond-percolation, cluster size, Poisson measures
Collection: 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
Issue Date: 2020
Date of publication: 10.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI