# Targeted cutting of random recursive trees

Laura Eslava  Instituto de Investigaciones en Matemáticas Aplicadas y en
Sistemas, Universidad Nacional Autónoma de México.  Sergio I. López  Facultad
de Ciencias, Universidad Nacional Autńoma de México.  Marco L. Ortiz  Facultad
de Ciencias, Universidad Nacional Autńoma de México.

###### Abstract

We propose a method for cutting down a random recursive tree that focuses on
its higher degree vertices. Enumerate the vertices of a random recursive tree
of size $n$ according to a decreasing order of their degrees; namely, let
$(v^{(i)})_{i=1}^{n}$ be so that $\deg(v^{(1)})\geq\cdots\geq\deg(v^{(n)})$.
The targeted, vertex-cutting process is performed by sequentially removing
vertices $v^{(1)}$, $v^{(2)},\ldots,v^{(n)}$ and keeping only the subtree
containing the root after each removal. The algorithm ends when the root is
picked to be removed. The total number of steps for this procedure,
$X_{n}^{targ}$, is upper bounded by $Z_{\geq D}$, which denotes the number of
vertices that have degree at least as large as the degree of the root. We
obtain that the first order growth of $X_{n}^{targ}$ is upper bounded by
$n^{1-\ln 2}$, which is substantially smaller than the required number of
removals if, instead, the vertices where selected uniformly at random. More
precisely, we prove that $\ln(Z_{\geq D})$ grows as $\ln(n)$ asymptotically
and obtain its limiting behavior in probability. Moreover, we obtain that the
$k$-th moment of $\ln(Z_{\geq D})$ is proportional to $(\ln(n))^{k}$.

##  1 Introduction

Random recursive trees (abbreviated as RRTs ) are rooted trees, where each
vertex has a unique label, obtained by the following procedure: Let $T_{1}$ be
a single vertex labeled $1$. For $n>1$ the tree $T_{n}$ is obtained from the
tree $T_{n-1}$ by adding a edge directed from a new vertex labeled $n$ to a
vertex with label in $\\{1,...,n-1\\}$, chosen uniformly at random and
independent for each $n$. We say that $T_{n}$ has size $n$ and that the degree
of a vertex $v$ is the number of edges directed towards $v$.

The idea of cutting random recursive trees was introduced by Meir and Moon
[27]. They studied the following procedure: Start with a random recursive tree
on $n$ vertices. Choose an edge at random and remove it, along with the cut
subtree that does not contain the root. Repeat until the remaining tree
consists only of the root; at which point, we say that the tree has been
deleted. Let $X_{n}$ be the number of edge removals needed to delete a RRT
with $n$ vertices.

By a recursive approach using that the remaining tree after one deletion has
itself the distribution of a RRT of smaller, random size, Meir and Moon proved
that the expectation of $X_{n}$ grows asymptotically as $\frac{n}{\ln(n)}$.
Panholzer [28] proposed an extension of this procedure: to study the total
cost of the algorithm until deletion; which is the sum of the costs at every
step where cutting an edge of a tree of size $n$ has a cost of $n^{c}$ for
some non negative constant $c$ (the original cutting corresponds to $c=0$). By
the use of generating functions and recursion, they obtained the asymptotic
behavior for the $k$-moment of the total cost and proved, as a corollary, that
$\frac{\ln(n)}{n}X_{n}$ converges to one, in probability. Iksanov and Möhle
[19] obtained the expression of $X_{n}$ up to its random order; namely, that

$\displaystyle Y_{n}:=\frac{(\ln(n))^{2}}{n}X_{n}-\ln(n)-\ln(\ln(n))$ (1)

converges weakly to a random variable $Y$ with characteristic function given
by

$\varphi_{Y}(\lambda):=\exp\Big{\\{}i\lambda\ln|\lambda|-\frac{\pi|\lambda|}{2}\Big{\\}}.$

Their proof is based on the construction of a coupling of $X_{n}$ with the
first passage time of certain random walk; while Drmota et al. [15] give a
proof of this theorem using recursive methods.

In this work we consider random recursive trees and propose a cutting
procedure that corresponds to a targeted cutting (focused on high-degree
vertices). We first present our model together with the main result, we then
overview the proof strategy and discuss some possible interpretations of this
procedure and several related models of tree-deletion.

To define the targeted cutting, let $T_{n}$ be a RRT of size $n$ and enumerate
its vertices as $(v^{(i)})_{i=1}^{n}$ according to a decreasing order of their
degrees; that is, $\deg(v^{(1)})\geq\cdots\geq\deg(v^{(n)})$, breaking ties
uniformly at random. The targeted vertex-cutting process is performed by
sequentially removing vertices $v^{(1)}$, $v^{(2)},\ldots,v^{(n)}$ and keeping
only the subtree containing the root after each removal (skip a step if the
chosen vertex had been previously removed). The procedure ends when the root
is picked to be removed. Let $X^{targ}_{n}$ denote the number of vertex
deletions before we select the root to be removed.

Our main theorem is an stochastic upper bound for the deletion time. In doing
so, we analyse the number of vertices with degree as large as that of the
root; see Section 1.1.

######  Theorem 1.1.

The random number of cuts $X_{n}^{targ}$ in the targeted cutting of $T_{n}$
satisfies, for any $\varepsilon>0$,
$X_{n}^{targ}=O_{p}(n^{\gamma+\varepsilon})$ where $\gamma:=1-\ln 2$. Namely,
for each $\delta>0$, there is $M=M(\varepsilon,\delta)>0$ and
$N=N(\varepsilon,\delta)\in\mathbb{N}$ such that for all $n\geq N$,

$\displaystyle{\mathbf{P}}\left(X_{n}^{targ}>Mn^{\gamma+\varepsilon}\right)<\delta.$
(2)

Theorem 1.1 gives a precise answer to an expected outcome: the targeted
cutting deletion time is significantly smaller compared to the deletion time
for uniformly random removals.

In the next section we provide precise statements on a random upper bound for
$X_{n}^{targ}$ from which Theorem 1.1 follows.

###  1.1 A random tail of the degree sequence

For $d\in\mathbb{N}$, we let $Z_{d}$ and $Z_{\geq d}$ be the number of
vertices in $T_{n}$ that have degree $d$ and degree at least $d$, respectively
(we omit the dependence in $n$ for these variables throughout). The asymptotic
joint distribution of $(Z_{d})_{d\geq 0}$ is described by the limiting
distribution, as $n\to\infty$, of certain urn models in [20], while the
limiting joint distribution of $(Z_{\geq
d+\lfloor\log_{2}n\rfloor})_{d\in\mathbb{Z}}$ is described (along suitable
subsequences) by an explicit Poisson point process in
$\mathbb{Z}\cup\\{\infty\\}$ in [2]; the lattice shift by $\log_{2}n$ steams
from the fact that $\Delta_{n}/\log_{2}n$, the renormalized maximum degree in
$T_{n}$, converges a.s. to 1 [13]. In contrast, the degree of the root in
$T_{n}$ is asymptotically normal with mean $\ln n$ (note that
$\log_{2}n\approx 1.4\ln n$).

In this paper we are interested in the random variable $Z_{\geq D}$, which
corresponds to the number of vertices that have degree at least the degree of
the root of $T_{n}$, henceforth denoted by $D=D(n)$. The techniques developed
in [16] provide bounds on the total variation distance between $Z_{\geq c\ln
n}$ and a Poisson random variable with mean $n^{\alpha}$ with a suitable
$\alpha=\alpha(c)$ for $c\in(1,\log_{2}n)$. However, there is far less control
over the random variables $Z_{\geq c\ln n}$ for $c\leq 1$ [2]. The following
two theorems provide precise statements to back up the informal approximation
$Z_{\geq D}\sim n^{1-\ln 2}$.

######  Theorem 1.2.

Let $\gamma:=1-\ln(2)$, the following convergence in probability holds

$\dfrac{\ln(Z_{\geq D})}{\ln(n)}\stackrel{{\scriptstyle
p}}{{\longrightarrow}}\gamma.$

######  Theorem 1.3.

Let $\gamma:=1-\ln(2)$. For any positive integer $k$,

$\displaystyle{\mathbf{E}}\left[\big{(}\ln\left(Z_{\geq
D}\right)\big{)}^{k}\right]=\big{(}\gamma\ln\left(n\right)\big{)}^{k}\left(1+o(1)\right).$

Theorem 1.1 follows immediately from Theorem 1.2.

###### Proof of Theorem 1.1 assuming Theorem 1.2.

Since the removal of vertices is done accordingly to their degree, $Z_{\geq
D}$ gives us the worst-case destruction time for the targeted cutting
procedure; that is, $X^{targ}_{n}\leq Z_{\geq D}$ a.s.. It then follows that
(2) is satisfied, for $\varepsilon,\delta>0$, by letting
$M(\varepsilon,\delta)=1$ and $N$ large enough that ${\mathbf{P}}\left(Z_{\geq
D}\geq n^{\gamma+\varepsilon}\right)<\delta$, for $n\geq N$. ∎

The proof of Theorem 1.2 is based on the concentration of $D$ and the first
and second moment method, see Section 2. Unfortunately, the tails of $D$ do
not vanish as fast as a naive bounding of the moments of $Z_{\geq D}$ would
require by the current control we have on the distribution of $Z_{\geq d}$ for
$d\sim\ln n$ (see (8) and Propositions 2.1 and 2.2, respectively). Instead, to
establish Theorem 1.3, we resort to a coupling between a random recursive tree
$T_{n}$ of size $n$ and a random recursive tree $T_{n}^{(\varepsilon)}$ of
size $n$ conditioned on $D$ to take values in
$((1-\varepsilon)\ln(n),(1+\varepsilon)\ln(n))$, for any given
$\varepsilon\in(0,1)$, see Section 3.

Briefly described, the coupling is the following. Let $n\in\mathbb{N}$, for
the construction of both $T_{n}$ and $T_{n}^{(\varepsilon)}$ it suffices to
define the parent of vertex $i$, for each $1<i\leq n$. For each tree, we break
down this choice in two steps: First sample a random Bernoulli to decide
whether $i$ attaches to the root or not. Then the parent of $i$ is either the
root or a uniformly sampled vertex among the rest of the possible parents. The
Bernoulli variables are coupled in such a way that $T_{n}$ is constructed by
independent variables while the Bernoulli random variables related to the tree
$T_{n}^{(\varepsilon)}$ imply the conditioning on $D$ taking values in the
aforementioned interval. On the other hand, if a given vertex chooses a parent
distinct from the root, then this choice is exactly the same for both the
unconditioned and conditioned tree.

###  1.2 Discussion on related models

Cutting processes of random trees and graphs can serve as a proxy to the
resilience of a particular network to breakdowns, either from intentional
attacks or fortuitous events. What is considered a breakdown and resilience
may differ depending on the context. In the first cutting procedure,
introduced by Meir and Moon for random recursive trees [27]: it considers
contamination from a certain source within an organism and one may think of
the number of cuts as the necessary steps to isolate the source of the
contamination.

Janson [21], noted that the number of cuts needed to destroy a tree is
equivalent to the number of records that arises from a random labeling of the
edges, this approach is further used by Holmgren [17, 18] to study split trees
and binary search trees, respectively.

Several modifications of the uniform edge deletion process have been proposed
by different authors. Javanian and Vahini-Asl [23] modified the process with
the objective of isolating the last vertex added to the network. Kuba and
Panholzer [24, 25, 26] published a series of articles focusing specifically on
isolating a distinguished vertex; for example, the isolation of a leaf or
isolating multiple distinguished vertices.

In the context of Galton-Watson trees, cutting down trees has been
predominantly studied from the perspective of vertex-cutting. That is,
vertices are selected to be removed, rather than edges, and once a vertex has
been removed, we keep the subtree containing the root; the procedure is
repeated until the root is removed. Note that selecting an edge uniformly at
random is equivalent to uniformly selecting a vertex other than the root.
Bertoin and Miermont [5] constructed a method to compare vertex-cutting versus
edge cutting and studied the tree destruction process. Addario-Berry et al.
[1] studied the case of Galton-Watson trees with critical, finite-variance
offspring distribution, conditioned to have a fixed number of total progeny.
Dieuleveut [14] modified the vertex-cutting process so that the probability of
a given vertex to be cut, at each step, is proportional to its degree. This
process was generalized by Cai et al. [10] by considering that every vertex
can stand $k$ attacks before being removed. This generalization was later
studied by Berzunza et al. [7] for deterministic trees and by Berzunza et al.
[6] for conditioned Galton-Watson trees.

Similar cutting procedures have been studied in more general graphs. To name a
few, Berche et al. [4] studied public transport networks; Xu et al. [29]
studied a broad range of dynamical processes including birth-death processes,
regulatory dynamics and epidemic processes on scale free graphs and Erdös-
Renyi networks under two different targeted attacks, with both high-degree and
low-degree vertices; Alenazi and Sterbenz [3] compared different graph
metrics, such as node betweenness, node centrality and node degree, to measure
network resilience to random and directed attacks.

As we mentioned before, what is considered a breakdown and resilience may
differ depending on the context. In the internet, for example, the failures of
connectivity that happen over time can be modeled by random cuts, while
malicious attacks, from a hacker or enemy trying to disconnect some given
network of servers, can be mathematically described by targeted cutting
towards highly connected servers. These ideas on resilience were posed by
Cohen et al. [11, 12] for scale free graphs. Later, Bollobás and Riordan [8]
compared random versus malicious attacks on scale free graphs. Since malicious
attacks may hold an strategy to better take advantage of some characteristics
of the network, it is expected that the number of cuts required would be
significantly fewer than in a completely random attack.

For scale-free networks Cohen et al. [12] obtained the next result. Assume the
degree of a uniformly random vertex of the graph follows a power law with
decay $\alpha$ on the support $m,\dots,n$. If a proportion $p$ of the vertices
with the highest degree is deleted, then the probability $\bar{p}$ of a
randomly chosen node to connect to a deleted vertex is roughly approximated by
$p^{\frac{2-\alpha}{1-\alpha}}$, for $\alpha>2$. In the case $\alpha=2$ the
approximation of $\bar{p}$ is given by $\ln\Big{(}\frac{np}{m}\Big{)}$. This
result supports the intuition of needing a small proportion of vertices to be
removed in a targeted attack to delete a network.

###  1.3 Notation

We use $|A|$ to denote the cardinality of a set $A$. For $n<m\in\mathbb{N}$ we
write $[n]:=\\{1,2,\dots,n\\}$ and $[m,n]=\\{m,m+1,\ldots,n\\}$. For
$a,b,c,x\in\mathbb{R}$ with $b,c>0$, we use $x\in(a\pm b)c$ as an abbreviation
for $(a-b)c\leq x\leq(a+b)c$. In what follows we denote natural and base $2$
logarithms by $\ln(\cdot)$ and $\log(\cdot)$, respectively. We often use the
identity $\ln(a)=\ln(2)\log(a)$ for $a>0$.

For $r\in\mathbb{R}$ and $a\in\mathbb{N}$ define
$(r)_{a}:=r(r-1)\cdots(r-a+1)$ and $(r)_{0}=1$. For real functions $f,g$ we
write $f(x)=o(g(x))$ when $\lim_{x\to\infty}f(x)/g(x)=0$ and $f(x)=O(g(x))$
when $|f(x)/g(x)|\leq C$ for some $C>0$. The convergence in probability will
be written as $\stackrel{{\scriptstyle p}}{{\longrightarrow}}$. A rooted tree
is a tree with a distinguished vertex, which we call the root. We always
consider the edges to be directed towards the root. A directed edge $e=uv$ is
directed from $u$ to $v$ and, in this case, we will say that $v$ is the parent
of $u$. Given a rooted tree $T$ and one of its vertices $v$, the degree of $v$
in $T$, denoted by $d_{T}(v)$, is the number of edges directed towards $v$. We
say that $T$ has size $n$ if it has $n$ vertices, and $[n]$ will denote the
set of vertices of a tree of size $n$.

##  2 Deterministic tails of the degree sequence

Given a random recursive tree $T_{n}$, let $Z_{\geq d}$ denote the number of
vertices with degree at least $d$, that is

$\displaystyle Z_{\geq d}\equiv Z_{\geq
d}(n):=\big{|}\\{v\in[n]:d_{T_{n}}(v)\geq d\\}\big{|}.$ (3)

Our theorems build upon results on the convergence of the variables $Z_{\geq
d}$ since, they are non-increasing on $d$ and $Z_{\geq D}$ is a tail of the
degree sequence with random index; recall that $D=D(n)$ denotes the degree of
the root of $T_{n}$. The following two propositions are simplified versions of
Proposition 2.1 in [2] and Theorem $1.8$ in [16], respectively.

######  Proposition 2.1 (Moments of $Z_{\geq d}$).

For any $d\in\mathbb{N}$, ${\mathbf{E}}\left[Z_{\geq d}\right]\leq
2^{\log(n)-d}$. Moreover, there exists $\alpha>0$ such that if
$d<\frac{3}{2}\ln(n)$ and $k\in\\{1,2\\}$ then

$\displaystyle{\mathbf{E}}\left[(Z_{\geq d})_{k}\right]$
$\displaystyle=(2^{\log(n)-d})^{k}(1+o(n^{-\alpha})),$ (4)
$\displaystyle{\mathbf{E}}\left[Z_{\geq d}^{2}\right]$
$\displaystyle={\mathbf{E}}\left[Z_{\geq
d}\right]^{2}\big{(}1+o(n^{-\alpha})\big{)}.$ (5)

######  Proposition 2.2 (Total variation distance).

Let $0<\varepsilon<\frac{1}{3}$, then for
$(1+\varepsilon)\ln(n)<d<(1+3\varepsilon)\ln(n)$ there exists
$\alpha^{\prime}=\alpha^{\prime}(\varepsilon)>0$ such that

$\mathrm{d}_{\mathrm{TV}}(Z_{\geq d},\mathrm{Poi}({\mathbf{E}}\left[Z_{\geq
d}\right]))\leq O(n^{-\alpha^{\prime}}).$

As we mentioned before, the error bounds in the previous propositions are not
strong enough to estimate the moments of $Z_{\geq D}$. Instead we focus on the
variable $\ln(Z_{\geq D})$. Furthermore, we will transfer the task of moment
estimation, for Theorem 1.3, to ${\mathbf{E}}\left[(\ln X)^{\ell}\right]$
where instead of having $X=Z_{\geq D}$ we consider either $1+Z_{\geq m_{-}}$
or $1+Z_{\geq m_{+}}$ for suitable values $m_{\pm}=c_{\pm}\ln n$ with
$c_{-}<1<c_{+}$.

The upper bound in the following proposition follows from a straightforward
application of Jensen’s inequality, together with Proposition 2.1; while the
lower bound uses the refined bounds given in Proposition 2.2.

######  Proposition 2.3.

Let $\varepsilon\in(0,\frac{1}{3})$ and $\ell\in\mathbb{N}$. Let
$m_{-}:=\lfloor(1-\frac{\varepsilon}{2\ln(2)})\ln(n)\rfloor$,
$m_{+}:=\lceil(1+\frac{\varepsilon}{2\ln(2)})\ln(n)+1\rceil$. There exist
$\alpha^{\prime}=\alpha^{\prime}(\varepsilon)>0$ and
$C_{\ell}=C_{\ell}(\varepsilon)>0$ such that

$\displaystyle{\mathbf{E}}\left[\big{(}\ln\left(1+Z_{\geq
m_{-}}\right)\big{)}^{\ell}\right]$
$\displaystyle\leq\left[\big{(}1-\ln(2)+\varepsilon\big{)}\ln(n)\right]^{\ell}+C_{\ell},$
(6) $\displaystyle{\mathbf{E}}\left[\big{(}\ln\left(1+Z_{\geq
m_{+}}\right)\big{)}^{\ell}\right]$
$\displaystyle\geq\left[\left(1-\ln(2)-\varepsilon\right)\ln(n)\right]^{\ell}\left(1-O(n^{-\alpha^{\prime}})\right).$
(7)

###### Proof.

First, let $f(x)=(\ln(x))^{\ell}$ and note that $f^{\prime\prime}(x)\leq 0$
for $x>e^{\ell-1}$. Hence, by Jensen’s inequality, for any non negative random
variable $X$ it holds

${\mathbf{E}}\left[(\ln(X))^{\ell}\right]={\mathbf{E}}\left[(\ln(X))^{\ell}\mathbf{1}_{\\{X>e^{\ell-1}\\}}\right]+{\mathbf{E}}\left[(\ln(X))^{\ell}\mathbf{1}_{\\{X\leq
e^{\ell-1}\\}}\right]\leq(\ln({\mathbf{E}}\left[X\right]))^{\ell}+(\ell-1)^{\ell}.$

Next we will use the upper bound in Proposition 2.1 for
${\mathbf{E}}\left[Z_{\geq m_{-}}\right]$. Note that
$\log(n)-m_{-}\leq(1-\ln(2)+\frac{\varepsilon}{2})\log(n)$. Thus,
${\mathbf{E}}\left[1+Z_{\geq m_{-}}\right]\leq
1+2n^{1-\ln(2)+\frac{\varepsilon}{2}}\leq n^{1-\ln(2)+\varepsilon}$; where the
second inequality holds for $n_{0}=n_{0}(\varepsilon)$ large enough. Then

$\displaystyle{\mathbf{E}}\left[\left(\ln(1+Z_{\geq
m_{-}})\right)^{\ell}\right]$
$\displaystyle\leq\left[\ln\left({\mathbf{E}}\left[1+Z_{\geq
m_{-}}\right]\right)\right]^{\ell}+(\ell-1)^{\ell}\leq\left[(1-\ln(2)+\varepsilon)\ln(n)\right]^{\ell}+C_{\ell};$

where $C_{\ell}=\sup_{n\leq
n_{0}}\\{(\ln(1+2n^{1-\ln(2)+\frac{\varepsilon}{2}}))^{\ell}\\}+(\ell-1)^{\ell}$.

Next, let $\mu={\mathbf{E}}\left[Z_{\geq m_{+}}\right]$ and let
$(X,X^{\prime})$ be random variables coupled so that
$X\stackrel{{\scriptstyle\mathcal{L}}}{{=}}Z_{\geq m_{+}}$,
$X^{\prime}\stackrel{{\scriptstyle\mathcal{L}}}{{=}}\mathrm{Poi}(\mu)$ and
${\mathbf{P}}\left(X=X^{\prime}\right)$ is maximized; that is,
${\mathbf{P}}\left(X\neq
X^{\prime}\right)=\mathrm{d}_{\mathrm{TV}}(X,X^{\prime})$. Note that

$\displaystyle{\mathbf{E}}\left[(\ln(1+X))^{\ell}\right]\geq{\mathbf{E}}\left[(\ln(1+X))^{\ell}{\mathbf{1}}_{[X>n^{\gamma-\varepsilon}]}\right]\geq\left(\ln\left(n^{\gamma-\varepsilon}\right)\right)^{\ell}{\mathbf{P}}\left(X>n^{\gamma-\varepsilon}\right);$

then (7) boils down to lower bounding
${\mathbf{P}}\left(X>n^{\gamma-\varepsilon}\right)$. Since $X<n$, by the
coupling assumption, we have

$\displaystyle{\mathbf{P}}\left(X>n^{\gamma-\varepsilon}\right)$
$\displaystyle\geq{\mathbf{P}}\left(n^{\gamma-\varepsilon}<X^{\prime}<n\right)-{\mathbf{P}}\left(X\neq
X^{\prime}\right)$ $\displaystyle=1-{\mathbf{P}}\left(X^{\prime}\geq
n\right)-{\mathbf{P}}\left(X^{\prime}\leq
n^{\gamma-\varepsilon}\right)-\mathrm{d}_{\mathrm{TV}}(X,X^{\prime}).$

By Proposition 2.2,
$\mathrm{d}_{\mathrm{TV}}(X,X^{\prime})=O(n^{-\alpha^{\prime}})$ for
$\alpha^{\prime}(\varepsilon)>0$. Using the Chernoff bounds for the tails of a
Poisson variable (see, e.g. Section 2.2 in [9]) and that
$\mu=n^{\gamma-\frac{\varepsilon}{2}}(1+o(1))$ we have

$\displaystyle{\mathbf{P}}\left(X^{\prime}\geq n\right)$
$\displaystyle\leq\left(\frac{en^{\gamma-\frac{\varepsilon}{2}}}{n}\right)^{n}e^{-n^{\gamma-\frac{\varepsilon}{2}}}\leq\left(\frac{e^{n^{\ln(2)}}}{en^{\ln(2)}}\right)^{-n},$
$\displaystyle{\mathbf{P}}\left(X^{\prime}\leq n^{\gamma-\varepsilon}\right)$
$\displaystyle\leq\left(\frac{en^{\gamma-\frac{\varepsilon}{2}}}{n^{\gamma-\varepsilon}}\right)^{n^{\gamma-\varepsilon}}e^{-n^{\gamma-\frac{\varepsilon}{2}}}\leq\left(\frac{e^{n^{\varepsilon/2}}}{en^{\frac{\varepsilon}{2}}}\right)^{-n^{\gamma-\varepsilon}};$

both bounds are $o(n^{-\alpha^{\prime}})$ so the proof is completed. ∎

###  2.1 Proof of Theorem 1.2

We will use the first and second moment method, together with Proposition 2.1,
the concentration of $D$ and the fact that for each $n$, $Z_{\geq m}$ is non-
increasing in $m$.

For completeness, we show that $D$ is concentrated around $\ln n$. Indeed, $D$
is a sum of independent Bernoulli random variables $(B_{i})_{1<i\leq n}$, each
with mean $1/(i-1)$ and so ${\mathbf{E}}\left[D\right]=H_{n-1}>\ln n$ where
$H_{n}$ denotes the $n$-th harmonic number. From the fact that $H_{n}-\ln n$
is a decreasing sequence we infer that: for any $0<\varepsilon<3/2$ and $n$
sufficiently large, $|D-H_{n-1}|\leq\frac{\varepsilon}{2}H_{n-1}$ implies
$|D-\ln n|\leq\varepsilon\ln n$. Using the contrapositive of such statement
and Bernstein’s inequality (see, e.g. Theorem 2.8 in [22]) we obtain, for $n$
large enough,

${\mathbf{P}}\left(D\notin(1\pm\varepsilon)\ln(n)\right)\leq{\mathbf{P}}\left(\left|D-H_{n-1}\right|>\dfrac{\varepsilon}{2}H_{n-1}\right)\leq
2\exp\left\\{-\dfrac{\varepsilon^{2}}{12}H_{n-1}\right\\}\leq
2n^{-\varepsilon^{2}/12}.$ (8)

Recall $\gamma=1-\ln(2)$. It suffices to prove that for every $\varepsilon>0$,

$\lim_{n\to\infty}{\mathbf{P}}\left(Z_{\geq
D}\notin(n^{\gamma-\varepsilon},n^{\gamma+\varepsilon})\right)=0.$

We infer from (8) that ${\mathbf{P}}\left(Z_{\geq
D}\notin(n^{\gamma-\varepsilon},n^{\gamma+\varepsilon}),D\notin(1\pm\varepsilon)\ln(n)\right)$
vanishes as $n$ grows.

Let $m_{-}:=m_{-}(\varepsilon)=\lfloor(1-\varepsilon)\ln(n)\rfloor$ and
$m_{+}:=m_{+}(\varepsilon)=\lceil(1+\varepsilon)\ln(n)\rceil$. Using the
monotonicity of $Z_{\geq m}$ on $m$, we have

${\mathbf{P}}\left(Z_{\geq
D}\notin(n^{\gamma-\varepsilon},n^{\gamma+\varepsilon}),\,D\in(1\pm\varepsilon)\ln(n)\right)\leq{\mathbf{P}}\left(Z_{\geq
m_{-}}\geq n^{\gamma+\varepsilon}\right)+{\mathbf{P}}\left(Z_{\geq m_{+}}\leq
n^{\gamma-\varepsilon}\right);$ (9)

so it remains to show that both terms in the right side of (9) vanish. First,
using that $\ln(n)=\ln(2)\log n$ and so $\log(n)-(1\pm\varepsilon)\ln
n=(1-\ln(2)\mp\varepsilon\ln(2))\log(n)$, we infer from Proposition 2.1 that

$\displaystyle\frac{1}{2}n^{\gamma-\varepsilon\ln(2)}(1-o(n^{-\alpha}))\leq{\mathbf{E}}\left[Z_{\geq
m_{+}}\right]\leq{\mathbf{E}}\left[Z_{\geq m_{-}}\right]\leq
2n^{\gamma+\varepsilon\ln(2)}.$ (10)

Markov’s inequality then gives ${\mathbf{P}}\left(Z_{\geq m_{-}}\geq
n^{\gamma+\varepsilon}\right)\leq 2n^{-\varepsilon\gamma}\to 0$. Next, let
$\theta$ be defined so that
$n^{\gamma-\varepsilon}=\theta{\mathbf{E}}\left[Z_{\geq m_{+}}\right]$; in
particular, $\theta\leq 2n^{-\varepsilon\gamma}$. Paley-Zygmund inequality
gives

$\displaystyle{\mathbf{P}}\left(Z_{\geq
m_{+}}>n^{\gamma-\varepsilon}\right)\geq{\mathbf{P}}\left(Z_{\geq
m_{+}}>\theta{\mathbf{E}}\left[Z_{\geq
m_{+}}\right]\right)\geq(1-\theta)^{2}\dfrac{{\mathbf{E}}\left[Z_{\geq
m_{+}}\right]^{2}}{{\mathbf{E}}\left[Z_{\geq m_{+}}^{2}\right]};$

which tends to 1 as $n\to\infty$ by the upper bound for $\theta$ and (5). This
implies ${\mathbf{P}}\left(Z_{\geq m_{+}}\leq n^{\gamma-\varepsilon}\right)$
vanishes, as desired.

##  3 Control on $D$ through a coupling

Let $n\in\mathbb{N}$. Write $\mathcal{I}_{n}$ for the set of increasing trees
of size $n$; namely, labelled rooted trees with label set $[n]$ such that
vertex labels are increasing along any path starting from the root. It is
straightforward to verify that the law of $T_{n}$ is precisely the uniform
distribution on $\mathcal{I}_{n}$.

Consider the following construction of an increasing tree of size $n$. Let
$(b_{i})_{1<i\leq n}$ and $(y_{i})_{1<i\leq n}$ be integer-valued sequences
such that $b_{2}=y_{2}=1$, $b_{i}\in\\{0,1\\}$ and $2\leq y_{i}\leq i-1$ for
$3\leq i\leq n$. Let vertex labelled 1 be the root and, for each $1<i\leq n$,
let vertex $i$ be connected to vertex $1$ if $b_{i}=1$ and, otherwise, let
vertex $i$ be connected to vertex $y_{i}$.

The following coupling is exploited in the proof of Theorem 1.3. Define random
vectors $(B_{i})_{1<i\leq n},(B_{i}^{(\varepsilon)})_{1<i\leq
n},(Y_{i})_{1<i\leq n}$ as follows. Let $(B_{i})_{1<i\leq n}$ be independent
$\mathrm{Bernoulli}(\frac{1}{i-1})$ random variables, let
$(B_{i}^{(\varepsilon)})_{1<i\leq n}$ have the law of $(B_{i})_{1<i\leq n}$
conditioned on $\sum_{i=2}^{n}B_{i}\in(1\pm\varepsilon)\ln(n)$ and let
$(Y_{i})_{1<i\leq n}$ be independent random variables such that $Y_{2}=1$ a.s.
and $Y_{i}$ is uniform over $\\{2,\ldots,i-1\\}$ for $3\leq i\leq n$. We
assume that the vector $(Y_{i})_{1<i\leq n}$ is independent from the rest,
while the coupling of $(B_{i})_{1<i\leq n}$ and
$(B_{i}^{(\varepsilon)})_{1<i\leq n}$ is arbitrary.

The tree obtained from $(B_{i})_{1<i\leq n},(Y_{i})_{1<i\leq n}$ and the
construction above has the distribution of a RRT. To see this, write $v_{i}$
for the parent of vertex $i$; then $1\leq v_{i}<i$ for each $1<i\leq n$.
First, note that each $v_{i}$ is independent from the rest since
$(B_{i})_{1<i\leq n}$ and $(Y_{i})_{1<i\leq n}$ are independent. Next we show
that $v_{i}$ is chosen uniformly at random from $\\{1,2,\dots,i-1\\}$. First,
we have $v_{2}=1$ almost surely. For $2\leq\ell<i\leq n$, by the independence
of $B_{i}$ and $Y_{i}$, we have

$\displaystyle{\mathbf{P}}\left(v_{i}=1\right)$
$\displaystyle={\mathbf{P}}\left(B_{i}=1\right)=\frac{1}{i-1}={\mathbf{P}}\left(B_{i}=0,Y_{i}=\ell\right)={\mathbf{P}}\left(v_{i}=\ell\right);$

therefore, the tree obtained has the law of a RRT and so we denote it by
$T_{n}$. Analogously, write $T_{n}^{(\varepsilon)}$ for the tree obtained from
$(B_{i}^{(\varepsilon)})_{1<i\leq n}$ and $(Y_{i})_{1<i\leq n}$, and let
$D^{(\varepsilon)}$ be the degree of its root.

By definition of $D$ and the construction above we have
$D=\sum_{i=2}^{n}B_{i}$. Thus, conditioning on $\sum_{i=2}^{n}B_{i}$ means,
under this construction, to condition $T_{n}$ on the root degree $D$. In
particular, the distribution of $(B_{i}^{(\varepsilon)})_{1<i\leq n}$ is
defined so that $T_{n}^{(\varepsilon)}$ has the distribution of a RRT of size
$n$ conditioned on $D^{(\varepsilon)}\in(1\pm\varepsilon)\ln(n)$.

Since $D$ is concentrated around $\ln(n)$, the conditioning on
$T_{n}^{(\varepsilon)}$ is over an event of probability close to one and so
the degree sequences of $T_{n}$ and $T_{n}^{(\varepsilon)}$ do not differ by
much. Hence, the proof strategy of Theorem 1.3 is to estimate the moments
${\mathbf{E}}\left[(\ln(Z_{\geq D}))^{k}\right]$ using the monotonicity of
$Z_{\geq d}$, by conditioning on $D\in(1\pm\varepsilon)\ln(n)$ while retaining
$Z_{\geq d}$ instead of $Z_{\geq d}^{(\varepsilon)}$ ; see (22)–(24).

The following two propositions makes this idea rigorous. For $d\geq 0$, let

$\displaystyle W_{d}$ $\displaystyle=\frac{1+Z_{\geq
d}^{(\varepsilon)}}{1+Z_{\geq d}}$ (11)

where $Z_{\geq d}$ is defined as in (3) and, similarly, let $Z_{\geq
d}^{(\varepsilon)}:=|\\{v\in
T_{n}^{(\varepsilon)}:\,d_{T_{n}^{(\varepsilon)}}(v)\geq d\\}|$.

The key in the proof of Proposition 3.1 lies on (14), which yields an upper
bound on the number of vertices that have differing degrees in $T_{n}$ and
$T_{n}^{(\varepsilon)}$ under the coupling. In turn, this allows us to infer
bounds on the ratio $W_{d}$ that hold with high probability and are uniform on
$d$.

######  Proposition 3.1.

Let $\varepsilon,\delta\in(0,1)$ and $0\leq
d\leq(1+\varepsilon)\ln\left(n\right)$. There is $C>0$,
$\beta=\beta(\varepsilon)$ and $n_{0}=n_{0}(\delta)$ such that for $n\geq
n_{0}$, under the coupling described above, we have

${\mathbf{P}}\left(W_{d}\in(1\pm\delta)\right)\geq 1-Cn^{-\beta}.$

###### Proof.

Let $m_{+}=\lceil(1+\varepsilon)\ln n\rceil$ so that $Z_{\geq d}\geq Z_{\geq
m_{+}}$. By Chebyshev’s inequality and (5), for $c\in(0,1)$,

$\displaystyle{\mathbf{P}}\left(Z_{\geq m_{+}}\leq c{\mathbf{E}}\left[Z_{\geq
m_{+}}\right]\right)\leq{\mathbf{P}}\left(\left|Z_{\geq
m_{+}}-{\mathbf{E}}\left[Z_{\geq
m_{+}}\right]\right|\geq(1-c){\mathbf{E}}\left[Z_{\geq
m_{+}}\right]\right)=o(n^{-\alpha}).$ (12)

Rewrite $W_{d}=1+\frac{Z_{\geq d}^{(\varepsilon)}-Z_{\geq d}}{1+Z_{\geq d}}$
to see $W_{d}\in(1\pm\delta)$ is equivalent to $|Z_{\geq
d}^{(\varepsilon)}-Z_{\geq d}|\in[0,\delta(1+Z_{\geq d}))$. Hence, it suffices
to show that there is $n_{0}(\delta)\in\mathbb{N}$, such that for $n\geq
n_{0}$,

$\displaystyle\\{Z_{\geq m_{+}}\geq c{\mathbf{E}}\left[Z_{\geq
m_{+}}\right],D\in(1\pm\varepsilon)\ln(n)\\}\subset\\{|Z_{\geq
d}^{(\varepsilon)}-Z_{\geq d}|\leq\delta(1+Z_{\geq d})\\};$ (13)

which by a contrapositive argument, together with (8) and (12), yields for
$\beta=\min{\\{\alpha,\varepsilon^{2}/12\\}}>0$,

$\displaystyle{\mathbf{P}}\left(|Z_{\geq d}^{(\varepsilon)}-Z_{\geq
d}|>\delta(1+Z_{\geq d})\right)$
$\displaystyle\leq{\mathbf{P}}\left(D\notin(1\pm\varepsilon)\ln(n)\right)+{\mathbf{P}}\left(Z_{\geq
m_{+}}\leq c{\mathbf{E}}\left[Z_{\geq m_{+}}\right]\right)=O(n^{-\beta}).$

We extend the notation introduced for the coupling; let
${\mathcal{S}}:=\\{i\in[2,n]:v_{i}=v_{i}^{(\varepsilon)}\\}$ be the set of
vertices that have the same parent in $T_{n}$ and $T_{n}^{(\varepsilon)}$ and
for $i\in[n]$ denote the set of children of $i$ in $T_{n}$ and
$T_{n}^{(\varepsilon)}$, respectively, by

$\displaystyle\mathcal{C}(i):=\\{j\in[2,n]:v_{j}=i\\}\qquad\text{and}\qquad\mathcal{C}^{(\varepsilon)}(i):=\\{j\in[2,n]:v_{j}^{(\varepsilon)}=i\\}.$

By the coupling construction,
${\mathcal{S}}\cup(\mathcal{C}(1)\bigtriangleup\mathcal{C}^{(\varepsilon)}(1))$
is a partition of $[2,n]$; that is, whenever the parent of a vertex
$i\in[2,n]$ differs in $T_{n}$ and $T_{n}^{(\varepsilon)}$ we infer $B_{i}\neq
B_{i}^{(\varepsilon)}$ and so either
$i\in\mathcal{C}(1)\setminus\mathcal{C}^{(\varepsilon)}(1)$ or
$i\in\mathcal{C}(1)^{(\varepsilon)}\setminus\mathcal{C}(1)$. The consequence
of this observation is two-fold: First, for any $i\in[2,n]$, a necessary
condition for $d_{T_{n}}(i)\neq d_{T_{n}^{(\varepsilon)}}(i)$ is that
$\mathcal{C}(i)\neq\mathcal{C}^{(\varepsilon)}(i)$. Second, the function
$j\mapsto Y_{j}$ that maps
$\mathcal{C}(1)\bigtriangleup\mathcal{C}^{(\varepsilon)}(1)$ to
$\\{i\in[2,n]:\mathcal{C}(i)\neq\mathcal{C}^{(\varepsilon)}(i)\\}$ is
surjective. Indeed, if $i\neq 1$ and
$\mathcal{C}(i)\neq\mathcal{C}^{(\varepsilon)}(i)$ then there exists
$j\in\mathcal{C}(1)\bigtriangleup\mathcal{C}^{(\varepsilon)}(1)$ such that
$Y_{j}=i$. Together they imply the following chain of inequalities,

$|\\{i\in[2,n]:d_{T_{n}}(i)\neq
d_{T_{n}^{(\varepsilon)}}(i)\\}|\leq|\\{i\in[2,n]:\mathcal{C}(i)\neq\mathcal{C}^{(\varepsilon)}(i)\\}|\leq|\mathcal{C}(1)\bigtriangleup\mathcal{C}(1)^{(\varepsilon)}|;$
(14)

the first inequality by containment of the corresponding sets and the second
one by the surjective function described above. On the other hand, $|Z_{\geq
d}-Z_{\geq d}^{(\varepsilon)}|$ equals

$\displaystyle\left|\sum_{i=1}^{n}1_{\\{d_{T_{n}}(i)\geq
d\\}}(i)-\sum_{i=1}^{n}1_{\\{d_{T_{n}^{(\varepsilon)}\\!}(i)\geq
d\\}}(i)\right|$ $\displaystyle\leq\sum_{i=1}^{n}\Big{|}1_{\\{d_{T_{n}}(i)\geq
d\\}}(i)-1_{\\{d_{T_{n}^{(\varepsilon)}\\!}(i)\geq d\\}}(i)\Big{|}$
$\displaystyle\leq 1+|\\{i\in\\{2,...,n\\}:d_{T_{n}}(i)\neq
d_{T_{n}^{(\varepsilon)}}(i)\\}|.$

Therefore,

$\displaystyle|Z_{\geq d}-Z_{\geq d}^{(\varepsilon)}|\leq
1+|\mathcal{C}(1)\bigtriangleup\mathcal{C}^{(\varepsilon)}(1)|\leq
1+2\max\\{|\mathcal{C}(1)|,|\mathcal{C}^{(\varepsilon)}(1)|\\}.$ (15)

We are now ready to prove (13). Fix, e.g., $c=1/2$ and let
$n_{0}=n_{0}(\delta)$ be large enough that
$\frac{1+4\ln(n)}{\delta}<c{\mathbf{E}}\left[Z_{\geq m_{+}}\right]$; this is
possible since ${\mathbf{E}}\left[Z_{\geq m_{+}}\right]$ grows polynomially in
$n$, by Proposition 2.1. In particular, recalling $Z_{\geq d}\geq Z_{\geq
m_{+}}$, for $n\geq n_{0}$ and any $\varepsilon\in(0,1)$ we have

$\displaystyle\\{Z_{\geq m_{+}}\geq c{\mathbf{E}}\left[Z_{\geq
m_{+}}\right]\\}\subset\left\\{Z_{\geq
d}\geq\frac{1+2(1+\varepsilon)\ln(n)}{\delta}\right\\}.$ (16)

Moreover, by the construction of $T_{n}^{(\varepsilon)}$,
$|\mathcal{C}(1)^{(\varepsilon)}|=D^{(\varepsilon)}\leq(1+\varepsilon)\ln n$,
so that (15) implies

$\displaystyle\left\\{Z_{\geq
d}\geq\frac{1+2(1+\varepsilon)\ln(n)}{\delta},D\in(1\pm\varepsilon)\ln(n)\right\\}\subset\\{|Z_{\geq
d}^{(\varepsilon)}-Z_{\geq d}|\leq\delta(1+Z_{\geq d})\\};$ (17)

note that (17) holds for all $n\in\mathbb{N}$. Together with (16), implies
(13) for $n\geq n_{0}$, as desired. ∎

######  Proposition 3.2.

Let $\varepsilon\in(0,1)$, $\ell\in\mathbb{N}$. For $0\leq
d\leq(1+\varepsilon)\ln\left(n\right)$, there is $\beta=\beta(\varepsilon)>0$
such that, under the coupling described above, we have

$\left|{\mathbf{E}}\left[(\ln\left(W_{d}\right))^{\ell}\right]\right|\leq(\ln\left(n\right))^{\ell}O(n^{-\beta})+1.$

###### Proof.

We first simplify to consider

$\displaystyle\left|{\mathbf{E}}\left[(\ln\left(W_{d}\right))^{\ell}\right]\right|\leq{\mathbf{E}}\left[\left|(\ln(W_{d}))^{\ell}\right|\right]\leq{\mathbf{E}}\left[|\ln(W_{d})|^{\ell}\right].$

Now, $\frac{1}{n}\leq W_{d}\leq n$ for every $0\leq
d\leq(1\pm\varepsilon)\ln(n)$, since $W_{0}\equiv 1$ while $\max\\{Z_{\geq
d},Z_{\geq d}^{(\varepsilon)}\\}<n$ for $d\geq 1$, as in any tree there is at
least one vertex of degree zero. Then, for any $\delta\in(0,1)$, we have

$\displaystyle{\mathbf{E}}\left[|\ln(W_{d})|^{\ell}{\mathbf{1}}_{[W_{d}<1-\delta]}\right]\leq(\ln(n))^{\ell}{\mathbf{P}}\left(W_{d}<1-\delta\right),$
$\displaystyle{\mathbf{E}}\left[|\ln(W_{d})|^{\ell}{\mathbf{1}}_{[W_{d}>1+\delta]}\right]\leq(\ln(n))^{\ell}{\mathbf{P}}\left(W_{d}>1+\delta\right).$

Proposition 3.1 implies these two terms are
$(\ln(n))^{\ell}O\left(n^{-\beta}\right)$, where the implicit constant depends
on the choice of $\delta$. With foresight fix $\delta$ to satisfy
$\left(\frac{\delta}{1-\delta}\right)^{\ell}+\delta^{\ell}=1$. Using that
$x\geq 0$ satisfies $1-\frac{1}{x}\leq\ln(x)\leq x-1$,

$\displaystyle{\mathbf{E}}\left[|\ln(W_{d})|^{\ell}{\mathbf{1}}_{[W_{d}\in(1\pm\delta)]}\right]$
$\displaystyle\leq{\mathbf{E}}\left[\Big{|}1-\frac{1}{W_{d}}\Big{|}^{\ell}{\mathbf{1}}_{[W_{d}\in(1-\delta,1)]}\right]+{\mathbf{E}}\left[|W_{d}-1|^{\ell}{\mathbf{1}}_{[W_{d}\in[1,1+\delta)]}\right]$
$\displaystyle\leq\Big{(}\frac{\delta}{1-\delta}\Big{)}^{\ell}+\delta^{\ell}=1;$

and so the result follows. ∎

###  3.1 Proof of Theorem 1.3

Fix $k\in\mathbb{N}$ and recall $\gamma:=1-\ln(2)$. Suppose that for any
$\varepsilon\in(0,\frac{1}{3})$ there exists $c=c(\varepsilon)>0$ and
$C=C(k,\varepsilon)>0$ such that

$\displaystyle\big{(}(\gamma-\varepsilon)\ln\left(n\right)\big{)}^{k}\big{(}1+O(n^{-c})\big{)}-C\leq{\mathbf{E}}\left[\big{(}\ln\left(Z_{\geq
D}\right)\big{)}^{k}\right]\leq\big{(}(\gamma+\varepsilon)\ln\left(n\right)\big{)}^{k}+C.$
(18)

It is straightforward to verify that (18) establishes Theorem 1.3. So it
remains to prove (18).

Let $\varepsilon^{\prime}=\varepsilon/(2\ln(2))$ and write

$\displaystyle
m_{-}=\lfloor(1-\varepsilon^{\prime})\ln(n)\rfloor\quad\text{and}\quad
m_{+}=\lceil(1+\varepsilon^{\prime})\ln(n)+1\rceil.$ (19)

We focus on the term ${\mathbf{E}}\left[(\ln\left(Z_{\geq
D}\right))^{k}\mathbf{1}_{\\{D\in(1\pm\varepsilon^{\prime})\ln(n)\\}}\right]$
as (8) and $1\leq Z_{\geq D}\leq n$ imply

$0\leq{\mathbf{E}}\left[(\ln\left(Z_{\geq
D}\right))^{k}\mathbf{1}_{\\{D\notin(1\pm\varepsilon^{\prime})\ln(n)\\}}\right]\leq(\ln\left(n\right))^{k}{\mathbf{P}}\left(D\notin(1\pm\varepsilon^{\prime})\ln\left(n\right)\right)=(\ln\left(n\right))^{k}O(n^{-\varepsilon^{\prime}/12}).$
(20)

Using the monotonicity of $Z_{\geq d}$, we have

$\displaystyle{\mathbf{E}}\left[(\ln\left(Z_{\geq
D}\right))^{k}\mathbf{1}_{\\{D\in(1\pm\varepsilon^{\prime})\ln(n)\\}}\right]\leq{\mathbf{E}}\left[(\ln\left(Z_{\geq
m_{-}}\right))^{k}\mathbf{1}_{\\{D\in(1\pm\varepsilon^{\prime})\ln(n)\\}}\right]\leq{\mathbf{E}}\left[(\ln\left(Z_{\geq
m_{-}}\right))^{k}\right],$

which by (6) yields,

${\mathbf{E}}\left[(\ln\left(Z_{\geq
D}\right))^{k}\mathbf{1}_{\\{D\in(1\pm\varepsilon^{\prime})\ln(n)\\}}\right]\leq((\gamma+\varepsilon)\ln(n))^{k}+C_{k}.$
(21)

For the lower bound we consider the conditional variable
$Z^{(\varepsilon^{\prime})}_{\geq d}$ defined in the previous section with
$d=m_{+}$. Observe that, if $D\in(1\pm\varepsilon^{\prime})\ln(n)$ then
$Z_{\geq D}\geq 1+Z_{m_{+}}$, thus we obtain

$\displaystyle{\mathbf{E}}\left[(\ln\left(Z_{\geq
D}\right))^{k}\mathbf{1}_{\\{D\in(1\pm\varepsilon^{\prime})\ln(n)\\}}\right]$
$\displaystyle\geq{\mathbf{E}}\left[(\ln\left(1+Z_{\geq
m_{+}}\right))^{k}\mathbf{1}_{\\{D\in(1\pm\varepsilon^{\prime})\ln(n)\\}}\right]$
$\displaystyle\geq{\mathbf{E}}\left[\left(\ln\left(1+Z^{(\varepsilon^{\prime})}_{\geq
m_{+}}\right)\right)^{k}\right]{\mathbf{P}}\left(D\in(1\pm\varepsilon^{\prime})\ln(n)\right).$
(22)

The definition of $W_{d}$ gives

$\displaystyle\ln\left(1+Z_{\geq
m_{+}}^{(\varepsilon^{\prime})}\right)=\ln\left(\left(1+Z_{\geq
m_{+}}^{(\varepsilon^{\prime})}\right)\dfrac{1+Z_{\geq m_{+}}}{1+Z_{\geq
m_{+}}}\right)=\ln\left(1+Z_{\geq m_{+}}\right)+\ln\left(W_{m_{+}}\right);$
(23)

similarly, for $k\geq 2$, the binomial expansion implies

$\displaystyle\left(\ln\left(1+Z_{\geq
m_{+}}^{(\varepsilon^{\prime})}\right)\right)^{k}=\left(\ln(1+Z_{\geq
m_{+}})\right)^{k}+\sum_{\ell=1}^{k}\binom{k}{\ell}\ln(1+Z_{\geq
m_{+}})^{k-\ell}\ln(W_{m_{+}})^{\ell}.$ (24)

We use (7) for a lower bound on the expectation of the main term in these last
two decompositions. For the error terms involving $W_{m_{+}}$ we use
Proposition 3.2. If $k=1$, we directly get

$\displaystyle{\mathbf{E}}\left[\ln\left(1+Z_{m_{+}}^{(\varepsilon^{\prime})}\right)\right]$
$\displaystyle={\mathbf{E}}\left[\ln\left(1+Z_{\geq
m_{+}}\right)\right]+{\mathbf{E}}\left[\ln\left(W_{m_{+}}\right)\right]$
$\displaystyle\geq(\gamma-\varepsilon)\ln(n)\left(1+O(n^{-\alpha^{\prime}})\right)+\ln\left(n\right)O(n^{-\beta})-1.$

If $k\geq 2$, we control each of the terms in the sum of (24). For
$1\leq\ell\leq k$, the Cauchy-Schwarz inequality gives

$\displaystyle\bigg{|}{\mathbf{E}}\left[\ln(1+Z_{\geq
m_{+}})^{k-\ell}\ln(W_{m_{+}})^{\ell}\right]\bigg{|}$
$\displaystyle\leq{\mathbf{E}}\left[\ln(1+Z_{\geq
m_{+}})^{2(k-\ell)}\right]^{1/2}{\mathbf{E}}\left[\ln(W_{m_{+}})^{2\ell}\right]^{1/2}.$
(25)

The deterministic bound $Z_{\geq m_{+}}<n$ implies
${\mathbf{E}}\left[\ln(1+Z_{\geq
m_{-}})^{2(k-\ell)}\right]^{1/2}\leq(\ln(n))^{k-\ell}$. On the other hand,
Proposition 3.2 yields

$\displaystyle{\mathbf{E}}\left[\ln(W_{m_{+}})^{2\ell}\right]^{1/2}$
$\displaystyle\leq\left((\ln\left(n\right))^{2\ell}O(n^{-\beta})+1\right)^{1/2}\leq\left(\ln(n)\right)^{\ell}O(n^{-\beta})+1.$
(26)

Thus, after taking expectations in (24), we get

$\displaystyle{\mathbf{E}}\left[\left(\ln\left(1+Z^{(\varepsilon^{\prime})}_{\geq
m_{+}}\right)\right)^{k}\right]\geq((\gamma-\varepsilon)\ln(n))^{k}(1-o(n^{-c}))-C;$
(27)

where $c=\min\\{\alpha^{\prime},\beta\\}$ and $C=\max\\{C_{k},2^{k}\\}$. Then
(20), (21), (27) together with (8), imply (18) completing the proof.

##  4 Conclusion and open problems

As far as we know, our results provide the first quantitative estimate for the
deletion time $X^{targ}_{n}$ for random recursive trees. Our main result,
Theorem 1.1, confirms the intuition that the targeted procedure requires
substantially fewer cuts than the random edge deletion procedure. It remains
an open question whether $\ln(X^{targ}_{n})$ also grows asymptotically as
$\ln(n)$. Contrary to the case of uniform edge-cutting, in the targeted
vertex-cutting process it is challenging to describe, at each step, the
distribution of either the cut tree or the remaining tree. Even keeping track
of the number of vertices in the first cut tree remains an open question.

## References

  * [1] L. Addario-Berry, N. Broutin, and C. Holmgren.  Cutting down trees with a Markov chainsaw.  The Annals of Applied Probability, 24(6):2297–2339, 2014.
  * [2] L. Addario-Berry and L. Eslava.  High degrees in random recursive trees.  Random Structures and Algorithms, 52(4):560–575, 2017.
  * [3] M. Alenazi and J. Sterbenz.  Comprehensive comparison and accuracy of graph metrics in predicting network resilience.  International Conference on the Design of Reliable Communication Networks (DRCN), 11:157–164, 2015.
  * [4] B. Berche, C. von Ferber, T. Holovatch, and Y. Holovatch.  Resilience of public transport networks against attacks.  The European Physical Journal B, 71(1):125–137, 2009.
  * [5] J. Bertoin and G. Miermont.  The cut-tree of large galton-watson trees and the brownian crt.  Annals of Applied Probability, 23:1469–1493, 2013.
  * [6] G. Berzunza, X. S. Cai, and C. Holmgren.  The k-Cut Model in Conditioned Galton-Watson Trees.  In M. Drmota and C. Heuberger, editors, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020), volume 159 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1–5:10, Dagstuhl, Germany, 2020\. Schloss Dagstuhl–Leibniz-Zentrum für Informatik.
  * [7] G. Berzunza, X. S. Cai, and C. Holmgren.  The k-Cut Model in Deterministic and Random Trees.  The Electronic Journal of Combinatorics, 28(1):P1.25, 2021.
  * [8] B. Bollobás and O. Riordan.  Robustness and vulnerability of scale-free random graphs.  Internet Mathematics, 1(1):1–35, 2004.
  * [9] S. Boucheron, G. Lugosi, and P. Massart.  Concentration inequalities.  Oxford University Press, Oxford, 2013.  A nonasymptotic theory of independence, With a foreword by Michel Ledoux.
  * [10] X. Cai, L. Devroye, C. Holmgren, and F. Skerman.  K-cut on paths and some trees.  Electronic Journal of Probability, 25(53):22, 2019.
  * [11] R. Cohen, K. Erez, D. ben Avraham, and S. Havlin.  Resilience of the internet to random breakdowns.  Physical review letters, 85:4626–8, 2000.
  * [12] R. Cohen, K. Erez, D. ben Avraham, and S. Havlin.  Breakdown of the internet under intentional attack.  Physical review letters, 86:3682–5, 2001.
  * [13] L. Devroye and J. Lu.  The strong convergence of maximal degrees in uniform random recursive trees and dags.  Random Structures Algorithms, 7(1):1–14, 1995.
  * [14] D. Dieuleveut.  The vertex-cut-tree of galton-watson trees converging to a stable tree.  Annals of Applied Probability, 25:2215–2262, 2015.
  * [15] M. Drmota, A. Iksanov, M. Möhle, and U. Roesler.  A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree.  Random Structures and Algorithms, 34(3):319–336, 2009.
  * [16] L. Eslava.  A non-increasing tree growth process for recursive trees and applications.  Combinatorics, Probability and Computing, pages 1–26, 2020.
  * [17] C. Holmgren.  Random records and cuttings in split trees.  Discrete Mathematics $\&$ Theoretical Computer Science, pages 269–282, 2008.
  * [18] C. Holmgren.  Random records and cuttings in binary search trees.  Combinatorics, Probability and Computing, 19(3):391–424, 2010.
  * [19] A. Iksanov and M. Möhle.  A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree.  Electronic Communications in Probability, 12:28 – 35, 2007.
  * [20] S. Janson.  Asymptotic degree distribution in random recursive trees.  Random Structures Algorithms, 26(1-2):69–83, 2005.
  * [21] S. Janson.  Random cutting and records in deterministic and random trees.  Random Structures and Algorithms, 29(2):139–179, 2006.
  * [22] S. Janson, T. Łuczak, and A. Rucinski.  Random graphs.  John Wiley $\&$ Sons, Inc., 1st edition, 2000.
  * [23] M. Javanian and M. Vahidi-Asl.  Isolating the most recent entry in a random recursive tree by random cuts.  Journal of Applied Mathematics and Computing, 16:115–123, 2004\.
  * [24] M. Kuba and A. Panholzer.  Isolating a leaf in rooted trees via random cuttings.  Annals of Combinatorics, 12:81–99, 2008.
  * [25] M. Kuba and A. Panholzer.  Isolating nodes in recursive trees.  Aequationes mathematicae, 76:258–280, 2008.
  * [26] M. Kuba and A. Panholzer.  Multiple isolation of nodes in recursive trees.  Online Journal of Analytic Combinatorics, 9, 2013.
  * [27] A. Meir and J. Moon.  Cutting down recursive trees.  Bellman Prize in Mathematical Biosciences, 21:173–181, 1974.
  * [28] A. Panholzer.  Destruction of recursive trees.  Mathematics and Computer Science III, 528:267–280, 2004.
  * [29] F. Xu, S. Si, D. Duan, C. Lv, and J. Xie.  Dynamical resilience of networks against targeted attack.  Physica A: Statistical Mechanics and Its Applications, 528:121329, 2019.