Almost giant clusters for percolation on large trees with logarithmic heights (Q2854070)

For a function \(\ell\) such that \(\lim_{x\to\infty}\ell(x)=+\infty\) and arbitrary \(c\geq 0\), put \(p(n):=1-c/\ell(n)+o(1/\ell(n))\). In a random tree with the root \(0\) and other vertices \(1,\dots,n\), keeping each edge with probability \(p(n)\) and deleting with probability \(1-p(n)\), independently of the other edges, splits the tree into connected components called clusters. Denote by \(C_{p(n)}^0\) the size of the cluster which contains the root and by \(C_{p(n)}^1\geq C_{p(n)}^2\geq \dots\) the sizes of the other clusters, ranked in nonincreasing order.NEWLINENEWLINEIn the first part of the paper, the author proves a criterion for \(\lim_{n\to\infty} n^{-1}C_{p(n)}^0= G\) in distribution, for a random variable \(G\) which is not identically zero. Further, a specialization of this result is given for the situation when the limit law is degenerate. Also, a sufficient condition is found under which \(\lim_{n\to\infty}n^{-1}C_{p(n)}^0=G\) in distribution, whereas \(\lim_{n\to\infty}n^{-1}C_{p(n)}^1=0\) in probability.NEWLINENEWLINEThe second part of the paper is a survey of the results obtained by the author [Random Struct. Algorithms 44, 29--44 (2014)] and the author and \textit{G. Uribe Bravo} [Ann. Appl. Probab. (to appear)]. These concern the asymptotic behavior of the largest clusters in random recursive trees and scale-free random trees. It turns out that \(C^0_{p(n)}\) is of order \(\text{const}\times n\) for explicitly known non-random constants, whereas each \(C_{p(n)}^j\) for \(1\leq j\leq k\) and fixed \(k\), grows like \(n/\log n\).