1. Introduction
The independence number is a fundamental graph invariant that arises often in computational complexity theory and the analysis of algorithms. In a graph
$G = (V,E)$
, a subset
$S\subseteq V$
of vertices is said to be an independent set if no two elements of
$S$
are adjacent. The dual notion is that of a vertex cover, namely a subset
$C\subseteq V$
such that every edge in
$G$
has an endpoint in
$C$
. The independence number
$I(G)$
of
$G$
is defined to be the size of the largest independent set in
$G$
. In this paper, we concern ourselves with the case
$G=T$
, a random tree in the Bienaymé–Galton–Watson model. In recent years, analysis of the independence number of trees has been carried out for various other random models. C. Banderier, M. Kuba, and A. Panholzer studied various families of simply -generated trees [Reference Banderier, Kuba and Panholzer4], and a recent paper of M. Fuchs, C. Holmgren, D. Mitsche, and R. Neininger considers random binary search trees as well as random recursive trees [Reference Fuchs, Holmgren, Mitsche and Neininger13].
Because every tree
$T$
is bipartite, the independence number
$I(T)$
is always at least
$|T|/2$
(we take the larger element of the bipartition). Recall that a vertex set
$S$
is a vertex cover of
$T$
if every edge of
$T$
intersects a vertex in
$S$
. Letting
$V(T)$
denote the size of a minimum-cardinality vertex cover, we have the formula
$n=V(T) + I(T)$
. In a tree, there always exists a maximum-cardinality independent set that includes all of the leaves, and the following algorithm, which will be the starting point of our discussion, uses this fact to find an independent set of maximum size. Note that this is only one of many possible algorithms that accomplishes this task.
Algorithm I repeatedly peels away leaves and their parents to arrive at what we shall call the layered independent set. We refer to
$L(T)$
as layer 0, to
$P(T)$
as layer 1, to
$L(T \setminus L(T) \setminus P(T))$
as layer 2, and so on. In this manner, each node
$u$
gets assigned a peel number
$\rho (u)$
, the layer number of the set to which it belongs. The peel number
$\rho (T)$
of a tree
$T$
is the peel number of the root of
$T$
. We also let
$m(T)$
denote the maximum of the peel numbers of vertices in
$T$
; this quantity is twice the number of loops that Algorithm I undergoes before termination, rounded up. Note that all the peel numbers can be computed by postorder traversal of the tree in time
$O(|T|)$
, and then the layered independent set is simply the collection of all nodes with even peel number.
Algorithm 1 Independent set Given a directed tree
$T$
, this algorithm computes a maximum-cardinality independent set
$A$
of vertices.
A quantity related to the peel number is the leaf-height
$\lambda (u)$
of a node
$u\in T$
. It is the length of the path to the nearest leaf in the (fringe) subtree rooted at
$u$
. The leaf-height
$\lambda (T)$
of a tree
$T$
is the maximal leaf-height of any node in
$T$
. The fact that
$\rho (u) = k$
implies that there is a leaf at depth
$k$
from the root, so
$\lambda (u) \leq \rho (u)$
for all nodes
$u$
in a tree. It is also easily seen that for any tree
$T$
,
$\lambda (T) \leq \rho (T)\leq m(T)$
. A small example is given in Figure 1; note that for nodes with few children or small subtrees, the two quantities are quite similar. One corollary of our main results is that under certain conditions, this phenomenon persists as
$n$
gets large, that is, the peel number and leaf-height have the same order of asymptotic growth.
Figure 1. Peel numbers and leaf-heights of nodes in a unary-binary tree.
The leaf-height goes by the name protection number in the literature and has enjoyed some recent attention. With this usage, a node whose minimal distance from any leaf is
$k$
is called
$k$
-protected and a
$2$
-protected node is often simply said to be protected. In this paper, we say that a node has leaf-height
$k$
, which we believe is more illustrative than saying it is
$k$
-protected. The number of nodes with leaf-height
$\geq 2$
was examined by G.-S. Cheon and L. W. Shapiro for planted plane trees, Motzkin trees, full binary trees, Catalan trees, and ternary trees [Reference Cheon and Shapiro8]; by T. Mansour [Reference Mansour23] for
$k$
-ary trees; by R. R. X. Du and H. Prodinger for digital search trees [Reference Du and Prodinger10]; by H. M. Mahmoud and M. D. Ward for binary search trees [Reference Mahmoud and Ward21] and for random recursive trees [Reference Mahmoud and Ward22]; and by L. Devroye and S. Janson, who considered simply generated trees and also unified some earlier results regarding binary search trees and random recursive trees. Nodes with leaf-height
$\gt 2$
were studied in binary search trees by M. Bóna [Reference Bóna5] and in planted plane trees by K. Copenhaver [Reference Copenhaver9]. In the setting of simply generated trees and Pólya trees, the leaf-height of the root as well as the leaf-height of a node chosen uniformly at random was studied in [Reference Gittenberger, Gołȩbiewski, Larcher and Sulkowska14].
The main results of this paper characterise the asymptotic behaviour of the independence number
$I_n = I(T_n)$
, the maximum peel number
$M_n = m(T_n)$
, and the maximum leaf-height
$L_n = \lambda (T_n)$
for a Bienaymé–Galton–Watson tree
$T_n$
, which is conditioned on having
$n$
nodes. We also include distributional properties of closely related statistics, such as the peel number and leaf-height of the root of an unconditional Bienaymé–Galton–Watson tree, as well as the leaf-height
$L_n^{\prime}$
of the root and the leaf-height
$L_n^{\prime\prime}$
of a node chosen uniformly at random in a conditional Bienaymé–Galton–Watson tree.
The Bienaymé–Galton–Watson model. For a nonnegative integer-valued random variable
$\xi$
, a Bienaymé–Galton–Watson tree is a random tree in which every node has
$i$
children independently with probability
$p_i = \mathbb{P}\{\xi =i\}$
. The random variable
$\xi$
is called the offspring distribution of the tree; we only consider distributions with mean
$\mathbb{E}\{\xi \} =1$
and variance
$\mathbb{V}\{\xi \} = \sigma ^2 \in (0,\infty )$
(standard references include [Reference Athreya and Ney3] and [Reference Lyons and Peres20]). Let
$T_n$
denote the tree
$T$
, conditioned on having
$n$
nodes. Note that many important simply generated families of trees can be characterised by a conditional Bienaymé–Galton–Watson tree with a certain distribution [Reference Janson15]. Strictly speaking,
$T$
is a graph
$(V,E)$
, but we will abuse notation and write
$v\in T$
to indicate that
$v$
is in the vertex set of
$T$
.
2. The independence number
We begin by studying unconditional Bienaymé–Galton–Watson trees. Recall that the generating function
$f(s)$
of an offspring distribution
$\xi$
is the infinite series
$\mathbb{E}\{s^\xi \}$
, which converges absolutely when
$0\leq s\leq 1$
. We can thus differentiate to obtain
$f'(s) = \mathbb{E}\{\xi s^{\xi -1}\}$
. A quantity that will play a key role in our story is
$q$
, the unique solution in
$(0,1)$
of
$q = f(1-q)$
. This is illustrated in Figure 2.
Lemma 1.
Let
$\xi$
be an offspring distribution with
$0\lt \mathbb{E}\{\xi \} \leq 1$
and let
$f(s)=\mathbb{E}\{s^\xi \}$
. The probability that the root of a Bienaymé–Galton–Watson tree
$T$
with this distribution belongs to the layered independent set is
$q$
, which belongs to the interval
$(1/2,1)$
.
Proof. Note that
$q$
is the probability that all the children of the root are not in the layered independent set. By the recursive definition of a Bienaymé–Galton–Watson tree, we have
\begin{equation} q = \sum _{i\geq 0} p_i(1-q)^i = f(1-q), \end{equation}
and the Banach fixed-point theorem guarantees the uniqueness of the solution to
$s = f(1-s)$
in the compact interval
$[0,1]$
. Of course,
$q$
cannot be
$1$
since
$\mathbb{P}\{\xi = 0\}\neq 0$
. The fact that
$f(s) \gt s$
for all
$s\in (0,1)$
implies that
$q = f(1-q) \gt 1-q$
, hence
$q\gt 1/2$
.
Figure 2. The parameter
$q$
satisfying
$q = f(1-q)$
.
Lemma 1 is essentially known (see, e.g., Banderier, Kuba, and Panholzer [Reference Banderier, Kuba and Panholzer4]).
Example. There is a well-known connection between certain families of trees and conditioned Bienaymé–Galton–Watson trees. In each of the following cases, sampling a conditional Bienaymé–Galton–Watson tree
$T_n$
with the given distribution is equivalent to uniformly sampling a tree of size
$n$
from the respective tree family.
-
i) In Flajolet’s
$t$
-ary tree, every node is either a leaf or has
$t$
children. This corresponds to the distribution with
$p_0 = 1-1/t$
and
$p_t = 1/t$
, so we can compute
$q$
numerically by finding the unique solution to the equation(2)in the interval
\begin{equation} q = 1-{1\over t} +{(1-q)^t\over t}. \end{equation}
$(1/2,1)$
. In the case
$t=2$
of full binary trees, we find that
$q = 2-\sqrt 2 \approx 0.585786$
, and since the
$(1-q)^t/t$
term is very small for larger values of
$t$
,
$q$
is approximately
$1-1/t$
for large
$t$
.
-
ii) To obtain a random rooted Cayley tree, we set
$p_i = (i!e)^{-1}$
for all
$i\geq 0$
. Since
$f(s)=e^{s-1}$
, we have
$qe^q = 1$
, which we can invert in terms of the Lambert
$W$
function. Concretely, we have(3)which is also known as the omega constant.
\begin{equation} q = W(1) = \left (\int _{-\infty }^\infty{dt\over (e^t-t)^2 + \pi ^2}\right )^{-1} - 1 \approx 0.567143, \end{equation}
-
iii) Planted plane trees correspond to the distribution
$p_i = 1/2^{i+1}$
for
$i\geq 0$
. In this case,
$f(s) = 1/(2-s)$
, yielding the equation
$q^2+q-1 = 0$
, whose solution in the correct range is
$q=1/\varphi \approx 0.618034$
. (The golden ratio
$\varphi = 1.618034$
is the more famous solution to this quadratic equation). -
iv) Motzkin trees, also known as unary-binary trees, are trees in which every non-leaf node has either one tree or two children. This corresponds to the distribution
$p_0 = p_1 = p_2 = 1/3$
and
$p_i = 0$
for all
$i\geq 3$
. So we have
$q = (1 + (1-q) + (1-q)^2)/3$
and we have
$q = 3-\sqrt 6 \approx 0.550510$
. -
v) A binomial tree of order
$d$
can be thought of as a tree in which every node has
$d$
“slots” for its children, some of which may be filled. Thus, a node can have
$r$
children in
$\Big(\begin{array}{l} d \\[3pt] r \end{array}\Big)$
different ways, for
$0\leq r\leq d$
. This corresponds, fittingly, to a binomial offspring distribution, where(4)for
\begin{equation} p_i =\left(\begin{array}{l} d \\ i \end{array}\right) \left ({1\over d}\right )^i\left (1-{1\over d}\right )^{d-i}, \end{equation}
$0\leq i\leq d$
, and
$p_i = 0$
otherwise. For this distribution, we have
$f(s) = (s/n + 1- 1/n)^n$
, meaning that(5)For large
\begin{equation} q = \left (1-{1\over d} +{1-q\over d}\right )^d = \left (1-{q\over d}\right )^d. \end{equation}
$d$
, this tends to the omega constant. An important case is
$d=2$
, which produces a random Catalan tree; it can be readily computed that
$q = 4-2\sqrt 3\approx 0.535898$
for these trees.
The following theorem shows the link between
$q$
and the size of the largest independent set in a conditioned Bienaymé–Galton–Watson tree.
Theorem 2.
Let
$\xi$
be an offspring distribution with
$\mathbb{E}\{\xi \}= 1$
and let
$f(s)=\mathbb{E}\{s^\xi \}$
. The independence number
$I_n = I(T_n)$
of a Bienaymé–Galton–Watson tree, conditioned on having
$n$
nodes, satisfies
\begin{equation*} {I_n\over n} \to q \end{equation*}
in probability as
$n\to \infty$
, where
$q$
is the unique solution in
$(1/2,1)$
of the equation
$q=f(1-q)$
.
Proof. For a vertex
$u$
, we let
$\Gamma _u$
denote the set of children of
$u$
and let
\begin{equation} g(u) = \left \{\begin{array}{ll} 1,& \mathrm{if\ the\ peel\ number\ of}\ u\ \mathrm{is\ even};\\ 0,& \mathrm{otherwise}. \end{array}\right . \end{equation}
Note that the recursive function
\begin{equation} G(u) = g(u) + \sum _{v\in \Gamma _u} G(v) \end{equation}
is exactly the independence number of the subtree rooted at
$u$
. Since
$g$
is bounded, we can apply a result of S. Janson ([Reference Janson16], Theorem 1.3) to find that for a conditional Bienaymé–Galton–Watson tree
$T_n$
with root
$u$
,
\begin{equation}{I_n\over n} ={G(u)\over n} \to \mathbb{E}\left \{g(u)\right \} = q \end{equation}
in probability as
$n\to \infty$
.
Note that examples (ii), (iii), and the Catalan case agree with explicit computations given in [Reference Banderier, Kuba and Panholzer4]. For simply generated trees, that paper, which uses singularity analysis, derives the constant
$q$
in a different manner, proves the stronger statement
$\mathbb{E}\bigl \{I(T_n)\bigr \} = qn + O(1)$
, and also gives a formula for the variance in terms of the degree-weight generating function. In particular, they show there exists a constant
$\nu$
depending on the family of trees such that the variance is
$\nu n + O(1)$
.
3. Minimum-size
$s$
-path vertex covers
This section represents a brief digression and will not be related to our remaining results, though it discusses the natural generalisation of Algorithm I and is related to the open problem we give at the end of the paper. As mentioned in the introduction, the size
$V(T)$
of the minimal vertex cover of a
$T$
with
$n$
nodes has size
$n - I(T)$
, where
$I(T)$
is the independence number. In particular, Algorithm I outputs a minimum-cardinality vertex cover alongside the maximum-cardinality independent set; it is the set of all nodes with odd peel number. We now tackle a more general notion of vertex covers. For an integer
$s\geq 2$
, an
$s$
-path vertex cover of a rooted tree
$T$
is a subset
$C$
of vertices such that any path of length
$s-1$
in the tree contains a vertex in
$C$
. Thus, the common-or-garden vertex cover corresponds to
$s=2$
. (The off-by-one quirk in the definition goes away if we measure a path not by its length, but instead by its order, that is, the number of vertices it contains.) Note that only directed paths are considered, so two children of the same node are not connected by a path of length 2.
One might be tempted to generalise our earlier observations by claiming that the set of nodes with peel number congruent to
$s-1$
modulo
$s$
is a minimal
$s$
-path vertex cover. This is not true! Consider a tree in which the root has two children, and one of the children has itself one child. Then no node has peel number equal to
$2$
, but of course, the minimal
$3$
-path vertex cover consists of the root. Towards a correct generalisation, consider the fact that if in every loop of Algorithm I, we removed all subtrees of height exactly 1, then the roots of these removed subtrees are precisely the vertices with odd peel number. Thus, we arrive at an algorithm for computing a minimal
$s$
-path vertex cover.
Note that if the original tree had height less than
$s-1$
, the algorithm outputs the empty set, which is a valid cover, since there are no paths of length
$s-1$
in the tree. The fact that this algorithm actually does output a minimum-size vertex cover is proved in [Reference Brešar, Jakovac, Katrenič, Semanišin and Taranenko6], and it is also remarked that the algorithm can be made to run in
$O(|T|)$
time.
Let
$V_s(T)$
denote the size of the minimum
$s$
-path vertex cover of a Bienaymé–Galton–Watson tree
$T$
. To determine this random quantity, we will have to determine the probability that a node is added to the set
$C$
in Algorithm P. We will say that a vertex
$v\in T$
is “marked” if Algorithm P adds it to the cover
$C$
. The following lemma gives necessary and sufficient conditions for the root of a tree to be marked.
Lemma 3.
The root
$u$
of a tree is marked if and only if there exists a path of length
$s-1$
from the root that contains no marked vertices (other than the root).
Proof. Suppose that the root
$u$
is marked. This means that in the final iteration of Algorithm P, after all other marked nodes have been removed, the tree has height
$s-1$
. This means that some unmarked node
$v$
is at depth
$s-1$
, and no node is marked on the path to this node. (This happens when
$v$
is a leaf or all children of
$v$
are marked, since if a child of
$v$
is unmarked, then we have an unmarked path of length
$s$
in the tree and the algorithm would have to mark some node on this path before marking the root.) Conversely, if such a path exists, then Algorithm P will be in this state in the final iteration of the loop and will therefore mark the root.
Algorithm P Compute
$s$
-path vertex cover Given
$s\geq 2$
, and a rooted tree
$T$
, this algorithm computes a minimal
$s$
-path vertex cover
$C$
.
This observation can be used to derive a functional equation for the probability that a node in an unconditional Bienaymé–Galton–Watson tree is marked, as the following lemma shows.
Lemma 4.
Let
$T$
be a Bienaymé–Galton–Watson tree with offspring distribution
$\xi$
satisfying
$\mathbb{E}\{\xi \}\leq 1$
. Let
$f(z) = \mathbb{E}\{\xi ^z\}$
be the generating function of the distribution and let
\begin{equation} g(z, q) = 1-f\left (q+(1-q)z\right ) \end{equation}
The probability
$q_s$
that the root of the tree is in the minimum
$s$
-path vertex cover produced by Algorithm P satisfies
\begin{equation} q_s = g(g(\cdots (g(0,q_s)\cdots,q_s),q_s),q_s), \end{equation}
where the function
$g$
is iterated
$s-1$
times.
Proof. For
$1\leq j\lt s$
, let
$E_j$
be the event that in an unconditional Bienaymé–Galton–Watson tree, there is a path of length
$j$
from the root that contains no marked vertices (except possibly the root). Thus
$q_s = \mathbb{P}\{E_{s-1}\}$
. Restating things slightly,
$E_j$
is the probability that there exists an unmarked child
$v$
of the root in whose subtree
$E_{j-1}$
is true. If the degree of the root is
$i$
, then the probability that all the children of the root fail to have this property is
$\left (q_s + (1-q_s)\mathbb{P}\{E_{j-1}\}\right )^i$
, so for
$1\lt j\lt s$
,
\begin{equation} \mathbb{P}\{E_j\} = \sum _{i\geq 0} p_i\left (1-(q_s+(1-q_s)\mathbb{P}\{E_{j-1}\})^i\right )= 1-f\left (q_s+(1-q_s)\mathbb{P}\{E_{j-1}\}\right ). \end{equation}
Note that
$\mathbb{P}\{E_1\}$
is simply the probability
$1-f(q_s) = g(0, q_s)$
that one of the children of the root is unmarked, so unravelling the above equation proves the lemma.
Note that when
$s=2$
,
$q_s = 1-q$
, where
$q$
is the solution to
$z=f(1-z)$
we studied earlier. By a recursive computation analogous to the one we performed for the independence number, we find that if
$V_s(T_n)$
denotes the minimum size of an
$s$
-path vertex cover of the conditional Bienaymé–Galton–Watson tree
$T_n$
, then as
$n\to \infty$
,
\begin{equation}{V_s(T_n)\over n}\to q_s, \end{equation}
in probability. The function
$g$
given by Lemma 5 is rather unwieldy, so we cannot hope to find neat closed forms for the limit of
$V_s(T_n)$
like we did for
$I_n$
in many special cases. However, we can, in principle, use
$g$
to numerically approximate the
$s$
-path vertex cover number for arbitrary distributions satisfying
$\mathbb{E}\{\xi \} \leq 1$
.
4. Distribution of the peel number
Let
$r_i$
denote the probability that the root of an unconditional Bienaymé–Galton–Watson tree has peel number
$i$
. In this section, we shall compute the distribution
$(r_i)_{i\geq 0}$
. It will also be convenient to set
$r_i = 0$
when
$i$
is negative. We will establish the notation
\begin{equation} r^{+}_i= \sum _{j\geq i}r_j\qquad \hbox{and}\qquad r^{-}_i = \sum _{j=0}^i r_j\,. \end{equation}
Figure 3. Children of nodes with even and odd peel numbers.
There will be some asymmetry for odd and even
$i$
, so let us write
$r^{+\mathrm{odd}}_i$
for the subsum of
$r^{+}_i$
consisting of odd terms and
$r^{+\mathrm{even}}_i$
for the subsum of
$r^{+}_i$
consisting of even terms. Defining
$r^{-\mathrm{odd}}_i$
and
$r^{-\mathrm{even}}_i$
similarly, we have, of course,
$r^{+\mathrm{odd}}_i+r^{+\mathrm{even}}_i=r^{+}_i$
and
$r^{-\mathrm{odd}}_i + r^{-\mathrm{even}}_i = r^{-}_i$
. The situation is depicted in Figure 3.
Clearly,
$r_0 = p_0$
. For even indices
$j$
, all children must have an odd peel number at most
$j-1$
and at least one must have peel number
$j-1$
. Thus, if
$\xi$
is the number of children at the root, then for
$i\geq 1$
,
\begin{equation} r_{2i} = \mathbb{E}\left \{\left (r^{-\mathrm{odd}}_{2i-1}\right )^\xi -\left (r^{-\mathrm{odd}}_{2i-3}\right )^\xi \right \} = f\left (r^{-\mathrm{odd}}_{2i-1}\right ) - f\left (r^{-\mathrm{odd}}_{2i-3}\right ). \end{equation}
For odd indices
$j$
, all the children of the root with even peel number must have peel number at least
$j-1$
, and at least one must have peel number
$j-1$
. Since
\begin{equation} \sum _{i\geq 0} r_{2i-1} = 1-q\qquad \hbox{and}\qquad \sum _{i\geq 0} r_{2i} = q, \end{equation}
we find that for
$i\geq 1$
,
\begin{equation} r_{2i-1} = \mathbb{E}\left \{\left (1-q+r^{+\mathrm{even}}_{2i-2}\right )^\xi - \left (1-q+r^{+\mathrm{even}}_{2i}\right )^\xi \right \}. \end{equation}
The following lemma describes
$r_i$
for large
$i$
.
Lemma 5.
Let
$r_i$
be the probability that the root of an unconditional Bienaymé–Galton–Watson tree with offspring distribution
$\xi \sim (p_i)_{i\geq 0}$
has peel number equal to
$i$
. As
$i\to \infty$
, we have
\begin{equation} r_i = f'(1-q)^{i+o(i)}. \end{equation}
Proof. In the even case, we have
\begin{align} \begin{split} r_{2i} &= f\left (r^{-\mathrm{odd}}_{2i-1}\right ) - f\left (r^{-\mathrm{odd}}_{2i-3}\right ) \\[3pt] &\sim r_{2i-1}\sum _{j\geq 0} jp_j \left (r^{-\mathrm{odd}}_{2i-3}\right )^{j-1}\\[3pt] &= r_{2i-1} f'\left (r^{-\mathrm{odd}}_{2i-3}\right ), \end{split} \end{align}
which, since
$r^{-\mathrm{odd}}_{2i-3}\to 1-q$
, is asymptotic to
$r_{2i-1}f'(1-q)$
. Similarly, we have
\begin{equation} r_{2i-1} = f\left (r^{+\mathrm{even}}_{2i-2} + 1-q\right ) - f\left (r^{+\mathrm{even}}_{2i} + 1-q\right ) \sim r_{2i-2}\sum _{j\geq 0} jp_j(1-q)^{j-1}, \end{equation}
which is also asymptotic to
$r_{2i-2}f'(1-q)$
.
If
$N_i$
is the number of nodes in the
$i$
th layer for our algorithm, then Aldous’s theorem [Reference Aldous1] implies that for every fixed
$i$
,
\begin{equation}{N_i\over n}\to r_i \end{equation}
in probability. The number of nodes in the layers decreases at the indicated rate, namely
$f'(1-q)$
. As
$q\in (1/2,1)$
, we have
\begin{equation} p_1 = f'(0) \lt f'(1-q) \lt f'\left ({1\over 2}\right ) \leq \mathbb{E}\left \{{1\over 2^\xi }\right \}. \end{equation}
The next section will need the event that the maximum peel number in an unconditional tree occurs at the root. We have the following lemma.
Lemma 6.
Let
$T$
be an unconditional Bienaymé–Galton–Watson tree with offspring distribution
$\xi$
. Let
$R$
be the peel number of the root of such a tree and let
$M$
be the maximum peel number of any node in the tree. Let
$q$
be the solution to
$q=f(1-q)$
, where
$f$
is the reproduction generating function of this distribution. Then
\begin{equation} \tau _i := \mathbb{P}\{R = M = i\} = f'(1-q)^{i+o(i)} \end{equation}
as
$i\to \infty$
.
Proof. The fact that
$\tau _i \leq \mathbb{P}\{R = i\} = r_i = f'(1-q)^{i+o(i)}$
means that we only have to worry about finding a lower bound. To that end, consider the
$\xi$
children of the root (each the root of unconditional Bienaymé–Galton–Watson trees), with peel numbers
$R_1,\ldots,R_\xi$
and maximum peel numbers
$M_1,\ldots, M_\xi$
. We consider the odd and even cases separately.
When
$i$
is odd, the event that
$R=M=i$
is implied by the event that there exists some
$1\leq j\leq \xi$
with
$R_j = M_j = i-1$
and for all
$k\ne j$
, we have
$R_j$
odd and
$M_j\le i$
. Therefore, when
$i$
is odd, we have, by the inclusion–exclusion inequality,
\begin{equation} \tau _i \ge \mathbb{E}\left \{ \xi \cdot \tau _{i-1} \mathbb{P}\{R\ \hbox{odd},\, M\le i\}^{\xi -1}\right \}-\mathbb{E}\left \{ \left(\begin{array}{l} \xi \\ 2 \end{array}\right) \cdot{\tau _{i-1}}^2 \mathbb{P}\{R\ \hbox{odd},\, M\le i\}^{\xi -2}\right \}. \end{equation}
Note that
$\mathbb{P}\{R\ \hbox{odd},\,M\gt i\} = o(1)$
as
$i\to \infty$
, and so
\begin{align} \begin{split} \tau _i &\ge \mathbb{E}\left \{ \xi \cdot \tau _{i-1} \left (1-q-o(1)\right )^{\xi -1}\right \} -\mathbb{E}\left \{\left(\begin{array}{l} \xi \\ 2 \end{array}\right) \cdot{\tau _{i-1}}^2 \left (1-q-o(1)\right )^{\xi -2}\right \} \\ &= \tau _{i-1} f'\left (1-q-o(1)\right ) -{{\tau _{i-1}}^2\over 2} f''(1-q) \\ &\ge \tau _{i-1} f'\left (1-q-o(1)\right ) -{{\tau _{i-1}}^2 \sigma ^2\over 2}. \end{split} \end{align}
When
$i$
is even, the event that
$R=M=i$
is implied by the event that there exists some
$1\leq j\leq \xi$
with
$R_j=M_j =i-1$
and for all
$k\ne j$
, we have
$R_j$
odd,
$R_j\leq i-2$
, and
$M_j\leq i$
. With another application of the inclusion–exclusion inequality and by a similar argument as in the odd case, we have
\begin{align} \begin{split} \tau _i &\ge \mathbb{E}\left \{ \xi \cdot \tau _{i-1} \mathbb{P}\left \{R\le i-2,\,M\le i,\, R\ \hbox{odd}\right \}^{\xi -1}\right \}\\ &\quad - \mathbb{E}\left \{ \left(\begin{array}{l} \xi \\ 2 \end{array}\right) {\tau _{i-1}}^2 \mathbb{P}\left \{R\le i-2,\,M\le i,\, R\ \hbox{odd}\right \}^{\xi -2}\right \} \\ &\ge \tau _{i-1} f'\left (1-q-o(1)\right ) -{{\tau _{i-1}}^2\sigma ^2\over 2}. \end{split} \end{align}
In both the odd and even cases, we see that
$\tau _i\ge f'(1-q)^{i+o(i)}$
, completing the proof.
Using this result, we can give the following property of the distribution of the maximum peel number.
Lemma 7.
The maximum peel number
$M$
in an unconditional Bienaymé–Galton–Watson tree satisfies
\begin{equation} \mathbb{P}\{M\geq i\} = f'(1-q)^{i/2 + o(i)}, \end{equation}
as
$i\to \infty$
, where
$f$
is the reproduction generating function.
Proof. As before, let
$R_1,\ldots,R_\xi$
denote the peel numbers of children of the root and let
$M_1,\ldots, M_\xi$
denote the maximum peel numbers in their respective subtrees. Let
$\mu _i = \mathbb{P}\{M=i\}$
,
$\mu _i^- = \mathbb{P}\{M\le i\}$
, and
$\mu _i^+=\mathbb{P}\{M\ge i\}$
. The event that
$M\ge i$
is implied by the event
\begin{equation} \Big (\max _{1\le j\le \xi } M_j\ge i\Big )\ \mathrm{or}\ \Big (\max _{1\le j\le \xi }M_j\lt i\ \mathrm{and\ there\ is\ some}\ 1\le j\le \xi \ \mathrm{with}\ R_j=M_j=i-1\Big ). \end{equation}
Thus, letting
$E_j$
be the event that
$R_j=M_j=i-1$
, we have
\begin{equation} \mathbb{P}\{M\ge i\} \ge \mathbb{P}\left \{\max _{1\le j\le \xi } M_j\ge i\right \} + \mathbb{P}\left \{ \max _{1\le j\le \xi } M_j\lt i,\, \bigcup _{j=1}^\xi E_j\right \}. \end{equation}
Note first that
\begin{equation} \mathbb{P}\left \{\max _{1\le j\le \xi } M_j\ge i\right \} = 1 - \mathbb{E}\left \{(1-\mu _i^+)^\xi \right \} = 1-f(1-\mu _i^+). \end{equation}
By taking the Taylor series expansion of
$f$
around
$1$
, we have
\begin{equation} f(1-s) = f(1) - sf'(1)+{s^2\over 2} f''(\theta ) \end{equation}
for some
$1-s\le \theta \le 1$
, so that
\begin{equation} f(1-s) =1-s+{s^2\over 2}f''(\theta )\leq 1-s+{s^2\over 2}\sigma ^2 \end{equation}
and
\begin{equation} \mathbb{P}\left \{\max _{1\le j\le \xi } M_j\ge i\right \} \ge \mu _i^+ -{{{\mu _i^+}^2}\sigma ^2\over 2}. \end{equation}
Next, by the union bound, we have
\begin{align} \begin{split} \mathbb{P}\left \{ \max _{1\le j\le \xi } M_j\lt i,\, \bigcup _{j=1}^\xi E_j\right \} &= \mathbb{P}\left \{\bigcup _{j=1}^\xi E_j\right \} - \mathbb{P}\left \{\bigcup _{j=1}^\xi E_j,\, \max _{1\leq j\leq \xi } M_j\ge i\right \}\\[3pt] &= 1 - \mathbb{E}\left \{ (1-\tau _{i-1})^\xi \right \} - \mathbb{E}\left \{ \xi (\xi -1) \tau _{i-1}\mu _i^+\right \}\\[3pt] &= 1 - f(1-\tau _{i-1}) - \sigma ^2 \tau _{i-1}\mu _i^+\\[3pt] &\ge \tau _{i-1} -{{\tau _{i-1}}^2\sigma ^2\over 2} - \sigma ^2 \tau _{i-1}\mu _i^+. \end{split} \end{align}
Collecting these bounds back into (28), we have
\begin{equation} \mu _i^+ \ge \mu _i^+ + \tau _{i-1} -{{\mu _i^+}^2\sigma ^2\over 2} -{{\tau _{i-1}}^2\sigma ^2\over 2}-\sigma ^2 \tau _{i-1}\mu _i^+ \end{equation}
and therefore
\begin{equation}{\sigma ^2\over 2}{\mu _i^+}^2 \geq \tau _{i-1}(1-\sigma ^2\mu _i^+) -{{\tau _{i-1}^2\sigma ^2}\over 2}. \end{equation}
Let
$\phi (x)$
be a decreasing function that is
$o(1)$
as
$x\to \infty$
. We combine (35) with Lemma 7 to conclude that
\begin{equation}{\sigma ^2\over 2}{\mu _i^+}^2 \ge \tau _{i-1}\left (1-\phi (i)\right ) = f'(1-q)^{i+o(i)}. \end{equation}
To bound
$\mu _i^+$
from above, we observe that since the event that
$M\ge i$
is a subset of the event (27), we have
\begin{align} \begin{split} \mu _i^+ &\le 1-f(1-\mu _i^+) + \mathbb{E}\left \{ 1-(1-\tau _{i-1})^\xi \right \} \\ &\le \mu _i^+ -{{\mu _i^+}^2\over 2}\left (\sigma ^2+o(1)\right ) + \tau _{i-1} -{{\tau _{i-1}}^2\over 2} \left (\sigma ^2+o(1)\right ), \end{split} \end{align}
and therefore
\begin{equation}{\sigma ^2+o(1)\over 2}{\mu _i^+}^2 \leq \tau _{i-1} = f'(1-q)^{i+o(i)}, \end{equation}
which is what we need.
5. Asymptotics of the peel number
We are now ready to prove an asymptotic result for the peel number of
$T_n$
; that is, the maximum peel number over all nodes in
$T_n$
. This is the number of rounds of peeling required by Algorithm I to calculate a maximum-cardinality independent set. Our proof uses Kesten’s tree
$T_\infty$
, whose construction we shall briefly recall here (see [Reference Kesten18]). Fix an offspring distribution
$\xi$
with
$\mathbb{E}\{\xi \} = 1$
. Starting from the root, we attach
$\zeta$
children, where
$\mathbb{P}\{\zeta = i\} = ip_i$
for
$i\geq 0$
. Now select a child uniformly at random and mark it. We repeat the process at the marked child, while all other children become the roots of independent unconditional Bienaymé–Galton–Watson trees with the ordinary offspring distribution
$\xi$
. For a tree
$t$
, we let
$\tau (t,k)$
denote
$t$
, truncated to include only the first
$k$
levels. Letting TV denote total variation distance, it is well known (see [Reference Kersting17] and [Reference Stufler25]) that if
$k=o(\sqrt n)$
, then
\begin{equation} \lim _{n\to \infty } \mathrm{TV}\left (\tau (T_\infty,k), \tau (T_n,k)\right ) = 0. \end{equation}
Theorem 8.
Let
$M_n$
be the maximum peel number in
$T_n$
, a conditional Bienaymé–Galton–Watson tree on
$n$
nodes with offspring distribution
$\xi$
. Then
\begin{equation}{M_n\over \log n}\to{1\over \log \left (1/f'(1-q)\right )} \end{equation}
in probability, where
$f$
is the generating function of
$\xi$
.
Proof. For any tree
$t$
, let
$h(t)$
denote its height and
$m(t)$
its maximum peel number. For the lower bound, we employ Kesten’s limit tree
$T_\infty$
. Let
$S_k$
denote the set of nodes of
$T_\infty$
that are children of nodes on the spine of
$\tau (T_\infty,k)$
(i.e. nodes that are marked in the construction of
$T_\infty$
). Let
\begin{equation*} \alpha _n = \left \lfloor {\sqrt n\over \log ^2 n}\right \rfloor \qquad \mathrm {and}\qquad \beta _n = \left \lfloor {\sqrt n\over \log n}\right \rfloor . \end{equation*}
By the same result of [Reference Kersting17] and [Reference Stufler25] that we used before, we can find a coupling of
$\tau (T_n, \beta _n)$
and
$\tau (T_\infty, \beta _n)$
such that
\begin{equation} \mathbb{P}\left \{ \tau (T_n,\beta _n) \ne \tau (T_\infty,\beta _n)\right \} = o(1). \end{equation}
For every node
$u$
in
$T_\infty$
, let
$T_u$
be the subtree of
$T_\infty$
rooted at
$u$
. Let
$M_n = m(T_n)$
. Letting
$E_{ux}$
denote the event that
$m(T_u)\le x$
, we have
\begin{align} \begin{split} \mathbb{P}\{M_n\le x\} &\leq \mathbb{P}\left \{ \tau (T_n,\beta _n) \ne \tau (T_\infty,\beta _n)\right \} +\mathbb{P}\left \{ \bigcap _{u\in S_{\alpha _n}} E_{ux}\right \}\\ &\quad +\mathbb{P}\left \{\max _{u\in S_{\alpha _n}} h(T_u) \ge \beta _n-\alpha _n\right \}. \end{split} \end{align}
We already pointed out that
$\mathbb{P}\left \{ \tau (T_n,\beta _n) \ne \tau (T_\infty,\beta _n)\right \} = o(1)$
; we bound the other two terms by
\begin{align} \begin{split} \mathbb{P}\left \{ \bigcap _{u\in S_{\alpha _n}} E_{ux} \right \} &+\mathbb{P}\left \{\max _{u\in S_{\alpha _n}} h(T_u) \ge \beta _n-\alpha _n\right \}\\ &\le \mathbb{P}\left \{|S_{\alpha _n}| \leq{\sigma ^2 \alpha _n\over 2}\right \} + \mathbb{P}\left \{|S_{\alpha _n}| \geq{\sigma ^2 3\alpha _n\over 2}\right \}\\ &\quad + \mathbb{P}\left \{ m(T)\leq x\right \}^{\sigma ^2\alpha _n/2} +{2\sigma ^2\over 2}\alpha _n \mathbb{P}\left \{h(T)\geq \beta _n- \alpha _n\right \}, \end{split} \end{align}
where
$T$
is an unconditional Bienaymé–Galton–Watson tree. Now,
$S_{\alpha _n}/ (\sigma ^2\alpha _n)\to 1$
in probability by the law of large numbers, as the expected number of children of any node on the spine of
$T_\infty$
is
$\sigma ^2+1$
. So, the first two terms of (43) tend to zero. Next, we see that
\begin{equation} \mathbb{P}\left \{m(T)\le x\right \}^{\sigma ^2\alpha _n/2} = \left (1-\mathbb{P}\left \{m(T)\gt x\right \}\right )^{\sigma ^2\alpha _n/2} \leq \exp \!\left (-f'(1-q)^{x/2 + o(x)}{\sigma ^2\alpha _n \over 2}\right ), \end{equation}
which tends to zero if
$x = (1-\epsilon )\log n/\log \left (1/f'(1-q)\right )$
. For the final term, we have, by Kolmogorov’s theorem (see, e.g. [Reference Lyons and Peres20] or [Reference Alsmeyer2])
\begin{equation}{3\sigma ^2\alpha _n\over 2} \mathbb{P}\left \{h(T) \gt \beta _n-\alpha _n\right \} \sim{3\sigma ^2\over 2} \cdot{2\alpha _n\over \sigma ^2(\beta _n-\alpha _n)}\sim{3\alpha _n\over \beta _n} \sim{3\over \log n}, \end{equation}
which goes to zero. We have shown that
\begin{equation} \mathbb{P}\left \{ M_n \lt (1-\epsilon ){\log n\over \log \left (1/f'(1-q)\right )}\right \}\to 0 \end{equation}
for all
$\epsilon \gt 0$
.
For the upper bound we will again work with
$T_\infty$
, truncated to level
$\beta _n$
, but also require some further auxiliary definitions. Let
$u^*$
denote the unique node on the spine of
$T_\infty$
at distance
$\alpha _n$
from the root of
$T_n$
and let
$T_n^*$
be its subtree in
$T_n$
(the setup is illustrated in Figure 4). Let
$S$
be the set of children of nodes on the spine at distance
$\leq \alpha _n$
from the root. We then define
\begin{equation*} M_n^{\prime} = \max _{u\in S} \rho (u)\qquad \hbox {and}\qquad M_n^{\prime\prime} = \max _{u\in S} m(T_u). \end{equation*}
Figure 4. The proof uses Kesten’s infinite tree
$T_\infty$
for both bounds.
Next, we let
$S^*$
denote the set of nodes
$u$
on the spine with the property that all of
$u$
’s non-spine children have an odd peel number. In particular, let
$Y_n$
be the maximal number of consecutive nodes on the spine that are in
$S^*$
. Lastly, we let
$Y_n^*$
denote the number of consecutive nodes on the spine, starting at the parent of
$u^*$
, whose non-spine children all have an odd peel number. Assuming that
$\tau (T_n, \beta _n) = \tau (T_\infty,\beta _n)$
, we have the inequality
\begin{equation} m(T_n) \leq \max \left ( m(T_n^*), \rho (u^*)+Y_n^*, M_n^{\prime} + Y_n, M_n^{\prime\prime}\right ) \leq \max \left (m(T_n^*) + Y_n^*, 2M_n^{\prime}, 2Y_n, M_n^{\prime\prime}\right ). \end{equation}
To explain this, we note that nodes in
$S^*$
have a peel number that is at most one more than the peel numbers of their children on the spine. Nodes on the spine that are not in
$S^*$
have a peel number that is at most one more than the maximum peel number of any of their non-spine children (and this is bounded from above by
$M_n^{\prime}$
).
Let
$\epsilon \gt 0$
be given and let
$x = (1+\epsilon ) \log n/\log \left (1/f'(1-q)\right )$
. We have
\begin{align} \begin{split} \mathbb{P}\left \{ m(T_n)\ge x\right \} &\leq \mathbb{P}\left \{ \tau (T_n,\beta _n)\neq \tau (T_\infty, \beta _n)\right \} + \mathbb{P}\left \{ \max _{u\in S} h(T_u) \geq \beta _n - \alpha _n\right \} + \mathbb{P}\left \{Y_n^* \geq \sqrt{\log n}\right \}\\[3pt] &+ \mathbb{P}\left \{Y_n\geq x/2\right \} + \mathbb{P}\left \{ M_n^{\prime} \geq x/2\right \} + \mathbb{P}\left \{M_n^{\prime\prime} \geq x\right \} + \mathbb{P}\left \{m(T_n^*) \geq x-\sqrt{\log n}\right \}. \end{split} \end{align}
As noted in our proof of the lower bound, the first two terms are
$o(1)$
, so we have reduced our task to showing that the latter five terms are also
$o(1)$
.
Let
$\zeta$
be the offspring distribution of nodes on the spine (recall that
$\mathbb{P}\{\zeta = i\} = ip_i$
). For a node on the spine, the probability that it is in
$S^*$
is
\begin{equation} \mathbb{E}\left \{(1-q)^{\zeta -1}\right \} = \sum _{i\geq 0} ip_i (1-q)^{i-1} = f'(1-q). \end{equation}
Thus,
$Y_n^*$
is a geometric random variable with parameter
$1-f'(1-q)$
, and hence
\begin{equation} \mathbb{P}\left \{Y_n^*\geq \sqrt{\log n}\right \} = o(1). \end{equation}
Also,
$Y_n$
is bounded from above in distribution by the maximum of
$\alpha _n$
independent
$\mathrm{Geo}\left (f'(1-q)\right )$
random variables, so that
\begin{equation} \mathbb{P}\{Y_n\geq x/2\} \leq \alpha _n f'(1-q)^{x/2} = o(1). \end{equation}
Next,
\begin{equation} \mathbb{P}\{M_n^{\prime}\geq x/2\} \leq \mathbb{E}\left \{|S|\right \} \mathbb{P}\{R\geq x/2\}=\sigma ^2\alpha _n f'(1-q)^{x/2+o(x)}=o(1) \end{equation}
and
\begin{equation} \mathbb{P}\{M_n^{\prime\prime}\geq x\}\leq \mathbb{E}\left \{|S|\right \}\mathbb{P}\{M\geq x\}=\sigma ^2 \alpha _n f'(1-q)^{x/2+o(x)} = o(1). \end{equation}
This leaves us with the final term of (48). Observe that
$|T_n^*| = n-\alpha _n - \sum _{u\in S} |T_u|$
, which is at most
$n - \max _{u\in S} |T_u|$
. Thus,
\begin{align} \begin{split} \mathbb{P}\left \{|T_n^*|\geq n-{n\over \log ^5 n}\right \}&\leq \mathbb{P}\left \{\max _{u\in S} |T_u|\leq{n\over \log ^5 n}\right \}\\ &= \mathbb{E}\Bigg \{ \mathbb{P}\left \{|T|\leq{n\over \log ^5 n}\right \}^{|S|}\Bigg \} \\ &\le \mathbb{P}\left \{ |S|\leq{\sigma ^2\alpha _n\over 2}\right \} + \left (1-\mathbb{P}\left \{|T|\gt{n\over \log ^5 n}\right \}\right )^{\sigma ^2\alpha _n/2}. \end{split} \end{align}
Since, as noted earlier,
$|S|/(\sigma ^2\alpha _n)\to 1$
in probability and since
$\mathbb{P}\left \{|T|\ge n\right \}=\Theta (1/\sqrt n)$
, we have
\begin{align} \begin{split} \mathbb{P}\left \{|T_n^*|\geq n-{n\over \log ^5 n}\right \}&\leq o(1) + \exp \!\left (-\Theta \left ({\log ^{5/2} n\over \sqrt n}\right ){\sigma ^2\over 2}\alpha _n\right )\\ &\leq o(1) + \exp \left (-\Theta \left (\sqrt{\log n}\right )\right ), \end{split} \end{align}
which is
$o(1)$
. So
\begin{align} &\mathbb{P}\left \{ m(T_n^*) \geq x-\sqrt{\log n}\right \}\leq \max _{1\leq k \leq n-n/\log ^5 n} \mathbb{P}\left \{ m(T_n^*) \geq x - \sqrt{\log n} \Big |\, |T_n^*| = k\right \} \nonumber \\ &\ \ + \mathbb{P}\left \{ |T_n^*| \geq n-{n\over \log ^5 n}\right \}. \end{align}
Noting that given
$|T_n^*|=k$
,
$T_n^*$
is again a Bienaymé–Galton–Watson tree and letting
$F_k$
be the event that there exists a node
$v\in T_n$
with
$|T_v|\leq k$
and
$m(T_v) \geq x - \sqrt{\log n}$
, we see that
\begin{equation} \mathbb{P}\left \{ m(T_n^*) \geq x-\sqrt{\log n} \Big |\, |T_n^*|=k\right \} \leq \mathbb{P}\left \{ F_{n-n/\log ^5 n}\right \}. \end{equation}
Now define
$t(v)$
to be the subtree of
$v$
in the shifted preorder degree sequence
$\xi _v, \xi _{v+1}, \dots, \xi _n, \xi _1, \dots \xi _{v-1}$
. Let
$\rho (v)$
be the peel number of the root
$v$
of
$t(v)$
and let
$G_{vx}$
denote the event that
$\rho (v)\ge x-\sqrt{\log n}$
and
$|t(v)|\le n/\log ^5 n$
. We have
\begin{equation} \mathbb{P}\{M_n\ge x\} \leq \mathbb{P}\Bigl \{\bigcup _{v\in T_n} G_{vx}\Bigr \} + o(1). \end{equation}
Note that
$\max _{v\in T_n; |t(v)| \leq n/\log ^5 n} \rho (v)$
, is invariant under the cyclic shift of the preorder degree sequence. This rotational invariance, by Dwass’ device [Reference Dwass11], shows that
\begin{equation} \mathbb{P}\left \{\bigcup _{v\in T_n} G_{vx}\right \} ={\mathbb{P}\left \{ \bigcup _{v\in T_n} G_{vx},\, \sum _{1\leq i\leq n} (\xi _i - 1) = -1\right \}\over \mathbb{P}\left \{ \sum _{1\leq i\leq n} (\xi _i-1) = -1\right \}}, \end{equation}
where on the right-hand side, all probabilities are with respect to an i.i.d. sequence
$\xi _1,\ldots,\xi _n$
. We bound (59) from above by
\begin{equation} \mathbb{P}\left \{\bigcup _{v\in T_n} G_{vx}\right \} \leq n \cdot{\mathbb{P}\left \{ \rho (1) \geq x-\sqrt{\log n},\, |t(1)|\leq n/\log ^5 n,\, \sum _{i=1}^n (\xi _i-1) = -1\right \}\over \mathbb{P}\left \{ \sum _{i=1}^n (\xi _i-1) = -1\right \}}. \end{equation}
By conditioning on the size of
$t(1)$
, we obtain the further bound
\begin{equation*} \mathbb {P}\left \{\bigcup _{v\in T_n} G_{vx}\right \} \leq n\cdot \mathbb {P}\left \{\rho (1)\geq x-\sqrt {\log n}\right \} \cdot {\sup _{n/\log ^5 n \leq k\leq n} \mathbb {P}\left \{\sum _{i=1}^k (\xi _i- 1) = 0\right \} \over \mathbb {P}\left \{\sum _{i=1}^n(\xi _i-1) = -1\right \}}. \end{equation*}
By Kolchin’s estimate [Reference Kolchin19], the fraction is
$\Theta (1)$
, therefore,
\begin{equation*} \mathbb {P}\left \{\bigcup _{v\in T_n} G_{vx}\right \} \leq n f'(1-q)^{x+o(x)}, \end{equation*}
which goes to
$0$
if
$x = (1+\epsilon ) \log n/ \log \bigl (1-f'(1-q)\bigr )$
.
If, instead of removing leaves and parents at each step, we only remove leaves, then it is clear that the number of rounds needed to delete all nodes is simply the height of the tree. The height of random binary trees was studied by P. Flajolet and A. Odlyzko, who showed that in this case,
$H_n/\sqrt n$
converges in law to a theta distribution [Reference Flajolet and Odlyzko12]. Earlier, it was shown by N. G. de Bruijn, D. E. Knuth, and S. O. Rice that the expected height of a random planted plane tree is
$\sqrt{\pi n}+O(1)$
. It is interesting that deleting only leaves from
$T_n$
at each step requires
$\Theta \bigl (\sqrt n\bigr )$
rounds of deletion, but deleting leaves and their parents causes the number of rounds to decrease to
$\Theta (\log n)$
.
Examples. We apply Theorem 8 to calculate explicit asymptotics of the maximum peel number for the various families of trees mentioned earlier.
-
i.) Flajolet’s
$t$
-ary trees: We have
$f'(1-q) = 1-q$
and thus
$M_n/\log n \to 1/\log (1/(1-q))$
in probability. As
$t$
gets large,
$q$
approaches
$1-1/t$
, so that the limit of
$M_n/\log n$
is approximately
$1/\log t$
for large
$t$
. For the case of full binary trees when
$t=2$
, recall that
$q = 2 - \sqrt{2}$
and thus
$M_n/\log n \to -1/\log (\sqrt{2} - 1)$
in probability. -
ii.) Cayley trees: In this case,
$f'(1-q) = e^{-q}$
and hence
$M_n/\log n \to 1/q$
in probability; we know from earlier that
$q=W(1)$
, so
$1/q\approx 1.763223$
. -
iii.) Planted plane trees: We calculate
$f'(1-q) = 1/(q+1)^2$
. Recalling that
$q = 1/\varphi$
where
$\varphi = (\sqrt{5}-1)/2$
is the golden ratio, we have in probability
$M_n/\log n \to 1/\varphi ^2 \approx 0.381966$
. -
iv.) Motzkin trees: The derivative
$f'(1-q) = (3-2q)/3$
and substituting
$q = 3 - \sqrt{6}$
we get
$M_n/\log n \to 1/(\log 3 - \log (2\sqrt{6}-3)) \approx 2.186769$
. -
v.) Binomial trees: In this case, we have
$f'(1-q) = (1-q/d)^{d-1}$
. As
$d \to \infty$
, it is clear to see that
$M_n/\log n \to 1/W(1)$
in probability, matching the earlier calculation for Cayley trees above. For the special case
$d = 2$
of Catalan trees, we have
$f'(1-q) = 1-q/2$
and thus
$M_n/\log n \to -1/\log (\sqrt{3}-1)$
. This constant is greater than that we obtain for full binary trees above, which is consistent with intuitive reasoning about the maximal peel numbers of these trees.
6. Distribution of the leaf-height
We now repeat the treatment given in Section 4, but this time for the distribution
$(\ell _i)_{i\geq 0}$
, where for each
$i\geq 0$
,
$\ell _i$
denotes the probability that the root of an unconditional Bienaymé–Galton–Watson tree has leaf-height equal to
$i$
. Observe that
$\ell _0$
is exactly the probability
$p_0$
that the root has no children and in general, for a node
$u$
with children
$\Gamma _u$
the leaf-height
$\lambda (u)$
is
\begin{equation} \lambda (u) = \left \{\begin{array}{ll} 0,& \mathrm{if}\ u\ \mathrm{is\ a\ leaf};\\ \min _{v\in \Gamma _u}\lambda (v) + 1,& \mathrm{otherwise}. \end{array}\right . \end{equation}
We define
$\ell ^{+}_i$
and
$\ell ^{-}_i$
analogously to
$r^{+}_i$
and
$r^{-}_i$
:
\begin{equation} \ell ^{+}_i = \sum _{j\geq i}\ell _j\qquad \hbox{and}\qquad \ell ^{-}_i = \sum _{j=0}^i \ell _j\,; \end{equation}
since
$(\ell _i)_{i\geq 0}$
defines a distribution,
$\ell ^{+}_{i+1} + \ell ^{-}_i = 1$
for every
$i\geq 0$
. Letting
$E_i$
be the event that all the children of the root have leaf-height at least
$i$
, we have, for
$i\geq 1$
,
$\ell _i = \mathbb{P}\{E_{i-1}\} - \mathbb{P}\{E_i\}$
. We can then compute
\begin{equation} \ell _1 = 1-\mathbb{E}\left \{(1-\ell _0)^\xi \right \} = 1-f(1-\ell _0) = 1-f(1-p_0). \end{equation}
and, in general, for
$i\geq 1$
,
\begin{align} \begin{split} \ell _{i+1} &= \mathbb{P}\{E_i\} - \mathbb{P}\{E_{i+1}\} \\ &= \mathbb{E}\left \{(\ell ^{+}_i)^\xi \right \} - \mathbb{E}\left \{(\ell ^{+}_{i+1})^\xi \right \}\\ &= f(\ell ^{+}_i) - f(\ell ^{+}_{i+1})\\ &= f(1-\ell ^{-}_{i-1}) - f(1-\ell ^{-}_i). \end{split} \end{align}
By convexity of
$f$
, we see that
$\ell _i$
is nonincreasing, and this formula provides a fast method to compute the
$\ell _i$
recursively. The following lemma describes the behaviour of
$\ell _i$
as
$i$
gets large.
Lemma 9.
Let
$T$
be a Bienaymé–Galton–Watson tree with offspring distribution
$\xi \sim (p_i)_{i\geq 0}$
. If
$p_1 \neq 0$
, then
$\ell _i = (p_1 + o(1))^i$
. Otherwise if
$p_1 = 0$
and
$\kappa = \min \{i\gt 1:p_i\neq 0\}$
, then
\begin{equation} \log \ell _i = \Theta (\kappa ^i) \end{equation}
as
$i\to \infty$
.
Proof. The recursive formula above is our starting point. Expanding
$f$
as a power series, for
$i\geq 1$
we have, by our choice of
$\kappa$
,
\begin{align} \begin{split} \ell _{i+1} &= \sum _{j=0}^\infty p_j\left ((\ell ^{+}_i)^j - (\ell ^{+}_{i+1})^j\right ) \\ &= 0 + p_1(\ell ^{+}_i - \ell ^{+}_{i+1}) + \sum _{j\geq \kappa }p_j\left ((\ell ^{+}_i)^j - (\ell ^{+}_{i+1})^j\right )\\
&= p_1 \ell _i + p_\kappa \ell _i\left ((\ell ^{+}_i)^{\kappa -1} + (\ell ^{+}_i)^{\kappa - 2}(\ell ^{+}_{i+1})^{1} + \dots + (\ell ^{+}_{i+1})^{\kappa - 1}\right ) + \sum _{j\gt \kappa }p_j\left ((\ell ^{+}_i)^j - (\ell ^{+}_{i+1})^j\right ).\\ &\leq p_1\ell _i + \kappa p_\kappa \ell _i(\ell ^{+}_i)^{\kappa -1} + \sum _{j\gt \kappa } jp_j\ell _i(\ell ^{+}_i)^{j-1}\\ &\leq p_1\ell _i + \ell _i(\ell ^{+}_1)^{\kappa -1}\Big (\sum _{j\geq \kappa } jp_j\Big )\\ &=p_1\ell _i + \ell _i(1-p_0)^{\kappa -1}(1-p_1).
\end{split} \end{align}
Letting
$\alpha = p_1 + (1-p_1)(1-p_0)^{\kappa -1}\lt 1$
, we have
$\ell _{i+1} \leq \ell _i\alpha$
. Hence
$\ell _{i+1}\leq \ell _1\alpha ^i$
and therefore
$\ell _i\to 0$
as
$i\to \infty$
.
Let
$\epsilon \gt 0$
and pick
$n_\epsilon$
large enough such that
$\ell ^{+}_i\leq \epsilon$
for all
$i\geq n_\epsilon$
. When
$p_1\neq 0$
, we have
$\ell _ip_1\leq \ell _{i+1} \leq \ell _i(p_1+\epsilon ^{\kappa -1})$
, so we immediately conclude that
$\ell _i = \left (p_1+o(1)\right )^i$
. If
$p_1 = 0$
, then
\begin{align} \begin{split} \ell _{i+1}&\leq \kappa p_\kappa \ell _i(\ell ^{+}_i)^{\kappa -1} + \sum _{j\gt \kappa }jp_j\ell _i(\ell ^{+}_i)^{\kappa -1}(\ell ^{+}_i)^{j-\kappa }\\ &\leq \kappa p_\kappa \ell _i (\ell ^{+}_i)^{\kappa -1} \Big (1+\sum _{j\gt \kappa } jp_j\epsilon ^{j-\kappa }\Big )\\ &\leq \kappa p_\kappa \ell _i (\ell ^{+}_i)^{\kappa -1} \bigg (1+{\epsilon \over 1-\epsilon }\bigg )\\ &\leq \kappa p_\kappa \ell _i (\ell _i)^{\kappa -1} \Big (\sum _{j=0}^\infty \alpha ^j\Big )^{\kappa -1}\bigg ({1\over 1-\epsilon }\bigg )\\ &={\kappa p_\kappa \over (1-\alpha )^{\kappa - 1}(1-\epsilon )}{\ell _i}^\kappa . \end{split} \end{align}
From this and the fact that
$\ell _i\to 0$
, we see that for some positive constants
$c_1$
,
$c_2\lt 1$
, and
$c_3$
,
\begin{equation} \ell _i\leq c_1{c_2}^{\kappa ^{i-c_3}} \end{equation}
for all
$i\geq c_3$
. We also have
\begin{equation} \ell _{i+1} \geq \kappa p_\kappa \ell _i(\ell ^{+}_i)^{\kappa -1}\geq \kappa p_\kappa{\ell _i}^k, \end{equation}
so that for some positive constants
$c_1^{\prime}$
,
$c_2^{\prime}\lt 1$
, and
$c_3^{\prime}$
,
\begin{equation} \ell _i\geq c_1^{\prime}{c_2^{\prime}}^{\kappa ^{i-c_3^{\prime}}} \end{equation}
for all
$i\geq c_3^{\prime}$
. This proves that
$\log \ell _i = \Theta (\kappa ^i)$
. We finish the proof by noting that
$\ell ^{+}_i$
can be bounded in a similar manner.
7. Asymptotics of the leaf-height
In this section, we will describe the asymptotic behaviour of the leaf-height of a tree
$T_n$
(recall that this is the maximum of
$\lambda (v)$
, taken over all the nodes
$v\in T_n$
). The result depends on whether
$p_1$
is zero or nonzero, and we have split this into two lemmas, since both of the proofs are rather involved.
Lemma 10.
Let
$L_n$
be the leaf-height of
$T_n$
, a conditional Bienaymé–Galton–Watson tree on
$n$
nodes with offspring distribution
$\xi \sim (p_i)_{i\geq 0}$
. If
$p_1\neq 0$
, then
\begin{equation}{L_n\over \log n} \to{1\over \log (1/p_1)} \end{equation}
in probability.
Proof. Let
$Y_n$
be the length of the longest string, oriented away from the root, of nodes of degree one in
$T_n$
. Clearly
$L_n\geq Y_n$
, so we will first show that for
$\epsilon \gt 0$
,
\begin{equation*} \mathbb {P}\left \{Y_n\lt (1-\epsilon ) \log n/ \log (1/p_1)\right \}\to 0. \end{equation*}
Now,
$\mathbb{P}\{Y_n\lt x\}$
is the probability that a string of 1s appears in the preorder degree sequence of the tree
$(\xi _1, \xi _2, \ldots,\xi _n)$
, given that the sequence is of length
$n$
and that the sequence does, in fact, define a tree; as we have used previously, this latter probability is
$\Theta (n^{-3/2})$
, from Dwass [Reference Dwass11]. So letting
$Y_n(\xi _1,\xi _2,\ldots,\xi _n)$
be the length of the longest subsequence of 1s in the preorder degree sequence, we have
\begin{equation} \mathbb{P}\{Y_n\lt x\} = \Theta (n^{-3/2})\mathbb{P}\left \{Y_n(\xi _1,\xi _2,\ldots,\xi _n)\lt x\right \}. \end{equation}
We divide the sequence into
$n/x$
subsequences of length
$x$
each and let
$E_i$
be the event that the
$i$
th subsequence does not consist only of 1s. Then
\begin{equation} \mathbb{P}\left \{Y_n(\xi _1,\xi _2,\ldots,\xi _n)\lt x\right \} = \mathbb{P}\left \{\bigcup _{i=1}^{n/2} E_i\right \} = \mathbb{P}\{E_i\}^{n/2}. \end{equation}
Since
$\mathbb{P}\{E_i\} = 1-{p_1}^x$
for all
$i$
,
\begin{equation} \mathbb{P}\left \{Y_n(\xi _1,\xi _2,\ldots,\xi _n)\lt x\right \} = (1-{p_1}^x)^{n/x} \leq \exp \!\bigg (\!\!-\!{n{p_1}^x\over x}\bigg ). \end{equation}
When
$x = (1-\epsilon ) \log n/ \log (1/p_1)$
, this is equal to
$\exp (-n^\epsilon/x)$
, so
\begin{equation} \mathbb{P}\left \{L_n \lt (1-\epsilon ) \log n/ \log (1/p_1)\right \} \leq \mathbb{P}\left \{Y_n \lt (1-\epsilon ) \log n/ \log (1/p_1)\right \} \leq \Theta (n^{3/2})e^{-\Theta (n^\epsilon/\log n)}, \end{equation}
which goes to
$0$
as
$n\to \infty$
.
To tackle the upper bound, it will be helpful for us to reorder the degrees into level (also called breadth-first) ordering and to consider the following random variable. Arrange the level-order degree sequence
$\xi _1,\xi _2,\ldots,\xi _n$
in a cycle, and let
$Z_n$
be the longest string of consecutive nonzero numbers in this cyclic ordering. Clearly the probability that no sub-cycle of length
$x$
of this ordering consists only of zeroes is at most
$n(1-p_0)^x$
. So letting
$A$
be the event that
$(\xi _1,\xi _2,\ldots,\xi _n)$
defines a tree, we can crudely bound
$\mathbb{P}\{Z_n\geq x\}$
by
\begin{equation} \mathbb{P}\{Z_n\geq x\} ={\mathbb{P}\{Z_n\geq x,\,A\}\over \mathbb{P}\{A\}} \leq \Theta (n^{3/2})n(1-p_0)^x=\Theta (n^{5/2})(1-p_0)^x, \end{equation}
which goes to zero if
$c \gt (5/2)/\log \left (1/(1-p_0)\right )$
and
$x$
is set to
$c\log n$
. By symmetry, if
$Z_n$
is the longest string of nonzeros in the preorder listing, then the same result holds, that is,
\begin{equation} \mathbb{P}\left \{Z_n\geq{3\log n\over \log \left (1/(1-p_0)\right )}\right \}\to 0. \end{equation}
Note that
$L_n\leq Z_n$
. Now for
$1\leq \Delta \leq n$
let
$L_n(\xi _1,\xi _2,\ldots,\xi _\Delta )$
be the smallest leaf depth if we start constructing a tree using degrees
$\xi _1,\xi _2,\ldots,\xi _\Delta$
, in preorder. Two situations can occur: either
$\xi _1,\xi _2,\ldots,\xi _\Delta$
defines at least one tree in a possible forest or
$\xi _1,\xi _2,\ldots,\xi _\Delta$
defines an incomplete tree. In the former case,
$L_n(\xi _1,\xi _2,\ldots,\xi _\Delta )$
is the leaf-height of the first completed tree; in the latter, set
$L_n(\xi _1,\xi _2,\ldots,\xi _\Delta ) = 0$
. Note that if
$Z_n\leq \Delta$
, then
$L_n(\xi _1,\xi _2,\ldots,\xi _\Delta )\leq \Delta$
. For a sequence
$\xi _1,\xi _2,\ldots,\xi _n$
of degrees, we define
\begin{equation} L_{ni} = L_n(\xi _i,\xi _{i+1}\ldots,\xi _{i+\Delta -i}), \end{equation}
where addition in the indices is taken modulo
$n$
. If
$Z_n\leq \Delta$
, note that
$L_n\leq \max _{1\leq i\leq n} L_{ni}$
. So we have
\begin{align} \begin{split} \mathbb{P}\{L_n\gt x\} &\leq \mathbb{P}\{L_n\gt x,\,Z_n\leq \Delta \} + \mathbb{P}\{Z_n\gt \Delta \} \\[3pt] &\leq \mathbb{P}\left \{\max _{1\leq i\leq n} L_{ni}\gt x,\,Z_n\leq \Delta \right \} + \mathbb{P}\{Z_n\gt \Delta \}\\[3pt] &\leq \mathbb{P}\left \{\max _{1\leq i\leq n} L_{ni}\gt x\right \} + \mathbb{P}\{Z_n\gt \Delta \}. \end{split} \end{align}
The second term is
$o(1)$
if we pick
$c \gt (5/2)/\log \left (1/(1-p_0)\right )$
as before and set
$\Delta = c\log n$
. In the first term, the maximum is invariant under rotations of
$(\xi _1,\xi _2,\ldots,\xi _n)$
, so we use may use a version of the cycle lemma [Reference Dwass11], obtaining
\begin{align} \begin{split} \mathbb{P}\left \{\max _{1\leq i\leq n} L_{ni}\gt x\right \} &={\mathbb{P}\left \{\max _{1\leq i\leq n} L_{ni}\gt x,\,\sum _{i=1}^n\xi _i=n-1\right \}\over \mathbb{P}\left \{\sum _{i=1}^n\xi _i=n-1\right \}}\\[3pt] &\leq{\mathbb{P}\left \{\max _{1\leq i\leq n} L_{ni}\gt x,\,\sum _{i=\Delta +1}^n\xi _i=n-1-\sum _{i=1}^\Delta \xi _i\right \}\over \Theta (n^{-1/2})}\\[3pt] &\leq O(n^{3/2})\sup _\ell \mathbb{P}\left \{L_{n1}\gt x,\,\sum _{i=\Delta +1}^n\xi _i=\ell \right \}\\ &= O(n^{3/2})\cdot \mathbb{P}\{L_{n1}\gt x\}\cdot \sup _\ell \,\mathbb{P}\left \{\sum _{i=\Delta +1}^n\xi _i=\ell \right \}. \end{split} \end{align}
Rogozin’s inequality [Reference Rogozin24] tells us that
\begin{equation} \sup _\ell \,\mathbb{P}\Biggl \{\sum _{i=\Delta +1}^n\xi _i=\ell \Biggr \} \leq{\gamma \over \sqrt{1-\Pi }}\cdot{1\over \sqrt{n-\Delta }}, \end{equation}
where
$\gamma$
is a universal constant and
$\Pi = \sup _j p_j$
. So if
$L(T)$
is the leaf-height of the root of an unconditional Bienaymé–Galton–Watson tree, then
\begin{equation} \mathbb{P}\{L_n\gt x\} \leq O(n) \mathbb{P}\{L_{n1}\gt x\}\leq O(n)\mathbb{P}\{L(T)\gt x\}\leq O(n)\ell ^{+}_x\leq O(n)\left (p_1+o(1)\right )^x, \end{equation}
which goes to 0 when
$x = (1+\epsilon )\log n/\log (1/p_1)$
.
The next lemma handles the other case, in which
$p_1$
is zero.
Lemma 11.
Let
$L_n$
be the leaf-height of
$T_n$
, a conditional Bienaymé–Galton–Watson tree on
$n$
nodes with offspring distribution
$\xi \sim (p_i)_{i\geq 0}$
. Let
$\kappa = \min \{i\gt 1: p_i\neq 0\}$
. If
$p_1 = 0$
, then
\begin{equation}{L_n\over \log \log n} \to{1\over \log \kappa } \end{equation}
in probability.
Proof. Let
$\epsilon \gt 0$
,
$A$
be the event that
$(\xi _1,\xi _2,\ldots,\xi _n)$
forms a tree and let
$L_n(\xi _1,\xi _2,\ldots,\xi _n)$
be as in the previous lemma. If
$L(T)$
is the leaf-height of the root of an unconditional Bienaymé–Galton–Watson tree
$T$
, we have, by the cycle lemma,
\begin{align} \begin{split} \mathbb{P}\{L_n\geq x\} &={\mathbb{P}\left \{L_n(\xi _1,\xi _2,\ldots,\xi _n)\geq x,\, A\right \}\over \mathbb{P}\{A\}} \\[3pt] &\leq \Theta (n^{3/2}) \mathbb{P}\left \{L_n(\xi _1,\xi _2,\ldots,\xi _n)\geq x\right \} \\[3pt] &\leq \Theta (n^{3/2}) n\mathbb{P}\{L(T)\geq x\} \\[3pt] &\leq \Theta (n^{5/2}) c_1 c_2 ^{\kappa ^{x-c_3}}, \end{split} \end{align}
for some positive constants
$c_1$
,
$c_2\lt 1$
, and
$c_3$
. When
$x = (1+\epsilon )\log _\kappa \log n$
, this is
$\Theta (n^{5/2}) c_2^{\Theta ((\log n)^{1+\epsilon })}$
, which goes to
$0$
as
$n\to \infty$
.
Let
$T_\infty$
be Kesten’s infinite tree. Our proof of the lower bound, which the reader may find easier to follow by consulting the illustration in Figure 5, uses the fact that
\begin{equation} \mathbb{P}\left \{\tau (T_\infty, n^{1/3})\neq \tau (T_n,n^{1/3})\right \}\to 0 \end{equation}
as
$n\to \infty$
. Let
$U$
be the set of all unconditional Bienaymé–Galton–Watson trees
$T$
rooted less than
$n^{1/4}$
of the way down the spine. Let
$h(T)$
denote the height of an unconditional Bienaymé–Galton–Watson tree; the probability that one of these trees has height greater than
$n^{1/3}/2$
is bounded above by
\begin{equation} \mathbb{E}\left \{|U|\right \}\mathbb{P}\left \{h(T)\gt n^{1/3}\right \} \leq \sigma ^2n^{1/4} \bigg ({2+o(1)\over \sigma ^2n^{1/3}/2}\bigg )\sim{4\over n^{1/12}}, \end{equation}
which goes to
$0$
. Here we used the fact that
$\mathbb{E}\{\zeta \} = \sigma ^2+1$
and applied Kolmogorov’s result (see [Reference Lyons and Peres20] and [Reference Alsmeyer2]) about the height of a Bienaymé–Galton–Watson tree. If all the heights above are at most
$n^{1/3}/2$
, then
$T_n^*$
, the tree obtained by taking the spine up to level
$n^{1/4}$
and all hanging unconditional trees up to that point, is a subtree of
$\tau (T_\infty, n^{1/3})$
, since
$n^{1/4} + n^{1/3}/2 \lt n^{1/3}$
.
Figure 5. The construction in the lower bound. Note that none of the unconditional trees in
$T_n^*$
reach level
$n^{1/3}$
.
For every tree
$t\in U$
, let
$E_t$
be the event that the leaf-height of the root of
$t$
is less than
$x$
and let
$E_T$
be the same event for an unconditional Bienaymé–Galton–Watson tree (since each
$t$
in
$U$
is such a tree, there is no real moral distinction between these events). We have
\begin{align} \begin{split} \mathbb{P}\{L_n\lt x\}&\leq \mathbb{P}\left \{\tau (T_\infty )\neq (T_n,n^{1/3})\right \} + \mathbb{P}\left \{T_n^*\neq (T_n,n^{1/3})\right \}+ \mathbb{P}\left \{\bigcap _{t\in U} E_t\right \} \\[3pt] &\leq o(1) + \mathbb{E}\left \{ \mathbb{P}\{E_T\}^{|U|}\right \}\\[3pt] &\leq o(1) + \mathbb{E}\left \{ \left (1-c_{1}^{\prime }\cdot c_2^{\prime \kappa{^{x-c_3^{\prime}}}}\right )^{|U|}\right \}\\[3pt] &\leq o(1) + \mathbb{E}\left \{ \left (1-c_{1}^{\prime }\cdot c_2^{\prime \kappa{^{x-c_3^{\prime}}}}\right )^{n^{1/4}\sigma ^2/2}\right \}+\mathbb{P}\left \{|U|\lt{n^{1/4}\sigma ^2\over 2}\right \}, \end{split} \end{align}
for some
$c_1^{\prime},c_2^{\prime},c_3^{\prime}$
positive,
$c_2^{\prime}\lt 1$
. Take
$x = (1-\epsilon )\log _\kappa \log n$
. Letting
$\zeta _1,\zeta _2,\ldots,\zeta _n$
be independent and distributed as
$\zeta$
, we find that
\begin{equation} \mathbb{P}\{L_n\lt x\}\leq o(1) + \exp \!\left (-\Theta (n^{1/4}e^{-\Theta ((\log n)^{1-\epsilon })})\right ) + \mathbb{P}\left \{\sum _{i=1}^{n^{1/4}} (\zeta _i - 1) \lt{n^{1/4}\sigma ^2\over 2}\right \}. \end{equation}
Since
$\mathbb{E}\{\zeta -1\} = \sigma ^2$
, by the law of large numbers, this entire expression is
$o(1)$
.
It is important to note that the node with maximum leaf-height in a tree usually is not the root. We have the following result for the distribution of the leaf-height of the root of a conditional Bienaymé–Galton–Watson tree
$T_n$
.
Lemma 12.
Let
$L_n^{\prime}$
denote the leaf-height of the root of
$T_n$
, a conditional Bienaymé–Galton–Watson tree of size
$n$
, and offspring distribution
$\xi$
. Let
$f$
be the generating function of this distribution. Then the probability distribution of
$L_n^{\prime}$
is given by
\begin{equation} \lim _{n\to \infty }\mathbb{P}\{L_n^{\prime} = i\} = \prod _{j=0}^{i-1}f'(\ell ^{+}_j). \end{equation}
Proof. For a node
$v$
on the spine of Kesten’s infinite tree
$T_\infty$
, let
$H^*$
be the leaf-height of the spine child of
$v$
, and
$H(1),H(2),\ldots,H(\zeta -1)$
be the leaf-heights of the
$\zeta -1$
independent unconditional Bienaymé–Galton–Watson trees spawned by
$v$
. Then the leaf-height of a node
$v$
on the spine is
\begin{equation} 1+\min _{w\in \Gamma _v} \lambda (w) = 1+\min \left (H(1), H(2),\ldots,H(\zeta -1)\right ). \end{equation}
This defines a Markov chain on the positive integers that proceeds up the spine. The state
$H^*$
(which is just a positive integer indicating the leaf-height of the node on the spine) is taken to the state
\begin{equation} 1+\min \!\left (H^*, H(1), H(2), \ldots,H(\zeta -1)\right ) \end{equation}
in one step of the Markov chain; here all
$H_i$
have distribution
$(\ell _i)_{i\geq 0}$
. Let
$H^{**}$
be the limit stationary random variable of this Markov chain. That the limit exists and that the chain is positive recurrent follows from the fact that at each step, there is a positive probability that the next state is
$1$
. This happens when
$\zeta \gt 1$
and one of
$H(i)$
is 0. In fact,
$H^{**}$
is the unique solution of the distributional identity
\begin{equation} H^{**} \stackrel{\mathcal{L}}{=} 1 + \min \left (H^{**}, H(1), H(2),\ldots,H(\zeta -1)\right ). \end{equation}
Broutin, Devroye, and Fraiman showed that under a coalescence condition (satisfied here), the limit of the root value of
$T_n$
tends in distribution to the stationary random variable for Kesten’s spinal Markov chain [Reference Broutin, Devroye and Fraiman7]. Thus
$L_n^{\prime}\to H^{**}$
in distribution.
We can describe the distribution of
$H^{**}$
more explicitly. For convenience, let
$\ell ^{\ast \ast }_i = \mathbb{P}\{H^{**}=i\}$
. For
$i\geq 1$
,
\begin{equation} \ell ^{\ast \ast }_i = \mathbb{P}\{H_j \geq i+1\ \hbox{for all}\ 1\leq j\leq \zeta -1\}\mathbb{P}\{H^{**}\geq i-1\}. \end{equation}
This means that
\begin{equation} \ell ^{\ast \ast }_i = \ell ^{\ast \ast }_{i-1}\mathbb{E}\left \{(\ell ^{+}_{i-1})^{\zeta -1}\right \}=\ell ^{\ast \ast }_{i-1}\sum _{j\geq 1}jp_j (\ell ^{+}_{i-1})^{j-1}, \end{equation}
and we can rewrite this in terms of the generating function
$f(s)$
of
$\xi$
as
\begin{equation} \ell ^{\ast \ast }_i = \ell ^{\ast \ast }_{i-1} f'(\ell ^{+}_{i-1}) = \ell ^{\ast \ast }_0\prod _{j=0}^{i-1}f'(\ell ^{+}_j) = \prod _{j=0}^{i-1}f'(\ell ^{+}_j), \end{equation}
proving the lemma.
Lastly, we can obtain a random variable by taking the leaf-height of a node chosen uniformly at random from
$T_n$
. Its distribution is asymptotically the same as the leaf-height of the root of an unconditional Bienaymé–Galton–Watson tree.
Lemma 13.
Let
$L_n^{\prime\prime}$
be a random variable obtained by taking the leaf-height of a node chosen uniformly at random from a conditional Bienaymé–Galton–Watson tree
$T_n$
. We have
\begin{equation} \lim _{n\to \infty }\mathbb{P}\{L_n^{\prime\prime} = i\} = \ell _i \end{equation}
for all
$i\geq 0$
.
Proof. By Aldous’s theorem [Reference Aldous1], if
$T_n^*$
denotes the subtree of
$T_n$
rooted at a uniformly selected random node, then for all trees
$t$
,
\begin{equation} \lim _{n\to \infty } \mathbb{P}\{T_n^*=t\} = \mathbb{P}\{T = t\}, \end{equation}
where
$T$
is the unconditional Bienaymé–Galton–Watson tree. The result is immediate.
Examples. We now apply Lemmas 10 and 11 to compute the maximum leaf-height (asymptotically in probability) for common families of trees. These results, along with the independence numbers and maximum peel numbers we computed earlier, are collected in Table 1. In the table,
$W$
denotes the Lambert function and
$\varphi = (\sqrt{5}-1)/2$
is the golden ratio.
Table 1 Asymptotic values of parameters for certain families of trees
-
i) Flajolet’s
$t$
-ary trees: For
$t\geq 2$
, we have
$p_1 = 0$
here and
$\kappa = t$
, so we have
$L_n/\log \log n \to 1/\log t$
in probability, by Lemma 13. -
ii) Cayley trees: In this case,
$p_1 = 1/e$
, so Lemma 12 gives us
$L_n/\log n \to 1$
in probability. -
iii) Planted plane trees: For these trees,
$p_1 = 1/4$
, so we have
$L_n/\log n \to 1/\log 4$
in probability, by Lemma 12. -
iv) Motzkin trees: This family has
$p_1 = 1/3$
and
$L_n/\log _n \to 1/\log 3$
in probability. -
v) Binomial trees: For a parameter
$d\geq 2$
, we have
$p_1 = (1-1/d)^{d-1}$
, which means that Ł
$_n/\log n \to 1/((1-d)\log (1-1/d))$
in probability. As
$d\to \infty$
, the denominator approaches
$1$
, which gives the same leaf-height as the case of Cayley trees. In the special case when
$d=2$
, we have the Catalan trees, for which
$p_1 = 1/2$
and
$L_n/\log n \to 1/\log 2$
in probability.
8. Further directions
The definition of the peel number and our characterisation of its asymptotic growth fully describes the running time of Algorithm I, mentioned in the introduction, which computes the layered independent set. It would be interesting to consider the runtime of the more general Algorithm P, described in Section 3. To this end, we define higher-order peel numbers as follows. Algorithm P generates an
$(r+1)$
-path vertex cover by repeatedly deleting subtrees with height exactly
$r$
(and marking their roots). If a node
$u$
is deleted in the
$m$
th iteration of the loop and is at depth
$i$
of the subtree that is deleted, then its peel number of order
$r$
(or
$r$
th order peel number) is
$mk-i$
. Note that the loop counter
$m$
should start at
$1$
and we have
$0\leq i\leq r$
. By this definition, the peel number we studied in this paper is simply the first-order peel number. To determine the runtime of Algorithm P, one should in principle be able to approach the higher order peel numbers in the same way we approached the case
$r=1$
in Sections 4 and 5. However, even in this case one had to handle the even and odd cases separately, and we anticipate that the analysis of higher-order peel numbers will require careful reasoning with respect to congruence modulo
$r+1$
.
Acknowledgements
All three authors are supported by the Natural Sciences and Engineering Research Council of Canada (NSERC). We also thank Anna Brandenberger for wonderful discussions and for her valuable technical feedback. Last but not least, we owe a debt of gratitude to the anonymous referees for their careful reading of our paper and for their detailed and insightful comments.
