Percolation on random recursive trees

Abstract

We study Bernoulli bond percolation on a random recursive tree of size $n$ with percolation parameter $p(n)$ converging to $1$ as $n$ tends to infinity. The sizes of the percolation clusters are naturally stored in a tree. We prove convergence in distribution of this tree to the genealogical tree of a continuous-state branching process in discrete time. As a corollary we obtain the asymptotic sizes of the largest and next largest percolation clusters, extending thereby a recent work of Bertoin (2014) which deals with cluster sizes in the supercritical regime. In a second part, we show that the same limit tree appears in the study of the tree components which emerge from a continuous-time destruction of a random recursive tree. We comment on the connection to our first result on Bernoulli bond percolation.

32 pages, 4 figures

References in corpus (2)

• The cut-tree of large Galton-Watson trees and the Brownian CRT
• Supercritical percolation on large scale-free random trees

Cited by in corpus (1)

• Random Recursive Trees and the Elephant Random Walk