# Dynamic random graphs with vertex removal

Josep Díaz111Supported by grant MOTION, PID2020-112581GB-C21 from MCIN/ AEI
/10.13039/501100011033 Universitat Politècnica de Catalunya, Barcelona, Spain
Lyuben Lichev  Univ. Jean Monnet, Saint-Etienne, France  Institut Camille
Jordan, Lyon, France  Bas Lodewijks  Univ. Jean Monnet, Saint-Etienne, France
Institut Camille Jordan, Lyon, France

###### Abstract

We introduce and analyse a Dynamic Random Graph with Vertex Removal (DRGVR)
defined as follows. At every step, with probability $p>1/2$ a new vertex is
introduced, and with probability $1-p$ a vertex, chosen uniformly at random
among the present ones (if any), is removed from the graph together with all
edges adjacent to it. In the former case, the new vertex connects by an edge
to every other vertex with probability proportional to the number of vertices
already present.

We prove that the DRGVR converges to a local limit and determine this limit.
Moreover, we analyse its component structure and distinguish a subcritical and
a supercritical regime with respect to the existence of a giant component. As
a byproduct of this analysis, we obtain upper and lower bounds for the
critical parameter. Furthermore, we provide precise expression of the maximum
degree (as well as in- and out-degree for a natural orientation of the DRGVR).
Several concentration and stability results complete the study.

Keywords: random graph, complex network, local limit, component structure,
maximum degree, Poisson process

MSC Class: 05C80

##  1 Introduction

Since the appearance of the first random graph models in the late 50’s [13,
15], the study of random graphs has attracted great interest both from
theoretical and applied point of view.

In the last twenty years, apart from the study of classical random graph
theory, much effort has been made to provide and analyse accurate models for
large-scale real-world networks like the internet or different P2P social
networks. One key characteristic of such networks is that for most of them,
the degree of the vertices follows an inverse power law, that is, the
proportion of vertices with degree $d$ is approximately $cd^{-\alpha}$ for
some constants $c,\alpha>0$. As a consequence, the fact that the classical
random graphs as $G(n,m)$ and $G(n,p)$ typically have Poisson degree
distribution makes them unsuitable as models for real-world networks. An
important contribution was made by Albert and Barabási [2] who proposed a
scale-free dynamic network model with a preferential attachment rule. In their
model, a new vertex is introduced at every step. At its arrival, a vertex
chooses to attach to existing vertices with probability proportional to the
degree of the existing vertices. Since Albert and Barabási’s breakthrough, the
analysis of his scale-free model and its variations has been object of
intensive study, see for example [24, 27].

Although the power-law behaviour is an important characteristic of real-world
networks, it is not the only one. One natural observation is that besides the
creation of vertices in a dynamic network, sometimes vertices could also
disappear: for instance, in a social network a user could delete their
account, or in a web network a server could break down due to failure.
However, most dynamic network models did not consider the possibility of
vertex removal. Among the few exceptions are [6, 7], which both consider
settings based on Albert and Barabási’s scale-free model. In the model of
Chung and Lu [6], each of vertex creation, vertex deletion, edge creation and
edge deletion may happen at any given step with probabilities that sum up to
1. When a vertex is created, it connects to an existing vertex by a single
edge according to a preferential attachment rule. The authors provide bounds
for the diameter, the graph distance between two typical vertices, the
connected components and the spectrum of the adjacency matrix. In the similar
model of Cooper, Frieze and Vera [7] every vertex is connected to $m\geq 1$
neighbours at its arrival. The authors analyse the degree sequence of the
obtained dynamic graph and prove its scale-freeness.

The notion of a dynamic network on a set of aging individuals has also been
considered. Instead of deleting a vertex at a given step, which forbids later
vertices to attach to it, several works [3, 10, 14] considered models in which
new vertices connect to any fixed vertex with smaller probability as time goes
by. The main motivation of such models comes from real-world networks like the
citation network where empirical observations show that papers usually get
less popular with time. Contrary to [6, 7] and similarly to the model we
introduce below, the authors of [14] consider a setting where every new vertex
connects to the present ones by a random number of edges. This allows new
vertices to occasionally have large degrees even upon their arrival, which is
another common feature of a number of real-world networks.

In this paper, we introduce and study a new model of a dynamically growing
network with vertex removal based on uniform attachment.

######  Definition 1.1 (Dynamic Random Graph with Vertex Removal (DRGVR)).

Fix constants $\beta>0$, $\varepsilon\in(0,1/2]$ and a sequence
$(\xi_{n})_{n\geq 0}$ of i.i.d. random variables with Bernoulli distribution
with parameter $p:=1/2+\varepsilon$. We define a sequence of graphs
$(G_{n})_{n\geq 0}=((V_{n},E_{n}))_{n\geq 0}$ by initialising $G_{0}$ to be
the empty graph, and for every $n\geq 1$, we construct $G_{n}$ from $G_{n-1}$
as follows. If $\xi_{n}=1$, set $V_{n}=V_{n-1}\cup\\{n\\}$ and conditionally
on $V_{n-1}$, add each of the edges $(\\{i,n\\})_{i\in V_{n-1}}$ to $E_{n-1}$
independently with probability
$\min\big{\\{}\tfrac{\beta}{|V_{n-1}|},1\big{\\}}$ to construct $E_{n}$. If
$\xi_{n}=0$, select a vertex uniformly at random from $V_{n-1}$ (if any) and
remove it together with all edges incident to it.

Note that the graph $G_{n}$ will sometimes be seen as a directed graph where
the edges are directed from the vertex arriving later to the vertex arriving
earlier. In this case, the edge set will be denoted by $\vv{E}_{n}$, and the
directed graph itself by $\vv{G}_{n}$.

Finally, we remark that the well-studied _Dubin’s model_ [12, 18, 26] is a
particular case of the DRGVR for $\varepsilon=1/2$ (or equivalently $p=1$). In
this particular setting Shepp [26] showed the existence of a sharp threshold
at $\beta=1/4$ for the appearance of a giant component, and Dereich and
Mörters later recovered the result in a more general framework, see
Proposition 1.3 in [8]. Similar results were obtained in [11, 12] and for the
closely related CHKNS model.

##### Notation

Throughout the paper we set $\mathbb{N}:=\\{1,2,\ldots\\}$ denote the set of
natural numbers, $\mathbb{N}_{0}:=\mathbb{N}\cup\\{0\\}$, and
$[t]:=\\{i\in\mathbb{N}:i\leq t\\}$ for every $t\geq 1$. For $x\in\mathbb{R}$,
we let $\lceil x\rceil:=\inf\\{n\in\mathbb{Z}:n\geq x\\}$ and $\lfloor
x\rfloor:=\sup\\{n\in\mathbb{Z}:n\leq x\\}$. For positive real sequences
$(a_{n},b_{n})_{n\in\mathbb{N}}$, we say that $a_{n}=o(b_{n})$ if
$\lim_{n\to\infty}a_{n}/b_{n}=0$, $a_{n}=\omega(b_{n})$ if $b_{n}=o(a_{n})$,
$a_{n}\sim b_{n}$ if $\lim_{n\to\infty}a_{n}/b_{n}=1$,
$a_{n}=\mathcal{O}(b_{n})$ if there exists a constant $C>0$ such that
$a_{n}\leq Cb_{n}$ for all $n\in\mathbb{N}$, and $a_{n}=\Omega(b_{n})$ if
$b_{n}=\mathcal{O}(a_{n})$. Note that we allow the constant $C$ to depend on
the parameters of the problem that are _fixed_ , that is, do not depend on the
choice of a sufficiently large $n$. For random variables
$(X_{n})_{n\in\mathbb{N}}$ and $X$, we let
$X_{n}\overset{d}{\longrightarrow}X$,
$X_{n}\overset{\mathbb{P}}{\longrightarrow}X$ and
$X_{n}\overset{\mathrm{a.s.}}{\longrightarrow}X$ denote convergence in
distribution, in probability and almost sure convergence of
$(X_{n})_{n\in\mathbb{N}}$ to $X$, respectively. Furthermore, we denote by
$\mathcal{L}(X)$ the distribution of $X$.

For a graph $G$, the _size_ of $G$, often denoted $|G|$, is the number of
vertices in $G$. For two vertices $u,v$ in $G$, we let $u\to v$ denote the
fact that $u$ is connected to $v$ by a (directed) edge. Moreover, for two
finite rooted graphs $(G,o_{G})$ and $(H,o_{H})$, we denote by
$(G,o_{G})\cong(H,o_{H})$ the fact that the two rooted graphs are isomorphic.

Finally, for an event $\mathcal{E}$ in a given probability space, we denote by
$\mathcal{E}^{c}$ the _complement_ of $\mathcal{E}$.

###  1.1 Results

In this section we present our results related to the properties of the DRGVR
model. The first theorem in this section is the main result of the paper. To
introduce it, we first need to explain the notion of _local convergence_ of a
sequence of graphs. Fix a sequence of rooted graphs $(H_{n},o_{n})_{n\geq 0}$,
where $o_{n}$ is a vertex of $H_{n}$ chosen uniformly at random. Also, for a
graph $H$, a vertex $v$ in $H$ and an integer $r\geq 0$, we denote by
$B_{r}(H,v)$ the graph induced by all vertices at distance at most $r$ from
$v$ in $H$ (often referred to as _the ball with radius $r$ around $v$ in
$H$_). For ease of writing we often assume that $B_{r}(H,v)$ is a graph
_rooted at_ $v$. Given a probability measure $\mu$ on the set of finite rooted
graphs $\mathcal{G}$, we say that the sequence $(H_{n},o_{n})_{n\geq 1}$
converges locally to $\mu$ if for every integer $r\geq 0$ and every finite
rooted graph $(H,o_{H})\in\mathcal{G}$ we have that

$\mathbb{P}\left(B_{r}(H_{n},o_{n})\cong(H,o_{H})\right)\xrightarrow[n\to\infty]{}\mu(\\{(G,o_{G})\in\mathcal{G}:B_{r}(G,o_{G})\cong(H,o_{H})\\}).$

Often the limiting measure $\mu$ is identified with a (possibly random) rooted
graph. For a complete account and applications on the notion of local
convergence, see for example [25].

In this paper we provide a stronger result for the local weak convergence in
terms of the _total variation distance_. For two probability distributions
$\mu_{1}$ and $\mu_{2}$ defined on a common probability space $\Omega$, the
total variation distance between $\mu_{1}$ and $\mu_{2}$ is defined as

$d_{\mathrm{TV}}(\mu_{1},\mu_{2}):=\sup_{A\subseteq\Omega}|\mu_{1}(A)-\mu_{2}(A)|=\inf\\{\mathbb{P}\left(X\neq
Y\right):(X,Y)\text{ is a coupling of }(\mu_{1},\mu_{2})\\}.$ (1)

By taking $\Omega=\mathcal{G}$, we may consider the total variation between
the distributions of $B_{r}(G_{n},k_{0})$ and $B_{r}(\mathcal{T},0)$, where
$(\mathcal{T},0)$ is some rooted random graph and $k_{0}$ is a vertex chosen
uniformly at random from $G_{n}$. In this paper, the definition of the total
variation distance in terms of couplings is particularly useful.

The first and main result of this paper deals with the local weak convergence
of the DRGVR model. To this end, we define the following multi-type branching
process.

######  Definition 1.2 (Binomial birth-death tree).

Fix $\beta>0$, $\varepsilon\in(0,1/2]$ and set $p:=1/2+\varepsilon$. We define
a multi-type branching process $\mathcal{T}$ with type space $(0,1]$ as
follows. The root $0$ of $\mathcal{T}$ has type
$a_{0}\sim\mathrm{Beta}(\tfrac{p}{2\varepsilon},1)$. Then, any vertex $v$ in
$\mathcal{T}$ with type $a_{v}$ produces an offspring independently of all
other vertices according to a Poisson point process on $(0,1]$. Conditionally
on $a_{v}$, the density of this Poisson process is given by

$\lambda_{v}^{-}(\mathrm{d}x):=\frac{\beta p}{2\varepsilon
a_{v}}x^{(1-p)/2\varepsilon}\,\mathrm{d}x\text{ for
}x\in(0,a_{v}),\quad\text{and}\quad\lambda^{+}(\mathrm{d}x):=\frac{\beta
p}{2\varepsilon}x^{(1-p)/(2\varepsilon)-1}\,\mathrm{d}x\text{ for
}x\in(a_{v},1].$ (2)

The types of the vertices in the offspring are identified by their position in
the Poisson point process.

######  Theorem 1.3.

Fix $\beta>0$ and $\varepsilon\in(0,1/2]$, and consider the DRGVR model and
Binomial birth-death tree given in Definitions 1.1 and 1.2, respectively. Let
$k_{0}$ be a vertex selected uniformly at random from $V_{n}$. Then, for any
$r\in\mathbb{N}$,

$d_{\mathrm{TV}}(\mathcal{L}(B_{r}(G_{n},k_{0})),\mathcal{L}(B_{r}(\mathcal{T},0)))\leq(\log\log
n)^{-(1-p)/(2\varepsilon)-1/r}.$ (3)

In particular, $(G_{n},k_{0})_{n\geq 0}$ converges locally to the random
rooted tree $(\mathcal{T},0)$.

The following corollary is obtained by applying Theorem 1.3 for $r=1$ and
integrating the density of the Poisson process, associated to the offspring of
the origin, over the interval $(0,1]$.

######  Corollary 1.4.

Let $D_{n}^{0}$ denote the degree of the vertex $k_{0}$, and conditionally on
$a_{0}$ let

$X_{0}\sim\mathrm{Poi}\Big{(}\frac{\beta
p}{1-p}\Big{(}1-\frac{2p-1}{p}a_{0}^{(1-p)/(2\varepsilon)}\Big{)}\Big{)}.$

Then,
$\mathrm{d}_{\mathrm{TV}}(\mathcal{L}(D^{0}_{n}),\mathcal{L}(X_{0}))\leq(\log\log
n)^{-p/(2\varepsilon)}$.

Recall that in the case $p=1$, the DRGVR recovers Dubin’s model. Though a
tailored proof for the case $p=1$ might result in an improved rate of
convergence, the existence of a local weak limit for Dubin’s model by Theorem
1.3 is novel in itself. Furthermore, we directly obtain the limiting degree
distribution as well as bounds on the convergence rate of the empirical degree
distribution as a result. Though Corollary 1.4 is a result already obtained by
Bollobás, Janson and Riordan [5] for a “closely related” inhomogeneous random
graph model (see Section 6 for more details), the convergence in total
variation distance strengthens this result.

We now present several results that discuss more global properties. First, we
discuss the conditions for the emergence of a giant component and the relation
with the local weak limit. Define

$\gamma=\gamma(\beta):=\mathbb{P}\left(|\mathcal{T}|=\infty\right)$ (4)

to be the survival probability of the branching process $\mathcal{T}$.

######  Theorem 1.5.

Fix $\beta>0$ and $\varepsilon\in(0,1/2]$, and consider the DRGVR model as in
Definition 1.1. Moreover, consider the survival probability $\gamma$ of its
local weak limit given in (4). Let $\mathcal{C}_{1}=\mathcal{C}_{1}(G_{n})$
and $\mathcal{C}_{2}=\mathcal{C}_{2}(G_{n})$ denote the first and the second
largest component in $G_{n}$. Then, there exists $\beta_{c}=\beta_{c}(p)$ such
that:

  * •

if $\beta<\beta_{c}$, then $|\mathcal{C}_{1}|/n$ converges in probability to
$0$ as $n\to\infty$;

  * •

if $\beta>\beta_{c}$, then $|\mathcal{C}_{1}|/n$ converges in probability to
$2\varepsilon\gamma\in(0,1]$, and moreover $|\mathcal{C}_{2}|=\mathcal{O}(\log
n)$ with high probability.

######  Remark 1.6.

$(i)$ It may seem counter-intuitive at first that the size of the largest
component is proportional to $2\varepsilon\gamma$. However, heuristically, the
_proportion_ of vertices in the giant component, i.e.
$|\mathcal{C}_{1}|/|V_{n}|$, converges to $\gamma$ in probability, and it can
be checked that $|V_{n}|/n$ converges to $2\varepsilon$ almost surely (see
Lemma 2.5). Combining the two observations yields the result.

$(ii)$ It follows directly from the definition of the DRGVR model that _bond
percolation_ on $G_{n}$ with retention probability $q$ yields a graph with a
giant component only when $\beta>\beta_{c}$ and $q>\beta_{c}/\beta$.

Theorem 1.5 raises the natural question of how $\beta_{c}$ behaves as a
function of $p$. The following proposition partially answers this question by
providing a lower and upper bound for $\beta_{c}$ in terms of $p$.

######  Proposition 1.7.

Consider the same set-up as Theorem 1.5, the threshold function
$\beta_{c}=\beta_{c}(p)$ is a non-increasing continuous function over the
interval $(1/2,1]$. Moreover, for every $p\in(1/2,1]$,

$\max\left\\{\sqrt{\frac{1-p}{p}},\frac{1}{4}\right\\}\leq\beta_{c}(p)\leq\inf_{t\in(-1/2,\infty)}\left(\frac{(1+2t)(2t^{2}+7t+4+1/p)}{(1+t)^{2}(t+1/p)(2t+2/p-1)}\right)^{-1/2}\leq\sqrt{\frac{2-p}{p(1+4p)}}.$

######  Remark 1.8.

While the tighter upper bound for $\beta_{c}(p)$, as provided by the infimum
in Proposition 1.7 is strictly smaller for all $p\in(1/2,1]$, we still provide
a weaker but also simpler upper bound in terms of $p$. This bound is realised
by taking $t=0$ in the infimum. Note that $\beta_{c}(1)=1/4$ and
$\lim_{p\downarrow 1/2}\beta_{c}(p)=1$, as can be observed in Figure 1.

Figure 1: A plot of the lower bound and the two upper bounds for $\beta_{c}$
from Proposition 1.7. The sharper upper bound given by
$f(p):=\inf_{t\in(-1/2,\infty)}\Big{(}\frac{(1+2t)(2t^{2}+7t+4+1/p)}{(1+t)^{2}(t+1/p)(2t+2/p-1)}\Big{)}^{-1/2}$
is approximated numerically.

Once the giant component is established, one may wonder what else can be said
about its structure. We are unable to provide a conclusive answer to this
question. However, we can say a lot more for the graph that is induced by the
vertices born “not too early”. For example, deleting the vertices in the set
$V_{\lambda n}\cap V_{n}$ from $G_{n}$ does not lead to a “big” change in the
size of the giant when $\lambda$ is a “small constant”.

######  Theorem 1.9.

Consider the setup of Theorem 1.5 with $\beta>\beta_{c}(p)$ and recall the
constant $\gamma=\gamma(p)$ from (4). Then, for every $\delta\in(0,\gamma)$
there exists $\lambda>0$ such that the graph $G^{\lambda}_{n}$, induced from
$G_{n}$ by the vertices in $V_{n}\setminus V_{\lambda n}$, satisfies w.h.p.
each of the following statements:

  1. 1.

$(2\varepsilon\gamma-\delta)n\leq|\mathcal{C}_{1}(G^{\lambda}_{n})|\leq(2\varepsilon\gamma+\delta)n$,

  2. 2.

$|\mathcal{C}_{2}(G^{\lambda}_{n})|=\mathcal{O}(\log n)$,

  3. 3.

there is a constant $\zeta=\zeta(\beta,p)>0$ such that two vertices of
$G^{\lambda}_{n}$, chosen uniformly at random, have a graph distance in the
interval $[(1-\delta)\zeta\log n,(1+\delta)\zeta\log n]$ (in
$G^{\lambda}_{n}$).

The graph $G_{n}$ being constructed recursively, its edges may naturally be
equipped with an orientation from the vertex arriving at a later step to the
vertex arriving earlier. Therefore, by setting
$V_{n}=\\{v_{1},\ldots,v_{|V_{n}|}\\}$ with $v_{i}<v_{j}$ if $i<j$, for every
$j\in[|V_{n}|]$ we denote by $d^{-}_{n}(v_{j})$ (respectively
$d^{+}_{n}(v_{j})$) the number of neighbors of $v_{j}$ in the set
$\\{v_{1},\ldots,v_{j-1}\\}$ (respectively in the set
$\\{v_{j+1},\ldots,v_{|V_{n}|}\\}$). Also, we denote by
$d^{s}_{n}(v_{j}):=d^{+}_{n}(v_{j})+d^{-}_{n}(v_{j})$ the total degree of
$v_{j}$ in $G_{n}$. We remark that in general we identify the vertices in the
process in two different ways: as elements of
$V_{n}=\\{v_{1},\ldots,v_{|V_{n}|}\\}$, and by their labels which indicate the
step at which they were born. The latter notation is more general as it is
applied to all vertices in the process and not only the ones that survive
until step $n$.

The following theorem precisely characterises the maximum degree, the maximum
in-degree and the maximum out-degree, as well as the the labels of vertices
that attain these maximal degrees.

######  Theorem 1.10.

Consider the DRGVR model as in Definition 1.1 with $\beta>0$ and
$\varepsilon\in(0,1/2)$. Then, for $\square\in\\{s,+\\}$,

$\frac{(\log\log n)^{2}}{\log n}\max_{v\in V_{n}}d_{n}^{\square}(v)-\log\log
n-\log\log\log n\overset{\mathbb{P}}{\longrightarrow}1+\log\Big{(}\frac{\beta
p}{1-p}\Big{)},$ (5)

and

$\frac{(\log\log n)^{2}}{\log n}\max_{v\in V_{n}}d_{n}^{-}(v)-\log\log
n-\log\log\log n\overset{\mathbb{P}}{\longrightarrow}1+\log\beta.$ (6)

Finally, let $\mathcal{I}^{\square}_{n}:=\\{u\in V_{n}\text{ and
}d_{n}^{\square}(u)=\max_{v\in V_{n}}d_{n}^{\square}(v)\\}$ be the set of
vertices that attain the maximum (in-/out-)degree. Then, for
$\square\in\\{s,+\\}$ and for any fixed $\delta\in(0,1)$,

$\frac{\log\min\mathcal{I}^{\square}_{n}}{\log
n}\overset{\mathbb{P}}{\longrightarrow}1,\quad\text{and}\quad\mathbb{P}\left(\max\mathcal{I}^{\square}_{n}\leq\delta
n\right)=1-o(1),\quad\text{and}\quad\frac{\min\mathcal{I}^{-}_{n}}{n}\overset{\mathbb{P}}{\longrightarrow}1.$
(7)

Note that Theorem 1.10 does not include the case $p=1$ (or, equivalently,
$\varepsilon=1/2$) in which no vertices are removed. Indeed, as can be
observed from the results by Lodewijks [22, 23] and Banerjee and Bhamidi [1]
(in the case of deterministic out-degree equal to $1$), the behaviour of
large-degree vertices and their labels in the case $p=1$ is rather different.
Most notably, the vertices with maximal (in-)degree have labels of the order
$n^{(1-1/(2\log 2))+o(1)}$ instead of $n^{1-o(1)}$.

The last result in this section concerns a large family of Lipschitz-type
parameters. Fix a function $f$ from the set of finite directed graphs to the
real numbers. We say that $f$ is _$L$ -Lipschitz_ if for any two directed
graphs $H_{1}$ and $H_{2}$ that differ in only one edge (that is,
$|E(H_{1})\setminus E(H_{2})|+|E(H_{2})\setminus E(H_{1})|\leq 1$) we have
$|f(H_{1})-f(H_{2})|\leq L$. We remark that the definition does not make any
reference to the vertex sets of $H_{1}$ and $H_{2}$, in particular, the family
of functions we are interested in is insensitive to isolated vertices.

######  Theorem 1.11.

Fix $\beta>0$ and $\varepsilon\in(0,1/2]$, and consider the DRVGR model as in
Definition 1.1. Fix an integer $L\in\mathbb{N}$ and an $L$-Lipschitz function
$f$ defined on the set of directed graphs. Then, for any $t\geq 0$,

  1. (i)

$\mathbb{P}\left(\Big{|}f(\vv{G}_{n})-\mathbb{E}\left[f(\vv{G}_{n})\mid|V_{n}|,(d_{n}^{+}(v_{i}))_{i=1}^{|V_{n}|}\right]\Big{|}\geq
t\;\Big{|}\;|V_{n}|,(d_{n}^{+}(v_{i}))_{i=1}^{|V_{n}|}\right)\leq
2\exp\left(-\frac{t^{2}}{8|E_{n}|L^{2}}\right);$

  2. (ii)

$\mathbb{P}\left(\Big{|}f(\vv{G}_{n})-\mathbb{E}\left[f(\vv{G}_{n})\mid(V_{i})_{i=1}^{n},|E_{n}|\right]\Big{|}\geq
t\;\Big{|}\;(V_{i})_{i=1}^{n},|E_{n}|\right)\leq
2\exp\left(-\frac{t^{2}}{8|E_{n}|L^{2}}\right).$

Note that despite the fact that both statements show conditional concentration
of $f(\vv{G}_{n})$, the two are quite different in nature. In the first case,
the conditioning is done over the out-degrees of all vertices in $\vv{G}_{n}$
and is independent from the vertex process $(V_{i})_{i\geq 0}$ conditionally
on $V_{n}$. In the second case, the conditioning is done over the entire
vertex process $(V_{i})_{i\geq 0}$ but the only structural information about
$\vv{G}_{n}$ is its number of edges.

##### Main ideas of the proofs.

The proofs of the main results use a variety of techniques. First, Theorem 1.3
is obtained by providing a coupling between the Breadth-First Search (BFS)
exploration of the neighbourhood of a vertex $k_{0}$ selected uniformly at
random in $G_{n}$, and the recursive construction of the multi-type branching
process $\mathcal{T}$ with root $0$, as defined in Definition 1.2. This
coupling is mainly inspired by techniques used for proving the local weak
limit of affine preferential attachment models (see [4, 21]), and ensures that
the $r$-neighbourhood of $k_{0}$ in the BFS is isomorphic to the subtree of
$\mathcal{T}$, induced by the first $r$ generations, as required for the local
weak convergence. The aim is to show that this coupling is successful with
high probability. Whilst such an approach is common for random graph models
with a “tree-like” structure, and for evolving random graph models in
particular (see e.g. [4, 21]), the main technical contribution is to prove
that, despite the randomness introduced by the vertex removal, the direct
neighbours of vertices with “sufficiently large” labels in $G_{n}$ can be
coupled w.h.p. with a discretised Poisson point process which encodes the
offspring of vertices in the multi-type branching process $\mathcal{T}$.

The proof of Theorem 1.5 combines a comparison of the DRGVR model $G_{n}$ with
a particular inhomogeneous Erdős-Rényi graph model on the vertex set $V_{n}$
(of $G_{n}$) and results by Bollobás, Janson and Riordan [5]. More precisely,
we use necessary and sufficient conditions for the existence of a giant
component of a wide family of inhomogeneous random graph models from [5], and
the comparison between the DRGVR model and an instance of this family allows
us to transfer their results to our setting. Proposition 1.7 is a byproduct of
this proof and is shown by analysing a related linear operator. Theorem 1.9
combines the fact that the restriction of the inhomogeneous Erdős-Rényi graph
on $V_{n}\setminus V_{\lambda n}$ satisfies that every two edges appear in
$G^{\lambda}_{n}$ with probabilities which are a constant factor away from
each other (this is not the case for $G_{n}$ itself) with results from [5].

Theorem 1.10 combines the comparison between the DRGVR model and an
inhomogeneous Erdős-Rényi graph model with precise bounds on the tail
distribution of the vertex-degrees for the latter model. These bounds are used
to show that, when the expected number of vertices with degree at least
$k_{n}$ either tends to zero (respectively to infinity), then the largest
degree is at most (respectively at least) $k_{n}$ with high probability. With
the growth rate of the maximum degree at hand, the tail distribution bounds
can be used to argue that vertices with “too small” or “too large” label have
degrees that are substantially smaller than the maximum degree in $G_{n}$.

Finally, the proof of Theorem 1.11 is based on constructing martingales with
bounded differences and the use of the classical Azuma inequality.

##### Organisation of the paper.

We provide some preliminary results in Section 2 that are to be used in the
proofs of the results presented in Section 1. Sections 3, 4 and 5 are
dedicated to proving our main result (Theorem 1.3) regarding the local weak
convergence of the DRGVR model. In Section 6, we compare our model with a
particular instance of the inhomogeneous Erdős-Rényi graph, and use
established results for inhomogeneous random graphs to prove Theorem 1.5,
Proposition 1.7 and Theorem 1.9. Section 7 is then devoted to proving the size
of the maximum degree and the labels of the vertices that attain the maximum
degree (Theorem 1.10). Finally, in Section 8 we prove Theorem 1.11.

##  2 Preliminaries

###  2.1 General probabilistic preliminaries

Let $\Gamma$ be a probability distribution on $(0,1]\times\\{0,1\\}$ defined
as

$\Gamma(x,y):=px^{(1-p)/(2\varepsilon)}\,\mathrm{d}x\,\delta_{1}(y)+\big{(}1-px^{(1-p)/(2\varepsilon)}\big{)}\,\mathrm{d}x\,\delta_{0}(y),$
(8)

where $\delta_{0}$ and $\delta_{1}$ are a Dirac measures. As we shall see, the
distribution of $\Gamma$ is tightly connected to the distribution of the birth
times of the vertices in $V_{n}$. For now, we state and prove a key property
of this distribution.

######  Lemma 2.1.

Let $(X,Y)$ be sampled from $\Gamma$. Then, for every $x\in(0,1]$,

$\mathbb{P}\left(X\leq x\,|\,Y=1\right)=x^{p/(2\varepsilon)}.$ (9)

In particular, conditionally on $Y=1$,
$X\sim\mathrm{Beta}(\tfrac{p}{2\varepsilon},1)$. Equivalently, let
$X\sim\mathrm{Unif}(0,1)$ and, conditionally on $X$,
$Y\sim\mathrm{Ber}(pX^{(1-p)/(2\varepsilon)})$. Then, conditionally on $Y=1$,
$X\sim\mathrm{Beta}(\tfrac{p}{2\varepsilon},1)$.

###### Proof.

Recall that $p=\tfrac{1}{2}+\varepsilon$. Thus, both results readily follow
from the fact that

$\mathbb{P}\left(X\leq
x\,|\,Y=1\right)=\frac{\int_{0}^{x}ps^{(1-p)/(2\varepsilon)}\,\mathrm{d}s}{\int_{0}^{1}ps^{(1-p)/(2\varepsilon)}\,\mathrm{d}s}=x^{p/(2\varepsilon)},$
(10)

as desired. ∎

The next lemma provides a useful coupling of the Bernoulli and the Poisson
distributions.

######  Lemma 2.2 ([20], page 5, (1.11)).

Fix $\lambda\in(0,1)$, and let $X\sim\mathrm{Poi}(\lambda)$ and $Y$ be a
Bernoulli random variable with success probability $\lambda$. There exists a
coupling $(\widehat{X},\widehat{Y})$ of $(X,Y)$ such that
$\hat{X}\geq\mathbbm{1}_{\\{Y\leq 1\\}}Y$ almost surely and

$\mathbb{P}(\widehat{X}\neq\widehat{Y})\leq 2\lambda^{2}.$ (11)

######  Lemma 2.3.

Fix $\lambda_{1},\lambda_{2}>0$. There exists a coupling $(X_{1},X_{2})$ of
the Poisson distributions with means $\lambda_{1}$ and $\lambda_{2}$ so that

$\mathbb{P}(X_{1}\neq X_{2})\leq|\lambda_{1}-\lambda_{2}|.$ (12)

###### Proof.

Assume without loss of generality that $\lambda_{1}<\lambda_{2}$. Let
$X_{1}\sim\mathrm{Po}(\lambda_{1})$ and let
$Y\sim\mathrm{Po}(\lambda_{2}-\lambda_{1})$ be a Poisson variable independent
from $X_{1}$. Set $X_{2}=X_{1}+Y$. Then, $X_{2}\sim\mathrm{Po}(\lambda_{2})$
and

$\mathbb{P}\left(X_{1}\neq X_{2}\right)=\mathbb{P}\left(Y\geq
0\right)=1-\mathrm{e}^{-(\lambda_{2}-\lambda_{1})}\leq\lambda_{2}-\lambda_{1},$

where the last inequality uses that for all $x\in\mathbb{R}$,
$1-x\leq\mathrm{e}^{-x}$. ∎

Finally, we state versions of the well-known _Chernoff’s inequality_ and
_Azuma’s inequality_. Recall that a (finite or infinite) stochastic process
$(X_{n})_{n\geq 0}$ is called a _martingale_ if for every $n\geq 0$,
$\mathbb{E}[|X_{n}|]<\infty$ and
$\mathbb{E}[X_{n+1}\mid(X_{i})_{i=0}^{n}]=X_{n}$.

######  Lemma 2.4.

  1. (i)

_(Theorem 2.1 and Corollary 2.3 in[17])_ Denote
$\phi:x\in[-1,\infty)\mapsto(1+x)\log(1+x)-x$. Given a binomial random
variable $X$,

$\displaystyle\mathbb{P}(X-\mathbb{E}[X]\geq t)$
$\displaystyle\leq\exp{}\left(-\mathbb{E}[X]\cdot\phi\Big{(}\frac{t}{\mathbb{E}[X]}\Big{)}\right)\leq\exp{}\left(-\frac{t^{2}}{2(\mathbb{E}[X]+t/3)}\right)\text{
for every }t\geq 0,$ $\displaystyle\mathbb{P}(X-\mathbb{E}[X]\leq-t)$
$\displaystyle\leq\exp{}\left(-\mathbb{E}[X]\cdot\phi\Big{(}-\frac{t}{\mathbb{E}[X]}\Big{)}\right)\leq\exp{}\left(-\frac{t^{2}}{2(\mathbb{E}[X]+t/3)}\right)\text{
for every }t\in[0,\mathbb{E}[X]].$

  2. (ii)

_(Theorem 2.25 in[17])_ Fix a sequence of positive real numbers
$(c_{i})_{i=1}^{n}$ and a random variable $X$. Suppose that $(X_{n})_{n\geq
0}$ is a martingale such that $X_{n}=X$, $X_{0}=\mathbb{E}[X]$ and for every
$i\in[n]$, $|X_{i-1}-X_{i}|\leq c_{i}$. Then, for every $t\geq 0$,

$\mathbb{P}(|X-\mathbb{E}[X]|\geq t)\leq
2\exp{}\left(-\frac{t^{2}}{2\sum_{i=1}^{n}c_{i}^{2}}\right).$

###  2.2 Preliminaries for the DRGVR

##### An alternative viewpoint on the vertex process $(V_{n})_{n\geq 0}$.

In this section we introduce a formal framework that will help us to keep
track of the vertex process $(V_{n})_{n\geq 0}$. To begin with, we define
recursively a set of _marks_ $(\nu_{i,n})_{1\leq i\leq n}$ as follows:

  * •

if $n=1$, set $\nu_{1,1}=1$ if $\xi_{1}=1$ and $\nu_{1,1}=0$ otherwise,

  * •

if $n\geq 2$ and $\xi_{n}=1$, set $\nu_{i,n}=\nu_{i,n-1}$ for all $i\in[n-1]$
and $\nu_{n,n}=1$,

  * •

if $n\geq 2$ and $\xi_{n}=0$, select a uniformly random element $i_{n}$ from
$V_{n-1}$ and set $\nu_{i_{n},n}=\nu_{n,n}=0$ and $\nu_{i,n}=\nu_{i,n-1}$ for
all $i\in[n-1]\setminus\\{i_{n}\\}$.

Note that by definition $V_{n}=\\{i\in[n],\nu_{i,n}=1\\}$, so the set of all
marks contains the entire information for the vertex process $(V_{n})_{n\geq
1}$ (and is, in a sense, equivalent to it). From this point, we say that the
vertices in $V_{n}$ are the ones that are _alive after $n$ steps_ (of the
vertex process), or equivalently _survive after $n$ steps_. One advantage of
the marks is that they allow to describe the distribution of the alive
vertices in a clear way. More precisely, as we shall see in Lemma 4.2, the
empirical distribution

$\Gamma^{(n)}:=\frac{1}{n}\sum_{i=1}^{n}\delta_{(i/n,\nu_{i,n})}$ (13)

over the set $(0,1]\times\\{0,1\\}$, where $\delta_{(x,j)}$ denotes a Dirac
mass at the point $(x,j)\in(0,1]\times\\{0,1\\}$, converges in distribution to
the distribution $\Gamma$ defined in (8).

##### Further preliminary results.

We define

$\mathcal{Q}_{n}:=\\{||V_{n}|-2\varepsilon n|\leq n^{2/3}\\}.$ (14)

######  Lemma 2.5.

Fix $j\in[n]$ and $S\subset[n]$ such that $j=\omega(1)$ and $|S|=o(j^{2/3})$.
Then, there exists a constant $C=C(\varepsilon)>0$ such that

$\mathbb{P}(\mathcal{Q}_{j}^{c}\,\mid\,\forall i\in
S:\nu_{i,i}=1)\leq\mathrm{e}^{-Cj^{1/3}}.$ (15)

###### Proof.

The proof consists of two parts. For the lower bound, note that the process
$(|V_{i}|)_{i\geq 0}$ dominates a random walk $(S_{i})_{i\geq 0}$ on
$\mathbb{Z}$ that makes a step $+1$ with probability $p$ and $-1$ with
probability $1-p$. On the other hand, the variable
$\widehat{S}_{i}:=(S_{i}+i)/2$ has Binomial distribution with parameters $i$
and $p$. Using Chernoff’s inequality for the binomial random variable
$\widehat{S}_{j}$, we conclude that

$\displaystyle\mathbb{P}\left(|V_{j}|-2\varepsilon j\leq
j^{2/3}\,\Big{|}\,\forall i\in
S:\nu_{i,i}=1\right)\leq\;\mathbb{P}\left(|V_{j}|-2\varepsilon j\leq
j^{2/3}\right)\leq\mathbb{P}\left(S_{j}-2\varepsilon j\leq j^{2/3}\right)$
$\displaystyle\leq\;\mathbb{P}\left(\widehat{S}_{j}-(1/2+\varepsilon)j\leq
j^{2/3}/2\right)=\mathrm{e}^{-\Omega(j^{1/3})}.$

For the upper bound, for all $i\geq 0$ we define $Z_{i}$ as the number of
steps $r\in[i]$ at which $S_{r}=\min_{t\in[r]}S_{t}$, that is, the last step
of the random walk is a minimum of the walk up to now. We now show that
conditionally on the event $\\{\forall i\in S:\nu_{i,i}=1\\}$, $|V_{j}|$ is
dominated by the process $\widetilde{M}_{j}:=|S|+S_{j-|S|}+Z_{j-|S|}$. On the
one hand, $(|V_{i}|)_{i\geq 0}$ and $(S_{i}+Z_{i})_{i\geq 0}$ have the same
distribution (which is the one of a discrete biased random walk conditioned to
stay non-negative). On the other hand, $|V_{j}|$ conditioned on births at the
final $|S|$ steps stochastically dominates $|V_{j}|$ conditioned on
$\\{\forall i\in S:\nu_{i,i}=1\\}$ (i.e. births at steps $i\in S$) for any
other choice of $S\subseteq[j]$. Indeed, note that by introducing $|S|$
vertices at the last $|S|$ steps we ensure that none of these vertices is
removed until step $j$.

At the same time, the distribution of $\max_{i\geq 0}Z_{i}$ is dominated by a
geometric random variable since at every step $i\geq 0$, the event $\\{\forall
t>i,S_{t}-S_{i}>0\\}$ has strictly positive probability depending only on
$\varepsilon$, see e.g. Example 21.2 in [19]. Therefore, together with
Chernoff’s inequality, we get

$\displaystyle\mathbb{P}\left(|V_{j}|-2\varepsilon j\geq j^{2/3}\mid\forall
i\in S,\nu_{i,i}=1\right)\leq\;$
$\displaystyle\mathbb{P}\left(S_{j-|S|}+Z_{j-|S|}+|S|-2\varepsilon j\geq
j^{2/3}\right)$ $\displaystyle\leq\;$
$\displaystyle\mathbb{P}\left(S_{j-|S|}-2\varepsilon(j-|S|)\geq
j^{2/3}/3\right)+\mathbb{P}\left(Z_{j-|S|}\geq j^{2/3}/3\right)$
$\displaystyle\leq\;$
$\displaystyle\mathrm{e}^{-\Omega(j^{1/3})}+\mathrm{e}^{-\Omega(j^{2/3})}=\mathrm{e}^{-\Omega(j^{1/3})},$

which finishes the proof. ∎

Now, for $i\in[n]$ and a set $S\subseteq[i]$, define the event
$\mathcal{W}_{i}(S)=\\{S\subseteq V_{i}\\}$, that is, at each of the steps in
$S$, a vertex was born, and each of these vertices survives until step $i$.
Similarly to Lemma 2.5, the following lemma allows us to control the number of
vertices alive after $n$ steps conditionally on the introduction of vertices
at certain steps.

######  Lemma 2.6.

Fix $j=\omega((\log n)^{3})$ such that $j<n$, $S\subseteq[n]$ such that
$|S|=o(j^{2/3})$ and $R\subseteq[j]$ such that $R\cap S=\emptyset$ and
$|R|=o\left((\log n)^{2}\wedge\tfrac{j^{1/3}}{\log n}\right)$. Then,

$\mathbb{P}\left(\mathcal{W}_{n}(R)\mid\mathcal{W}_{n}(S)\cap\mathcal{W}_{j}(R)\right)=\left(\frac{j}{n}\right)^{|R|(1-p)/(2\varepsilon)}\left(1+\mathcal{O}\left(\frac{|R|\log
n}{j^{1/3}}\right)\right).$

The lemma implies that, in particular, as long as the set $S$ of vertices,
conditioned to survive after $n$ steps, is not “too large”, the probability
that a vertex is born at step $j$ and survives after step $n$ remains the same
as in the unconditional setting up to lower order terms.

###### Proof of Lemma 2.6.

First, note that

$\mathbb{P}\left(\mathcal{W}_{n}(R)\mid\mathcal{W}_{n}(S)\cap\mathcal{W}_{j}(R)\right)=\mathbb{E}\left[\prod_{\ell\in[j+1,n]\setminus
S}\left(1-\frac{|R|(1-p)}{|V_{\ell-1}\backslash S|}\right)\right].$ (16)

Indeed, at each step $\ell$ between $j+1$ and $n$ apart from the steps in $S$
(at which we know that no deletion takes place), a vertex in $R$ is deleted
with probability $\tfrac{|R|(1-p)}{|V_{\ell-1}\backslash S|}$. Define the
event

$\mathcal{C}_{n}:=\bigcap_{\ell\in[j+1,n]\setminus S}\mathcal{Q}_{\ell}\,.$
(17)

Using that $|V_{\ell-1}\backslash S|\leq|V_{\ell-1}|$ and
$1-x\leq\mathrm{e}^{-x}$ for all $x\in\mathbb{R}$, we obtain

$\displaystyle\mathbb{E}\left[\prod_{\ell\in[j+1,n]\setminus
S}\left(1-\frac{|R|(1-p)}{|V_{\ell-1}\backslash S|}\right)\right]$
$\displaystyle\leq\mathbb{E}\left[\mathbbm{1}_{\mathcal{C}_{n}}\prod_{\ell\in[j+1,n]\setminus
S}\left(1-\frac{|R|(1-p)}{|V_{\ell-1}\backslash
S|}\right)\right]+\mathbb{P}\left(\mathcal{C}_{n}^{c}\right)$ (18)
$\displaystyle\leq\prod_{\ell\in[j+1,n]\setminus
S}\exp\left(-\frac{|R|(1-p)}{2\varepsilon\ell+\ell^{2/3}}\right)+\mathbb{P}\left(\mathcal{C}_{n}^{c}\right).$
(19)

Moreover, Lemma 2.5 implies that

$\mathbb{P}\left(\mathcal{C}^{c}_{n}\right)\leq\sum_{\ell=j+1}^{n}\exp\left(-\Omega(\ell^{1/3})\right)\leq
n\exp\left(-\Omega(j^{1/3})\right)=o\left(n^{-|R|(1-p)/(2\varepsilon)}\right),$
(20)

where the third inequality follows from a union bound and Lemma 2.5.

Let us focus on the first term in (19). Transforming the above product into a
sum yields

$\exp\Big{(}-\frac{|R|(1-p)}{2\varepsilon}\sum_{\ell\in[j+1,n]\setminus
S}\frac{1}{\ell}\frac{1}{1+(2\varepsilon\ell^{1/3})^{-1}}\Big{)}\leq\exp\Big{(}-\frac{|R|(1-p)}{2\varepsilon}\Big{(}1-\frac{1}{2\varepsilon
j^{1/3}}\Big{)}\sum_{\ell\in[j+1,n]\setminus S}\frac{1}{\ell}\Big{)},$ (21)

where we used that $\tfrac{1}{1+(2\varepsilon\ell^{1/3})^{-1}}\geq
1-\tfrac{1}{2\varepsilon j^{1/3}}$ for all $\ell\geq j+1$.

Let us set $S_{>j}:=\\{s\in S:s>j\\}$ and write
$S_{>j}:=\\{s_{1},\ldots,s_{|S_{>j}|}\\}$ such that
$s_{0}:=j<s_{1}<\ldots<s_{|S_{>j}|}<s_{|S_{>j}|+1}:=n+1$. We can write the sum
on the right-hand side of (21) as

$\sum_{m=1}^{|S_{>j}|+1}\\!\\!\sum_{\ell=s_{m-1}+1}^{s_{m}-1}\frac{1}{\ell}\geq\\!\\!\sum_{m=1}^{|S_{>j}|+1}\\!\\!\int_{s_{m-1}+1}^{s_{m}}\frac{1}{x}\,\mathrm{d}x=\\!\\!\sum_{m=1}^{|S_{>j}|+1}\\!\\!\log\Big{(}\frac{s_{m}}{s_{m-1}+1}\Big{)}=\log\Big{(}\frac{n+1}{j+1}\Big{)}+\sum_{m=1}^{|S_{>j}|}\log\Big{(}1-\frac{1}{s_{m}+1}\Big{)}.$
(22)

Writing $\log(\tfrac{n+1}{j+1})\geq\log(\tfrac{n}{j})+\log(1-\tfrac{1}{j+1})$
and using that $s_{m}\geq j$ for all $m\in[|S_{>j}|]$, we thus have

$\sum_{\ell\in[j+1,n]\setminus
S}\frac{1}{\ell}\geq\log\left(\frac{n}{j}\right)+(|S_{>j}|+1)\log\left(1-\frac{1}{j+1}\right)\geq\log\left(\frac{n}{j}\right)-\mathcal{O}\left(\frac{|S_{>j}|+1}{j}\right).$
(23)

Using this bound in (21) then yields the upper bound

$\displaystyle\exp{}$
$\displaystyle\left(-\frac{|R|(1-p)}{2\varepsilon}\left(1-\frac{1}{2\varepsilon
j^{1/3}}\right)\left(\log\left(\frac{n}{j}\right)-\mathcal{O}\left(\frac{|S_{>j}|+1}{j}\right)\right)\right)$
(24)
$\displaystyle=\left(\frac{j}{n}\right)^{|R|(1-p)/(2\varepsilon)}\left(1+\mathcal{O}\left(\frac{|R|\log
n}{j^{1/3}}+\frac{|R|(|S_{>j}|+1)}{j}\right)\right)$
$\displaystyle=\left(\frac{j}{n}\right)^{|R|(1-p)/(2\varepsilon)}\left(1+\mathcal{O}\left(\frac{|R|\log
n}{j^{1/3}}\right)\right).$

The last step follows from the fact that
$\tfrac{|S_{>j}|}{j}\leq\tfrac{|S|}{j}=o(j^{-1/3})$, which concludes the proof
of the upper bound since $\mathbb{P}\left(\mathcal{C}^{c}_{n}\right)$ is of
smaller order than (24).

For a lower bound, we again use (16) to get

$\mathbb{P}\left(\mathcal{W}_{n}(R)\,|\,\mathcal{W}_{n}(S)\cap\mathcal{W}_{j}(R)\right)\geq\mathbb{E}\left[\mathbbm{1}_{\mathcal{C}_{n}}\prod_{\ell=j+1}^{n}\left(1-\frac{|R|(1-p)}{\max\\{|V_{\ell-1}|-|S|,1\\}}\right)\right],$
(25)

which holds since including more terms smaller than one in the product yields
a lower bound. On $\mathcal{C}_{n}$, it then follows that the right hand side
of (25) is at least

$(1-\mathbb{P}\left(\mathcal{C}_{n}^{c}\right))\prod_{\ell=j+1}^{n}\left(1-\frac{|R|(1-p)}{\max\\{2\varepsilon(\ell-1)-(\ell-1)^{2/3}-|S|,1\\}}\right).$
(26)

By the constraints on $|S|$, the denominator is larger than $1$ for any value
of $\ell\geq j+1$ and for any sufficiently large $n$, so that the maximum with
one can be omitted. Moreover,

$2\varepsilon(\ell-1)-(\ell-1)^{2/3}-|S|=2\varepsilon\ell-(1+o(1))\ell^{2/3}.$

Using this together with the inequality $1-x\geq\mathrm{e}^{-x-x^{2}}$ for all
sufficiently small $x$ yields the lower bound

$\exp\left(-\sum_{\ell=j+1}^{n}\frac{|R|(1-p)}{2\varepsilon\ell-(1+o(1))\ell^{2/3}}+\left(\frac{|R|(1-p)}{2\varepsilon\ell-(1+o(1))\ell^{2/3}}\right)^{2}\right)(1-\mathbb{P}\left(\mathcal{C}_{n}^{c}\right)).$
(27)

Since for every large enough $n$ we have
$2\varepsilon\ell-(1+o(1))\ell^{2/3}\geq\varepsilon\ell$, the exponential term
can be bounded from below by

$\displaystyle\exp{}\left(-\frac{|R|(1-p)}{2\varepsilon}\sum_{\ell=j+1}^{n}\frac{1}{\ell}\frac{1}{1-(1+o(1))(2\varepsilon\ell^{1/3})^{-1}}-C_{p,\varepsilon}|R|^{2}\sum_{\ell=j+1}^{\infty}\ell^{-2}\right)(1-\mathbb{P}\left(\mathcal{C}_{n}^{c}\right))$
(28)
$\displaystyle\geq\exp\left(-\frac{|R|(1-p)}{2\varepsilon}\log\left(\frac{n}{j}\right)\left(1+\frac{1}{(\varepsilon
j)^{1/3}}\right)-\frac{C_{p,\varepsilon}|R|^{2}}{j}\right)(1-\mathbb{P}\left(\mathcal{C}_{n}^{c}\right)),$
(29)

where the final step holds for all sufficiently large $n$ and a sufficiently
large constant $C_{p,\varepsilon}>0$. By the upper bound on the probability in
(20), we finally arrive at the lower bound

$\displaystyle\left(\frac{j}{n}\right)^{|R|(1-p)/(2\varepsilon)}\left(1-\mathcal{O}\left(\frac{|R|\log
n}{j^{1/3}}\right)\right)\left(1-\mathcal{O}(\mathrm{e}^{-(j-1)^{1/3}/3}(j-1)^{2/3})\right)$
$\displaystyle=$
$\displaystyle\left(\frac{j}{n}\right)^{|R|(1-p)/(2\varepsilon)}\left(1-\mathcal{O}\left(\frac{|R|\log
n}{j^{1/3}}\right)\right),$

which, combined with the upper bound in (24), yields the desired result. ∎

######  Lemma 2.7.

Fix $i=i(n)=\omega((\log n)^{3})$ and set
$\\{v_{1},\ldots,v_{|V_{n}|}\\}=V_{n}$, where the vertices are listed in
increasing order of their labels.

  1. (i)

$\mathbb{P}(v_{1}\text{ is well defined and }v_{1}\leq
i)\leq\frac{i^{p/(2\varepsilon)}}{n^{(1-p)/(2\varepsilon)}}$;

  2. (ii)

Fix $\ell=\lceil 4\varepsilon(\log n)^{p/\varepsilon}\rceil$. Then, there is a
sequence $(\delta_{i})_{i=1}^{\infty}$ satisfying $\delta_{n}=o(1)$ such that
w.h.p. for all $j\in[\ell,|V_{n}|]$ one has

$v_{j}\in\left[(1-\delta_{n})n^{(1-p)/p}\left(\frac{j}{2\varepsilon}\right)^{(2\varepsilon)/p},(1+\delta_{n})n^{(1-p)/p}\left(\frac{j}{2\varepsilon}\right)^{(2\varepsilon)/p}\right].$
(30)

###### Proof.

First, we conduct a first moment computation used in the proof of both Parts
(i) and (ii). For every $i\in\mathbb{N}$, set $M_{i,n}:=|V_{i}\cap V_{n}|$ and
recall the event $\mathcal{Q}_{i}:=\\{||V_{i}|-2\varepsilon i|\leq
i^{2/3}\\}$. Together with Lemma 2.6 applied with $i$ instead of $j$,
$S=\emptyset$ and $R$ being a single vertex in $V_{i}$, this implies that

$\displaystyle\mathbb{E}[M_{i,n}]$
$\displaystyle=\;\sum_{j=1}^{i}\mathbb{P}(\nu_{j,n}=1)=\sum_{j=1}^{i}\mathbb{P}(\nu_{j,i}=1)\mathbb{P}(\nu_{j,n}=1\mid\nu_{j,i}=1)=\mathbb{P}(\nu_{i,n}=1\mid\nu_{i,i}=1)\mathbb{E}|V_{i}|$
(31) $\displaystyle=\;\left(1+\mathcal{O}\left(\frac{\log
n}{i^{1/3}}\right)\right)\frac{2\varepsilon
i^{1+(1-p)/(2\varepsilon)}}{n^{(1-p)/(2\varepsilon)}}=\left(1+\mathcal{O}\left(\frac{\log
n}{i^{1/3}}\right)\right)\frac{2\varepsilon
i^{p/(2\varepsilon)}}{n^{(1-p)/(2\varepsilon)}},$ (32)

where the third equality uses that the probability that a vertex is born at
step $j<i$ and survives after step $n$, knowing that it survives after step
$i$, is the same as the probability that a vertex born at step $i$ survives
after $n$ steps. Part (i) readily follows from (32) by Markov’s inequality.

Now, we prove Part (ii) by a second moment argument. From now on, we assume
that $i=\omega(n^{(1-p)/p})$ so that $\mathbb{E}M_{i,n}=\omega(1)$. Similar
reasoning as above implies

$\displaystyle\sum_{j_{1},j_{2}\in[i];\;j_{1}\neq
j_{2}}\mathbb{P}(\nu_{j_{1},n}=\nu_{j_{2},n}=1)=\sum_{j_{1},j_{2}\in[i];\;j_{1}\neq
j_{2}}\mathbb{P}(\nu_{j_{1},i}=\nu_{j_{2},i}=1)\mathbb{P}(\nu_{j_{1},n}=\nu_{j_{2},n}=1\mid\nu_{j_{1},i}=\nu_{j_{2},i}=1).$

Using Lemma 2.6 applied with $i$ instead of $j$, $S=\emptyset$ and $R$ being a
pair of vertices in $V_{i}$ for the first term, for all $j_{1}\neq j_{2}$ we
get

$\mathbb{P}(\nu_{j_{1},n}=\nu_{j_{2},n}=1\mid\nu_{j_{1},i}=\nu_{j_{2},i}=1)=\left(1+\mathcal{O}\left(\frac{\log
n}{i^{1/3}}\right)\right)\frac{i^{(1-p)/\varepsilon}}{n^{(1-p)/\varepsilon}}.$

Moreover, by Lemma 2.5 applied with $\mathcal{Q}_{i}$ and $S=\emptyset$,

$\displaystyle\sum_{j_{1},j_{2}\in[i];\;j_{1}\neq
j_{2}}\mathbb{P}(\nu_{j_{1},i}=\nu_{j_{2},i}=1)$
$\displaystyle=\;\mathbb{E}[|V_{i}|^{2}]-\mathbb{E}[|V_{i}|]=\mathbb{E}[|V_{i}|^{2}\mid\mathcal{Q}_{i}]-\mathbb{E}[|V_{i}|\mid\mathcal{Q}_{i}]+\mathcal{O}(i^{2}\mathbb{P}(\mathcal{Q}_{i}^{c}))$
$\displaystyle=\;\left(1+\mathcal{O}\left(\frac{1}{i^{1/3}}\right)\right)4i^{2}\varepsilon^{2}.$

We conclude that

$\displaystyle\mathbb{E}[M_{i,n}^{2}]-\mathbb{E}[M_{i,n}]^{2}$
$\displaystyle\leq\;\mathbb{E}[M_{i,n}]+\sum_{j_{1},j_{2}\in[i];\;j_{1}\neq
j_{2}}\mathbb{P}(\nu_{j_{1},n}=\nu_{j_{2},n}=1)-\left(1+\mathcal{O}\left(\frac{\log
n}{i^{1/3}}\right)\right)\frac{(2\varepsilon)^{2}i^{p/\varepsilon}}{n^{(1-p)/\varepsilon}}$
$\displaystyle=\;\left(1+\mathcal{O}\left(\frac{\log
n}{i^{1/3}}\right)\right)\frac{2\varepsilon
i^{p/(2\varepsilon)}}{n^{(1-p)/(2\varepsilon)}}+\mathcal{O}\left(\frac{i^{p/\varepsilon-1/3}\log
n}{n^{(1-p)/\varepsilon}}\right)$
$\displaystyle=\;\mathbb{E}[M_{i,n}]^{2}\mathcal{O}\left(\frac{\log
n}{i^{1/3}}+\frac{n^{(1-p)/(2\varepsilon)}}{i^{p/(2\varepsilon)}}\right),$

where we used (32) in the last equality. Define $\psi(i):=\tfrac{\log
n}{i^{1/3}}+\tfrac{n^{(1-p)/(2\varepsilon)}}{i^{p/(2\varepsilon)}}$; then,
Chebyshev’s inequality implies

$\mathbb{P}(|M_{i,n}-\mathbb{E}[M_{i,n}]|\geq\psi(i)^{-1/3}\mathbb{E}[M_{i,n}])\leq\frac{\mathbb{E}[|M_{i,n}-\mathbb{E}[M_{i,n}]|^{2}]}{(\psi(i)^{-1/3}\mathbb{E}M_{i,n})^{2}}=\mathcal{O}\big{(}\psi(i)^{5/3}\big{)}.$
(33)

Now, set $\alpha=\alpha(n)=((n^{(1-p)/p}(\log n)^{2})^{-1}n)^{1/\lfloor\log
n\rfloor^{2}}$, and for all integer $k$ between $0$ and $\lfloor\log
n\rfloor^{2}$, set $i_{k}=\lfloor\alpha^{k}n^{(1-p)/p}(\log n)^{2}\rfloor$. By
(33) we have that for all $k$ as above,
$|M_{i_{k},n}-\mathbb{E}[M_{i_{k},n}]|\geq\psi(i_{k})^{-1/3}\mathbb{E}[M_{i_{k},n}]$
holds with probability $\mathcal{O}\big{(}\psi(i_{k})^{5/3}\big{)}$. Moreover,
since $i_{k}$ is increasing in $k$ (for $n$ sufficiently large), $\phi(i)$
decreasing in $i$ and $5p>9\varepsilon$,

$\sum_{k=1}^{\lfloor\log n\rfloor^{2}}\psi(i_{k})^{5/3}\leq\lfloor\log
n\rfloor^{2}\psi(i_{0})^{5/3}=\mathcal{O}\big{(}(\log
n)^{2-5p/(3\varepsilon)}\big{)}=o(1).$ (34)

Thus, a union bound over all $\lfloor\log n\rfloor^{2}+1$ values of $k$ shows
that the event

$\mathfrak{G}:=\\{\text{for all positive integers }k\leq\lfloor(\log
n)^{2}\rfloor,M_{i_{k},n}=(1+o(1))\mathbb{E}[M_{i_{k},n}]\\}$

holds w.h.p.

Finally, note that $(M_{i,n})_{i=1}^{n}$ is an increasing sequence of random
variables since for all $i<j$ one has $V_{i}\cap V_{n}\subseteq V_{j}\cap
V_{n}$. Thus, conditionally on the event $\mathfrak{G}$, for all positive
integers $k\leq\lfloor(\log n)^{2}\rfloor$ and $i\in[i_{k-1},i_{k}]$,

$1-o(1)=(1-o(1))\frac{\mathbb{E}[M_{i_{k-1},n}]}{\mathbb{E}[M_{i_{k},n}]}\leq\frac{M_{i_{k-1},n}}{\mathbb{E}[M_{i_{k},n}]}\leq\frac{M_{i,n}}{\mathbb{E}[M_{i,n}]}\leq\frac{M_{i_{k},n}}{\mathbb{E}[M_{i_{k-1},n}]}\leq(1+o(1))\frac{\mathbb{E}[M_{i_{k},n}]}{\mathbb{E}[M_{i_{k-1},n}]}=(1+o(1)),$

where the first and the last equalities follow from the fact that, for every
positive integer $k\leq\lfloor(\log n)^{2}\rfloor$,
$\mathbb{E}[M_{i_{k-1},n}]/\mathbb{E}[M_{i_{k},n}]=(1+o(1))(i_{k-1}/i_{k})^{p/(2\varepsilon)}=(1+o(1))$.
Hence, w.h.p. $M_{i,n}=(1+o(1))\mathbb{E}[M_{i,n}]$ for all $i\in[i_{0},n]$.
This allows us to conclude that, since

$v_{j}=\min\\{t\in[n]:|V_{t}\cap V_{n}|=j\\},$

for all vertices but the first
$(1+o(1))\mathbb{E}M_{i_{0},n}=(1+o(1))2\varepsilon(\log
n)^{p/\varepsilon}\leq\ell$ many, we have that w.h.p. the value of $v_{j}$ is
given, up to a $1+o(1)$ factor, by the solution of the equation

$\frac{2\varepsilon v_{j}^{p/(2\varepsilon)}}{n^{(1-p)/(2\varepsilon)}}=j,$

which yields $v_{j}=n^{(1-p)/p}(j/2\varepsilon)^{(2\varepsilon)/p}$ and
completes the proof of the lemma. ∎

##  3 Theorem 1.3: setting up the framework

To start this section, we introduce some important notations. For any non-
negative integer $r$, any graph $G$ and any vertex $v$ in $G$, we denote by
$\partial B_{r}(G,v)$ the set of vertices at graph distance exactly $r$ from
$v$ in $G$, that is, $\partial B_{r}(G,v)=B_{r}(G,v)\setminus B_{r-1}(G,v)$.
Note that $v$ will often be the root in some rooted graph. Also, some graphs
in this paper will be naturally defined as rooted, in which case we often omit
the root from the notation. Recall that for a random variable $X$, we denote
by $\mathcal{L}(X)$ the distribution of $X$.

##### The exploration process.

Recall the definition of the DRGVR model $G_{n}$ and the Binomial birth-death
tree $\mathcal{T}$ in Definitions 1.1 and 1.2, respectively. To prove the
local weak convergence of $G_{n}$ to $\mathcal{T}$, we couple the
neighbourhood of the root 0 in $\mathcal{T}$ and the neighbourhood of a vertex
$k_{0}$ in $G_{n}$ chosen uniformly at random. More precisely, we couple the
breadth-first search (BFS) exploration of the neighbourhood of $k_{0}$ in
$G_{n}$ with the iterative construction of $\mathcal{T}$, starting from the
root vertex $0$. In this section we provide some notation for this BFS
exploration.

We start by introducing the _Ulam-Harris tree_ , which we use to unify the
notation that underpins the construction of the multi-type branching process
$\mathcal{T}$ and the BFS exploration of the neighbourhood of $k_{0}$ in
$G_{n}$. The Ulam-Harris tree is an infinite rooted tree constructed as
follows: its root vertex is denoted by $0$ and for all $r\geq 0$, the children
of any vertex $u:=(0,u_{1},\ldots,u_{r})$ (where
$u_{1},\ldots,u_{r}\in\mathbb{N}$) are given by $((u,i))_{i\in\mathbb{N}}$. In
this way, the vertex $u:=(0,u_{1},\ldots,u_{r})$ is the $u_{r}^{\text{th}}$
child of the $u_{r-1}^{\text{th}}$ child of $\ldots$ of the
$u_{1}^{\text{th}}$ child of the root $0$ in the breath-first order.

Furthermore, we introduce an ordering $<_{\mathrm{UH}}$ on the vertices in the
Ulam-Harris tree. For two vertices $u:=(0,u_{1},\ldots,u_{r})$ and
$v:=(0,v_{1},\ldots,v_{k})$ (with $r,k\in\mathbb{N}_{0}$ and
$(u_{i})_{i=1}^{r}\in\mathbb{N}^{r},(v_{i})_{i=1}^{k}\in\mathbb{N}^{k}$), we
write $u<_{\mathrm{UH}}v$ when $u$ is smaller than $v$ in BFS order. That is,
when either $r<k$ or $r=k$ and $u_{j}<v_{j}$, where
$j:=\min\\{i\in[r]:u_{i}\neq v_{i}\\}$. For example
$(0,1,2,3)<_{\mathrm{UH}}(0,1,2,3,4)$ and $(0,2,5,4)<_{\mathrm{UH}}(0,2,6,3)$.
In a similar manner, we define the ordering $\leq_{\mathrm{UH}}$.

From now on, we see the tree $\mathcal{T}$ as a random sub-tree of the Ulam-
Harris tree. More precisely, if a vertex
$u:=(0,u_{1},\ldots,u_{r})\in\mathcal{T}$ has $\tau_{u}$ children, these are
labeled $(u,i)_{i=1}^{\tau_{u}}$ in increasing order of their types. Moreover,
we slightly abuse notation and use the Ulam-Harris formalism for the BFS
exploration of the neighbourhood of $k_{0}$ in $G_{n}$. This provides more
structure when keeping track of the BFS exploration and the parallel iterative
construction of $\mathcal{T}$. For a vertex $v=(0,v_{1},\ldots,v_{r})$ for
some $r\geq 0$ and $v_{1},\ldots,v_{r}\in\mathbb{N}$ in the sub-tree of the
Ulam-Harris tree obtained from the BFS exploration of $k_{n}$ in $G_{n}$, we
let $k_{v}\in[n]$ denote its label in $G_{n}$. In what follows, we identify
the vertex $v$ in the BFS exploration of $G_{n}$ by its label $k_{v}$. To
illustrate: $0$ has label $k_{0}$, and this is the root of the BFS
exploration. The neighbours of $0$ are $((0,i))_{i=1}^{\theta_{0}}$, where
$\theta_{0}$ denotes the number of neighbours of $k_{0}$ in $G_{n}$, and their
labels are $(k_{(0,i)})_{i=1}^{\theta_{0}}$. This is continued throughout the
BFS exploration. For convenience of notation we skip the parentheses and write
$k_{0,v_{1},\ldots,v_{r}}$ for the label of the vertex
$(0,v_{1},\ldots,v_{r})$.

In the BFS exploration, we consider nodes to be active, probed or neutral and
denote by
$(\mathcal{A}_{t},\mathcal{P}_{t},\mathcal{N}_{t})_{t\in\mathbb{N}_{0}}$ the
sets of active, probed and neutral vertices after $t$ steps of the
exploration, respectively. We initialise the process by setting

$(\mathcal{A}_{0},\mathcal{P}_{0},\mathcal{N}_{0})=(\\{k_{0}\\},\emptyset,V_{n}\backslash\\{k_{0}\\}).$
(35)

We also let $k[t]$ denote the active vertex with smallest BFS order in
$\mathcal{A}_{t-1}$. That is, $k[1]=k_{0}$ and for $t\geq 1$, if
$k_{v}\in\mathcal{A}_{t-1}$ and $v<_{\mathrm{UH}}u$ for all
$u\in\mathcal{A}_{t-1}\backslash\\{v\\}$, then $k[t]=k_{v}$. Let
$\mathcal{D}_{t}:=\\{u\in\mathcal{N}_{t-1}:\\{u,k[t]\\}\in E(G_{n})\\}$ denote
the set of neutral vertices attached to $k[t]$. Then, we update

$(\mathcal{A}_{t+1},\mathcal{P}_{t+1},\mathcal{N}_{t+1})=((\mathcal{A}_{t}\backslash\\{k[t]\\})\cup\mathcal{D}_{t},\mathcal{P}_{t}\cup\\{k[t]\\},\mathcal{N}_{t}\,\backslash\,\mathcal{D}_{t}),$
(36)

and if $\mathcal{A}_{t}=\emptyset$, we set
$(\mathcal{A}_{t+1},\mathcal{P}_{t+1},\mathcal{N}_{t+1})=(\mathcal{A}_{t},\mathcal{P}_{t},\mathcal{N}_{t})$.

Due to the definition of the DRGVR model it is convenient to split the
vertices in the BFS exploration into two parts. Indeed, for a vertex with
label $k_{v}$ the probability to connect to a vertex with a _smaller_ label is
different than to be connected to a vertex with a _larger_ label. As a result,
for each vertex $k_{v}$ we consider its neighbours to the _left_ (i.e.
vertices with a smaller label than $k_{v}$) and to the _right_ (i.e. vertices
with a larger label than $k_{v}$). We refer to these as the $L$-neighbours and
$R$-neighbours of $k_{v}$, respectively. Furthermore, we let $\theta_{v}^{L}$
and $\theta_{v}^{R}$ denote the number of $L$-neighbours and $R$-neighbours of
$k_{v}$, respectively, and set $\theta_{v}:=\theta_{v}^{L}+\theta_{v}^{R}$ to
be the number of neighbours of $v$ in the BFS exploration.

In an equivalent manner, we can define the $L$-children and $R$-children of a
vertex $v$ in the multi-type branching process $\mathcal{T}$ as in Definition
1.2. If we let $\tau_{v}$ denote the number of children of $v$, then the
$L$-children (respectively $R$-children) of $v$ are the children
$(v,i)_{i=1}^{\tau_{v}}$ such that $a_{v,i}<a_{v}$ (respectively
$a_{v,i}>a_{v}$). Let us write $\tau_{v}^{L}$ and $\tau_{v}^{R}$ for the
number of $L$-children and $R$-children of $v$, respectively. As we order the
children in increasing order of their types, it follows that
$(v,i)_{i=1}^{\tau_{v}^{L}}$ are $v$’s $L$-children and
$(v,i)_{i=\tau_{v}^{L}+1}^{\tau_{v}^{L}+\tau_{v}^{R}}$ are $v$’s $R$-children.

##  4 Coupling the $1$-neighbourhoods of $k_{0}$ in $G_{n}$ and $0$ in
$\mathcal{T}$

In this section we provide a coupling between the neighbours of $k_{0}$ in the
BFS exploration of $G_{n}$ and the children of the root $0$ of $\mathcal{T}$.
The coupling should be such that:

  1. (i)

the number of $L$\- and $R$-neighbours of $k_{0}$ in $G_{n}$ are equal to the
number of $L$\- and $R$-children of $0$,

  2. (ii)

the rescaled labels of the neighbours of $k_{0}$ and the types of the children
of $0$ are approximately the same.

Whilst $(ii)$ is not directly necessary for the $1$-neighbourhoods of $k_{0}$
and $0$ to be isomorphic, it aids in providing a coupling such that the
$2$-neighbourhoods are isomorphic.

In this section, we prove that the following events occur with high
probability:

$\displaystyle\mathcal{H}_{1,0}$ $\displaystyle:=\\{a_{0}\geq 1/\log\log
n\\},$ (37) $\displaystyle\mathcal{H}_{1,1}$
$\displaystyle:=\\{\min_{i\in[\tau_{0}^{L}]}a_{0,i}>1/(\log\log n)^{2}\\},$
$\displaystyle\mathcal{H}_{1,2}$
$\displaystyle:=\\{(B_{1}(G_{n},k_{0}),k_{0})\cong(B_{1}(\mathcal{T},0),0)\\}\cap\\{\forall
v\in V(B_{1}(\mathcal{T},0)),|a_{v}-\tfrac{k_{v}}{n}|\leq\tfrac{2}{n}\\},$
$\displaystyle\mathcal{H}_{1,3}$
$\displaystyle:=\\{\tau_{0}^{L}+\tau_{0}^{R}<\log\log n\\}.$

In words, the events $\mathcal{H}_{1,0}$ and $\mathcal{H}_{1,1}$ control the
types of the root $0$ and the $L$-children of the root $0$ in $\mathcal{T}$,
and ensure that these types are not “too small”. Similarly, the event
$\mathcal{H}_{1,3}$ ensures that the number of children of the root $0$ in
$\mathcal{T}$ is not “too large”. The event $\mathcal{H}_{1,2}$ then states
that the $1$-neighbourhoods of $k_{0}$ in $G_{n}$ and $0$ in $\mathcal{T}$ are
isomorphic and that the rescaled labels of the neighbours of $k_{0}$ in
$G_{n}$ are very close to the types of their corresponding counterparts in
$\mathcal{T}$. As mentioned, the events
$\mathcal{H}_{1,0},\mathcal{H}_{1,1},\mathcal{H}_{1,3}$ and the part of the
event $\mathcal{H}_{1,2}$ that states that the labels $k_{v}$ are
“sufficiently close” to the types $a_{v}$ are not strictly necessary for the
local convergence of the $1$-neighbourhoods to hold. However, they are
important to control error bounds, which are key to extend the coupling to the
$r$-neighbourhood later on (for any $r\geq 2$). More details related to this
follow in the upcoming sections.

We now state the main result of this section.

######  Lemma 4.1.

Fix $\beta>0$ and $\varepsilon\in(0,1/2]$, and consider the DRGVR model and
the Binomial birth-death tree model as in Definitions 1.1 and 1.2,
respectively. Recall the events $(\mathcal{H}_{1,i})_{i=0}^{4}$ from (37).
There exists a constant $C=C(\beta,\varepsilon)>0$ such that, for all
sufficiently large $n$,

$\mathbb{P}\bigg{(}\Big{(}\bigcap_{i=0}^{3}\mathcal{H}_{1,i}\Big{)}^{c}\bigg{)}\leq\frac{C}{(\log\log
n)^{p/(2\varepsilon)}}.$ (38)

Note that we can bound the probability in the statement of Lemma 4.1 from
above by

$\mathbb{P}\bigg{(}\Big{(}\bigcap_{i=0}^{3}\mathcal{H}_{1,i}\Big{)}^{c}\bigg{)}\leq\mathbb{P}\left(\mathcal{H}_{1,0}^{c}\right)+\mathbb{P}\left(\mathcal{H}_{1,1}^{c}\cap\mathcal{H}_{1,0}\right)+\mathbb{P}\left(\mathcal{H}_{1,3}^{c}\right)+\mathbb{P}\left(\mathcal{H}_{1,2}^{c}\cap\mathcal{H}_{1,0}\right).$
(39)

The first term on the right-hand side is readily bounded: since
$a_{0}\sim\text{Beta}(\tfrac{p}{2\varepsilon},1)$, it directly follows that

$\mathbb{P}\left(\mathcal{H}_{1,0}^{c}\right)=(\log\log
n)^{-p/(2\varepsilon)}.$ (40)

Let us write $\mathbf{V}^{L}_{0}$ for the Poisson point process on $(0,a_{0})$
with density $\lambda_{0}^{-}(\mathrm{d}x)$ as in (2). Using the construction
of the offspring of the root as in Definition 1.1, we can write

$\mathcal{H}_{1,1}=\\{\mathbf{V}^{L}_{0}\cap(0,1/(\log\log
n)^{2})=\emptyset\\}.$ (41)

As a result, conditionally on $a_{0}$,

$\displaystyle\mathbb{P}(\mathcal{H}^{c}_{1,1}\cap\mathcal{H}_{1,0})=\mathbb{P}\left(\mathbf{V}^{L}_{0}\cap(0,1/(\log\log
n)^{2})\neq\emptyset)\,|\,\mathcal{H}_{1,0}\right)\mathbb{P}\left(\mathcal{H}_{1,0}\right)$
(42)

Conditionally on $a_{0}$ and the event $\mathcal{H}_{1,0}$, and using that
$1-\mathrm{e}^{-x}\leq x$ for all $x\in\mathbb{R}$, we deduce that (42) is
bounded from above by

$1-\exp\Big{(}-\frac{\beta}{a_{0}}(\log\log n)^{-p/\varepsilon}\Big{)}\leq
1-\exp\big{(}-\beta(\log\log
n)^{1-p/\varepsilon}\big{)}\leq\beta\big{(}\log\log
n\big{)}^{-1/(2\varepsilon)},$ (43)

so that taking the expected value with respect to $a_{0}$ yields

$\mathbb{P}\left(\mathcal{H}^{c}_{1,1}\cap\mathcal{H}_{1,0}\right)=\mathcal{O}\Big{(}\big{(}\log\log
n\big{)}^{-1/(2\varepsilon)}\Big{)}.$ (44)

Furthermore, conditionally on $a_{0}$, $\tau^{L}_{0}+\tau^{R}_{0}$ is Poisson
distributed with rate

$\displaystyle\int_{0}^{a_{0}}\lambda_{0}^{-}(\mathrm{d}x)+\int_{a_{0}}^{1}\lambda^{+}(\mathrm{d}x)$
$\displaystyle=\frac{\beta
p}{2\varepsilon}\bigg{[}\int_{0}^{a_{0}}\frac{x^{(1-p)/(2\varepsilon)}}{a_{0}}\,\mathrm{d}x+\int_{a_{0}}^{1}x^{(1-p)/(2\varepsilon)-1}\,\mathrm{d}x\bigg{]}$
(45) $\displaystyle=\beta a_{0}^{(1-p)/(2\varepsilon)}+\frac{\beta
p}{1-p}\big{(}1-a_{0}^{(1-p)/(2\varepsilon)}\big{)}\leq\frac{\beta p}{1-p}.$

As a result, $\tau^{L}_{0}+\tau^{R}_{0}$ is stochastically dominated by
$\tau^{\prime}\sim\text{Poi}(\tfrac{\beta p}{1-p})$. It follows that for any
$t>0$,

$\mathbb{P}\left(\mathcal{H}_{1,3}^{c}\right)\leq\mathbb{P}\left(\tau^{\prime}\geq\log\log
n\right)\leq\frac{\mathbb{E}[\mathrm{e}^{t\tau^{\prime}}]}{\mathrm{e}^{t\log\log
n}}=\frac{\mathrm{e}^{(\beta p/(1-p))(\mathrm{e}^{t}-1)}}{(\log
n)^{t}}=o((\log\log n)^{-p/(2\varepsilon)}),$ (46)

where the second inequality follows from a Chernoff bound. The main goal in
this section is thus to construct a coupling such that the probability of
$\mathcal{H}_{1,2}^{c}\cap\mathcal{H}_{1,0}$ is $\mathcal{O}(\big{(}\log\log
n)^{-p/(2\varepsilon)})$.

###  4.1 Coupling the roots of $G_{n}$ and $\mathcal{T}$

We start by coupling the root vertex $0$ of $\mathcal{T}$ and the uniform
vertex $k_{0}$ from $V_{n}$, which in this model is non-trivial. Note that in
the proofs of the local weak convergence of preferential attachment models to
the Pólya point tree, which are similar in nature, the vertex $k_{0}$ is
uniform among $[n]$ and the root of the tree has a type
$a_{0}\sim\text{Unif}(0,1)$. Hence, a simple coupling via $k_{0}:=\lceil
a_{0}n\rceil$ provides that $k_{0}/n$ and $a_{0}$ are sufficiently close. In
our case, since $V_{n}$ is a random subset of $[n]$, this coupling requires
more work.

Let us define

$\mathcal{R}_{0}:=\\{a_{0}\leq\tfrac{k_{0}}{n}\leq a_{0}+\tfrac{1}{n}\\}.$
(47)

We show the following result.

######  Lemma 4.2.

Consider the DRGVR model and the Binomial birth-death tree model as in
Definitions 1.1 and 1.2, respectively. Let $k_{0}$ be a uniform vertex from
$V_{n}$. Then, there exists a constant $c=c(\beta,\varepsilon)>0$ and a
coupling of $k_{0}$ and the root vertex $0$ of $\mathcal{T}$ such that

$\mathbb{P}\left(\mathcal{R}_{0}^{c}\right)\leq\frac{c}{\log n}.$ (48)

###### Proof.

We sample an i.i.d. sequence $(X_{0}^{j},Y_{0}^{j})_{j\in\mathbb{N}}$ with
distribution $\Gamma$ (defined in (8)). Let
$\kappa_{0}=\inf\\{j\in\mathbb{N}:Y_{0}^{j}=1\\}$ and set
$a_{0}:=X_{0}^{\kappa_{0}}$ as the type of $0$. By Lemma 2.1, $a_{0}$ has the
desired distribution. We define $k_{0}^{j}:=\lceil nX_{0}^{j}\rceil$ as a
uniform vertex in $[n]$, and write its mark as
$\nu_{0}^{j}:=\nu_{k_{0}^{j},n}$ for brevity. We also introduce
$\psi_{0}:=\inf\\{j\in\mathbb{N}:\nu_{0}^{j}=1\\}$ and set
$k_{0}:=k_{0}^{\psi_{0}}$. Note that since the mark of $k_{0}$ equals one,
$k_{0}$ is uniform among all vertices with mark one, so $k_{0}$ also has the
desired distribution. Our aim is to couple $\kappa_{0}$ and $\psi_{0}$ so that
$\kappa_{0}=\psi_{0}$ with probability at least $1-c/\log n$. Indeed,
conditionally on the equality $\kappa_{0}=\psi_{0}$,
$a_{0}\leq\tfrac{k_{0}}{n}\leq a_{0}+\tfrac{1}{n}$ holds a.s.

We couple $\nu_{0}^{j}$ with
$Y^{j}_{0}\sim\text{Ber}(p(X_{0}^{j})^{(1-p)/(2\varepsilon)})$ using a
standard Bernoulli coupling, which conditionally on $X_{0}^{j}$ fails with
probability

$\big{|}\mathbb{P}\big{(}\nu_{0}^{j}=1\,|\,X_{0}^{j}\big{)}-\mathbb{P}(Y^{j}_{0}=1\,|\,X_{0}^{j})\big{|}.$
(49)

We say the coupling is successful at step $j$ when $\nu_{0}^{j}=Y_{0}^{j}$,
and that the entire coupling is successful when $\kappa_{0}=\psi_{0}$, i.e.
$\nu_{0}^{j}=Y_{0}^{j}$ for all $j\in[\kappa_{0}]$. Hence,

$\mathbb{P}\left(\text{Coupling
fails}\right)=\mathbb{P}\left(\kappa_{0}\neq\psi_{0}\right)=\mathbb{E}\left[\mathbb{P}\left(\cup_{j=1}^{\kappa_{0}}\\{\text{Coupling
fails at step $j$}\\}\,\Big{|}\,\kappa_{0}\right)\right].$ (50)

Since we have coupled $\nu_{0}^{j}$ and $Y_{0}^{j}$ at every step with a
probability of failure as in (49), it follows that independently of the value
of $Y_{0}^{j}$ (which is known for each $j\in[\kappa_{0}]$ when we condition
on $\kappa_{0}$), the probability of the event $\\{\nu_{0}^{j}\neq
Y_{0}^{j}\\}$ can be bounded from above by (49). Using a union bound and
observing that the expression in (49) is in fact independent of $j$, we thus
obtain the upper bound

$\displaystyle\mathbb{E}\left[\kappa_{0}\mathbb{E}\left[\big{|}\mathbb{P}\big{(}\nu^{1}_{0}=1\,|\,X_{0}^{1}\big{)}-\mathbb{P}\left(Y_{0}^{1}=1\,|\,X_{0}^{1}\right)\big{|}\right]\right],$
(51)

where the inner expected value is with respect to $X_{0}^{1}$ and the outer
expected value with respect to $\kappa_{0}$. Conditionally on $X_{0}^{1}$, it
follows from Lemma 2.6 and Lemma 2.1 that

$\mathbb{P}\left(\nu_{0}^{1}=1\,|\,X_{0}^{1}\right)=p\Big{(}\frac{\lceil
nX_{0}^{1}\rceil}{n}\Big{)}^{(1-p)/(2\varepsilon)}\Big{(}1+\mathcal{O}\Big{(}\frac{\log
n}{\lceil
nX_{0}^{1}\rceil^{1/3}}\Big{)}\Big{)}=\mathbb{P}\left(Y_{0}^{1}=1\,|\,X_{0}^{1}\right)\Big{(}1+\mathcal{O}\Big{(}\frac{\log
n}{\lceil nX_{0}^{1}\rceil^{1/3}}\Big{)}\Big{)}.$ (52)

On the event $\\{X_{0}^{1}\geq\tfrac{1}{\log n}\\}$, this yields

$\mathbb{P}\left(Y_{0}^{1}=1\,|\,X_{0}^{1}\right)+\mathcal{O}\Big{(}\frac{(\log
n)^{4/3}}{n^{1/3}}\Big{)}.$ (53)

Hence, for some positive constants $C,c>0$,

$\mathbb{P}\left(\text{Coupling fails}\right)\leq\mathbb{P}(\text{Coupling
fails}\mid X_{0}^{1}\geq\tfrac{1}{\log n})+\mathbb{P}(X_{0}^{1}<\tfrac{1}{\log
n})\leq C\frac{(\log
n)^{4/3}}{n^{1/3}}\mathbb{E}\left[\kappa_{0}\right]+\frac{1}{\log
n}\leq\frac{c}{\log n},$ (54)

where we used that $\mathbb{E}[\kappa_{0}]<\infty$ since $\kappa_{0}$ has
geometric distribution with parameter $2\varepsilon$. This concludes the
proof. ∎

Having coupled the roots, we can start coupling their direct neighbours.
Recall that $\theta_{0}^{L}$ and $\theta_{0}^{R}$ denote the number of
$L$-neighbours and $R$-neighbours of $k_{0}$, respectively. The aim is to
ensure that $\theta_{0}^{L}=\tau^{L}_{0}$, $\theta_{0}^{R}=\tau^{R}_{0}$, and
that for any neighbour $((0,i))_{i\in[\tau^{L}_{0}+\tau^{R}_{0}]}$, it holds
that $\tfrac{k_{0,i}}{n}\approx a_{0,i}$. Observe that the latter is not
required for the local weak convergence of the $1$-neighbourhood to hold but
is needed to ensure that the $2$-neighbourhoods of the root $0$ in
$\mathcal{T}$ and $k_{0}$ in $G_{n}$ can be coupled.

###  4.2 The $1$-neighbourhood of the root

The children of the root $0$ in $\mathcal{T}$ are distributed according to a
Poisson point process, whilst the direct neighbours of the root $k_{0}$ in
$G_{n}$ are characterised by a Bernoulli point process (that is, a sequence of
Bernoulli random variables). To provide a coupling between these
characterisations, we split the neighbours of $k_{0}$ into two groups: the
$L$-neighbours are the vertices $j\in[k_{0}-1]$ such that $k_{0}\to j$ in
$G_{n}$ while the $R$-neighbours are those $j\in\\{k_{0}+1,\ldots,n\\}$ for
which $j\to k_{0}$. As the connection probability to the $L$\- and
$R$-neighbours is somewhat different, we treat them separately.

####  4.2.1 $L$-children of the root $0$ and $L$-neighbours of $k_{0}$ in
$G_{n}$

The $L$-neighbours of the root $k_{0}$ of $G_{n}$ can be encoded by a
Bernoulli point process $\mathbf{I}^{L}_{k_{0}}=(I_{k_{0}\to
j})_{j=1}^{k_{0}-1}$, where $I_{k_{0}\to j}$ equals one if $k_{0}$ connects to
$j$ in $G_{n}$. Similarly, the $L$-children of the root $0$ of $\mathcal{T}$
can be encoded by a Poisson point process $\mathbf{V}^{L}_{k_{0}}$. We couple
the two processes by discretising $\mathbf{V}^{L}_{k_{0}}$ as follows: for all
$j\in[k_{0}-1]$, define $V_{k_{0}\to j}\sim\text{Poi}(\lambda_{j})$ where

$\lambda_{j}:=\int_{\frac{j-1}{n}}^{\frac{j}{n}}\frac{\beta p}{2\varepsilon
a_{0}}x^{(1-p)/(2\varepsilon)}\,\mathrm{d}x\text{ if }j\in[k_{0}-2],\text{ and
}\lambda_{k_{0}-1}:=\int_{\frac{k_{0}-2}{n}}^{a_{0}}\frac{\beta
p}{2\varepsilon a_{0}}x^{(1-p)/(2\varepsilon)}\,\mathrm{d}x.$ (55)

Then, we write $\mathbf{V}^{L}_{k_{0}}=(V_{k_{0}\to j})_{j=1}^{k_{0}-1}$.

The following lemma states that $\mathbf{I}^{L}_{k_{0}}$ and
$\mathbf{V}^{L}_{k_{0}}$ can be coupled successfully on the event
$\mathcal{H}_{1,0}\cap\mathcal{R}_{0}$.

######  Lemma 4.3.

Consider the Bernoulli point process $\mathbf{I}^{L}_{k_{0}}:=(I_{k_{0}\to
j})_{j=1}^{k_{0}-1}$ and the discretised Poisson point process
$\mathbf{V}^{L}_{k_{0}}:=(V_{k_{0}\to j})_{j=1}^{k_{0}-1}$ with means defined
in (55). Recall the events $\mathcal{H}_{1,0}$ and $\mathcal{R}_{0}$ from (37)
and (47), respectively, and fix
$\mathcal{E}_{0}:=\mathcal{R}_{0}\cap\mathcal{H}_{1,0}$ and
$\alpha:=\tfrac{1-p}{p}$. Then, there exists a coupling of
$\mathbf{I}^{L}_{k_{0}}$ and $\mathbf{V}^{L}_{k_{0}}$ such that

$\mathbb{P}\left(\\{\mathbf{I}^{L}_{k_{0}}\neq\mathbf{V}^{L}_{k_{0}}\\}\cap\mathcal{E}_{0}\right)=\mathcal{O}\Big{(}\frac{\log
n}{n^{\alpha/6}}\Big{)}.$ (56)

######  Remark 4.4.

When the coupling of the Bernoulli process and the (discretised) Poisson point
process is successful, we immediately obtain that
$\theta_{0}^{L}=\tau_{0}^{L}$, that is, the number of $L$-neighbours of the
root $k_{0}$ in $G_{n}$ and the number of $L$-children of the root $0$ in
$\mathcal{T}$ are the same. Moreover, for each $L$-child $(0,i)$ in
$\mathcal{T}$ (with $i\in[\tau_{0}^{L}]$) we have
$|a_{0,i}-\tfrac{k_{0,i}}{n}|\leq\tfrac{1}{n}$.

###### Proof of Lemma 4.3.

The coupling consists of several intermediate steps, which we outline first.

  1. 1.

We couple the Bernoulli process $\mathbf{I}^{L}_{k_{0}}$ with another
Bernoulli process
$\widetilde{\mathbf{I}}^{L}_{k_{0}}:=(\widetilde{I}_{k_{0}\to
j})_{j=1}^{k_{0}-1}$ of independent variables where $\widetilde{I}_{k_{0}\to
j}=0$ for all $j\leq n^{\alpha/2}$, and for all $j\in(n^{\alpha/2},k_{0}-1]$,

$\mathbb{P}\left(\widetilde{I}_{k_{0}\to
j}=1\,\Big{|}\,a_{0},k_{0}\right)=\widetilde{\lambda}_{j}:=\frac{\beta
p}{2\varepsilon k_{0}}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}.$ (57)

  2. 2.

We couple $\widetilde{\mathbf{I}}^{L}_{k_{0}}$ with a sequence
$\widetilde{\mathbf{V}}^{L}_{k_{0}}:=(\widetilde{V}_{k_{0}\to
j})_{j=1}^{k_{0}-1}$ of independent variables where $\widetilde{V}_{k_{0}\to
j}=0$ for all $j\leq n^{\alpha/2}$, and for all $j\in(n^{\alpha/2},k_{0}-1]$,
$\widetilde{V}_{k_{0}\to j}$ is a Poisson random variable with mean
$\widetilde{\lambda}_{j}$.

  3. 3.

We couple $\widetilde{\mathbf{V}}^{L}_{k_{0}}$ with $\mathbf{V}^{L}_{k_{0}}$.

We now provide details for each of the steps. Throughout the proof we use that
on the event $\mathcal{E}_{0}$ we have that $k_{0}\geq n/\log\log n$.
Step $1$. Recall $v_{1}$ from Lemma 2.7. It follows that

$\mathbb{P}\left(\forall j\leq n^{\alpha/2}:I_{k_{0}\to
j}=0\,\Big{|}\,a_{0},k_{0}\right)=1-\mathbb{P}\left(v_{1}\leq
n^{\alpha/2}\right)\mathbb{E}\left[\min\Big{\\{}\frac{\beta}{|V_{k_{0}-1}|},1\Big{\\}}\,\bigg{|}\,a_{0},k_{0}\right].$
(58)

Using that by Lemma 2.7 (i) one has $\mathbb{P}\left(v_{1}\leq
n^{\alpha/2}\right)=\mathcal{O}(n^{-\alpha p/(4\varepsilon)})$, and by Lemma
2.5

$\mathbb{E}\left[\min\Big{\\{}\frac{\beta}{|V_{k_{0}-1}|},1\Big{\\}}\,\bigg{|}\,a_{0},k_{0}\right]\leq\mathbb{E}\left[\mathbbm{1}_{\mathcal{Q}_{k_{0}-1}}\min\Big{\\{}\frac{\beta}{|V_{k_{0}-1}|},1\Big{\\}}\,\bigg{|}\,a_{0},k_{0}\right]+\mathbb{P}\left(\mathcal{Q}^{c}_{k_{0}-1}\right)=(1+o(1))\frac{\beta}{2\varepsilon
k_{0}},$

we get that

$\mathbb{P}\left(\forall j\leq n^{\alpha/2}:I_{k_{0}\to
j}=0\,\Big{|}\,a_{0},k_{0}\right)=1-\mathcal{O}\big{(}n^{-\alpha
p/(4\varepsilon)}k_{0}^{-1}\big{)}.$ (59)

It thus remains to show that $I_{k_{0}\to j}=\widetilde{I}_{k_{0}\to j}$ for
all $j\in(n^{\alpha/2},k_{0}-1]$ with high probability. By Lemmas 2.5, 2.6 and
on the event $\mathcal{E}_{0}$ we have that for all $j>n^{\alpha/2}$,

$\displaystyle\mathbb{P}\left(I_{k_{0}\to j}=1\,|\,a_{0},k_{0}\right)$
$\displaystyle=\mathbb{P}\left(\nu_{j,n}=1\,|\,a_{0},k_{0}\right)\mathbb{E}\left[\min\Big{\\{}\frac{\beta}{|V_{k_{0}-1}|},1\Big{\\}}\,\bigg{|}\,a_{0},k_{0}\right]$
(60)
$\displaystyle=p\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}\Big{(}1+\mathcal{O}\Big{(}\frac{\log
n}{n^{\alpha/6}}\Big{)}\Big{)}\frac{\beta}{2\varepsilon
k_{0}}\big{(}1+\mathcal{O}\big{(}k_{0}^{-1/3}\big{)}\big{)}$
$\displaystyle=\frac{\beta p}{2\varepsilon
k_{0}}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}+\mathcal{O}\Big{(}\Big{(}\frac{\log
n}{n^{\alpha/6}k_{0}}+\frac{1}{k_{0}^{4/3}}\Big{)}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}\Big{)}$
$\displaystyle=\frac{\beta p}{2\varepsilon
k_{0}}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}+\mathcal{O}\Big{(}\frac{\log
n}{n^{\alpha/6}k_{0}}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}\Big{)},$

where the last equality follows from the fact that $k_{0}\geq n^{\alpha/2}$.
As a result, using a standard Bernoulli coupling yields

$\displaystyle\mathbb{P}\left(\mathbf{I}^{L}_{k_{0}}\neq\widetilde{\mathbf{I}}^{L}_{k_{0}}\,\Big{|}\,a_{0},k_{0}\right)$
$\displaystyle\leq\mathcal{O}\big{(}n^{-\alpha
p/(4\varepsilon)}k_{0}^{-1}\big{)}+\sum_{j=\lceil
n^{\alpha/2}\rceil}^{k_{0}-1}\mathbb{P}\left(I_{k_{0}\to
j}\neq\widetilde{I}_{k_{0}\to j}\,|\,a_{0},k_{0}\right)$ (61)
$\displaystyle\leq\mathcal{O}\big{(}n^{-\alpha
p/(4\varepsilon)}k_{0}^{-1}\big{)}+\frac{\log
n}{n^{\alpha/6}k_{0}}\sum_{j=\lceil
n^{\alpha/2}\rceil}^{k_{0}-1}\mathcal{O}\Big{(}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}\Big{)}$
$\displaystyle=\mathcal{O}\big{(}n^{-\alpha
p/(4\varepsilon)}k_{0}^{-1}\big{)}+\mathcal{O}\Big{(}\frac{\log
n}{n^{\alpha/6}}\Big{)}=\mathcal{O}\Big{(}\frac{\log n}{n^{\alpha/6}}\Big{)},$

where for the last equality we used that $k_{0}\geq n^{\alpha/6}\log n$. This
finally yields that

$\mathbb{P}\left(\big{\\{}\mathbf{I}^{L}_{k_{0}}\neq\widetilde{\mathbf{I}}^{L}_{k_{0}}\big{\\}}\cap\mathcal{E}_{0}\right)=\mathbb{E}\left[\mathbbm{1}_{\mathcal{E}_{0}}\mathbb{P}\left(\mathbf{I}^{L}_{k_{0}}\neq\widetilde{\mathbf{I}}^{L}_{k_{0}}\,\Big{|}\,a_{0},k_{0}\right)\right]=\mathcal{O}\Big{(}\frac{\log
n}{n^{\alpha/6}}\Big{)}.$ (62)

Step $2$. Using Lemma 2.2 directly yields

$\mathbbm{1}_{\mathcal{E}_{0}}\mathbb{P}\left(\widetilde{\mathbf{I}}^{L}_{k_{0}}\neq\widetilde{\mathbf{V}}^{L}_{k_{0}}\,\Big{|}\,a_{0},k_{0}\right)\leq\mathbbm{1}_{\mathcal{E}_{0}}\sum_{j=1}^{k_{0}-1}2\Big{(}\frac{\beta
p}{2\varepsilon
k_{0}}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}\Big{)}^{2}\leq\mathbbm{1}_{\mathcal{E}_{0}}\frac{\beta^{2}p^{2}}{2\varepsilon^{2}k_{0}^{2}}\sum_{j=1}^{k_{0}-1}\Big{(}\frac{j}{k_{0}}\Big{)}^{(1-p)/\varepsilon}=\mathcal{O}\Big{(}\frac{\log\log
n}{n}\Big{)}.$ (63)

Step $3$. Via a standard Poisson coupling (see Lemma 2.3),

$\displaystyle\mathbb{P}\left(\widetilde{\mathbf{V}}^{L}_{k_{0}}\neq\mathbf{V}^{L}_{k_{0}}\,\Big{|}\,a_{0},k_{0}\right)$
$\displaystyle\leq\sum_{j=0}^{\lfloor
n^{\alpha/2}\rfloor}\mathbb{P}\left(V_{k_{0}\to j}\geq
1\,|\,a_{0},k_{0}\right)+\sum_{j=\lceil
n^{\alpha/2}\rceil}^{k_{0}-1}\mathbb{P}\left(\widetilde{V}_{k_{0}\to j}\neq
V_{k_{0}\to j}\,\Big{|}\,a_{0},k_{0}\right)$ (64)
$\displaystyle\leq\int_{0}^{\lceil n^{\alpha/2}\rceil/n}\frac{\beta
p}{2\varepsilon a_{0}}x^{(1-p)/(2\varepsilon)}\,\mathrm{d}x+\sum_{j=\lceil
n^{\alpha/2}\rceil}^{k_{0}-1}|\lambda_{j}-\widetilde{\lambda}_{j}|$
$\displaystyle\leq\frac{2\beta}{a_{0}}\Big{(}\frac{n^{\alpha/2}}{n}\Big{)}^{p/(2\varepsilon)}+\sum_{j=\lceil
n^{\alpha/2}\rceil}^{k_{0}-1}|\lambda_{j}-\widetilde{\lambda}_{j}|.$

Recall that for $j\in(n^{\alpha/2},k_{0}-2]$,

$\lambda_{j}=\frac{\beta}{a_{0}}\Big{(}\Big{(}\frac{j}{n}\Big{)}^{p/(2\varepsilon)}-\Big{(}\frac{j-1}{n}\Big{)}^{p/(2\varepsilon)}\Big{)}=\frac{\beta
p}{2\varepsilon
a_{0}}\Big{(}\frac{j}{n}\Big{)}^{p/(2\varepsilon)}\Big{(}\frac{1}{j}+\mathcal{O}\Big{(}\frac{1}{j^{2}}\Big{)}\Big{)}=\frac{\beta
p}{2\varepsilon
a_{0}n}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}\Big{(}1+\mathcal{O}\Big{(}\frac{1}{j}\Big{)}\Big{)}.$
(65)

It follows that on the event $\mathcal{E}_{0}$ and for all
$\varepsilon\in(0,1/2]$ and $j\in(n^{\alpha/2},k_{0}-1]$,

$\displaystyle|\lambda_{j}-\widetilde{\lambda}_{j}|$
$\displaystyle\leq\frac{\beta
p}{2\varepsilon}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}\Big{|}\frac{1}{k_{0}}-\frac{1}{a_{0}n}\Big{|}+\frac{\beta
p}{2\varepsilon a_{0}jn}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}$ (66)
$\displaystyle=\mathcal{O}\Big{(}\frac{1}{(a_{0}n)^{2}}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}\Big{)}+\mathcal{O}\Big{(}\frac{1}{a_{0}jn}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}\Big{)}$
$\displaystyle=\mathcal{O}\Big{(}\frac{(\log\log
n)^{2}}{jn}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}\Big{)}.$

When $j=k_{0}-1$,

$\displaystyle\lambda_{k_{0}-1}$
$\displaystyle=\frac{\beta}{a_{0}}\Big{(}a_{0}^{p/(2\varepsilon)}-\Big{(}\frac{k_{0}-2}{n}\Big{)}^{p/(2\varepsilon)}\Big{)}$
(67)
$\displaystyle=\beta\Big{(}\frac{k_{0}-1}{n}\Big{)}^{(1-p)/(2\varepsilon)}\frac{k_{0}-1}{a_{0}n}\Big{(}\Big{(}\frac{a_{0}n}{k_{0}-1}\Big{)}^{p/(2\varepsilon)}-\Big{(}\frac{k_{0}-2}{k_{0}-1}\Big{)}^{p/(2\varepsilon)}\Big{)},$

and on the event $\mathcal{E}_{0}$,

$\frac{k_{0}-1}{a_{0}n}\Big{(}\Big{(}\frac{a_{0}n}{k_{0}-1}\Big{)}^{p/(2\varepsilon)}-\Big{(}\frac{k_{0}-2}{k_{0}-1}\Big{)}^{p/(2\varepsilon)}\Big{)}=\frac{p}{2\varepsilon
k_{0}}\Big{(}1+\mathcal{O}\big{(}k_{0}^{-1}\big{)}\Big{)}.$ (68)

As a result, there is a constant $C>0$,

$\displaystyle\mathbbm{1}_{\mathcal{E}_{0}}\sum_{j=\lceil
n^{\alpha/2}\rceil}^{k_{0}-1}|\lambda_{j}-\widetilde{\lambda}_{j}|$
$\displaystyle\leq C\frac{(\log\log
n)^{2}}{n^{1+(1-p)/(2\varepsilon)}}\sum_{j=1}^{k_{0}-1}j^{(1-p)/(2\varepsilon)-1}$
(69) $\displaystyle\leq C\frac{(\log\log
n)^{2}}{n^{1+(1-p)/(2\varepsilon)}}\int_{0}^{k_{0}}x^{(1-p)/(2\varepsilon)-1}\,\mathrm{d}x$
$\displaystyle\leq\frac{2C\varepsilon}{1-p}\frac{(\log\log n)^{2}}{n}.$

Using this together with (64) and observing that
$\left(\tfrac{n^{\alpha/2}}{n}\right)^{p/(2\varepsilon)}\leq
n^{(\alpha-1)p/(2\varepsilon)}=n^{-1}$ yields

$\mathbb{P}\left(\\{\widetilde{\mathbf{V}}^{L}_{k_{0}}\neq\mathbf{V}^{L}_{k_{0}}\\}\cap\mathcal{E}_{0}\right)=\mathbb{E}\left[\mathbbm{1}_{\mathcal{E}_{0}}\mathbb{P}\left(\widetilde{\mathbf{V}}^{L}_{k_{0}}\neq\mathbf{V}^{L}_{k_{0}}\,\Big{|}\,a_{0},k_{0}\right)\right]=\mathcal{O}\Big{(}\frac{(\log\log
n)^{2}}{n}\Big{)}.$ (70)

Combining all three steps then yields

$\displaystyle\mathbb{P}\left(\\{\mathbf{I}^{L}_{k_{0}}\neq\mathbf{I}^{L}_{k_{0}}\\}\cap\mathcal{E}_{0}\right)$
$\displaystyle\leq\mathbb{P}\left(\\{\mathbf{I}^{L}_{k_{0}}\neq\widetilde{\mathbf{I}}^{L}_{k_{0}}\\}\cap\mathcal{E}_{0}\right)+\mathbb{P}\left(\\{\widetilde{\mathbf{I}}^{L}_{k_{0}}\neq\widetilde{\mathbf{V}}^{L}_{k_{0}}\\}\cap\mathcal{E}_{0}\right)+\mathbb{P}\left(\\{\widetilde{\mathbf{V}}^{L}_{k_{0}}\neq\mathbf{V}^{L}_{k_{0}}\\}\cap\mathcal{E}_{0}\right)$
(71) $\displaystyle=\mathcal{O}\Big{(}\frac{\log n}{n^{\alpha/6}}\Big{)},$

which concludes the proof. ∎

####  4.2.2 $R$-children of the root $0$ and $R$-neighbours of $k_{0}$ in
$G_{n}$

The $R$-neighbours of the root $k_{0}$ of $G_{n}$ can be encoded by a
Bernoulli point process $\mathbf{I}^{R}_{k_{0}}=(I_{j\to
k_{0}})_{j=k_{0}+1}^{n}$, where $I_{j\to k_{0}}$ equals one if $j$ connects to
$k_{0}$ in $G_{n}$. Similarly, the $R$-children of the root $0$ of
$\mathcal{T}$ can be encoded by a Poisson point process
$\mathbf{V}^{R}_{k_{0}}$.

We couple the two processes by discretising $\mathbf{V}^{R}_{k_{0}}$ as
follows: for all $j\in\\{k_{0}+1,\ldots,n\\}$, define $V_{k_{0}\to
j}\sim\text{Poi}(\lambda_{j})$ where

$\lambda_{k_{0}+1}:=\int_{a_{0}}^{(k_{0}+1)/n}\frac{\beta
p}{2\varepsilon}x^{(1-p)/(2\varepsilon)-1}\,\mathrm{d}x\text{ and
}\lambda_{j}:=\int_{(j-1)/n}^{j/n}\frac{\beta
p}{2\varepsilon}x^{(1-p)/(2\varepsilon)-1}\,\mathrm{d}x\text{ if
}j\in\\{k_{0}+2,\ldots,n\\}.$ (72)

Then, we write $\mathbf{V}^{R}_{k_{0}}=(V_{j\to k_{0}})_{j=k_{0}+1}^{n}$.
Moreover, recall the event $\mathcal{R}_{0}$ from (47) and note that
$\tfrac{k_{0}+1}{n}\geq a_{0}$ on this event (so $\lambda_{k_{0}+1}$ is non-
negative). The following lemma shows that $\mathbf{I}^{R}_{k_{0}}$ and
$\mathbf{V}^{R}_{k_{0}}$ can be coupled successfully on the event
$\mathcal{H}_{1,0}\cap\mathcal{R}_{0}$.

######  Lemma 4.5.

Consider the Bernoulli point process $\mathbf{I}^{R}_{k_{0}}:=(I_{j\to
k_{0}})_{j=k_{0}+1}^{n}$ and the discretised Poisson process
$\mathbf{V}^{R}_{k_{0}}:=(V_{j\to k_{0}})_{j=k_{0}+1}^{n}$ with means given in
(72). Recall the events $\mathcal{H}_{1,0}$ and $\mathcal{R}_{0}$ from (37)
and (47), respectively, and set
$\mathcal{E}_{0}:=\mathcal{H}_{1,0}\cap\mathcal{R}_{0}$. Then, there exists a
coupling of $\mathbf{I}^{R}_{k_{0}}$ and $\mathbf{V}^{R}_{k_{0}}$ such that

$\mathbb{P}\left(\\{\mathbf{I}^{R}_{k_{0}}\neq\mathbf{V}^{R}_{k_{0}}\\}\cap\mathcal{E}_{0}\right)\leq\frac{(\log
n)^{2}}{n^{1/3}}.$ (73)

######  Remark 4.6.

When the coupling of the Bernoulli process and the (discretised) Poisson point
process is successful, we immediately obtain that
$\theta_{0}^{R}=\tau_{0}^{R}$, that is, the number of $R$-neighbours of the
root $k_{0}$ in $G_{n}$ and the number of $R$-children of the root $0$ in
$\mathcal{T}$ are the same. Moreover, for each $R$-child $(0,i)$ in
$\mathcal{T}$ (with $i\in[\tau_{0}^{L}+1,\tau_{0}^{L}+\tau_{0}^{R}]$) we have
$|a_{0,i}-\tfrac{k_{0,i}}{n}|\leq\tfrac{1}{n}$.

###### Proof of Lemma 4.5.

As in the proof of Lemma 4.3, the coupling follows several intermediate steps,
which we outline first.

  1. 1.

We couple the Bernoulli process $\mathbf{I}^{R}_{k_{0}}$ with another
Bernoulli process $\widetilde{\mathbf{I}}^{R}_{k_{0}}:=(\widetilde{I}_{j\to
k_{0}})_{j=k_{0}+1}^{n}$, where the variables $(\widetilde{I}_{j\to
k_{0}})_{j=k_{0}+1}^{n}$ are independent and have success probabilities

$\mu_{j}:=\frac{\beta
p}{2\varepsilon}\frac{1}{n}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)-1}.$
(74)

  2. 2.

We couple $\widetilde{\mathbf{I}}^{R}_{k_{0}}$ with a sequence of independent
Poisson random variables
$\widetilde{\mathbf{V}}^{R}_{k_{0}}:=(\widetilde{V}_{j\to
k_{0}})_{j=k_{0}+1}^{n}$ with means given in (74).

  3. 3.

We couple $\widetilde{\mathbf{V}}^{R}_{k_{0}}$ with $\mathbf{V}^{R}_{k_{0}}$.

We now provide the details for each of the coupling steps. Throughout the
proof of the steps, we work on the event $\mathcal{E}_{0}$.

Step $1$. We couple $\mathbf{I}^{R}_{k_{0}}$ to
$\widetilde{\mathbf{I}}^{R}_{k_{0}}$. Since both are Bernoulli processes, a
standard coupling yields

$\mathbb{P}\left(\mathbf{I}^{R}_{k_{0}}\neq\widetilde{\mathbf{I}}^{R}_{k_{0}}\,\Big{|}\,a_{0},k_{0}\right)\leq\sum_{j=k_{0}+1}^{n}|\mathbb{P}(I_{j\to
k_{0}}=1\,|\,a_{0},k_{0})-\mathbb{P}(\widetilde{I}_{j\to
k_{0}}=1\,|\,a_{0},k_{0})|.$ (75)

Recall that $I_{j\to k_{0}}=1$ when at step $j$ a vertex is born, it connects
to $k_{0}$ and survives after step $n$. Hence,

$\displaystyle\mathbb{P}\left(I_{j\to k_{0}}=1\,|\,k_{0}\right)$
$\displaystyle=\mathbb{P}\left(\\{j\text{ connects to }k_{0}\text{ in
}G_{j}\\}\cap\\{\nu_{j,n}=1\\}\,|\,k_{0}\right)$ (76)
$\displaystyle=\mathbb{E}\left[\min\Big{\\{}\frac{\beta}{|V_{j-1}|},1\Big{\\}}\right]\mathbb{P}\left(\nu_{j,n}=1\,|\,k_{0}\right).$

Furthermore, by Lemma 2.5 (applied with $S=\\{k_{0}\\}$), Lemma 2.6 and on the
event $\mathcal{E}_{0}$,

$\displaystyle\mathbbm{1}_{\mathcal{E}_{0}}\mathbb{P}(\widetilde{I}_{j\to
k_{0}}=1\,|\,a_{0},k_{0})$
$\displaystyle=\mathbbm{1}_{\mathcal{E}_{0}}p\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}\Big{(}1+\mathcal{O}\left(\frac{\log
n}{j^{1/3}}\right)\Big{)}\mathbb{E}\left[\min\Big{\\{}\frac{\beta}{|V_{j-1}|},1\Big{\\}}\right]$
(77)
$\displaystyle=\mathbbm{1}_{\mathcal{E}_{0}}p\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}\Big{(}1+\mathcal{O}\left(\frac{\log
n}{j^{1/3}}\right)\Big{)}\frac{\beta}{2\varepsilon
j}\big{(}1+\mathcal{O}\big{(}j^{-1/3}\big{)}\big{)}$
$\displaystyle=\mathbbm{1}_{\mathcal{E}_{0}}\frac{\beta
p}{2\varepsilon}\frac{1}{n}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)-1}+\mathcal{O}\Big{(}\frac{\log
n}{j^{4/3}}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}\Big{)}.$

As a result, using (74) and (75) yields that

$\displaystyle\mathbb{P}\left(\\{\mathbf{I}^{R}_{k_{0}}\neq\widetilde{\mathbf{I}}^{R}_{k_{0}}\\}\cap\mathcal{E}_{0}\right)$
$\displaystyle=\mathbb{E}\left[\mathbbm{1}_{\mathcal{E}_{0}}\mathbb{P}\left(\mathbf{I}^{R}_{k_{0}}\neq\widetilde{\mathbf{I}}^{R}_{k_{0}}\,\Big{|}\,a_{0},k_{0}\right)\right]$
(78) $\displaystyle=\mathcal{O}\Big{(}\sum_{j=1}^{n}\frac{\log
n}{j^{4/3}}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}\Big{)}=\mathcal{O}\Big{(}\frac{\log
n}{n^{1/3}}\frac{1}{n}\sum_{j=1}^{n}\Big{(}\frac{j}{n}\Big{)}^{-4/3}\Big{)}=\mathcal{O}\Big{(}\frac{(\log
n)^{2}}{n^{1/3}}\Big{)}.$

Step $2$. For the coupling of $\widetilde{\mathbf{I}}^{R}_{k_{0}}$ and
$\widetilde{\mathbf{V}}^{R}_{k_{0}}$ we use Lemma 2.2. As a result,

$\mathbbm{1}_{\mathcal{E}_{0}}\mathbb{P}\left(\widetilde{\mathbf{I}}^{R}_{k_{0}}\neq\widetilde{\mathbf{V}}^{R}_{k_{0}}\,\Big{|}\,a_{0},k_{0}\right)\leq\sum_{j=\lceil
n/\log\log n\rceil}^{n}2\Big{(}\frac{\beta
p}{2\varepsilon}\frac{1}{n}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}\Big{)}^{2}\leq\frac{(\beta
p)^{2}}{2\varepsilon^{2}n^{2}}\sum_{j=\lceil n/\log\log
n\rceil}^{n}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/\varepsilon}.$ (79)

Using that

$\frac{1}{n}\sum_{j=\lceil n/\log\log
n\rceil}^{n}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/\varepsilon}\leq\frac{1}{n}\sum_{j=1}^{n}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/\varepsilon}=\mathcal{O}(1),$
(80)

we deduce that

$\mathbb{P}\left(\\{\widetilde{\mathbf{I}}^{R}_{k_{0}}\neq\widetilde{\mathbf{V}}^{R}_{k_{0}}\\}\cap\mathcal{E}_{0}\right)=\mathbb{E}\left[\mathbbm{1}_{\mathcal{E}_{0}}\mathbb{P}\left(\widetilde{\mathbf{I}}^{R}_{k_{0}}\neq\widetilde{\mathbf{V}}^{R}_{k_{0}}\,\Big{|}\,a_{0},k_{0}\right)\right]=\mathcal{O}\big{(}n^{-1}\big{)}.$
(81)

Step $3$. Recall $(\lambda_{j})_{j=k_{0}+1}^{n}$ from (72) and
$(\mu_{j})_{j=k_{0}+1}^{n}$ from (74). Via a standard coupling of Poisson
random variables (see Lemma 2.3),

$\displaystyle\mathbb{P}\left(\widetilde{\mathbf{V}}^{R}_{k_{0}}\neq\mathbf{V}^{R}_{k_{0}}\,\Big{|}\,a_{0},k_{0}\right)\leq\sum_{j=k_{0}+1}^{n}|\lambda_{j}-\mu_{j}|.$
(82)

It remains to bound $|\lambda_{j}-\mu_{j}|$, which follows by computing the
integral in the expression of $\lambda_{j}$. For $j\in\\{k_{0}+2,\ldots,n\\}$,

$\displaystyle\lambda_{j}=\int_{(j-1)/n}^{j/n}\frac{\beta
p}{2\varepsilon}x^{(1-p)/(2\varepsilon)-1}\,\mathrm{d}x$
$\displaystyle=\frac{\beta
p}{1-p}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}\Big{(}1-\Big{(}1-\frac{1}{j}\Big{)}^{(1-p)/(2\varepsilon)}\Big{)}$
(83) $\displaystyle=\frac{\beta
p}{1-p}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}\Big{(}\frac{1-p}{2\varepsilon
j}-\mathcal{O}\big{(}j^{-2}\big{)}\Big{)}$
$\displaystyle=\mu_{j}+\mathcal{O}\Big{(}j^{-2}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}\Big{)}.$

Hence,

$\sum_{j=k_{0}+2}^{n}|\lambda_{j}-\mu_{j}|=\mathcal{O}\Big{(}\frac{1}{n}\Big{)}$
(84)

almost surely. For $j=k_{0}+1$, we find in a similar way that

$\lambda_{k_{0}+1}=\int_{a_{0}}^{(k_{0}+1)/n}\frac{\beta
p}{2\varepsilon}x^{(1-p)/(2\varepsilon)-1}\,\mathrm{d}x=\frac{\beta
p}{1-p}\Big{(}\frac{k_{0}+1}{n}\Big{)}^{(1-p)/(2\varepsilon)}\Big{(}1-\Big{(}\frac{a_{0}n}{k_{0}+1}\Big{)}^{(1-p)/(2\varepsilon)}\Big{)}.$
(85)

Having that $n/\log\log n\leq a_{0}n\leq k_{0}\leq a_{0}n-1$ on the event
$\mathcal{E}_{0}$ implies that

$\Big{(}\frac{a_{0}n}{k_{0}+1}\Big{)}^{(1-p)/(2\varepsilon)}=\Big{(}1-\frac{k_{0}+1-a_{0}n}{k_{0}+1}\Big{)}^{(1-p)/(2\varepsilon)}=1-\mathcal{O}\Big{(}\frac{\log\log
n}{n}\Big{)}.$ (86)

Combining the above inequality with (85), and then with (82) and (84) yields

$\mathbb{P}\left(\\{\widetilde{\mathbf{V}}^{R}_{k_{0}}\neq\mathbf{V}^{R}_{k_{0}}\\}\cap\mathcal{E}_{0}\right)=\mathbb{E}\left[\mathbbm{1}_{\mathcal{E}_{0}}\mathbb{P}\left(\widetilde{\mathbf{V}}^{R}_{k_{0}}\neq\mathbf{V}^{R}_{k_{0}}\,\Big{|}\,a_{0},k_{0}\right)\right]=\mathcal{O}\Big{(}\frac{\log\log
n}{n}\Big{)}.$ (87)

Combining steps $1$ through $3$ via a union bound, we arrive at

$\mathbb{P}\left(\\{\mathbf{I}^{R}_{k_{0}}\neq\mathbf{V}^{R}_{k_{0}}\\}\cap\mathcal{E}_{0}\right)\leq\frac{(\log
n)^{2}}{n^{1/3}},$ (88)

which concludes the proof. ∎

###  4.3 Summary

We are now ready to prove Lemma 4.1.

###### Proof of Lemma 4.1.

Part of the proof has already been demonstrated in (39),(40), (44) and (46).
Furthermore, we observe that

$\mathcal{H}_{1,2}\supseteq\mathcal{R}_{0}\cap\\{\mathbf{I}^{L}_{k_{0}}=\mathbf{V}^{L}_{k_{0}}\\}\cap\\{\mathbf{I}^{R}_{k_{0}}=\mathbf{V}^{R}_{k_{0}}\\},$
(89)

where we recall the events $\mathcal{R}_{0}$,
$\\{\mathbf{I}^{L}_{k_{0}}=\mathbf{V}^{L}_{k_{0}}\\}$ and
$\\{\mathbf{I}^{R}_{k_{0}}=\mathbf{V}^{R}_{k_{0}}\\}$ from (47) and Lemmas 4.3
and 4.5, respectively. These events ensure that the immediate neighbourhoods
of $k_{0}$ in $G_{n}$ and $0$ in $\mathcal{T}$ are isomorphic, since the
number of $L$\- and $R$-neighbours are the same. Thus, from Lemmas 4.2, 4.3
and 4.5 we obtain that

$\mathbb{P}\left(\mathcal{H}_{1,2}^{c}\cap\mathcal{H}_{1,0}\right)\leq\mathbb{P}\left(\mathcal{R}_{0}^{c}\right)+\mathbb{P}\left(\\{\mathbf{I}^{L}_{k_{0}}\neq\mathbf{V}^{L}_{k_{0}}\\}\cap\mathcal{R}_{0}\cap\mathcal{H}_{1,0}\right)+\mathbb{P}\left(\\{\mathbf{I}^{R}_{k_{0}}\neq\mathbf{V}^{R}_{k_{0}}\\}\cap\mathcal{R}_{0}\cap\mathcal{H}_{1,0}\right)=\mathcal{O}\Big{(}\frac{1}{\log
n}\Big{)}.$ (90)

As a result, combining this with the steps from (39), (40), (44) and (46) we
finally obtain

$\displaystyle\mathbb{P}\left(\Big{(}\bigcap_{i=0}^{3}\mathcal{H}_{1,i}\Big{)}^{c}\right)\leq\mathbb{P}\left(\mathcal{H}_{1,0}^{c}\right)+\mathbb{P}\left(\mathcal{H}_{1,1}^{c}\right)+\mathbb{P}\left(\mathcal{H}_{1,2}^{c}\cap\mathcal{H}_{1,0}\right)+\mathbb{P}\left(\mathcal{H}_{1,3}^{c}\right)=\mathcal{O}\Big{(}\frac{1}{(\log\log
n)^{p/(2\varepsilon)}}\Big{)},$ (91)

which finishes the proof. ∎

##  5 Continuing the coupling

We continue the construction of the coupling described in the previous
sections by providing a coupling of the $r$-neighbourhoods of $k_{0}$ in
$G_{n}$ and $0$ in $\mathcal{T}$ that is successful with high probability for
any $r\geq 2$. Since the number of vertices in $G_{n}$ is “large” w.h.p,
exploring a finite neighbourhood of $G_{n}$ changes the distribution of the
remaining graph “very little”. As a result, the coupling of the
$r$-neighbourhoods follows a similar approach as the coupling of the
$1$-neighbourhood in the previous section. Modifications are necessary,
though, which make the proofs somewhat more technical and involved.

As in (37), fix $r\in\mathbb{N}$ and for all $q\in[r-1]$, define

$\displaystyle\mathcal{H}_{q,1}$ $\displaystyle:=\\{\forall v\in V(\partial
B_{q-1}(\mathcal{T},0)):\min_{i\in[\tau_{v}^{L}]}a_{v,i}\geq(\log\log
n)^{-(q+1)}\\},$ (92) $\displaystyle\mathcal{H}_{q,2}$
$\displaystyle:=\\{(B_{q}(G_{n},k_{0}),k_{0})\cong(B_{q}(\mathcal{T},0),0)\\}\cap\\{\forall
v\in V(\partial
B_{q}(\mathcal{T},0)),|a_{v}-\tfrac{k_{v}}{n}|\leq\tfrac{q+1}{n}\\},$
$\displaystyle\mathcal{H}_{q,3}$ $\displaystyle:=\Big{\\{}\forall v\in
V(B_{q-1}(\mathcal{T},0)):\tau_{v}^{L}+\tau_{v}^{R}<(\log\log
n)^{1/r}\Big{\\}}.$

Note that for $r=1$ and $q=0$, these events coincide with the last three
events in (37). When $r>1$, only minor modifications in (46) are required to
show that, when $q=0$, $\mathcal{H}_{1,3}$ holds with probability at least
$1-\mathcal{O}((\log\log n)^{-p/(2\varepsilon)})$. We now state the main
result of this section.

######  Proposition 5.1.

Fix $\varepsilon\in(0,\tfrac{1}{2}]$, $r\in\mathbb{N}\backslash\\{1\\}$ and
$q\in[r-1]$ and set $p:=\tfrac{1}{2}+\varepsilon$. Recall the events in (92),
and assume that for all $n$ sufficiently large there exists a coupling of
$(G_{n},k_{0})$ and $(\mathcal{T},0)$ and a constant $C_{q}>0$ such that

$\mathbb{P}\left(\Big{(}\bigcap_{i=1}^{3}\mathcal{H}_{q,i}\Big{)}^{c}\right)\leq
C_{q}(\log\log n)^{(q-1)/r-p/(2\varepsilon)}$ (93)

Then, there exists a coupling of $(G_{n},k_{0})$ and $(\mathcal{T},0)$ and a
constant $C_{q+1}>0$ such that

$\mathbb{P}\left(\Big{(}\bigcap_{i=1}^{3}\mathcal{H}_{q+1,i}\Big{)}^{c}\right)\leq
C_{q+1}(\log\log n)^{q/r-p/(2\varepsilon)}.$ (94)

Proposition 5.1 combined with Lemma 4.1 has the following result as an
immediate corollary.

######  Corollary 5.2.

Fix $\varepsilon\in(0,\tfrac{1}{2}]$ and set $p:=\tfrac{1}{2}+\varepsilon$.
For every fixed $r\in\mathbb{N}$ there exists a coupling of $(G_{n},k_{0})$
and $(\mathcal{T},0)$ such that

$\mathbb{P}\left(\Big{(}\bigcap_{i=1}^{3}\mathcal{H}_{r,i}\Big{)}^{c}\right)=\mathcal{O}\big{(}(\log\log
n)^{-(1-p)/(2\varepsilon)-1/r}\big{)}.$ (95)

To prove Proposition 5.1, we bound

$\displaystyle\mathbb{P}\left(\Big{(}\bigcap_{i=1}^{3}\mathcal{H}_{q+1,i}\Big{)}^{c}\right)\leq{}$
$\displaystyle\mathbb{P}\left(\Big{(}\bigcap_{i=1}^{3}\mathcal{H}_{q+1,i}\Big{)}^{c}\cap\bigcap_{i=1}^{3}\mathcal{H}_{q,i}\right)+\mathbb{P}\left(\Big{(}\bigcap_{i=1}^{3}\mathcal{H}_{q,i}\Big{)}^{c}\right)$
(96) $\displaystyle\leq{}$
$\displaystyle\mathbb{P}\left(\mathcal{H}_{q+1,3}^{c}\cap\mathcal{H}_{q,3}\right)+\mathbb{P}\left(\mathcal{H}_{q+1,1}^{c}\cap\mathcal{H}_{q+1,3}\cap\mathcal{H}_{q,1}\right)$
$\displaystyle+\mathbb{P}\left(\mathcal{H}_{q+1,2}^{c}\cap\mathcal{H}_{q+1,1}\cap\mathcal{H}_{q+1,3}\cap\bigcap_{i=1}^{3}\mathcal{H}_{q,i}\right)+\mathbb{P}\left(\Big{(}\bigcap_{i=1}^{3}\mathcal{H}_{q,i}\Big{)}^{c}\right).$

First, let $(P_{i})_{i\in\mathbb{N}}$ be i.i.d. $\text{Poi}(\tfrac{\beta
p}{1-p})$ random variables. Recall that a vertex $v$ in $\mathcal{T}$ has
$\tau^{L}_{v}+\tau^{R}_{v}$ many children. As in (45), it is readily checked
that for any type $a_{v}\in(0,1]$, $\tau^{L}_{v}+\tau^{R}_{v}$ is
stochastically dominated by $P_{1}$. Since for every $q\in[r-1]$,
conditionally on $\mathcal{H}_{q,3}$, we have that $|\partial
B_{q}(\mathcal{T},0)|\leq(\log\log n)^{q/r}$, a union bound and a similar
approach as in (46) with $t=1$ yield

$\displaystyle\mathbb{P}\left(\mathcal{H}_{q+1,3}^{c}\cap\mathcal{H}_{q,3}\right)$
$\displaystyle\leq\mathbb{P}\left(\max_{i\in[(\log\log
n)^{q/r}]}P_{i}\geq(\log\log n)^{1/r}\right)$ (97)
$\displaystyle\leq\mathcal{O}((\log\log n)^{q/r}\mathrm{e}^{-(\log\log
n)^{1/r}})=o((\log\log n)^{-s}),$

where the final equality holds for any $s>0$.

Similarly, for every $q\in[r-1]$, by using a similar approach as in (42) and a
union bound over $|\partial B_{q}(\mathcal{T},0)|\leq(\log\log n)^{q/r}$
vertices, we obtain

$\mathbb{P}\left(\mathcal{H}_{q+1,1}^{c}\cap\mathcal{H}_{q+1,3}\cap\mathcal{H}_{q,1}\right)\leq\beta(\log\log
n)^{q/r+q-(q+1)p/(2\varepsilon)}\leq\beta(\log\log n)^{q/r-p/(2\varepsilon)},$
(98)

since $\tfrac{p}{2\varepsilon}\geq 1$. By the induction hypothesis, we know
that the last term in (96) is at most
$C_{q}(\log\log n)^{(q-1)/r-p/(2\varepsilon)}$ for some constant $C_{q}>0$, so
only the third term on the right-hand side of (96) is left to analyse.

To extend the coupling from the $q$-neighbourhoods of $k_{0}$ and $0$ to their
respective $(q+1)$-neighbourhoods, we can assume that a coupling of
$B_{q}(G_{n},k_{0})$ and $B_{q}(\mathcal{T},0)$ exists such that
$\cap_{i=1}^{3}\mathcal{H}_{q,i}$ holds. Then, for each $v\in V(\partial
B_{q}(\mathcal{T},0))$, we want to couple its children in $\mathcal{T}$ to the
neighbours of $k_{v}\in V(\partial B_{q}(G_{n},k_{0}))$ in $G_{n}$ so that the
number of children and neighbours, respectively, are equal, and such that
their types and rescaled labels are sufficiently close.

Recall that $k[t]$ is the smallest vertex in $\mathcal{A}_{t-1}$ with respect
to the BFS order, and let, for ease of writing, $k_{v(t)}:=k[t]$. Suppose that
$k_{v(t)}\in V(\partial B_{q}(G_{n},k_{0}))$. We then define the event

$\displaystyle\mathcal{K}_{t,q}:=\\{{}$
$\displaystyle\theta^{L}_{v(t)}=\tau^{L}_{v(t)},\theta^{R}_{v(t)}=\tau^{R}_{v(t)}\\}\cap\Big{\\{}\forall
i\in[\tau_{v(t)}]:\Big{|}a_{v(t),i}-\tfrac{k_{v(t),i}}{n}\Big{|}\leq\tfrac{q+2}{n},k_{v(t),i}\not\in\mathcal{A}_{t-1}\Big{\\}},$
(99)

and the collection of random variables

$\widetilde{\mathcal{C}}_{t}:=((k_{v},a_{v})_{k_{v}\in\mathcal{A}_{t-1}\cup\mathcal{P}_{t-1}},((\theta_{w}^{L},\tau_{w}^{L}),(\theta_{w}^{R},\tau_{w}^{R}))_{k_{w}\in\mathcal{P}_{t-1}}).$
(100)

Note that the event $\\{\forall
i\in[\tau_{v(t)}]:k_{v(t),i}\not\in\mathcal{A}_{t-1}\\}$ is included in (99)
since the formation of a cycle in the BFS exploration in $G_{n}$ would
immediately invalidate the coupling.

Furthermore, for every $q\in[r-1]$, define $\rho[q]$ as

$\rho[q]=\begin{cases}|V(B_{q-1}(G_{n},k_{0}))|+1,&\mbox{ if
}V(B_{q}(G_{n},k_{0}))\neq\emptyset,\\\ \infty,&\text{ otherwise}.\end{cases}$
(101)

When $\rho[q]<\infty$, it denotes the time step of the BFS exploration at
which the smallest vertex $k[\rho[q]]$ (with respect to the BFS order) in
$V(\partial B_{q}(G_{n},k_{0}))$ is explored. Also observe that, for all
$q\in[r-1]$,

$(\mathcal{A}_{\rho[q]-1},\mathcal{P}_{\rho[q]-1},\mathcal{N}_{\rho[q]-1})=(V(\partial
B_{q}(G_{n},k_{0})),V(B_{q-1}(G_{n},k_{0})),V_{n}\backslash
V(B_{q}(G_{n},k_{0}))).$ (102)

We observe that

$\mathcal{H}_{q+1,2}=\mathcal{H}_{q,2}\cap\bigcap_{t=\rho[q]}^{\rho[q+1]-1}\mathcal{K}_{t,q}.$
(103)

As a result, to provide an upper bound for the probability

$\mathbb{P}\left(\mathcal{H}^{c}_{q+1,2}\cap\mathcal{H}_{q+1,1}\cap\mathcal{H}_{q+1,3}\cap\bigcap_{i=1}^{3}\mathcal{H}_{q,i}\right),$
(104)

we first bound

$\mathbb{P}\left(\mathcal{K}^{c}_{t,q}\cap\mathcal{H}_{q+1,1}\cap\mathcal{H}_{q+1,3}\cap\bigcap_{i=1}^{3}\mathcal{H}_{q,i}\right)$
(105)

for every $t\in\\{\rho[q],\ldots,\rho[q+1]-1\\}$. As for a fixed $q$ and any
$t\in\\{\rho[q],\ldots,\rho[q+1]-1\\}$ these bounds are rather similar, we
focus on the case $t=\rho[q]$. That is, we consider the vertex
$k_{v[q]}:=k[\rho[q]]$ and couple the neighbours of $k_{v[q]}$ in $G_{n}$ to
the children of $v[q]$ in $\mathcal{T}$. For ease of writing, let us set

$\mathcal{K}_{\rho[q]}:=\mathcal{K}_{\rho[q],q}=\\{\theta_{v[q]}^{L}=\tau_{v[q]}^{L},\theta_{v[q]}^{R}=\tau^{R}_{v[q]}\\}\cap\Big{\\{}\forall
i\in[\tau_{v[q]}]:\Big{|}a_{v[q],i}-\tfrac{k_{v[q],i}}{n}\Big{|}\leq\tfrac{q+2}{n},k_{v[q],i}\not\in\mathcal{A}_{\rho[q]-1}\Big{\\}},$
(106)

and

$\displaystyle\mathcal{C}_{q}:=\widetilde{\mathcal{C}}_{\rho[q]}={}$
$\displaystyle((k_{v},a_{v})_{k_{v}\in\mathcal{A}_{\rho[q]-1}\cup\mathcal{P}_{\rho[q]-1}},((\theta_{w}^{L},\tau_{w}^{L}),(\theta_{w}^{R},\tau_{w}^{R}))_{k_{w}\in\mathcal{P}_{\rho[q]-1}})$
(107) $\displaystyle={}$ $\displaystyle((k_{v},a_{v})_{k_{v}\in
V(B_{q}(G_{n},k_{0}))},((\theta_{w}^{L},\tau_{w}^{L}),(\theta_{w}^{R},\tau_{w}^{R}))_{k_{w}\in
V(B_{q-1}(G_{n},k_{0}))}).$

We only provide the details for the coupling of the neighbourhoods of $v[q]$
in $B_{q+1}(\mathcal{T},0)$ and of $k_{v[q]}$ in $B_{q+1}(G_{n},k_{0})$ and
briefly touch upon the coupling for the remaining vertices in $V(\partial
B_{q}(G_{n},k_{0}))$, as the coupling for these other vertices follows in a
similar way.

To couple the neighbours of $k_{v[q]}$ in $G_{n}$ and $v[q]$ in $\mathcal{T}$,
we assume that the random variables in $\mathcal{C}_{q}$ have been coupled
such that $\mathcal{E}_{q}:=\cap_{i=1}^{3}\mathcal{H}_{q,i}$ holds. In the
upcoming sections we prove the following result.

######  Lemma 5.3.

Fix $\varepsilon\in(0,\tfrac{1}{2}]$, $r\in\mathbb{N}\setminus\\{1\\}$,
$q\in[r-1]$, and set $p:=\tfrac{1}{2}+\varepsilon$ and
$\alpha:=\tfrac{1-p}{p}$. Recall $(\mathcal{H}_{q,i})_{i\in[3]}$ and
$\mathcal{K}_{\rho[q]}$ from (92) and (106), respectively. There exists a
coupling of $(G_{n},k_{0})$ and $(\mathcal{T},0)$ such that

$\mathbb{P}\left(\mathcal{K}_{\rho[q]}^{c}\cap\mathcal{E}_{q}\right)=\mathcal{O}\Big{(}\frac{\log
n}{n^{\alpha/6}}\Big{)}.$ (108)

###  5.1 Coupling the $L$-children of $v[q]$ in $\mathcal{T}$ with the
$L$-neighbours of $k_{v[q]}$ in $G_{n}$

To prove Lemma 5.3, we first couple the $L$-neighbours of $k_{v[q]}$ and the
$L$-children of $v[q]$ in this section. We define

$\displaystyle\mathcal{L}_{\rho[q]}:=\\{{}$
$\displaystyle\theta_{v[q]}^{L}=\tau_{v[q]}^{L}\\}\cap\\{\forall
i\in[\tau_{v[q]}^{L}]:|a_{v[q],i}-\tfrac{k_{v[q],i}}{n}|\leq\tfrac{q+2}{n}\text{
and }k_{v[q],i}\in\mathcal{N}_{\rho[q]-1}\\}.$ (109)

to be the event that the coupling of the $L$-neighbours of $k_{v[q]}$ and the
$L$-children of $v[q]$ is successful. In words, the first two parts of
$\mathcal{L}_{\rho[q]}$ imply that the number of $L$-neighbours of $k_{v[q]}$
and the $L$-children of $v[q]$ are the same, and that their respective
rescaled labels and types are sufficiently close. The last part ensures that
the exploration of the $L$-neighbours of $k_{v[q]}$ does not lead to cycles.

We now define an encoding of the $L$-neighbours of $k_{v[q]}$ in $G_{n}$ and
the $L$-children of $v[q]$ in $\mathcal{T}$ that allows us to construct a
coupling such that $\mathcal{L}_{\rho[q]}$ holds with high probability. Unlike
in the proof of Lemma 4.3, we cannot ensure that $\tfrac{k_{v[q]}-1}{n}\leq
a_{v[q]}$ holds on the event
$\mathcal{E}_{q}=\cap_{i=1}^{3}\mathcal{H}_{q,i}$. Instead, we let
$N_{v[q]}:=\lceil a_{v[q]}n\rceil$ and
$k^{*}_{q}:=\max\\{N_{v[q]},k_{v[q]}-1\\}$ and use $k^{*}_{q}$ to construct
the necessary processes that we couple further on in this section. If
$N_{v[q]}\geq k_{v[q]}-1$, we define conditionally on $a_{v[q]}$,

$\lambda^{\rho[q]}_{N_{v[q]}}:=\int_{N_{v[q]-1}/n}^{a_{v[q]}}\frac{\beta
p}{2\varepsilon a_{v[q]}}x^{(1-p)/(2\varepsilon)}\,\mathrm{d}x,\text{ and for
all
}j\in[N_{v[q]}-1],\;\lambda^{\rho[q]}_{j}:=\int_{\tfrac{j-1}{n}}^{\tfrac{j}{n}}\frac{\beta
p}{2\varepsilon a_{v[q]}}x^{(1-p)/(2\varepsilon)}\,\mathrm{d}x.$ (110)

If instead $N_{v[q]}\leq k_{v[q]}-2$, we additionally set
$\lambda^{\rho[q]}_{j}:=0$ for all integers $j\in[N_{v[q]}+1,k^{*}_{q}]$. This
defines $\lambda^{\rho[q]}_{j}$ for all $j\in[0,k^{*}_{q}]$, and allows us to
define the discretised Poisson point process
$\mathbf{V}^{L}_{k_{v[q]}}:=(V^{L}_{k_{v[q]}\to j})_{j=0}^{k^{*}_{q}}$, where
the $V^{L}_{k_{v[q]}\to j}$ are independent Poisson random variables with
means $\lambda^{\rho[q]}_{j}$ (where a Poisson variable with mean zero is
equal to zero almost surely). Note that $\mathbf{V}^{L}_{k_{v[q]}}$ is a
discretisation of the Poisson point process on $(0,a_{v[q]})$ with density
$\lambda^{-}_{v[q]}(\mathrm{d}x)$ that determines the $L$-children of $v[q]$
(see Definition 1.2).

Similarly, we define the Bernoulli point process
$\mathbf{I}^{L}_{k_{v[q]}}:=(I^{L}_{k_{v[q]}\to j})_{j=1}^{k^{*}_{q}}$ as
follows. For all $j\in[k_{v[q]}-1]$, $I^{L}_{k_{v[q]}\to j}$ equals one if
$k_{v[q]}$ connects to $j$ by an edge in $G_{n}$ and
$j\in\mathcal{N}_{\rho[q]-1}\cup\mathcal{A}_{\rho[q]-1}$, and equals zero
otherwise. For $j\in[k_{v[q]},k^{*}_{q},]$ (that is, when
$N_{v[q]}>k_{v[q]}-1$), we additionally set $I^{L}_{k_{v[q]}\to j}:=0$.

Our aim is to couple the Bernoulli point process $\mathbf{I}^{L}_{k_{v[q]}}$
and the discretised Poisson point process $\mathbf{V}^{L}_{k_{v[q]}}$. To do
this, we show the following lemma, which is similar in nature to Lemma 4.3.

######  Lemma 5.4.

Fix $\alpha=\tfrac{1-p}{p}$ and recall that
$\mathcal{E}_{q}=\cap_{i=1}^{3}\mathcal{H}_{q,i}$, where the events
$(\mathcal{H}_{q,i})_{i\in[3]}$ were defined in (92). Consider the processes
$\mathbf{I}^{L}_{k_{v[q]}}$ and $\mathbf{V}^{L}_{k_{v[q]}}$. There exists a
coupling such that

$\mathbb{P}\left(\big{(}\\{\mathbf{I}^{L}_{k_{v[q]}}=\mathbf{V}^{L}_{k_{v[q]}}\\}\cap\\{\forall
j\in\mathcal{A}_{\rho[q]-1}\cap[k_{q}^{*}]:I^{L}_{k_{v[q]}\to
j}=0\\}\big{)}^{c}\cap\mathcal{E}_{q}\right)=\mathcal{O}\left(\frac{\log
n}{n^{\alpha/6}}\right).$ (111)

######  Remark 5.5.

When the coupling is successful, in the sense that the event

$\\{\mathbf{I}^{L}_{k_{v[q]}}=\mathbf{V}^{L}_{k_{v[q]}}\\}\cap\\{\forall
j\in\mathcal{A}_{\rho[q]-1}\cap[k_{q}^{*}]:I^{L}_{k_{v[q]}\to j}=0\\}$ (112)

holds, it directly follows that the event $\mathcal{L}_{\rho[q]}$ holds as
well. As a result,

$\mathbb{P}\left(\mathcal{L}_{\rho[q]}^{c}\cap\mathcal{E}_{q}\right)=\mathcal{O}\left(\frac{\log
n}{n^{\alpha/6}}\right).$ (113)

###### Proof of Lemma 5.4.

Throughout the proof, we assume for simplicity that
$k^{*}_{q}=N_{v[q]}=k_{v[q]}-1$. The other cases can be dealt with in a
similar way with only minor modifications. We write

$\displaystyle\mathbb{P}{}$
$\displaystyle\Big{(}\big{(}\\{\mathbf{I}^{L}_{k_{v[q]}}=\mathbf{V}^{L}_{k_{v[q]}}\\}\cap\\{\forall
j\in\mathcal{A}_{\rho[q]-1}\cap[k_{q}^{*}]:V^{L}_{k_{v[q]}\to
j}=0\\}\big{)}^{c}\cap\mathcal{E}_{q}\Big{)}$ (114)
$\displaystyle=\mathbb{P}\left(\Big{\\{}\mathbf{I}^{L}_{k_{v[q]}}\neq\mathbf{V}^{L}_{k_{v[q]}}\Big{\\}}\cap\mathcal{E}_{q}\right)+\mathbb{P}\left(\\{\exists
j\in\mathcal{A}_{\rho[q]-1}\cap[k_{q}^{*}]:I^{L}_{k_{v[q]}\to
j}=1\\}\cap\\{\mathbf{I}^{L}_{k_{v[q]}}=\mathbf{V}^{L}_{k_{v[q]}}\\}\cap\mathcal{E}_{q}\right),$

We divide the coupling into several steps, similar to the proof of Lemma 4.3.

  1. 1.

We couple $\mathbf{I}^{L}_{k_{v[q]}}$ with a Bernoulli process
$\widetilde{\mathbf{I}}^{L}_{k_{v[q]}}=(\widetilde{I}_{k_{v[q]}\to
j})_{j=1}^{k_{v[q]}-1}$, where the variables $(\widetilde{I}_{k_{v[q]}\to
j})_{j=1}^{k_{v[q]}-1}$ are independent, $\widetilde{I}_{k_{v[q]}\to j}=0$ for
all $j\leq n^{\alpha/2}$ and otherwise

$\mathbb{P}\left(\widetilde{I}_{k_{v[q]}\to
j}=1\,\Big{|}\,\mathcal{C}_{q}\right)=\widetilde{\lambda}_{j}^{\rho[q]}:=\frac{\beta
p}{2\varepsilon
k_{v[q]}}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}\text{ for all
}j\in(n^{\alpha/2},k_{v[q]}].$ (115)

  2. 2.

We couple $\widetilde{\mathbf{I}}^{L}_{k_{v[q]}}$ with a sequence
$\widetilde{\mathbf{V}}^{L}_{k_{v[q]}}=(\widetilde{V}_{k_{v[q]}\to
j})_{j=1}^{k_{v[q]}-1}$ of independent variables where
$\widetilde{V}_{k_{v[q]}\to j}=0$ for all $j\leq n^{\alpha/2}$, and for
$j\in(n^{\alpha/2},k_{v[q]}-1]$, the $\widetilde{V}_{k_{v[q]}\to j}$ is a
Poisson random variables with means $\widetilde{\lambda}_{j}^{\rho[q]}$.

  3. 3.

We couple $\widetilde{\mathbf{V}}^{L}_{k_{v[q]}}$ with
$\mathbf{V}^{L}_{k_{v[q]}}$.

We now provide details for these steps.

Step $1$. Recall $v_{1}$ from Lemma 2.7. Then, by a computation similar to
(58) we conclude that

$\mathbb{P}\left(\exists j\leq n^{\alpha/2}:I_{k_{v[q]}\to
j}=1\,\Big{|}\,\mathcal{C}_{q}\right)=\mathcal{O}\big{(}n^{-\alpha
p/(4\varepsilon)}k_{v[q]}^{-1}\big{)}.$ (116)

Now, let $j\in(n^{\alpha/2},k_{v[q]}-1]$. We observe that all vertices in
$\mathcal{A}_{\rho[q]-1}\cup\mathcal{P}_{\rho[q]-1}$ survive up to step $n$.
We use Lemmas 2.5 and 2.6 with
$S=\mathcal{A}_{\rho[q]-1}\cup\mathcal{P}_{\rho[q]-1}$ and $R=\\{j\\}$. Since
$|S|=\mathcal{O}\big{(}(\log\log
n)^{q/r}\big{)}=\mathcal{O}\big{(}j^{2/3}\big{)}$ for any $j>n^{\alpha/2}$, we
obtain for all $j\not\in\mathcal{A}_{\rho[q]-1}\cup\mathcal{P}_{\rho[q]-1}$,

$\displaystyle\mathbbm{1}_{\mathcal{E}_{q}}\mathbb{P}\left(I_{k_{v[q]}\to
j}=1\,\Big{|}\,\mathcal{C}_{q}\right)$
$\displaystyle=\mathbbm{1}_{\mathcal{E}_{q}}\frac{\beta p}{2\varepsilon
k_{v[q]}}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}\Big{(}1+\mathcal{O}\Big{(}\frac{\log
n}{n^{\alpha/6}}\Big{)}\Big{)}\big{(}1+\mathcal{O}\big{(}k_{v[q]}^{-1/3}\big{)}\big{)}$
(117) $\displaystyle=\mathbbm{1}_{\mathcal{E}_{q}}\frac{\beta p}{2\varepsilon
k_{v[q]}}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}\\!\\!+\mathcal{O}\Big{(}\mathbbm{1}_{\mathcal{E}_{q}}\Big{(}\frac{\log
n}{n^{\alpha/6}k_{v[q]}}+\frac{1}{k_{v[q]}^{4/3}}\Big{)}\Big{)}$
$\displaystyle=\mathbbm{1}_{\mathcal{E}_{q}}\frac{\beta p}{2\varepsilon
k_{v[q]}}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}\\!\\!+\mathcal{O}\Big{(}\mathbbm{1}_{\mathcal{E}_{q}}\Big{(}\frac{\log
n}{n^{\alpha/6}k_{v[q]}}\Big{)}\Big{)},$

where for the last equality we used that $k_{v[q]}\geq n^{\alpha/3}$. Note
also that for $j\in\mathcal{P}_{\rho[q]-1}$, we know that $I_{k_{v[q]}\to
j}=0$ by definition. Hence, the coupling is successful for these $j$ only when
$\widetilde{I}_{k_{v[q]}\to j}=0$. Combining the above observations with a
standard Bernoulli coupling yields

$\displaystyle\mathbbm{1}_{\mathcal{E}_{q}}\mathbb{P}\left(\mathbf{I}^{L}_{k_{v[q]}}\neq\widetilde{\mathbf{I}}^{L}_{k_{v[q]}}\,\Big{|}\,\mathcal{C}_{q}\right)\leq{}$
$\displaystyle\mathbbm{1}_{\mathcal{E}_{q}}\mathbb{P}\bigg{(}\bigcup_{j\leq
n^{\alpha/2}}\\{I_{k_{v[q]}\to
j}=1\\}\,\bigg{|}\,\mathcal{C}_{q}\bigg{)}+\mathbbm{1}_{\mathcal{E}_{q}}\sum_{\begin{subarray}{c}j=\lceil
n^{\alpha/2}\rceil\\\
j\not\in\mathcal{P}_{\rho[q]-1}\end{subarray}}^{k_{v[q]}-1}\mathbb{P}\left(I_{k_{v[q]}\to
j}\neq\widetilde{I}_{k_{v[q]}\to j}\right)$ (118)
$\displaystyle+\mathbbm{1}_{\mathcal{E}_{q}}\sum_{\begin{subarray}{c}j=\lceil
n^{\alpha/2}\rceil\\\
j\in\mathcal{P}_{\rho[q]-1}\end{subarray}}^{k_{v[q]}-1}\mathbb{P}\left(\widetilde{I}_{k_{v[q]}\to
j}=1\,\Big{|}\,\mathcal{C}_{q}\right)$ $\displaystyle\leq{}$
$\displaystyle\mathcal{O}\big{(}\mathbbm{1}_{\mathcal{E}_{q}}n^{-\alpha
p/(4\varepsilon)}k_{v[q]}^{-1}\big{)}+\mathbbm{1}_{\mathcal{E}_{q}}\sum_{\begin{subarray}{c}j=\lceil
n^{\alpha/2}\rceil\\\
j\not\in\mathcal{P}_{\rho[q]-1}\end{subarray}}^{k_{v[q]}-1}\Big{|}\mathbb{P}\left(I_{k_{v[q]}}=1\,\Big{|}\,\mathcal{C}_{q}\right)-\mathbb{P}\left(\widetilde{I}_{k_{v[q]}\to
j}=1\,\Big{|}\,\mathcal{C}_{q}\right)\Big{|}$
$\displaystyle+\mathbbm{1}_{\mathcal{E}_{q}}\sum_{\begin{subarray}{c}j=\lceil
n^{\alpha/2}\rceil\\\
j\in\mathcal{P}_{\rho[q]-1}\end{subarray}}^{k_{v[q]}-1}\frac{\beta
p}{2\varepsilon k_{v[q]}}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}$
$\displaystyle\leq{}$
$\displaystyle\mathbbm{1}_{\mathcal{E}_{q}}\bigg{(}\mathcal{O}\big{(}n^{-\alpha
p/(4\varepsilon)}k_{v[q]}^{-1}\big{)}+\sum_{j=\lceil
n^{\alpha/2}\rceil}^{k_{v[q]}-1}\mathcal{O}\Big{(}\frac{\log
n}{n^{\alpha/6}k_{v[q]}}\Big{)}+\mathcal{O}\Big{(}\frac{|\mathcal{P}_{\rho[q]-1}|}{k_{v[q]}}\Big{)}\bigg{)}$
$\displaystyle\leq{}$
$\displaystyle\mathbbm{1}_{\mathcal{E}_{q}}\bigg{(}\mathcal{O}\big{(}n^{-\alpha
p/(4\varepsilon)}k_{v[q]}^{-1}\big{)}+\mathcal{O}\Big{(}\frac{\log
n}{n^{\alpha/6}}\Big{)}+\mathcal{O}\Big{(}\frac{|\mathcal{P}_{\rho[q]-1}|}{k_{v[q]}}\Big{)}\bigg{)}.$

Finally, using the bounds on $k_{v[q]}$ and $|\mathcal{P}_{\rho[q]-1}|$
ensured by the event $\mathcal{E}_{q}$ yields

$\mathbb{P}\left(\\{\mathbf{I}^{L}_{k_{v[q]}}\neq\widetilde{\mathbf{I}}^{L}_{k_{v[q]}}\\}\cap\mathcal{E}_{0}\right)=\mathbb{E}\left[\mathbbm{1}_{\mathcal{E}_{q}}\mathbb{P}\left(\mathbf{I}^{L}_{k_{v[q]}}\neq\widetilde{\mathbf{I}}^{L}_{k_{v[q]}}\,\Big{|}\,\mathcal{C}_{q}\right)\right]=\mathcal{O}\Big{(}\frac{\log
n}{n^{\alpha/6}}\Big{)}.$ (119)

Step $2$. By the Poisson-Bernoulli coupling given in Lemma 2.2, we obtain

$\mathbb{P}\left(\\{\widetilde{\mathbf{I}}^{L}_{k_{v[q]}}\neq\widetilde{\mathbf{V}}^{L}_{k_{v[q]}}\\}\cap\mathcal{E}_{q}\right)=\mathbb{E}\left[\mathbbm{1}_{\mathcal{E}_{q}}\mathbb{P}\left(\widetilde{\mathbf{I}}^{L}_{k_{v[q]}}\neq\widetilde{\mathbf{V}}^{L}_{k_{v[q]}}\,\Big{|}\,\mathcal{C}_{q}\right)\right]\leq\mathbb{E}\left[\mathbbm{1}_{\mathcal{E}_{q}}\sum_{j=\lceil
n^{\alpha/2}\rceil}^{k_{v[q]}-1}\Big{(}\frac{\beta p}{2\varepsilon
k_{v[q]}}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}\Big{)}^{2}\right].$
(120)

As $k_{v[q]}\leq n$ almost surely,

$\sum_{j=\lceil n^{\alpha/2}\rceil}^{k_{v[q]}-1}\Big{(}\frac{\beta
p}{2\varepsilon
k_{v[q]}}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}\Big{)}^{2}=\frac{1}{k_{v[q]}}\mathcal{O}\bigg{(}\frac{1}{k_{v[q]}}\sum_{j=1}^{k_{v[q]}}\Big{(}\frac{j}{k_{v[q]}}\Big{)}^{(1-p)/\varepsilon}\bigg{)}.$
(121)

Using that the term in the $\mathcal{O}$ in (121) is at most of constant
order, we get

$\mathbb{P}\left(\\{\widetilde{\mathbf{I}}^{L}_{k_{v[q]}}\neq\widetilde{\mathbf{V}}^{L}_{k_{v[q]}}\\}\cap\mathcal{E}_{q}\right)\leq\mathbb{E}\left[\mathbbm{1}_{\mathcal{E}_{q}}\mathcal{O}\big{(}k_{v[q]}^{-1}\big{)}\right]=\mathcal{O}\Big{(}\frac{(\log\log
n)^{q+1}}{n}\Big{)}.$ (122)

Step $3$. We first consider the case $j\leq n^{\alpha/2}$. As in (64),

$\mathbb{P}\left(\forall j\leq n^{\alpha/2}:V_{k_{v[q]}\to j}=0\right)\geq
1-\int_{0}^{\lceil n^{\alpha/2}\rceil/n}\frac{\beta p}{2\varepsilon
a_{v[q]}}x^{(1-p)/(2\varepsilon)}\,\mathrm{d}x\geq
1-\frac{2\beta}{a_{v[q]}}\Big{(}\frac{n^{\alpha/2}}{n}\Big{)}^{p/(2\varepsilon)},$
(123)

where for the first inequality we used our assumption that
$N_{v[q]}=k_{v[q]}-1$. Moreover, with a similar approach as in (66), for all
$j\in(n^{\alpha/2},k_{v[q]}-2]$ we have

$\big{|}\lambda^{\rho[q]}_{j}-\widetilde{\lambda}^{\rho[q]}_{j}\big{|}\leq\frac{\beta
p}{2\varepsilon}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}\Big{|}\frac{1}{k_{v[q]}}-\frac{1}{a_{v[q]}n}\Big{|}+\frac{\beta
p}{2\varepsilon a_{v[q]}jn}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}.$
(124)

Hence, on the event $\mathcal{E}_{q}$, for $j\in(n^{\alpha/2},k_{v[q]}-2]$,

$\big{|}\lambda^{\rho[q]}_{j}-\widetilde{\lambda}^{\rho[q]}_{j}\big{|}=\mathcal{O}\Big{(}\frac{(\log\log
n)^{2(q+1)}}{n^{1+(1-p)/(2\varepsilon)}}j^{(1-p)/(2\varepsilon)-1}\Big{)}.$
(125)

For $j=k_{v[q]}-1$, with a similar approach as in (67) and on the event
$\mathcal{E}_{q}$,

$\big{|}\lambda^{\rho[q]}_{k_{v[q]}-1}-\widetilde{\lambda}^{\rho[q]}_{k_{v[q]}-1}\big{|}=\mathcal{O}\Big{(}\Big{(}\frac{k_{v[q]}-1}{n}\Big{)}^{(1-p)/(2\varepsilon)}\frac{1}{k_{v[q]}^{2}}\Big{)}=\mathcal{O}\Big{(}\frac{(\log\log
n)^{2(q+1)}}{n^{1+(1-p)/(2\varepsilon)}}(k_{v[q]}-1)^{(1-p)/(2\varepsilon)-1}\Big{)}.$
(126)

Combining the estimates in (123), (125) and (126) then yields

$\displaystyle\mathbb{P}\left(\\{\mathbf{V}^{L}_{k_{v[q]}}\neq\widetilde{\mathbf{V}}^{L}_{k_{v[q]}}\\}\cap\mathcal{E}_{q}\right)$
$\displaystyle=\mathbb{E}\left[\mathbbm{1}_{\mathcal{E}_{q}}\mathbb{P}\left(\mathbf{V}^{L}_{k_{v[q]}}\neq\widetilde{\mathbf{V}}^{L}_{k_{v[q]}}\,\Big{|}\,\mathcal{C}_{q}\right)\right]$
(127) $\displaystyle=\mathcal{O}\big{(}(\log\log
n)^{q+1}n^{-(1-\alpha/2)p/(2\varepsilon)}\big{)}+\frac{(\log\log
n)^{2(q+1)}}{n^{1+(1-p)/(2\varepsilon)}}\sum_{j=1}^{n-1}j^{(1-p)/(2\varepsilon)-1}$
$\displaystyle=\mathcal{O}\Big{(}\frac{(\log\log n)^{2(q+1)}}{n}\Big{)}.$

Combining all three steps via a union, we finally arrive at

$\mathbb{P}\left(\Big{\\{}\mathbf{I}^{L}_{k_{v[q]}}\neq\mathbf{V}^{L}_{k_{v[q]}}\Big{\\}}\cap\mathcal{E}_{q}\right)=\mathcal{O}\Big{(}\frac{\log
n}{n^{\alpha/6}}\Big{)},$ (128)

so it remains to bound the second term on the right-hand side of (114). Via a
union bound and Markov’s inequality we obtain

$\displaystyle\mathbb{P}{}$ $\displaystyle\Big{(}\\{\exists
j\in\mathcal{A}_{\rho[q]-1}\cap[k_{q}^{*}]:I^{L}_{j\to
k_{v[q]}}=1\\}\cap\\{\mathbf{I}^{L}_{k_{v[q]}}=\mathbf{V}^{L}_{k_{v[q]}}\\}\cap\mathcal{E}_{q}\Big{)}$
(129)
$\displaystyle\leq\mathbb{E}\left[\mathbbm{1}_{\mathcal{E}_{q}}\mathbb{P}\left(\exists
j\in\mathcal{A}_{\rho[q]-1}\cap[k_{q}^{*}]:V^{L}_{j\to k_{v[q]}}\geq
1\,\Big{|}\,\mathcal{C}_{q}\right)\right]$
$\displaystyle\leq\mathbb{E}\left[\mathbbm{1}_{\mathcal{E}_{q}}|\mathcal{A}_{\rho[q]-1}|\max_{j\in[k_{v[q]}-1]}\lambda_{j}^{\rho[q]}\right].$

We then observe that for all $j\in[k^{*}_{q}]$,

$\lambda_{j}^{\rho[q]}\leq\frac{\beta p}{2\varepsilon
a_{v[q]}n}\Big{(}\frac{j+1}{n}\Big{)}^{(1-p)/(2\varepsilon)}\leq\frac{\beta
p}{2\varepsilon
a_{v[q]}n}\Big{(}\frac{k_{v[q]}}{n}\Big{)}^{(1-p)/(2\varepsilon)}\leq\frac{\beta
p}{\varepsilon n}a_{v[q]}^{(1-p)/(2\varepsilon)-1},$ (130)

where the final inequality holds on the event $\mathcal{E}_{q}$ for all
sufficiently large $n$. Regardless of the value of $\varepsilon\in(0,1/2]$, we
can bound $a_{v[q]}^{(1-p)/(2\varepsilon)-1}$ from above by $(\log\log
n)^{q+1}$ on the event $\mathcal{E}_{q}$. Using this upper bound in (129) and
bounding $|\mathcal{A}_{\rho[q]-1}|=\mathcal{O}\big{(}(\log\log
n)^{q/r}\big{)}$ on $\mathcal{E}_{q}$, this finally leads to

$\mathbb{P}\Big{(}\\{\exists
j\in\mathcal{A}_{\rho[q]-1}\cap[k_{q}^{*},n]:I^{L}_{j\to
k_{v[q]}}=1\\}\cap\\{\mathbf{I}^{L}_{k_{v[q]}}=\mathbf{V}^{L}_{k_{v[q]}}\\}\cap\mathcal{E}_{q}\Big{)}=\mathcal{O}\Big{(}\frac{(\log\log
n)^{q/r+q+1}}{n}\Big{)}.$ (131)

Combined with (128), this yields the desired result. ∎

###  5.2 Coupling the $R$-children of $v[q]$ in $\mathcal{T}$ with the
$R$-neighbours of $k_{v[q]}$ in $G_{n}$

In this section we couple the $R$-neighbours of $k_{v[q]}$ and the
$R$-children of $v[q]$. We define

$\mathcal{R}_{\rho[q]}:=\\{\theta_{v[q]}^{R}=\tau_{v[q]}^{R}\\}\cap\\{\forall
i\in[\tau_{v[q]}^{R}]:|a_{v[q],i}-\tfrac{k_{v[q],i}}{n}|\leq\tfrac{q+2}{n}\text{
and }k_{v[q],i}\in\mathcal{N}_{\rho[q]-1}\\}.$ (132)

to be the event that the coupling of the $R$-neighbours of $k_{v[q]}$ and the
$R$-children of $v[q]$ is successful. In words, the first two parts of
$\mathcal{R}_{\rho[q]}$ imply that the number of $R$-neighbours of $k_{v[q]}$
and the $R$-children of $v[q]$ are the same, and that their respective
rescaled labels and types are sufficiently close. The last part ensures that
the exploration of the $L$-neighbours of $k_{v[q]}$ of does not lead to
cycles.

We now define an encoding of the $R$-neighbours of $k_{v[q]}$ in $G_{n}$ and
the $R$-children of $v[q]$ in $\mathcal{T}$ that allows us to construct a
coupling such that $\mathcal{R}_{\rho[q]}$ holds with high probability. As in
Section 5.1, we cannot ensure that $\tfrac{k_{v[q]}+1}{n}\geq a_{v[q]}$ holds
on the event $\mathcal{E}_{q}=\cap_{i=1}^{3}\mathcal{H}_{q,i}$. Instead, we
let $N_{v[q]}:=\lceil a_{v[q]}n\rceil$ and
$k^{*}_{q}:=\min\\{N_{v[q]},k_{v[q]}+1\\}$ and use $k^{*}_{q}$ in constructing
the necessary processes that we couple further on in this section.

If $N_{v[q]}\leq k_{v[q]}+1$, we define conditionally on $a_{v[q]}$

$\lambda_{N_{v[q]}}^{\rho[q]}:=\int_{a_{v[q]}}^{N_{v[q]}/n}\frac{\beta
p}{2\varepsilon}x^{(1-p)/(2\varepsilon)-1}\,\mathrm{d}x,\text{ and for all
}j\in\\{N_{v[q]}+1,\ldots,n\\},\;\lambda^{\rho[q]}_{j}:=\int_{\tfrac{j-1}{n}}^{\tfrac{j}{n}}\frac{\beta
p}{2\varepsilon}x^{(1-p)/(2\varepsilon)-1}\,\mathrm{d}x.$ (133)

If instead $N_{v[q]}\geq k_{v[q]}+2$, we additionally set
$\lambda^{\rho[q]}_{j}:=0$ for all integers $j\in[k_{q}^{*},N_{v[q]}-1]$. This
defines $\lambda^{\rho[q]}_{j}$ for all $j\in[k_{q}^{*},n]$ and allows us to
define the discretised Poisson point process
$\mathbf{V}^{R}_{k_{v[q]}}:=(V^{R}_{j\to k_{v[q]}})_{j=k^{*}_{q}}^{n}$, where
the $V^{R}_{j\to k_{v[q]}}$ are independent Poisson random variables with
means $\lambda^{\rho[q]}_{j}$ (again, a Poisson variable with mean zero is
equal to zero almost surely). Note that $\mathbf{V}^{R}_{k_{v[q]}}$ is a
discretisation of the Poisson point process on $(a_{v[q]},1)$ with density
$\lambda^{+}(\mathrm{d}x)$ that determines the $R$-children of $v[q]$ (see
Definition 1.2).

Similarly, we define the Bernoulli point process
$\mathbf{I}^{R}_{k_{v[q]}}:=(I^{R}_{j\to k_{v_{q}}})_{j=k^{*}_{q}}^{n}$ as
follows. For all $j\in[k_{v[q]}+1,n]$, $I^{R}_{j\to k_{v[q]}}$ equals one if
$j$ connects to $k_{v[q]}$ by an edge in $G_{n}$ and
$j\in\mathcal{N}_{\rho[q]-1}\cup\mathcal{A}_{\rho[q]-1}$, and equals zero
otherwise. If $N_{v[q]}<k_{v[q]}+1$, for $j\in[k^{*}_{q},k_{v[q]}]$ we
additionally set $I^{R}_{j\to k_{v[q]}}:=0$.

Our aim is to couple the Bernoulli point process $\mathbf{I}^{R}_{k_{v[q]}}$
and the discretised Poisson point process $\mathbf{V}^{R}_{k_{v[q]}}$. To do
this, we show the following lemma, which is similar in nature to Lemma 4.5.

######  Lemma 5.6.

Recall the event $\mathcal{E}_{q}:=\cap_{i=1}^{3}\mathcal{H}_{q,i}$ where the
events $(\mathcal{H}_{q,i})_{i\in[3]}$ were defined in (92), and consider the
processes $\mathbf{I}^{R}_{k_{v[q]}}$ and $\mathbf{V}^{R}_{k_{v[q]}}$. There
exists a coupling such that

$\mathbb{P}\left(\big{(}\\{\mathbf{I}^{R}_{k_{v[q]}}=\mathbf{V}^{R}_{k_{v[q]}}\\}\cap\\{\forall
j\in\mathcal{A}_{\rho[q]-1}\cap[k_{q}^{*},n]:V^{R}_{j\to
k_{v[q]}}=0\\}\big{)}^{c}\cap\mathcal{E}_{q}\right)=\mathcal{O}\left(\frac{(\log
n)^{2}}{n^{1/3}}\right).$ (134)

######  Remark 5.7.

When the coupling is successful, in the sense that the event

$\\{\mathbf{I}^{R}_{k_{v[q]}}=\mathbf{V}^{R}_{k_{v[q]}}\\}\cap\\{\forall
j\in\mathcal{A}_{\rho[q]-1}\cap[k_{q}^{*},n]:V^{R}_{j\to k_{v[q]}}=0\\}$ (135)

holds, it directly follows that the event $\mathcal{R}_{\rho[q]}$ holds as
well. As a result,

$\mathbb{P}\left(\mathcal{R}_{\rho[q]}^{c}\cap\mathcal{E}_{q}\right)=\mathcal{O}\left(\frac{(\log
n)^{2}}{n^{1/3}}\right).$ (136)

###### Proof of Lemma 5.6.

We write

$\displaystyle\mathbb{P}{}$
$\displaystyle\Big{(}\big{(}\\{\mathbf{I}^{R}_{k_{v[q]}}=\mathbf{V}^{R}_{k_{v[q]}}\\}\cap\\{\forall
j\in\mathcal{A}_{\rho[q]-1}\cap[k_{q}^{*},n]:V^{R}_{j\to
k_{v[q]}}=0\\}\big{)}^{c}\cap\mathcal{E}_{q}\Big{)}$ (137)
$\displaystyle=\mathbb{P}\left(\Big{\\{}\mathbf{I}^{R}_{k_{v[q]}}\neq\mathbf{V}^{R}_{k_{v[q]}}\Big{\\}}\cap\mathcal{E}_{q}\right)+\mathbb{P}\left(\\{\exists
j\in\mathcal{A}_{\rho[q]-1}\cap[k_{q}^{*},n]:V^{R}_{j\to
k_{v[q]}}=1\\}\cap\\{\mathbf{I}^{R}_{k_{v[q]}}=\mathbf{V}^{R}_{k_{v[q]}}\\}\cap\mathcal{E}_{q}\right),$

and start by bounding the first term on the right-hand side. As in the proof
of Lemma 4.5, we use several intermediate steps to couple
$\mathbf{I}^{R}_{k_{v[q]}}$ and $\mathbf{V}^{R}_{k_{v[q]}}$.

  1. 1.

We define $\widetilde{\mathbf{I}}^{R}_{k_{v[q]}}:=(\widetilde{I}^{R}_{j\to
k_{v[q]}})_{j=k^{*}_{q}}^{n}$ as a sequence of independent Bernoulli random
variables with success probabilities $(\mu_{j})_{j=k^{*}_{q}}^{n}$ defined in
(74) and couple $\mathbf{I}^{R}_{k_{v[q]}}$ with
$\widetilde{\mathbf{I}}^{R}_{k_{v[q]}}$.

  2. 2.

We couple $\widetilde{\mathbf{I}}^{R}_{k_{v[q]}}$ with a sequence of
independent Poisson random variables
$\widetilde{\mathbf{V}}^{R}_{k_{v[q]}}:=(\widetilde{V}^{R}_{j\to
k_{v[q]}})_{j=k^{*}_{q}}^{n}$ with means $(\mu_{j})_{j=k^{*}_{q}}^{n}$.

  3. 3.

We couple $\widetilde{\mathbf{V}}^{R}_{k_{v[q]}}$ with
$\mathbf{V}^{R}_{k_{v[q]}}$.

Throughout the proof, we assume that $N_{v[q]}\geq k_{v[q]}+2$ so that
$k^{*}_{q}=k_{v[q]}+1$. The cases $N_{v[q]}=k_{v[q]}+1$ and
$N_{v[q]}<k_{v[q]}+1$ can be dealt with in a similar way with only minor
modifications. We now provide details for the three steps.

Step $1$. We start by observing that for all
$j\in[k^{*}_{q},n]\cap\mathcal{P}_{\rho[q]-1}$, $I^{R}_{j\to k_{v[q]}}=0$
almost surely. We first bound the probability that $\widetilde{I}^{R}_{j\to
k_{v[q]}}\neq I^{R}_{j\to k_{v[q]}}$ for any
$j\in[k^{*}_{q},n]\cap\mathcal{P}_{\rho[q]-1}$, which occurs when the former
is equal to 1. By a union bound,

$\displaystyle\mathbb{P}\bigg{(}\bigcup_{\begin{subarray}{c}j=k^{*}_{q}\\\
j\in\mathcal{P}_{\rho[q]-1}\end{subarray}}^{n}\big{\\{}\widetilde{I}^{R}_{j\to
k_{v[q]}}=1\big{\\}}\cap\mathcal{E}_{q}\bigg{)}$
$\displaystyle=\mathbb{E}\bigg{[}\mathbbm{1}_{\mathcal{E}_{q}}\mathbb{P}\bigg{(}\bigcup_{\begin{subarray}{c}j=k^{*}_{q}\\\
j\in\mathcal{P}_{\rho[q]-1}\end{subarray}}^{n}\big{\\{}\widetilde{I}^{R}_{j\to
k_{v[q]}}=1\big{\\}}\,\bigg{|}\,\mathcal{C}_{q}\bigg{)}\bigg{]}$ (138)
$\displaystyle\leq\mathbb{E}\bigg{[}\mathbbm{1}_{\mathcal{E}_{q}}\sum_{\begin{subarray}{c}j=k^{*}_{q}\\\
j\in\mathcal{P}_{\rho[q]-1}\end{subarray}}^{n}\frac{\beta
p}{2\varepsilon}\frac{1}{n}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)-1}\bigg{]}$
$\displaystyle\leq\mathbb{E}\left[\mathbbm{1}_{\mathcal{E}_{q}}\frac{\beta
p}{2\varepsilon}\frac{|\mathcal{P}_{\rho[q]-1}|}{k_{v[q]}}\right]=\mathcal{O}\Big{(}\frac{(\log\log
n)^{q+1+q/r}}{n}\Big{)},$

where in the last inequality we used that
$\tfrac{1}{n}\big{(}\tfrac{j}{n}\big{)}^{(1-p)/(2\varepsilon)-1}\leq\tfrac{1}{j}$
for all $j\leq n$, and the last equality is due to the bounds on $k_{v[q]}$
and $|\mathcal{P}_{\rho[q]-1}|$ on the event $\mathcal{E}_{q}$. For the
remaining indices, we use a standard Bernoulli coupling to obtain

$\mathbb{P}\bigg{(}\bigcup_{\begin{subarray}{c}j=k^{*}_{q}\\\
j\not\in\mathcal{P}_{\rho[q]-1}\end{subarray}}^{n}\big{\\{}\widetilde{I}^{R}_{j\to
k_{v[q]}}\neq I^{R}_{j\to
k_{v[q]}}\big{\\}}\cap\mathcal{E}_{q}\bigg{)}\leq\mathbb{E}\bigg{[}\mathbbm{1}_{\mathcal{E}_{q}}\\!\\!\\!\sum_{\begin{subarray}{c}j=k^{*}_{q}\\\
j\not\in\mathcal{P}_{\rho[q]-1}\end{subarray}}^{n}\\!\\!\\!\\!\Big{|}\frac{\beta
p}{2\varepsilon}\frac{1}{n}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)-1}-\mathbb{P}\left(I^{R}_{j\to
k_{v[q]}}=1\,\Big{|}\,\mathcal{C}_{q}\right)\Big{|}\bigg{]}$ (139)

As in (77), we show that the absolute value is small by providing a precise
asymptotic value for the probability. Using Lemmas 2.6 and 2.5 with
$S=\mathcal{A}_{\rho[q]-1,j}\cup\mathcal{P}_{\rho[q]-1,j}$ and $R=\\{j\\}$
(note that $j\geq k_{v[q]}=\omega((\log n)^{3})$ and $|S|=o(j^{2/3})$ on the
event $\mathcal{E}_{q}$), we arrive at

$\displaystyle\mathbbm{1}_{\mathcal{E}_{q}}\mathbb{P}\left(I^{R}_{j\to
k_{v[q]}}=1\,\Big{|}\,\mathcal{C}_{q}\right)=\mathbbm{1}_{\mathcal{E}_{q}}p\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)}\Big{(}1+\mathcal{O}\Big{(}\frac{\log
n}{j^{1/3}}\Big{)}\Big{)}.$ (140)

Combining this with the bound in (139), we get

$\mathbb{P}\bigg{(}\\!\\!\bigcup_{\begin{subarray}{c}j=k^{*}_{q}\\\
j\not\in\mathcal{P}_{\rho[q]-1}\end{subarray}}^{n}\\!\\!\big{\\{}\widetilde{I}^{R}_{j\to
k_{v[q]}}\neq I^{R}_{j\to
k_{v[q]}}\big{\\}}\cap\mathcal{E}_{q}\bigg{)}\leq\mathbb{E}\bigg{[}\mathbbm{1}_{\mathcal{E}_{q}}\sum_{j=k^{*}_{q}}^{n}\mathcal{O}\Big{(}\frac{\log
n}{j^{4/3}}\Big{)}\bigg{]}=\mathbb{E}\left[\mathbbm{1}_{\mathcal{E}_{q}}\mathcal{O}\big{(}(k^{*}_{q})^{-1/3}\log
n\big{)}\right]=\mathcal{O}\Big{(}\frac{(\log n)^{2}}{n^{1/3}}\Big{)},$ (141)

where the last equality holds by the lower bound on $k_{q}^{*}$ ensured by the
event $\mathcal{E}_{q}$. Combining this with (138) finishes the first step.

Step $2$. This step is identical to step $2$ in the proof of Lemma 4.5 and we
only state the main result:

$\mathbb{P}\left(\\{\widetilde{\mathbf{I}}^{R}_{k_{v[q]}}\neq\widetilde{\mathbf{V}}^{R}_{k_{v[q]}}\\}\cap\mathcal{E}_{q}\right)=\mathcal{O}\left(\frac{(\log\log
n)^{q+1}}{n}\right).$ (142)

Step $3$. We couple each $\widetilde{V}^{R}_{j\to k_{v[q]}}$ and $V^{R}_{j\to
k_{v[q]}}$ via a standard coupling between Poisson random variables (see Lemma
2.3). Recall that we assume that $N_{v[q]}\geq k_{v[q]}+2$, so that
$\lambda^{\rho[q]}_{j}=0$ for all $j\in[k^{*}_{q},N_{v[q]}-1]$. Also, we
define $\mu_{j}^{\rho[q]}$ as in (74) but for $j\in[k^{*}_{q},n]$ instead.
With steps equivalent to the ones in (83), it follows that for all
$j\in[N_{v[q]},n]$,

$|\lambda_{j}^{\rho[q]}-\mu_{j}^{\rho[q]}|=\mathcal{O}\Big{(}\frac{1}{n^{2}}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)-2}\Big{)}.$
(143)

Moreover, for all $j\in[k^{*}_{q},N_{v[q]}-1]$,
$\mu_{j}^{\rho[q]}\leq\tfrac{\beta p}{2\varepsilon j}\leq\tfrac{\beta
p}{2\varepsilon k^{*}_{q}}\leq\tfrac{\beta p}{2\varepsilon k_{v[q]}}$. Again,
we write

$\mathbb{P}\left(\Big{\\{}\widetilde{\mathbf{V}}^{R}_{k_{v[q]}}\neq\mathbf{V}^{R}_{k_{v[q]}}\Big{\\}}\cap\mathcal{E}_{q}\right)=\mathbb{E}\bigg{[}\mathbbm{1}_{\mathcal{E}_{q}}\mathbb{P}\left(\widetilde{\mathbf{V}}^{R}_{k_{v[q]}}\neq\mathbf{V}^{R}_{k_{v[q]}}\,\Big{|}\,\mathcal{C}_{q}\right)\Bigg{]},$
(144)

and the previous observations imply that

$\displaystyle\mathbb{P}\left(\widetilde{\mathbf{V}}^{R}_{k_{v[q]}}\neq\mathbf{V}^{R}_{k_{v[q]}}\,\Big{|}\,\mathcal{C}_{q}\right)$
$\displaystyle\leq\sum_{j=k^{*}_{q}}^{N_{v[q]}-1}\mu_{j}^{\rho[q]}+\sum_{j=N_{v[q]}}^{n}|\lambda_{j}^{\rho[q]}-\mu_{j}^{\rho[q]}|$
(145) $\displaystyle\leq\sum_{j=k^{*}_{q}}^{N_{v[q]}-1}\frac{\beta
p}{2\varepsilon
k_{v[q]}}+\mathcal{O}\Big{(}\sum_{j=N_{v[q]}}^{n}\frac{1}{n^{2}}\Big{(}\frac{j}{n}\Big{)}^{(1-p)/(2\varepsilon)-2}\Big{)}$
$\displaystyle\leq(\lceil a_{v[q]}n\rceil-1-k_{v[q]})\frac{\beta p(\log\log
n)^{q+1}}{2\varepsilon
n}+\mathcal{O}\Big{(}\frac{1}{n}\int_{N_{v[q]}/n}^{1}x^{(1-p)/(2\varepsilon)-2}\,\mathrm{d}x\Big{)}.$

Note that on the event $\mathcal{E}_{q}$ one has $|a_{v[q]}n-k_{v[q]}|\leq
q+1$, and the integral in the $\mathcal{O}$ satisfies that:

  * •

if $\tfrac{1-p}{2\varepsilon}>1$, its value is $\mathcal{O}(1)$;

  * •

if $\tfrac{1-p}{2\varepsilon}=1$, its value is $\mathcal{O}(\log n)$;

  * •

if $\tfrac{1-p}{2\varepsilon}<1$, its value is
$\mathcal{O}\left(\left(\tfrac{N_{v[q]}}{n}\right)^{(1-p)/(2\varepsilon)-1}\right)$.

Hence, on the event $\mathcal{E}_{q}$, in all three cases we obtain the upper
bound