On the peel number and the leaf-height of a Galton-Watson tree

We study several parameters of a random Bienaym'e-Galton-Watson tree $T_n$ of size $n$ defined in terms of an offspring distribution $\xi$ with mean $1$ and nonzero finite variance ${\sigma }^2$. Let $f(s)=\mathbf{E}\{s^{\xi }\}$ be the generating function of the random variable $\xi$. We show that the independence number is in probability asymptotic to $qn$, where $q$ is the unique solution to $q=f(1-q)$. One of the many algorithms for finding the largest independent set of nodes uses a notion of repeated peeling away of all leaves and their parents. The number of rounds of peeling is shown to be in probability asymptotic to $\log n\mathrm{/}\log (1\mathrm{/}{f}^{\mathrm{\prime }}(1-q))$. Finally, we study a related parameter which we call the leaf-height. Also sometimes called the protection number, this is the maximal shortest path length between any node and a leaf in its subtree. If $p_1=\mathbf{P}\{\xi =1\}>0$, then we show that the maximum leaf-height over all nodes in $T_n$ is in probability asymptotic to $\log n/\log(1/p_1)$\mathrm{.}If$p_1 = 0$and$\kappa$isthefirstinteger$i>1$with${\bf P}{\xi=i}>0$,thentheleaf-heightisinprobabilityasymptoticto$\log_\kappa\log n$.