The asymptotic non-normality of the giant cluster for percolation on random split trees
Preprint
Abstract
A split tree of cardinality $n$ is constructed by distributing $n$ "balls" (which often represent "key numbers") in a subset of vertices of an infinite tree. In this work, we study Bernoulli bond percolation on arbitrary split trees of large but finite cardinality $n$. We show for appropriate percolation regimes that depend on the cardinality $n$ of the split tree that there exists a unique giant cluster that is of size comparable of that of the entire tree (where size is defined as either the number of vertices or the number of balls). The main result shows that in such percolation regimes, also known as supercritical regimes, the fluctuations of the size of the giant cluster are non-Gaussian as $n \rightarrow \infty$. Instead, they are described by an infinitely divisible distribution that belongs to the class of stable Cauchy laws. This work is a generalization of the results for the random $m$-ary recursive trees due to Berzunza, which is one specific case of split trees. Other important examples of split trees include $m$-ary search trees, quad trees, median-of-$(2k+1)$ trees, fringe-balanced trees, digital search trees and random simplex trees. Our approach is based on a remarkable decomposition of the size of the giant percolation cluster as a sum of essentially independent random variables which allows us to apply a classical limit theorem for the convergence of triangular arrays to infinitely divisible distributions. This may be of independent interest and it may be useful for studying percolation on other classes of trees with logarithmic height, for instance in this work we study also the case of regular trees.
Keywords
All Related Versions
This publication has 31 references indexed in Scilit:
- Asymptotic normality of the size of the giant component in a random hypergraphRandom Structures & Algorithms, 2012
- Sizes of the largest clusters for supercritical percolation on random recursive treesRandom Structures & Algorithms, 2012
- A limiting distribution for the number of cuts needed to isolate the root of a random recursive treeRandom Structures & Algorithms, 2008
- Limiting distributions for additive functionals on Catalan treesTheoretical Computer Science, 2004
- On the internal path length ofd-dimensional quad treesRandom Structures & Algorithms, 1999
- Coalescent Random ForestsJournal of Combinatorial Theory, Series A, 1999
- On the expected height of fringe-balanced treesActa Informatica, 1993
- Analysis of the space of search trees under the random insertion algorithmJournal of Algorithms, 1989
- On the average internal path length of m-ary search treesActa Informatica, 1986
- Quad trees a data structure for retrieval on composite keysActa Informatica, 1974