# The giant in random graphs is almost local

Remco van der<EMAIL_ADDRESS>[ Department of
Mathematics and Computer Science, Eindhoven University of Technology,

###### Abstract

Local convergence techniques have become a key methodology to study random
graphs in sparse settings where the average degree remains bounded. However,
many random graph properties do not directly converge when the random graph
converges locally. A notable, and important, random graph property that does
not follow from local convergence is the size and uniqueness of the giant
component. We provide a simple criterion that guarantees that local
convergence of a random graph implies the convergence of the proportion of
vertices in the maximal connected component. We further show that, when this
condition holds, the local properties of the giant are also described by the
local limit.

We apply this novel method to the configuration model as a proof of concept,
reproving a result that is well-established. As a side result this proof, we
show that the proof also implies the small-world nature of the configuration
model.

60K37,

05C81,

82C27,

37A25,

Random graphs,

Local convergence,

Giant component,

Configuration model,

###### keywords:

[class=MSC2020]

###### keywords:

##  1 Introduction

Local convergence techniques, as introduced by Aldous and Steele [3] and
Benjamini and Schramm [13], have become the main methodology to study random
graphs in sparse settings where the average degree remains bounded. Local
convergence roughly means that the proportion of vertices whose neighborhoods
have a certain shape converges to some limiting value, which is to be
considered as a measure on rooted graphs. We refer to [39, Chapter 2] for
background on local convergence.

The giant component problem has received enormous attention ever since the
very first and seminal results by Erdős and Rényi on the Erdős-Rényi random
graph [33], see also [48, 18] for detailed further results for this model. The
simplest form of this question is whether there exists a linear-size connected
component or not, in many cases a sharp transition occurs depending on a
certain graph parameter. See [6, 32, 50, 38, 39], as well as the references
therein, for several books on the topic.

This paper combines these two threads by investigating the size of the giant
component when the random graph converges locally. Consider a sequence of
random graphs $(G_{n})_{n\geq 1}$, where we will simplify the notation by
assuming that $G_{n}=(V(G_{n}),E(G_{n}))$ is such that $|V(G_{n})|=n$. We let

$|\mathscr{C}_{\rm max}|=\max_{v\in V(G_{n})}|\mathscr{C}(v)|$ (1.1)

denotes the maximal cluster size. When the random graph converges locally to
some limiting rooted measure, then one would expect that also
$|\mathscr{C}_{\rm
max}|/n\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\zeta$,
where $\zeta$ is the survival probability of the local limit. However, while
the number of connected components is well behaved in the local topology, the
proportion of vertices in the giant is not so nicely behaved. Indeed, since
local convergence is all about proportions of vertices whose finite (but
arbitrarily large) neighborhoods converge to a limit, there is an enormous gap
between surviving locally and being in the giant component. Thus, local
convergence is obviously not enough to imply the convergence of the giant. In
this paper, we identify what extra condition is needed to imply this natural
implication.

##  2 Asymptotics and properties of the giant

In this section, we investigate the behavior of the giant component
$|\mathscr{C}_{\rm max}|$ for random graphs that converge locally. In Section
2.1, we introduce the notion of local convergence in probability. In Section
2.2, we study the asymptotic of $|\mathscr{C}_{\rm max}|$ for random graphs
that converge locally in probability, and in Section 2.3 we investigate local
properties of the giant.

###  2.1 Local convergence in probability

Local convergence was introduced independently by Aldous and Steele in [3] and
Benjamini and Schramm in [13]. The purpose of Aldous and Steele in [3] was to
describe the local structure of the so-called ‘stochastic mean-field model of
distance’, meaning the complete graph with i.i.d. exponential edge weights.
This local description allowed Aldous to prove the celebrated $\zeta(2)$ limit
of the random assignment problem [1]. Benjamini and Schramm in [13] instead
used local weak convergence to show that limits of planar graphs are with
probability one recurrent. Since its conception, local convergence has proved
a key ingredient in random graph theory. In this section, we provide some
basics of local convergence. For more detailed discussions, we refer the
reader to [22] or [39, Chapter 2]. Let us start with some definitions.

A rooted graph is a pair $(G,o)$, where $G=(V(G),E(G))$ is a graph with vertex
set $V(G)$ and edge set $E(G)$, and $o\in V(G)$ is a vertex. Further, a rooted
or non-rooted graph is called locally finite when each of its vertices has
finite degree (though not necessarily uniformly bounded). Two (finite or
infinite) graphs $G_{1}=(V(G_{1}),E(G_{1}))$ and $G_{2}=(V(G_{2}),E(G_{2}))$
are called isomorphic, which we write as $G_{1}\simeq G_{2}$, when there
exists a bijection $\phi\colon V(G_{1})\mapsto V(G_{2})$ such that
$\\{u,v\\}\in E(G_{1})$ precisely when $\\{\phi(u),\phi(v)\\}\in E(G_{2}).$
Similarly, two rooted (finite or infinite) graphs $(G_{1},o_{1})$ and
$(G_{2},o_{2})$ ,wtih $G_{i}=(V(G_{i}),E(G_{i}))$ for $i\in\\{1,2\\}$, are
called isomorphic, abbreviated as $(G_{1},o_{1})\simeq(G_{2},o_{2})$, when
there exists a bijection $\phi\colon V(G_{1})\mapsto V(G_{2})$ such that
$\phi(o_{1})=o_{2}$ and $\\{u,v\\}\in E(G_{1})$ precisely when
$\\{\phi(u),\phi(v)\\}\in E(G_{2}).$ These notions can be easily adapted to
multi-graphs (which we will need to rely on), for which
$G=(V(G),(x_{i,j})_{i,j\in V(G)})$, where $x_{i,j}$ denotes the number of
edges between $i$ and $j$, and $x_{i,i}$ the number of self-loops at $i$.
There, instead, the isomorphism $\phi\colon V(G)\mapsto V(G^{\prime})$ is
required to satisfy that $x_{i,j}=x^{\prime}_{\phi(i),\phi(j)}$, where
$(x_{i,j})_{i,j\in V(G)}$ and $(x_{i,j}^{\prime})_{i,j\in V(G^{\prime})}$ are
the edge multiplicities of $G$ and $G^{\prime}$ respectively.

We let $\mathscr{G}_{\star}$ be the space of (possibly infinite) connected
rooted graphs, where we consider two graphs to be equal when they are
isomorphic. Thus, we consider $\mathscr{G}_{\star}$ as the set of equivalence
classes of rooted graphs modulo isomorphisms. The space $\mathscr{G}_{\star}$
of rooted graphs is a nice metric space, with an explicit metric, see [39,
Appendix A] for details.

For a rooted graph $(G,o)$, we let $B_{r}^{\scriptscriptstyle(G)}(o)$ denote
the (rooted) subgraph of $(G,o)$ of all vertices at graph distance at most $r$
away from $o$. Formally, this means that
$B_{r}^{\scriptscriptstyle(G)}(o)=((V(B_{r}^{\scriptscriptstyle(G)}(o)),E(B_{r}^{\scriptscriptstyle(G)}(o)),o)$,
where

$\displaystyle V(B_{r}^{\scriptscriptstyle(G)}(o))$ $\displaystyle=\\{u\colon
d_{\scriptscriptstyle G}(o,u)\leq r\\},$ (2.1) $\displaystyle
E(B_{r}^{\scriptscriptstyle(G)}(o))$ $\displaystyle=\\{\\{u,v\\}\in E(G)\colon
d_{\scriptscriptstyle G}(o,u),d_{\scriptscriptstyle G}(o,v)\leq r\\}.$

Let $o\in V(G_{n})$ be chosen uniformly at random (u.a.r.) in $V(G_{n})$. We
say that the graph sequence $(G_{n})_{n\geq 1}$ converges locally in
probability to a limit $(G,o)\sim\mu$, when, for every $r\geq 0$ and
$H^{\star}\in\mathscr{G}_{\star}$,

$\frac{1}{|V(G_{n})}\sum_{v\in
V(G_{n})}\mathbbm{1}_{\\{B_{r}^{\scriptscriptstyle(G_{n})}(v)\simeq
H^{\star}\\}}\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\mu(B_{r}^{\scriptscriptstyle(G)}(v)\simeq
H^{\star}).$ (2.2)

This means that the subgraph proportions in the random graph $G_{n}$ are
close, in probability, to those given by $\mu$.

There are related notions of local convergence, such as local weak
convergence, where (2.2) is replaced by the expectation of the left-hand side
converging to those on the right hand side, and local almost sure convergence,
where the convergence in probability in (2.2) is replaced by convergence
almost surely. For our purposes, local convergence in probability is the most
convenient, for example since it implies that the neighborhoods of two
uniformly chosen vertices are close to being independent (see e.g., [39,
Corollary 2.18]), which is central in our proof.

###  2.2 Asymptotics of the giant

Given a random graph sequence $G_{n}$ that converges in locally probability to
$(G,o)\sim\mu$, one would expect that $|\mathscr{C}_{\rm
max}|/n\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\zeta:=\mu(|\mathscr{C}(o)|=\infty)$.
However, the proportion of vertices in the largest connected component
$|\mathscr{C}_{\rm max}|/n$ is not continuous in the local convergence
topology, as it is a global object. In fact, also $|\mathscr{C}(o_{n})|/n$
does not converge in distribution when $G_{n}$ converges locally in
probability to $(G,o)\sim\mu$. However, local convergence still tells us a
useful story about the existence of a giant, as well as its size. Indeed,
Corollary 2.1 shows that the upper bound is always valid, while Theorem 2.2
shows that a relative simple condition suffices to yield the lower bound as
well:

######  Corollary 2.1 (Upper bound on the giant).

Let $(G_{n})_{n\geq 1}$ be a sequence of graphs whose sizes $|V(G_{n})|=n$
tend to infinity. Assume that $G_{n}$ converges locally in probability to
$(G,o)\sim\mu$. Write $\zeta=\mu(|\mathscr{C}(o)|=\infty)$ for the survival
probability of the limiting graph $(G,o)$. Then, for every $\varepsilon>0$
fixed,

${\mathbb{P}}(|\mathscr{C}_{\rm max}|\leq n(\zeta+\varepsilon))\rightarrow 1.$
(2.3)

In particular, Corollary 2.1 implies that $|\mathscr{C}_{\rm
max}|/n\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}0$
when $\zeta=0$, so that there can only be a giant when the local limit has a
positive survival probability.

###### Proof.

Define

$Z_{\scriptscriptstyle\geq k}=\sum_{v\in
V(G_{n})}\mathbbm{1}_{\\{|\mathscr{C}(v)|\geq k\\}}.$ (2.4)

Assume that $G_{n}$ converges locally in probability to $(G,o)\sim\mu$ as
defined in (2.2). Since $\\{|\mathscr{C}(v)|\geq
k\\}=\\{|B_{k}^{\scriptscriptstyle(G)}(v)|\geq k\\}$,with $\zeta_{\geq
k}=\mu(|\mathscr{C}(o)|\geq k)$,

$\frac{Z_{\scriptscriptstyle\geq
k}}{n}\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\zeta_{\geq
k}.$ (2.5)

For every $k\geq 1$,

$\\{|\mathscr{C}_{\rm max}|\geq k\\}=\\{Z_{\scriptscriptstyle\geq k}\geq
k\\},$ (2.6)

and, on the event that $Z_{\scriptscriptstyle\geq k}\geq 1$, also
$|\mathscr{C}_{\rm max}|\leq Z_{\scriptscriptstyle\geq k}$. Note that
$\zeta=\lim_{k\rightarrow\infty}\zeta_{\geq k}=\mu(|\mathscr{C}(o)|=\infty)$.
We take $k$ so large that $\zeta\geq\zeta_{\geq k}-\varepsilon/2$. Then, for
every $k\geq 1$, $\varepsilon>0$, and all $n$ large enough,

$\displaystyle{\mathbb{P}}(|\mathscr{C}_{\rm max}|\geq n(\zeta+\varepsilon))$
$\displaystyle\leq{\mathbb{P}}(Z_{\scriptscriptstyle\geq k}\geq
n(\zeta+\varepsilon))$ (2.7)
$\displaystyle\leq{\mathbb{P}}(Z_{\scriptscriptstyle\geq k}\geq n(\zeta_{\geq
k}+\varepsilon/2))=o(1).$

∎

We conclude that while local convergence cannot determine the size of the
largest connected component, it can prove an upper bound on $|\mathscr{C}_{\rm
max}|$. There are many results that extend this to $|\mathscr{C}_{\rm
max}|/n\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\zeta$
(see Section 4 for pointers to the literature), but this is no longer a
consequence of local convergence alone. Therefore, in general, more involved
arguments must be used. We next prove that one, relatively simple, condition
suffices. In its statement, and for $x,y\in V(G_{n})$, we write
$x\longleftrightarrow{/}\hskip 7.74998pty$ when $x\not\in\mathscr{C}(y)$:

######  Theorem 2.2 (The giant is almost local).

Let $G_{n}=(V(G_{n}),E(G_{n}))$ denote a random graph of size $|V(G_{n})|=n$.
Assume that $G_{n}$ converges locally in probability to $(G,o)\sim\mu$. Assume
further that

$\lim_{k\rightarrow\infty}\limsup_{n\rightarrow\infty}\frac{1}{n^{2}}{\mathbb{E}}\Big{[}\\#\big{\\{}(x,y)\in
V(G_{n})\colon|\mathscr{C}(x)|,|\mathscr{C}(y)|\geq
k,x\longleftrightarrow{/}\hskip 7.74998pty\big{\\}}\Big{]}=0.$ (2.8)

Then, with $\mathscr{C}_{\rm max}$ and $\mathscr{C}_{\scriptscriptstyle(2)}$
denoting the largest and second largest connected components (with ties broken
arbitrarily),

$\frac{|\mathscr{C}_{\rm
max}|}{n}\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\zeta=\mu(|\mathscr{C}(o)|=\infty),\qquad\frac{|\mathscr{C}_{\scriptscriptstyle(2)}|}{n}\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}0.$
(2.9)

Theorem 2.2 shows that a relatively mild condition as in (2.8) suffices for
the giant to have the expected limit. In fact, we will see that it is
necessary and sufficient.

We now start with the preparations for the proof of Theorem 2.2. We first note
that, by Corollary 2.1, it suffices to prove Theorem 2.2 for $\zeta>0$, which
we assume from now on.

We recall that the vector $(|\mathscr{C}_{\scriptscriptstyle(i)}|)_{i\geq 1}$
denotes the cluster sizes ordered in size, from large to small with ties
broken arbitrarily, so that
$\mathscr{C}_{\scriptscriptstyle(1)}=\mathscr{C}_{\rm max}$. The following
lemma gives a useful estimate on the sum of squares of these ordered cluster
sizes. In its statement, we write
$X_{n,k}=o_{k,{\scriptscriptstyle{\mathbb{P}}}}(1)$ when

$\lim_{k\rightarrow\infty}\limsup_{n\rightarrow\infty}{\mathbb{P}}(|X_{n,k}|>\varepsilon)=0.$
(2.10)

######  Lemma 2.3 (Convergence of sum of squares of cluster sizes).

Under the conditions of Theorem 2.2,

$\frac{1}{n^{2}}\sum_{i\geq
1}|\mathscr{C}_{\scriptscriptstyle(i)}|^{2}\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\zeta^{2},$
(2.11)

and

$\frac{1}{n^{2}}\sum_{i\geq
1}|\mathscr{C}_{\scriptscriptstyle(i)}|^{2}\mathbbm{1}_{\\{|\mathscr{C}_{\scriptscriptstyle(i)}|\geq
k\\}}=\zeta^{2}+o_{k,{\scriptscriptstyle{\mathbb{P}}}}(1).$ (2.12)

###### Proof.

By local convergence in probability and for any $k\geq 1$ fixed (recall (2.5))

$\frac{1}{n}\sum_{i\geq
1}|\mathscr{C}_{\scriptscriptstyle(i)}|\mathbbm{1}_{\\{|\mathscr{C}_{\scriptscriptstyle(i)}|\geq
k\\}}=\frac{1}{n}\sum_{v\in V(G_{n})}\mathbbm{1}_{\\{|\mathscr{C}(v)|\geq
k\\}}=\frac{1}{n}Z_{\scriptscriptstyle\geq
k}\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\zeta_{\geq
k},$ (2.13)

where we recall that $\zeta_{\geq k}=\mu(|\mathscr{C}(o)|\geq k)$. Thus, since
$\zeta_{\geq k}\rightarrow\zeta$,

$\frac{1}{n}\sum_{i\geq
1}|\mathscr{C}_{\scriptscriptstyle(i)}|\mathbbm{1}_{\\{|\mathscr{C}_{\scriptscriptstyle(i)}|\geq
k\\}}=\zeta+o_{k,{\scriptscriptstyle{\mathbb{P}}}}(1).$ (2.14)

Further,

$\displaystyle\frac{1}{n^{2}}\\#\big{\\{}(x,y)\in
V(G_{n})\colon|\mathscr{C}(x)|,|\mathscr{C}(y)|\geq
k,x\longleftrightarrow{/}\hskip 7.74998pty\big{\\}}$ (2.15)
$\displaystyle\qquad=\frac{1}{n^{2}}\sum_{\stackrel{{\scriptstyle{\large
i,j\geq 1}}}{{i\neq
j}}}|\mathscr{C}_{\scriptscriptstyle(i)}||\mathscr{C}_{\scriptscriptstyle(j)}|\mathbbm{1}_{\\{|\mathscr{C}_{\scriptscriptstyle(i)}|,|\mathscr{C}_{\scriptscriptstyle(j)}|\geq
k\\}}.$

By the Markov inequality,

$\displaystyle\lim_{k\rightarrow\infty}\limsup_{n\rightarrow\infty}{\mathbb{P}}(\frac{1}{n^{2}}\\#\big{\\{}(x,y)\in
V(G_{n})\colon|\mathscr{C}(x)|,|\mathscr{C}(y)|\geq
k,x\longleftrightarrow{/}\hskip 7.74998pty\big{\\}}\geq\varepsilon)$ (2.16)
$\displaystyle\qquad\leq\lim_{k\rightarrow\infty}\limsup_{n\rightarrow\infty}\frac{1}{\varepsilon
n^{2}}{\mathbb{E}}\Big{[}\\#\big{\\{}(x,y)\in
V(G_{n})\colon|\mathscr{C}(x)|,|\mathscr{C}(y)|\geq
k,x\longleftrightarrow{/}\hskip 7.74998pty\big{\\}}\Big{]}=0,$

by our main assumption in (2.8). As a result,

$\frac{1}{n^{2}}\\#\big{\\{}(x,y)\in
V(G_{n})\colon|\mathscr{C}(x)|,|\mathscr{C}(y)|\geq
k,x\longleftrightarrow{/}\hskip
7.74998pty\big{\\}}=o_{k,{\scriptscriptstyle{\mathbb{P}}}}(1).$ (2.17)

We conclude that, by (2.13),

$\displaystyle\frac{1}{n^{2}}\sum_{i\geq
1}|\mathscr{C}_{\scriptscriptstyle(i)}|^{2}\mathbbm{1}_{\\{|\mathscr{C}_{\scriptscriptstyle(i)}|\geq
k\\}}$ $\displaystyle=\Big{(}\frac{1}{n}\sum_{i\geq
1}|\mathscr{C}_{\scriptscriptstyle(i)}|\mathbbm{1}_{\\{|\mathscr{C}_{\scriptscriptstyle(i)}|\geq
k\\}}\Big{)}^{2}+o_{k,{\scriptscriptstyle{\mathbb{P}}}}(1)$ (2.18)
$\displaystyle=\zeta^{2}+o_{k,{\scriptscriptstyle{\mathbb{P}}}}(1).$ (2.19)

This proves (2.12). Finally,

$\frac{1}{n^{2}}\sum_{i\geq
1}|\mathscr{C}_{\scriptscriptstyle(i)}|^{2}\mathbbm{1}_{\\{|\mathscr{C}_{\scriptscriptstyle(i)}|<k\\}}\leq
k\frac{1}{n^{2}}\sum_{i\geq
1}|\mathscr{C}_{\scriptscriptstyle(i)}|\mathbbm{1}_{\\{|\mathscr{C}_{\scriptscriptstyle(i)}|<k\\}}\leq\frac{k}{n},$
(2.20)

so that, almost surely,

$\frac{1}{n^{2}}\sum_{i\geq
1}|\mathscr{C}_{\scriptscriptstyle(i)}|^{2}=\frac{1}{n^{2}}\sum_{i\geq
1}|\mathscr{C}_{\scriptscriptstyle(i)}|^{2}\mathbbm{1}_{\\{|\mathscr{C}_{\scriptscriptstyle(i)}|\geq
k\\}}+O\big{(}\frac{k}{n}\big{)},$ (2.21)

which, together with (2.12), completes the proof of (2.11). ∎

We are now ready to complete the proof of Theorem 2.2:

Proof of Theorem 2.2. By Lemma 2.3,

$\frac{1}{n^{2}}\sum_{i\geq
1}|\mathscr{C}_{\scriptscriptstyle(i)}|^{2}\mathbbm{1}_{\\{|\mathscr{C}_{\scriptscriptstyle(i)}|\geq
k\\}}=\zeta^{2}+o_{k,{\scriptscriptstyle{\mathbb{P}}}}(1).$ (2.22)

Denote
$x_{i,n}=|\mathscr{C}_{\scriptscriptstyle(i)}|\mathbbm{1}_{\\{|\mathscr{C}_{\scriptscriptstyle(i)}|\geq
k\\}}/n$. Then, by (2.13) and (2.22), for every $\varepsilon>0$ and whp,

$\sum_{i\geq 1}x_{i,n}\leq\zeta+\varepsilon/4,\qquad\sum_{i\geq
1}x_{i,n}^{2}\geq\zeta^{2}-\varepsilon^{2}.$ (2.23)

We wish to show that
$x_{1,n}=\zeta+o_{k,{\scriptscriptstyle{\mathbb{P}}}}(1)$. Clearly
$x_{1,n}\leq\zeta+o_{k,{\scriptscriptstyle{\mathbb{P}}}}(1)$. Since $x_{1,n}$
is bounded, it has a subsequence that converges in probability. Now suppose by
contradiction that, along such a subsequence,
$x_{1,n}=|\mathscr{C}_{\scriptscriptstyle(1)}|\mathbbm{1}_{\\{|\mathscr{C}_{\scriptscriptstyle(1)}|\geq
k\\}}/n\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}a_{k}$,
where $a_{k}\rightarrow a=\zeta-\delta$ for some $\delta>0$, so that
$x_{1,n}=\zeta-\delta+o_{k,{\scriptscriptstyle{\mathbb{P}}}}(1)$. Let us work
along this subsequence. Then, again using (2.22),

$\sum_{i\geq 2}x_{i,n}^{2}=\sum_{i\geq
1}x_{i,n}^{2}-x_{1,n}^{2}=\zeta^{2}-(\zeta-\delta)^{2}+o_{k,{\scriptscriptstyle{\mathbb{P}}}}(1)=\delta(2\zeta-\delta)+o_{k,{\scriptscriptstyle{\mathbb{P}}}}(1).$
(2.24)

Also, $\sum_{i\geq
2}x_{i,n}=\delta+o_{k,{\scriptscriptstyle{\mathbb{P}}}}(1)$. As a result,

$\delta^{2}+o_{k,{\scriptscriptstyle{\mathbb{P}}}}(1)=\Big{(}\sum_{i\geq
2}x_{i,n}\Big{)}^{2}=\sum_{i\geq 2}x_{i,n}^{2}+\sum_{i,j\geq 2\colon i\neq
j}x_{i,n}x_{j,n}.$ (2.25)

Clearly, by our main assumption (2.8),

$o_{k,{\scriptscriptstyle{\mathbb{P}}}}(1)=\sum_{i,j\geq 2\colon i\neq
j}x_{i,n}x_{j,n}\leq\Big{(}\sum_{i\geq 1}x_{i,n}\Big{)}^{2}-\sum_{i\geq
1}x_{i,n}^{2},$ (2.26)

so that combining (2.24)–(2.26) leads to $\delta^{2}=\delta(2\zeta-\delta)$
which gives $\delta=\zeta$. In turn, this implies that
$x_{1,n}=o_{k,{\scriptscriptstyle{\mathbb{P}}}}(1)$. By (2.12) and
$x_{i,n}\leq x_{1,n}$, we get $\zeta=0$, contradicting our assumption that
$\zeta>0$. ∎

#### Proof of necessity of (2.8)

Here we complete the proof by showing that (2.8) is also necessary for
$|\mathscr{C}_{\rm
max}|/n\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\zeta$
to hold. Indeed, (2.15) implies that when (2.8) fails, for every $k\geq 1$ and
by monotonicity,

$\limsup_{n\rightarrow\infty}{\mathbb{E}}\Big{[}\frac{1}{n^{2}}\sum_{\stackrel{{\scriptstyle{\large
i,j\geq 1}}}{{i\neq
j}}}|\mathscr{C}_{\scriptscriptstyle(i)}||\mathscr{C}_{\scriptscriptstyle(j)}|\mathbbm{1}_{\\{|\mathscr{C}_{\scriptscriptstyle(i)}|,|\mathscr{C}_{\scriptscriptstyle(j)}|\geq
k\\}}\Big{]}=\kappa_{k}\geq\kappa>0.$ (2.27)

Denote the random variable in the expectation in (2.27) by
$P^{\scriptscriptstyle(2)}_{k,n}$, so that there exists a subsequence
$(n_{l})_{l\geq 1}$ for which
$\lim_{l\rightarrow\infty}{\mathbb{E}}[P^{\scriptscriptstyle(2)}_{k,n_{l}}]=\kappa>0$.
Since $|\mathscr{C}_{\rm max}|/n$ is bounded, along a subsequence it converges
in probability to some limit $a$. Our task is to show that $a<\zeta$. For
this, by bounded convergence and again along the subsequence $(n_{l})_{l\geq
1}$,

$\displaystyle a^{2}$
$\displaystyle=\lim_{l\rightarrow\infty}\frac{1}{n_{l}^{2}}{\mathbb{E}}[|\mathscr{C}_{\rm
max}|^{2}]\leq\lim_{l\rightarrow\infty}\frac{1}{n_{l}^{2}}\sum_{i}{\mathbb{E}}[|\mathscr{C}_{\scriptscriptstyle(i)}|\mathbbm{1}_{\\{|\mathscr{C}_{\scriptscriptstyle(i)}|\geq
k\\}}^{2}]$ (2.28)
$\displaystyle=\lim_{n\rightarrow\infty}\frac{1}{n_{l}^{2}}{\mathbb{E}}[Z_{\geq
k}^{2}-P^{\scriptscriptstyle(2)}_{k,n_{l}}]\leq\zeta_{\geq k}^{2}-\kappa.$

Letting $k\rightarrow\infty$ and using that $\zeta_{\geq k}\rightarrow\zeta$,
we obtain that $a<\zeta$ as claimed. ∎

###  2.3 Local properties of the giant

We next extend Theorem 2.2 by investigating the structure of the giant. For
this, we first let $v_{k}(\mathscr{C}_{\rm max})$ denote the number of
vertices with degree $k$ in the giant component, and we recall that
$|E(\mathscr{C}_{\rm max})|$ denotes the number of edges in the giant
component:

######  Theorem 2.4 (Properties of the giant).

Under the assumptions of Theorem 2.2, when
$\zeta=\mu(|\mathscr{C}(o)|=\infty)>0$,

$\frac{v_{\ell}(\mathscr{C}_{\rm
max})}{n}\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\mu(|\mathscr{C}(o)|=\infty,d_{o}=\ell).$
(2.29)

Further, assume that $D_{n}=d_{o_{n}}^{\scriptscriptstyle(G_{n})}$ is
uniformly integrable. Then,

$\frac{|E(\mathscr{C}_{\rm
max})|}{n}\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\tfrac{1}{2}{\mathbb{E}}_{\mu}\Big{[}d_{o}\mathbbm{1}_{\\{|\mathscr{C}(o)|=\infty\\}}\Big{]}.$
(2.30)

###### Proof.

We now define, for $k\geq 1$ and $A\subseteq{\mathbb{N}}$ and with
$d_{v}^{\scriptscriptstyle(G_{n})}$ the degree of $v$ in $G_{n}$,

$Z_{\scriptscriptstyle A,\geq
k}=\sum_{v\in[n]}\mathbbm{1}_{\\{|\mathscr{C}(v)|\geq
k,d_{v}^{\scriptscriptstyle(G_{n})}\in A\\}}.$ (2.31)

Assume that $G_{n}$ converges locally in probability to $(G,o)\sim\mu$. Then,

$\frac{Z_{\scriptscriptstyle A,\geq
k}}{n}\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\mu(|\mathscr{C}(o)|\geq
k,d_{o}^{\scriptscriptstyle(G)}\in A).$ (2.32)

Since $|\mathscr{C}_{\rm max}|\geq k$ whp by Theorem 2.2, we thus obtain, for
every $A\subseteq{\mathbb{N}}$,

$\frac{1}{n}\sum_{a\in A}v_{a}(\mathscr{C}_{\rm
max})\leq\frac{Z_{\scriptscriptstyle A,\geq
k}}{n}\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\mu(|\mathscr{C}(o)|\geq
k,d_{o}^{\scriptscriptstyle(G)}\in A).$ (2.33)

Applying this to $A=\\{\ell\\}^{c}$, we obtain that, for all $\varepsilon>0$,

$\lim_{n\rightarrow\infty}{\mathbb{P}}\Big{(}\frac{1}{n}\Big{[}|\mathscr{C}_{\rm
max}|-v_{\ell}(\mathscr{C}_{\rm max})\Big{]}\leq\mu(|\mathscr{C}(o)|\geq
k,d_{o}^{\scriptscriptstyle(G)}\neq\ell)+\varepsilon/2\Big{)}=1.$ (2.34)

We argue by contradiction. Suppose that, for some $\ell$,

$\liminf_{n\rightarrow\infty}{\mathbb{P}}\Big{(}\frac{v_{\ell}(\mathscr{C}_{\rm
max})}{n}\leq\mu(|\mathscr{C}(o)|=\infty,d_{o}^{\scriptscriptstyle(G)}=\ell)-\varepsilon\Big{)}=\kappa>0.$
(2.35)

Then, along the subsequence $(n_{l})_{l\geq 1}$ that attains the liminf in
(2.35), with asymptotic probability $\kappa>0$, and using (2.34) and (2.35),

$\frac{|\mathscr{C}_{\rm max}|}{n}=\frac{1}{n}[|\mathscr{C}_{\rm
max}|-v_{\ell}(\mathscr{C}_{\rm max})]+\frac{v_{\ell}(\mathscr{C}_{\rm
max})}{n}\leq\mu(|\mathscr{C}(o)|=\infty)-\varepsilon/2,$ (2.36)

which contradicts Theorem 2.2. We conclude that (2.35) cannot hold, so that
(2.29) follows.

For (2.30), we note that

$|E(\mathscr{C}_{\rm max})|=\tfrac{1}{2}\sum_{\ell\geq 1}\ell
v_{\ell}(\mathscr{C}_{\rm max}).$ (2.37)

We divide by $n$ and split the sum over $\ell$ in
$\ell\in[K]=\\{1,\ldots,K\\}$ and $\ell>K$ as

$\frac{|E(\mathscr{C}_{\rm max})|}{n}=\frac{1}{2n}\sum_{\ell\in[K]}\ell
v_{\ell}(\mathscr{C}_{\rm max})+\frac{1}{2n}\sum_{\ell>K}\ell
v_{\ell}(\mathscr{C}_{\rm max}).$ (2.38)

For the first term in (2.38), by (2.29),

$\displaystyle\tfrac{1}{2n}\sum_{\ell\in[K]}\ell v_{\ell}(\mathscr{C}_{\rm
max})$
$\displaystyle\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\tfrac{1}{2}\sum_{\ell\in[K]}\mu(|\mathscr{C}(o)|=\infty,d_{o}^{\scriptscriptstyle(G)}=\ell)$
(2.39)
$\displaystyle=\tfrac{1}{2}{\mathbb{E}}_{\mu}\Big{[}d_{o}\mathbbm{1}_{\\{|\mathscr{C}(o)|=\infty,d_{o}^{\scriptscriptstyle(G)}\in[K]\\}}\Big{]}.$

For the second term in (2.38), we bound, with $n_{\ell}$ the number of
vertices in $G_{n}$ of degree $\ell$,

$\frac{1}{2n}\sum_{\ell>K}\ell v_{\ell}(\mathscr{C}_{\rm
max})\leq\frac{1}{2}\sum_{\ell>K}\ell\frac{n_{\ell}}{n}=\frac{1}{2}{\mathbb{E}}\big{[}d_{o_{n}}^{\scriptscriptstyle(G_{n})}\mathbbm{1}_{\\{d_{o_{n}}^{\scriptscriptstyle(G_{n})}>K\\}}\mid
G_{n}\big{]}.$ (2.40)

By uniform integrability of $(d_{o_{n}}^{\scriptscriptstyle(G_{n})})_{n\geq
1}$,

$\lim_{K\rightarrow\infty}\limsup_{n\rightarrow\infty}{\mathbb{E}}\big{[}d_{o_{n}}^{\scriptscriptstyle(G_{n})}\mathbbm{1}_{\\{d_{o_{n}}^{\scriptscriptstyle(G_{n})}>K\\}}\big{]}=0.$
(2.41)

As a result, by the Markov inequality and for every $\varepsilon>0$, there
exists a $K=K(\varepsilon)<\infty$ such that

${\mathbb{P}}\Big{(}{\mathbb{E}}\big{[}d_{o_{n}}^{\scriptscriptstyle(G_{n})}\mathbbm{1}_{\\{d_{o_{n}}^{\scriptscriptstyle(G_{n})}>K\\}}\mid
G_{n}\big{]}>\varepsilon\Big{)}\rightarrow 0.$ (2.42)

This completes the proof of (2.30). ∎

It is not hard to extend the above analysis to the local convergence in
probability of the giant, as well as its complement, as formulated in the
following theorem:

######  Theorem 2.5 (Local limit of the giant).

Under the assumptions of Theorem 2.2, when
$\zeta=\mu(|\mathscr{C}(o)|=\infty)>0$,

$\frac{1}{n}\sum_{v\in\mathscr{C}_{\rm
max}}\mathbbm{1}_{\\{B_{r}^{\scriptscriptstyle(G_{n})}(v)\simeq
H_{\star}\\}}\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\mu(|\mathscr{C}(o)|=\infty,B_{r}^{\scriptscriptstyle(G)}(o)\simeq
H_{\star}),$ (2.43)

and

$\frac{1}{n}\sum_{v\not\in\mathscr{C}_{\rm
max}}\mathbbm{1}_{\\{B_{r}^{\scriptscriptstyle(G_{n})}(v)\simeq
H_{\star}\\}}\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\mu(|\mathscr{C}(o)|<\infty,B_{r}^{\scriptscriptstyle(G)}(o)\simeq
H_{\star}).$ (2.44)

###### Proof.

The convergence in (2.44) follows from that in (2.43) combined with the fact
that, by assumption,

$\frac{1}{n}\sum_{v\in
V(G_{n})}\mathbbm{1}_{\\{B_{r}^{\scriptscriptstyle(G_{n})}(v)\simeq
H_{\star}\\}}\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\mu(B_{r}^{\scriptscriptstyle(G)}(o)\simeq
H_{\star}).$ (2.45)

The convergence in (2.43) can be proved as for Theorem 2.4, now using that

$\displaystyle\frac{1}{n}Z_{\scriptscriptstyle\mathscr{H}_{\star},\geq k}$
$\displaystyle\equiv\frac{1}{n}\sum_{v\in
V(G_{n})}\mathbbm{1}_{\\{|\mathscr{C}(v)|\geq
k,B_{r}^{\scriptscriptstyle(G_{n})}(v)\in\mathscr{H}_{\star}\\}}$ (2.46)
$\displaystyle\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\mu(|\mathscr{C}(o)|\geq
k,B_{r}^{\scriptscriptstyle(G)}(o)\in\mathscr{H}_{\star}),$

and, since $|\mathscr{C}_{\rm
max}|/n\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\zeta>0$
by Theorem 2.2,

$\frac{1}{n}\sum_{v\in\mathscr{C}_{\rm
max}}\mathbbm{1}_{\\{B_{r}^{\scriptscriptstyle(G_{n})}(v)\in\mathscr{H}_{\star}\\}}\leq
Z_{\scriptscriptstyle\mathscr{H}_{\star},\geq k}.$ (2.47)

We leave the details to the reader. ∎

###  2.4 The ‘giant is almost local’ condition revisited

The ‘giant is almost local’ condition (2.8) is sometimes not so convenient to
verify, and we now give an alternative form that is often easier to work with:

######  Lemma 2.6 (Condition (2.8) revisited).

Consider $(G_{n})_{n\geq 1}$ under the conditions of Theorem 2.2. Assume
further that there exists $r=r_{k}\rightarrow\infty$ such that

$\mu(|\mathscr{C}(o)|\geq k,|\partial
B^{\scriptscriptstyle(G)}_{r}(o)|<r_{k})\rightarrow
0,\qquad\mu(|\mathscr{C}(o)|<k,|\partial B_{r}^{\scriptscriptstyle(G)}(o)|\geq
r_{k})\rightarrow 0.$ (2.48)

Then, the ‘giant is almost local’ condition in (2.8) holds when

$\lim_{r\rightarrow\infty}\limsup_{n\rightarrow\infty}\frac{1}{n^{2}}{\mathbb{E}}\Big{[}\\#\big{\\{}(x,y)\in
V(G_{n})\colon|\partial B^{\scriptscriptstyle(G_{n})}_{r}(x)|,|\partial
B^{\scriptscriptstyle(G_{n})}_{r}(y)|\geq r,x\longleftrightarrow{/}\hskip
7.74998pty\big{\\}}\Big{]}=0.$ (2.49)

###### Proof.

Denote

$\displaystyle P_{k}$ $\displaystyle=\\#\big{\\{}(x,y)\in
V(G_{n})\colon|\mathscr{C}(x)|,|\mathscr{C}(y)|\geq
k,x\longleftrightarrow{/}\hskip 7.74998pty\big{\\}},$ (2.50) $\displaystyle
P_{r}^{\scriptscriptstyle(2)}$ $\displaystyle=\\#\big{\\{}(x,y)\in
V(G_{n})\colon|\partial B_{r}^{\scriptscriptstyle(G_{n})}(x)|,|\partial
B_{r}^{\scriptscriptstyle(G_{n})}(y)|\geq r,x\longleftrightarrow{/}\hskip
7.74998pty\big{\\}}.$ (2.51)

Then,

$|P_{r}-P_{k}^{\scriptscriptstyle(2)}|\leq
2n\big{[}Z_{\scriptscriptstyle<r,\geq k}+Z_{\scriptscriptstyle\geq
r,<k}\big{]},$ (2.52)

where

$\displaystyle Z_{\scriptscriptstyle<r,\geq k}$ $\displaystyle=\sum_{v\in
V(G_{n})}\mathbbm{1}_{\\{|\partial
B_{r}^{\scriptscriptstyle(G_{n})}(v)|<r,|\mathscr{C}(v)|\geq k\\}},$ (2.53)
$\displaystyle Z_{\scriptscriptstyle\geq r,<k}$ $\displaystyle=\sum_{v\in
V(G_{n})}\mathbbm{1}_{\\{|\partial B_{r}^{\scriptscriptstyle(G_{n})}(v)|\geq
r,|\mathscr{C}(v)|<k\\}}.$ (2.54)

Therefore, by local convergence in probability,

$\displaystyle\frac{1}{n^{2}}|P_{k}-P_{r}^{\scriptscriptstyle(2)}|$
$\displaystyle\leq\frac{2}{n}\big{[}Z_{\scriptscriptstyle<r,\geq
k}+Z_{\scriptscriptstyle\geq r,<k}\big{]}$
$\displaystyle\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}2\mu(|\mathscr{C}(o)|\geq
k,|\partial
B_{r}^{\scriptscriptstyle(G)}(o)|<r)+2\mu(|\mathscr{C}(o)|<k,|\partial
B_{r}^{\scriptscriptstyle(G)}(o)|\geq r).$ (2.55)

Take $r=r_{k}$ as in (2.48). Then, the right hand side vanishes, so that, by
Dominated Convergence, also

$\lim_{k\rightarrow\infty}\limsup_{n\rightarrow\infty}\frac{1}{n^{2}}{\mathbb{E}}\big{[}|P_{k}-P_{r_{k}}^{\scriptscriptstyle(2)}|\big{]}=0.$
(2.56)

We arrive at

$\lim_{k\rightarrow\infty}\limsup_{n\rightarrow\infty}\frac{1}{n^{2}}{\mathbb{E}}\big{[}P_{k}\big{]}\leq\lim_{k\rightarrow\infty}\limsup_{n\rightarrow\infty}\frac{1}{n^{2}}{\mathbb{E}}\big{[}P_{r_{k}}^{\scriptscriptstyle(2)}\big{]}=0,$
(2.57)

by (2.49) and since $r_{k}\rightarrow\infty$ when $k\rightarrow\infty$. ∎

The assumption in (2.49) is more convenient than (2.8), as it requires that
most pairs of vertices who have many vertices at distance $r$ are connected to
one another. In many random graphs, there is some weak dependence between
$B_{r}^{\scriptscriptstyle(G_{n})}(x)$ and the graph outside of it. This is
more complicated when dealing with $|\mathscr{C}(x)|\geq k$.

The assumption in (2.48) on the local limit is often easily verified. For
example, for the unimodular branching processes with bounded offspring, to
which we will apply it below, we can take $r_{k}=k$ and use that on the event
of survival

$\nu^{-r}|\partial B_{r}^{\scriptscriptstyle(G)}(o)|\stackrel{{\scriptstyle
a.s.}}{{\longrightarrow}}M,$ (2.58)

where $(G,o)$ denotes the unimodular branching process with bounded offspring,
and where $M>0$ on the event of survival by [38, Theorem 3.9]. Therefore,
$\mu(|\mathscr{C}(o)|\geq k,|\partial
B_{k}^{\scriptscriptstyle(G)}(o)|<k)\rightarrow 0$ as $k\rightarrow\infty$.
Further, $\mu(|\mathscr{C}(o)|<k,|\partial
B_{k}^{\scriptscriptstyle(G)}(o)|\geq k)=0$ trivially. However, there are
examples where (2.48) fails, and then also the equivalence of (2.8) and (2.49)
may be false.

##  3 Application to the configuration model

In this section, we apply our results to the configuration model. An
application to Erdős-Rényi random graph is provided in [39, Chapter 2]. The
giant in the configuration model has a long history. It was first investigated
by Molloy and Reed [55, 56] in a setting where the degrees are general. The
problem was revisited by Janson and Luczak [49] and Bollobás and Riordan [20],
amongst others. This section is organised as follows. We start by introducing
the model and stating our results in Section 3.1. We then prove the main
result in Section 3.2, and state a consequence on typical graph distances,
that is proved along the way, in Section 3.3. Some remaining technical
ingredients are deferred to Appendix A.

###  3.1 Model definition and results

The configuration model is invented by Bollobás [17] in the context of random
regular graphs. It has the nice property that, when conditioned on being
simple, it yields a uniform random graph with the prescribed degree
distribution. We refer to [38, Chapter 7] for a thorough introduction to the
model.

#### Model definition and assumptions

Fix an integer $n$ that will denote the number of vertices in the random
graph. Consider a sequence of degrees $\boldsymbol{d}=(d_{i})_{i\in[n]}$.
Without loss of generality, we assume throughout this paper that $d_{j}\geq 1$
for all $j\in[n]$, since when $d_{j}=0$, vertex $j$ is isolated and can be
removed from the graph. We assume that the total degree

$\ell_{n}=\sum_{j\in[n]}d_{j}$ (3.1)

is even.

To construct the multigraph where vertex $j$ has degree $d_{j}$ for all
$j\in[n]$, we have $n$ separate vertices and incident to vertex $j$, we have
$d_{j}$ half-edges. We number the half-edges in an arbitrary order from $1$ to
$\ell_{n}$, and start by randomly connecting the first half-edge with one of
the $\ell_{n}-1$ remaining half-edges. Once paired, two half-edges form a
single edge of the multigraph, and the half-edges are removed from the list of
half-edges that need to be paired. We continue the procedure of randomly
choosing and pairing the half-edges until all half-edges are connected, and
call the resulting graph the configuration model with degree sequence
$\boldsymbol{d}$, abbreviated as ${\rm CM}_{n}(\boldsymbol{d})$. A careful
reader may worry about the order in which the half-edges are being paired. In
fact, this ordering turns out to be irrelevant since the random pairing of
half-edges is completely exchangeable. It can even be done in a random
fashion, which will be useful when investigating neighborhoods in the
configuration model. See e.g., [38, Definition 7.5 and Lemma 7.6] for more
details on this exchangeability.

We denote the degree of a uniformly chosen vertex $o$ in $[n]$ by
$D_{n}=d_{o}$. The random variable $D_{n}$ has distribution function $F_{n}$
given by

$F_{n}(x)=\frac{1}{n}\sum_{j\in[n]}\mathbbm{1}_{\\{d_{j}\leq x\\}},$ (3.2)

which is the empirical distribution of the degrees. Equivalently,
${\mathbb{P}}(D_{n}=k)=n_{k}/n$, where $n_{k}$ denotes the number of vertices
of degree $k$. We assume that the vertex degrees satisfy the following
_regularity conditions:_

######  Condition 3.1 (Regularity conditions for vertex degrees).

(a) Weak convergence of vertex weight. There exists a distribution function
$F$ such that, as $n\rightarrow\infty$,

$D_{n}\stackrel{{\scriptstyle d}}{{\longrightarrow}}D,$ (3.3)

where $D_{n}$ and $D$ have distribution functions $F_{n}$ and $F$,
respectively. Further, we assume that $F(0)=0$, i.e., ${\mathbb{P}}(D\geq
1)=1$.
(b) Convergence of average vertex degrees. As $n\rightarrow\infty$,

${\mathbb{E}}[D_{n}]\rightarrow{\mathbb{E}}[D]<\infty,$ (3.4)

where $D_{n}$ and $D$ have distribution functions $F_{n}$ and $F$ from part
(a), respectively.

While Conditions 3.1(a)-(b) may appear to be quite strong, in fact, they are
quite close to assuming uniform integrability of $(D_{n})_{n\geq 1}$. Indeed,
when $(D_{n})_{n\geq 1}$ is uniformly integrable, then there is a subsequence
along which $D_{n}$ converges in distribution as in Condition 3.1(a), and
along this subsequence also Condition 3.1(b) holds. We can then apply our
results along this subsequence.

#### The giant in the configuration model

We now come to our result on the connected components in the configuration
model ${\rm CM}_{n}(\boldsymbol{d})$, where the degrees
$\boldsymbol{d}=(d_{i})_{i\in[n]}$ satisfy Conditions 3.1(a)-(b). For a graph
$G$, we write $v_{k}(G)$ for the number of vertices of degree $k$ in $G$, and
$|E(G)|$ for the number of edges. The main result concerning the size and
structure of the largest connected components of ${\rm
CM}_{n}(\boldsymbol{d})$ is the following:

######  Theorem 3.2 (Phase transition in ${\rm CM}_{n}(\boldsymbol{d})$).

Suppose that Conditions 3.1(a)-(b) hold and consider the random graph ${\rm
CM}_{n}(\boldsymbol{d})$, letting $n\rightarrow\infty$. Assume that
$p_{2}={\mathbb{P}}(D=2)<1$. Let $\mathscr{C}_{\rm max}$ and
$\mathscr{C}_{\scriptscriptstyle(2)}$ be the largest and second largest
components of ${\rm CM}_{n}(\boldsymbol{d})$ (breaking ties arbitrarily).

  1. (a)

If $\nu={\mathbb{E}}[D(D-1)]/{\mathbb{E}}[D]>1$, then there exist
$\xi\in[0,1),\zeta\in(0,1]$ such that

$\displaystyle|\mathscr{C}_{\rm max}|/n$
$\displaystyle\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}$
$\displaystyle\zeta\text{,}$ $\displaystyle v_{k}(\mathscr{C}_{\rm max})/n$
$\displaystyle\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}$
$\displaystyle p_{k}(1-\xi^{k})\quad\text{ for every }k\geq 0\text{,}$
$\displaystyle|E(\mathscr{C}_{\rm max})|/n$
$\displaystyle\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}$
$\displaystyle\tfrac{1}{2}{\mathbb{E}}[D](1-\xi^{2}).$

while
$|\mathscr{C}_{\scriptscriptstyle(2)}|/n\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}0$
and
$|E(\mathscr{C}_{\scriptscriptstyle(2)})|/n\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}0$.

  2. (b)

If $\nu={\mathbb{E}}[D(D-1)]/{\mathbb{E}}[D]\leq 1$, then $|\mathscr{C}_{\rm
max}|/n\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}0$
and $|E(\mathscr{C}_{\rm
max})|/n\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}0$.

We prove Theorem 3.2 in Section 3.2 below. We now remark upon the result and
on the conditions arising in it.

#### Local structure of $\mathscr{C}_{\rm max}$

Theorem 3.2 is the main result for ${\rm CM}_{n}(\boldsymbol{d})$ proved in
[49]. The result in [20] only concerns $|\mathscr{C}_{\rm max}|/n$. Related
results are in [55, 56, 59]. Many of these proofs use an exploration of the
connected components in the graph, albeit that the precise explorations can be
performed in rather different ways in that in [55, 56] it is in discrete time,
while in [49] it is in continuous time. Further, [20] use concentration
inequalities combined with a sprinkling argument. The present approach is,
even in this light, novel, since it also allows one to study the local
structure of the giant and non-giant, as stated in Theorem 2.5. It is not
clear whether the proof in [49], for example, can be easily extended to
include this extra information.

#### Local convergence of configuration models

The fact that the configuration model converges locally in probability is
well-established, and is the starting point for the proof of Theorem 3.2 using
Theorems 2.2 and 2.4. Dembo and Montanari [27] crucially rely on it in order
to identify the limiting pressure for the Ising model on the configuration
model. Many alternative proofs exist. We use some of the ingredients in [39,
Proof of Theorem 4.1], since these are helpful in the proof of Theorem 3.2 as
well. We also refer to the lecture notes by Bordenave [22] for a nice
exposition of local convergence proofs for the configuration model. Further,
Bordenave and Caputo [23] prove that the neighborhoods in the configuration
model satisfy a large deviation principle at speed $n$ in the context where
the degrees of the configuration model are bounded.

Let us now describe the local limit of ${\rm CM}_{n}(\boldsymbol{d})$ subject
to Conditions 3.1(a)-(b). The root has offspring distribution $(p_{k})_{k\geq
1}$ where $p_{k}={\mathbb{P}}(D=k)$ and $D$ is from Condition 3.1(a), while
all other individuals in the tree have offspring distribution
$(p_{k}^{\star})_{k\geq 0}$ given by

$p_{k}^{\star}=\frac{k+1}{{\mathbb{E}}[D]}{\mathbb{P}}(D=k+1).$ (3.5)

The distribution $(p_{k}^{\star})_{k\geq 0}$ has the interpretation of the
forward degree of a uniform edge. The above branching process is a so-called
unimodular branching process (recall [2]) with root offspring distribution
$(p_{k})_{k\geq 1}$. We refer to Appendix A.1 for more details on local
convergence of ${\rm CM}_{n}(\boldsymbol{d})$.

Having identified the local limit of ${\rm CM}_{n}(\boldsymbol{d})$, to prove
Theorem 3.2, we are left to prove the ‘giant component is almost local’
condition in (2.8), which we will do in the form of (2.49). We do this in the
next section.

#### Reformulation in terms of branching processes

We next interpret the results in Theorem 3.2 in terms of our unimodular
branching processes. In terms of this, $\xi$ is the extinction probability of
a branching process with offspring distribution $(p_{k}^{\star})_{k\geq 0}$,
and $\zeta$ as the survival probability of the unimodular branching process
with root offspring distribution $(p_{k})_{k\geq 1}$. Thus, $\zeta$ satisfies

$\zeta=\sum_{k\geq 1}p_{k}(1-\xi^{k}),$ (3.6)

with $\xi$ the smallest solution to

$\xi=\sum_{k\geq 0}p_{k}^{\star}\xi^{k}.$ (3.7)

Clearly, $\xi=1$ precisely when $\nu\leq 1$, where

$\nu=\sum_{k\geq 0}kp_{k}^{\star}=\frac{1}{{\mathbb{E}}[D]}\sum_{k\geq
0}k(k+1)p_{k+1}={\mathbb{E}}[D(D-1)]/{\mathbb{E}}[D],$ (3.8)

by (3.5). This explains the condition on $\nu$ in Theorem 3.2(a). Further, to
understand the asymptotics of $v_{k}(\mathscr{C}_{\rm max})$, we note that
there are $n_{k}\approx np_{k}$ vertices with degree $k$. Each of the $k$
direct neighbors of a vertex of degree $k$ survives with probability close to
$1-\xi$, so that the probability that at least one of them survives is close
to $1-\xi^{k}$. When one of the neighbors of the vertex of degree $k$
survives, the vertex itself is part of the giant component, which explains why
$v_{k}(\mathscr{C}_{\rm
max})/n\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}p_{k}(1-\xi^{k})$.
Finally, an edge consists of two half-edges, and an edge is part of the giant
component precisely when one of the vertices incident to it is, which occurs
with asymptotic probability $1-\xi^{2}$. There are in total
$\ell_{n}/2=n{\mathbb{E}}[D_{n}]/2\approx n{\mathbb{E}}[D]/2$ edges, which
explains why $|E(\mathscr{C}_{\rm
max})|/n\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\frac{1}{2}{\mathbb{E}}[D](1-\xi^{2})$.
Therefore, all results in Theorem 3.2 have a simple explanation in terms of
the branching process approximation of the connected component for ${\rm
CM}_{n}(\boldsymbol{d})$ of a uniform vertex in $[n]$.

#### The condition ${\mathbb{P}}(D=2)=p_{2}<1$

The case $p_{2}=1$, for which $\nu=1$, is quite exceptional. We give three
examples showing that then quite different behaviors are possible, see [39,
Section 4.2] for more details. Our first example is when $d_{i}=2$ for all
$i\in[n]$, so we are studying a random 2-regular graph. In this case, the
components are cycles and the distribution of cycle lengths in ${\rm
CM}_{n}(\boldsymbol{d})$ is given by the Ewen’s sampling formula ESF(1/2), see
e.g. [8]. This implies that $|\mathscr{C}_{\rm max}|/n$ converges in
distribution to a non-degenerate distribution on $[0,1]$ and not to any
constant [8, Lemma 5.7]. Moreover, the same is true for
$|\mathscr{C}_{\scriptscriptstyle(2)}|/n$ (and for
$|\mathscr{C}_{\scriptscriptstyle(3)}|/n$,…), so in this case there are
several large components. Our second example with $p_{2}=1$ is obtained by
letting $n_{1}\rightarrow\infty$ be such that $n_{1}/n\rightarrow 0$, and
$n_{2}=n-n_{1}$. In this case, components can either be cycles, or strings of
vertices with degree 2 terminated with two vertices with degree 1, for which
$|\mathscr{C}_{\rm max}|=o_{\scriptscriptstyle{\mathbb{P}}}(n)$. Our third
example with $p_{2}=1$ is obtained by instead letting $n_{4}\rightarrow\infty$
such that $n_{4}/n\rightarrow 0$, and $n_{2}=n-n_{4}$, in $|\mathscr{C}_{\rm
max}|=n-o_{\scriptscriptstyle{\mathbb{P}}}(n)$. We conclude that the case
where $p_{2}={\mathbb{P}}(D=2)=1$ is quite sensitive to the precise properties
of the degree structure that are not captured by the limiting distribution
$(p_{k})_{k\geq 1}$ only. In the sequel, we thus ignore the case where
$p_{2}=1$.

###  3.2 The ‘giant component is almost local’ proof

In this section, we prove Theorem 3.2 using the ‘giant is almost local’
results in Theorems 2.2 and 2.4. We start by setting the stage.

#### Setting the stage for the proof of Theorem 3.2

Theorem 3.2(b) follows directly from Corollary 2.1 combined with the local
convergence in probability discussed below Theorem 3.2 and the fact that, for
$\nu\leq 1$, the unimodular Galton-Watson tree with root offspring
distribution $(p_{k})_{k\geq 0}$ given by $p_{k}={\mathbb{P}}(D=k)$ dies out.

Theorem 3.2(a) follows from Theorem 2.4, together with the facts that, for the
unimodular Galton-Watson tree with root offspring distribution $(p_{k})_{k\geq
0}$ given by $p_{k}={\mathbb{P}}(D=k)$,

$\mu(|\mathscr{C}(o)|=\infty,d_{o}=\ell)=p_{k}(1-\xi^{k}),$ (3.9)

and

${\mathbb{E}}_{\mu}\Big{[}d_{o}\mathbbm{1}_{\\{|\mathscr{C}(o)|=\infty\\}}\Big{]}={\mathbb{E}}[D](1-\xi^{2}).$
(3.10)

Thus, it suffices to check the assumptions to Theorem 2.4. The uniform
integrability of $D_{n}$ follows from Condition 3.1(a)-(b). For the conditions
in Theorem 2.2, the local convergence in probability is discussed below
Theorem 3.2 , so we are left to proving the crucial hypothesis in (2.8), which
the remainder of the proof will do.

Before turning to the proof of (2.8), we apply the degree-truncation technique
from Theorem A.1 with $b$ large, to which we refer for details. By Condition
3.1(a)-(b), we can choose $b$ so large that

${\mathbb{P}}(D_{n}^{\star}>b)=\frac{1}{\ell_{n}}\sum_{v\in[n]}d_{v}\mathbbm{1}_{\\{d_{v}>b\\}}\leq\frac{\varepsilon
n}{\ell_{n}}.$ (3.11)

This implies that ${\rm CM}_{n^{\prime}}(\boldsymbol{d}^{\prime})$ has at most
$(1+\varepsilon)n$ vertices, and the at most $\varepsilon n$ exploded vertices
all have degree 1, while the vertices in $[n]$ have degree $d_{v}^{\prime}\leq
b$. As a result, it suffices to prove Theorem 3.2(b) for ${\rm
CM}_{n^{\prime}}(\boldsymbol{d}^{\prime})$ instead. As a result, in the
remainder of this proof, we will assume that $d_{\mathrm{max}}^{\prime}\leq b$
is uniformly bounded. We will thus apply Theorem 2.4 to ${\rm
CM}_{n^{\prime}}(\boldsymbol{d}^{\prime})$. We denote its parameters as
$(p_{k}^{\prime})_{k\geq 1},\xi^{\prime}$ and $\zeta^{\prime}$, respectively,
and note that, for $\varepsilon$ as in (3.11), when $\varepsilon\searrow 0$,

$p_{k}^{\prime}\rightarrow
p_{k},\qquad\xi^{\prime}\rightarrow\xi,\qquad\zeta^{\prime}\rightarrow\zeta,$
(3.12)

so that it suffices to prove Theorem 2.4 for ${\rm
CM}_{n^{\prime}}(\boldsymbol{d}^{\prime})$. Thus, from now on, we work with
${\rm CM}_{n^{\prime}}(\boldsymbol{d}^{\prime})$, and we let $G_{n}={\rm
CM}_{n^{\prime}}(\boldsymbol{d}^{\prime})$.

To start with our proof of (2.8), applied to ${\rm
CM}_{n^{\prime}}(\boldsymbol{d}^{\prime})$, we first use the alternative
formulation from Lemma 2.6, and note that (2.48) holds for for the unimodular
Galton-Watson tree with root offspring distribution $(p_{k})_{k\geq 0}$ given
by $p_{k}={\mathbb{P}}(D=k)$. Then, note that, with $o_{1},o_{2}\in[n]$ chosen
independently and uniformly at random,

$\displaystyle\frac{1}{n^{2}}{\mathbb{E}}\Big{[}\\#\big{\\{}(x,y)\in
V(G_{n})\colon|\partial B_{r}^{\scriptscriptstyle(G_{n})}(x)|,|\partial
B_{r}^{\scriptscriptstyle(G_{n})}(y)|\geq r,x\longleftrightarrow{/}\hskip
7.74998pty\big{\\}}\Big{]}$ (3.13) $\displaystyle\qquad={\mathbb{P}}(|\partial
B_{r}^{\scriptscriptstyle(G_{n})}(o_{1})|,|\partial
B_{r}^{\scriptscriptstyle(G_{n})}(o_{2})|\geq
r,o_{1}\longleftrightarrow{/}\hskip 7.74998pto_{2}).$

Thus, our main aim is to show that

$\lim_{r\rightarrow\infty}\limsup_{n\rightarrow\infty}{\mathbb{P}}(|\partial
B_{r}^{\scriptscriptstyle(G_{n})}(o_{1})|,|\partial
B_{r}^{\scriptscriptstyle(G_{n})}(o_{2})|\geq
r,o_{1}\longleftrightarrow{/}\hskip 7.74998pto_{2})=0.$ (3.14)

This is what we will focus on from now on.

#### Coupling to $n$-dependent branching process

We next apply the sharp coupling result stated in Lemma A.2 in Appendix A.3,
in particular using the two extensions in Remark A.3. See Appendix A.3 for
details.

Take an arbitrary $\underline{m}_{n}=o(\sqrt{n})$, then Remark A.3 shows that
whp we can perfectly couple
$(B_{k}^{\scriptscriptstyle(G_{n})}(o_{1}))_{k\leq\underline{k}_{n}}$, where

$\underline{k}_{n}=\inf\big{\\{}k\colon|B_{k}^{\scriptscriptstyle(G_{n})}(o_{1})|\geq\underline{m}_{n}\big{\\}},$
(3.15)

to a unimodular branching processes $({\sf
BP}_{k}^{\scriptscriptstyle(1)})_{k\leq\underline{k}_{n}}$ with root offspring
distribution $({\mathbb{P}}(D_{n}=k))_{k\geq 1}$.

Since all degree are bounded,
$|B_{\underline{k}_{n}}^{\scriptscriptstyle(G_{n})}(o_{1})|\leq(1+b)\underline{m}_{n}=\Theta(\underline{m}_{n})$.
Let $\mathcal{C}_{n}(1)$ denote the event that this perfect coupling happens,
so that

$\mathcal{C}_{n}(1)=\big{\\{}(|\partial
B_{k}^{\scriptscriptstyle(G_{n})}(o_{1})|)_{k\leq\underline{k}_{n}}=(|{\sf
BP}_{k}^{\scriptscriptstyle(1)}|)_{k\leq\underline{k}_{n}}\big{\\}},\quad\text{and}\quad{\mathbb{P}}(\mathcal{C}_{n}(1))=1-o(1).$
(3.16)

Here $|{\sf BP}_{k}^{\scriptscriptstyle(1)}$ is the size of the $k$th
generation in our $n$-dependent branching process.

We extend the above coupling to also deal with vertex $o_{2}$, for which we
explore a little further. For this, we start by defining the necessary
notation. Let

$\bar{k}_{n}=\inf\big{\\{}k\colon|B_{k}^{\scriptscriptstyle(G_{n})}(o_{2})|\geq\bar{m}_{n}\big{\\}},$
(3.17)

and, again since all degrees are bounded,
$|B_{\bar{k}_{n}}^{\scriptscriptstyle(G_{n})}(o_{2})|\leq(1+b)\bar{m}_{n}=\Theta(\bar{m}_{n})$.
Further, for $\delta>0$, we let

$\mathcal{C}_{n}(2)=\big{\\{}\big{|}|\partial
B_{k}^{\scriptscriptstyle(G_{n})}(o_{2})|-|{\sf
BP}_{k}^{\scriptscriptstyle(2)}|\big{|}\leq(\bar{m}_{n}^{2}/\ell_{n})^{1+\delta}~{}\forall
k\in[\bar{k}_{n}]\big{\\}}.$ (3.18)

Here $({\sf BP}_{k}^{\scriptscriptstyle(2)})_{k\geq 0}$ is again an
$n$-dependent unimodular branching process independent of $({\sf
BP}_{k}^{\scriptscriptstyle(1)})_{k\geq 0}$. With
$\underline{m}_{n}=o(\sqrt{n})$, we will later pick $\bar{m}_{n}$ such that
$\underline{m}_{n}\bar{m}_{n}\gg n$ to reach our conclusion. The following
lemma shows that also $\mathcal{C}_{n}(2)$ occurs whp:

######  Lemma 3.3 (Coupling beyond Lemma A.2).

Fix ${\rm CM}_{n^{\prime}}(\boldsymbol{d}^{\prime})$ and let
$\bar{m}_{n}^{2}/\ell_{n}\rightarrow\infty$. Then, for every $\delta>0$,

${\mathbb{P}}(\mathcal{C}_{n}(2))=1-o(1).$ (3.19)

For the proof, we refer to Appendix A.3.

We now define the successful coupling event $\mathcal{C}_{n}$ to be

$\mathcal{C}_{n}=\mathcal{C}_{n}(1)\cap\mathcal{C}_{n}(2),\qquad\text{so
that}\qquad{\mathbb{P}}(\mathcal{C}_{n})=1-o(1).$ (3.20)

#### Branching process neighborhood growth

The previous step relates the graph exploration process to two independent
$n$-dependent unimodular branching process $({\sf
BP}_{k}^{\scriptscriptstyle(1)},{\sf BP}_{k}^{\scriptscriptstyle(2)})_{k\geq
1}$. In this step, we investigate the growth of these branching processes.
Denote $b_{0}^{\scriptscriptstyle(i)}=|{\sf BP}_{r}^{\scriptscriptstyle(i)}|$,
which we assume to be at least $r$ (and which is true on the event
$\mathcal{C}_{n}\cap\\{|\partial
B_{r}^{\scriptscriptstyle(G_{n})}(o_{1})|,|\partial
B_{r}^{\scriptscriptstyle(G_{n})}(o_{2})|\geq r\\}$).

Let

$\nu_{n}^{\prime}=\frac{1}{\ell_{n}}\sum_{v\in[n^{\prime}]}d_{v}^{\prime}(d_{v}^{\prime}-1),$
(3.21)

be the expected forward degree of a uniform half-edge in ${\rm
CM}_{n^{\prime}}(\boldsymbol{d}^{\prime})$, which equals the expected
offspring of the branching processes $({\sf
BP}_{k}^{\scriptscriptstyle(i)})_{k\geq 0}$. Define

$\mathcal{D}_{n}=\big{\\{}\underline{b}_{k}^{\scriptscriptstyle(i)}\leq|{\sf
BP}_{r+k}^{\scriptscriptstyle(i)}|\leq\bar{b}_{k}^{\scriptscriptstyle(i)}~{}\forall
i\in[2],~{}k\geq 1\big{\\}},$ (3.22)

where $(\underline{b}_{k}^{\scriptscriptstyle(i)})_{k\leq k_{n}-r}$ and
$(\bar{b}_{k}^{\scriptscriptstyle(i)})_{k\leq k_{n}-r}$ satisfy the recursions
$\underline{b}_{0}^{\scriptscriptstyle(i)}=\bar{b}_{0}^{\scriptscriptstyle(i)}=b_{0}^{\scriptscriptstyle(i)}$,
while, for some $\alpha\in(\tfrac{1}{2},1)$,

$\underline{b}_{k+1}^{\scriptscriptstyle(i)}=\nu_{n}^{\prime}\underline{b}_{k}^{\scriptscriptstyle(i)}-(\bar{b}_{k}^{\scriptscriptstyle(i)})^{\alpha},\qquad\bar{b}_{k+1}^{\scriptscriptstyle(i)}=\nu_{n}^{\prime}\bar{b}_{k}^{\scriptscriptstyle(i)}+(\bar{b}_{k}^{\scriptscriptstyle(i)})^{\alpha}.$
(3.23)

The following lemma investigates the asymptotics of
$(\underline{b}_{k}^{\scriptscriptstyle(i)})_{k\geq 1}$ and
$(\bar{b}_{k}^{\scriptscriptstyle(i)})_{k\geq 1}$:

######  Lemma 3.4 (Asymptotics of $\underline{b}_{k}^{\scriptscriptstyle(i)}$
and $\bar{b}_{k}^{\scriptscriptstyle(i)}$).

Assume that $\lim_{n\rightarrow\infty}\nu_{n}^{\prime}=\nu>1$, and assume that
$b_{0}^{\scriptscriptstyle(i)}={\sf BP}_{r}^{\scriptscriptstyle(i)}\geq r$.
Then, there exists an $A=A_{r}>1$ such that, for all $k\geq 1$,

$\bar{b}_{k}^{\scriptscriptstyle(i)}\leq
Ab_{0}^{\scriptscriptstyle(i)}(\nu_{n}^{\prime})^{k},\qquad\underline{b}_{k}^{\scriptscriptstyle(i)}\geq
b_{0}^{\scriptscriptstyle(i)}(\nu_{n}^{\prime})^{k}/A.$ (3.24)

###### Proof.

First, obviously, $\bar{b}_{k}^{\scriptscriptstyle(i)}\geq
b_{0}^{\scriptscriptstyle(i)}(\nu_{n}^{\prime})^{k}$. Thus,

$\displaystyle\bar{b}_{k+1}^{\scriptscriptstyle(i)}$
$\displaystyle=\nu_{n}^{\prime}\bar{b}_{k}^{\scriptscriptstyle(i)}+(\bar{b}_{k}^{\scriptscriptstyle(i)})^{\alpha}=\nu_{n}^{\prime}\bar{b}_{k}^{\scriptscriptstyle(i)}(1+(\bar{b}_{k}^{\scriptscriptstyle(i)})^{\alpha-1})$
(3.25)
$\displaystyle\leq\nu_{n}^{\prime}\bar{b}_{k}^{\scriptscriptstyle(i)}\big{(}1+r^{-(1-\alpha)}(\nu_{n}^{\prime})^{-(1-\alpha)k}\big{)},$

By iteration, this implies the upper bound with $A$ replaced by $\bar{A}_{r}$
given by

$\bar{A}_{r}=\prod_{k\geq
0}\big{(}1+r^{-(1-\alpha)}(\nu_{n}^{\prime})^{-(1-\alpha)k}\big{)}<\infty.$
(3.26)

For the lower bound, we use that
$\bar{b}_{k}^{\scriptscriptstyle(i)}\leq\bar{A}_{r}b_{0}^{\scriptscriptstyle(i)}(\nu_{n}^{\prime})^{k}$
to obtain

$\underline{b}_{k+1}^{\scriptscriptstyle(i)}\geq\nu_{n}^{\prime}\underline{b}_{k}^{\scriptscriptstyle(i)}-\bar{A}_{r}^{\alpha}(b_{0}^{\scriptscriptstyle(i)})^{\alpha}(\nu_{n}^{\prime})^{\alpha
k}.$ (3.27)

We now use induction to show that

$\underline{b}_{k}^{\scriptscriptstyle(i)}\geq
a_{k}b_{0}^{\scriptscriptstyle(i)}(\nu_{n}^{\prime})^{k},$ (3.28)

where $a_{0}=1$ and

$a_{k+1}=a_{k}-\bar{A}_{r}^{\alpha}r^{1-\alpha}(\nu_{n}^{\prime})^{(\alpha-1)k-1}.$
(3.29)

The initialization follows, since
$\underline{b}_{0}^{\scriptscriptstyle(i)}=b_{0}^{\scriptscriptstyle(i)}$ and
$a_{0}=1$. To advance the induction hypothesis, we substitute the induction
hypothesis to obtain that

$\displaystyle\underline{b}_{k+1}^{\scriptscriptstyle(i)}$ $\displaystyle\geq
a_{k}b_{0}^{\scriptscriptstyle(i)}(\nu_{n}^{\prime})^{k+1}-\bar{A}_{r}^{\alpha}(b_{0}^{\scriptscriptstyle(i)})^{\alpha}(\nu_{n}^{\prime})^{\alpha
k}$ (3.30)
$\displaystyle=b_{0}^{\scriptscriptstyle(i)}(\nu_{n}^{\prime})^{k+1}\big{(}a_{k}+\bar{A}_{r}^{\alpha}(b_{0}^{\scriptscriptstyle(i)})^{\alpha-1}(\nu_{n}^{\prime})^{(\alpha-1)k}\big{)}$
$\displaystyle\geq
b_{0}^{\scriptscriptstyle(i)}(\nu_{n}^{\prime})^{k+1}\big{(}a_{k}+\bar{A}_{r}^{\alpha}r^{\alpha-1}(\nu_{n}^{\prime})^{(\alpha-1)k-1}\big{)}=a_{k+1}b_{0}^{\scriptscriptstyle(i)}(\nu_{n}^{\prime})^{k+1},$

by (3.29). Finally, $a_{k}\searrow a\equiv 1/\underline{A}_{r},$ where
$\underline{A}_{r}<\infty$ for $r$ large enough, so that the claim follows
with $A=A_{r}=\max\\{\bar{A}_{r},\underline{A}_{r}\\}$. ∎

The following lemma shows that $\mathcal{D}_{n}$ occurs whp when first
$n\rightarrow\infty$ followed by $r\rightarrow\infty$:

######  Lemma 3.5 ($\mathcal{D}_{n}$ occurs whp).

Assume that $b_{0}^{\scriptscriptstyle(i)}=|{\sf
BP}_{r}^{\scriptscriptstyle(i)}|\geq r$. Then

$\lim_{r\rightarrow\infty}\limsup_{n\rightarrow\infty}{\mathbb{P}}(\mathcal{D}_{n})=1.$
(3.31)

###### Proof.

We will show that
$\lim_{r\rightarrow\infty}\limsup_{n\rightarrow\infty}{\mathbb{P}}(\mathcal{D}_{n}^{c})=0$.
We write

${\mathbb{P}}(\mathcal{D}_{n}^{c})\leq\sum_{k=1}^{\infty}{\mathbb{P}}(\mathcal{D}_{n,k}^{c}\cap\mathcal{D}_{n,k-1}),$
(3.32)

where

$\mathcal{D}_{n,k}=\big{\\{}\underline{b}_{k}^{\scriptscriptstyle(i)}\leq|{\sf
BP}_{r+k}^{\scriptscriptstyle(i)}|\leq\bar{b}_{k}^{\scriptscriptstyle(i)}~{}\forall
i\in[2]\big{\\}}.$ (3.33)

Note that, when $|{\sf
BP}_{r+k}^{\scriptscriptstyle(i)}|>\bar{b}_{k}^{\scriptscriptstyle(i)}$ and
$|{\sf
BP}_{r+k-1}^{\scriptscriptstyle(i)}|\leq\bar{b}_{k}^{\scriptscriptstyle(i)}$,

$|{\sf BP}_{r+k}^{\scriptscriptstyle(i)}|-\nu_{n}^{\prime}|{\sf
BP}_{r+k-1}^{\scriptscriptstyle(i)}|>\bar{b}_{k}^{\scriptscriptstyle(i)}-\nu_{n}^{\prime}\bar{b}_{k-1}^{\scriptscriptstyle(i)}=(\bar{b}_{k-1}^{\scriptscriptstyle(i)})^{\alpha},$
(3.34)

while, when $|{\sf
BP}_{r+k}^{\scriptscriptstyle(i)}|<\underline{b}_{k}^{\scriptscriptstyle(i)}$
and $|{\sf
BP}_{r+k-1}^{\scriptscriptstyle(i)}|\geq\underline{b}_{k}^{\scriptscriptstyle(i)}$,

$|{\sf BP}_{r+k}^{\scriptscriptstyle(i)}|-\nu_{n}^{\prime}|{\sf
BP}_{r+k-1}^{\scriptscriptstyle(i)}|<\underline{b}_{k}^{\scriptscriptstyle(i)}-\nu_{n}^{\prime}\underline{b}_{k-1}^{\scriptscriptstyle(i)}=(\bar{b}_{k-1}^{\scriptscriptstyle(i)})^{\alpha},$
(3.35)

Thus,

$\displaystyle\mathcal{D}_{n,k}^{c}\cap\mathcal{D}_{n,k-1}$ (3.36)
$\displaystyle\quad\subseteq\big{\\{}\big{|}|{\sf
BP}_{r+k}^{\scriptscriptstyle(1)}|-\nu_{n}^{\prime}|{\sf
BP}_{r+k-1}^{\scriptscriptstyle(1)}|\big{|}\geq(\bar{b}_{k-1}^{\scriptscriptstyle(1)})^{\alpha}\big{\\}}\cup\big{\\{}\big{|}|{\sf
BP}_{r+k}^{\scriptscriptstyle(2)}|-\nu_{n}^{\prime}|{\sf
BP}_{r+k-1}^{\scriptscriptstyle(2)}|\big{|}\geq(\bar{b}_{k-1}^{\scriptscriptstyle(2)})^{\alpha}\big{\\}}.$

By the Chebychev inequality, conditionally on $\mathcal{D}_{n,k-1}$,

$\displaystyle{\mathbb{P}}\big{(}\big{|}|{\sf
BP}_{r+k}^{\scriptscriptstyle(i)}|-\nu_{n}^{\prime}|{\sf
BP}_{r+k-1}^{\scriptscriptstyle(i)}|\big{|}\geq(\bar{b}_{k-1}^{\scriptscriptstyle(i)})^{\alpha}\mid\mathcal{D}_{n,k-1}\big{)}$
(3.37) $\displaystyle\qquad\leq\frac{\mathrm{Var}(|{\sf
BP}_{r+k}^{\scriptscriptstyle(i)}|\mid|{\sf
BP}_{r+k-1}^{\scriptscriptstyle(i)}|)}{(\bar{b}_{k-1}^{\scriptscriptstyle(i)})^{2\alpha}}\leq\frac{\sigma_{n}^{2}|{\sf
BP}_{r+k-1}^{\scriptscriptstyle(i)}|}{(\bar{b}_{k-1}^{\scriptscriptstyle(i)})^{2\alpha}}\leq\sigma_{n}^{2}(\bar{b}_{k-1}^{\scriptscriptstyle(i)})^{1-2\alpha},$

where $\sigma_{n}^{2}$ is the variance of the offspring distribution given by

$\sigma_{n}^{2}=\frac{1}{\ell_{n}}\sum_{v\in[n^{\prime}]}d_{v}^{\prime}(d_{v}^{\prime}-1)^{2}-(\nu_{n}^{\prime})^{2},$
(3.38)

which is uniformly bounded. Thus,

${\mathbb{P}}(\mathcal{D}_{n,k}^{c}\cap\mathcal{D}_{n,k-1})\leq\sigma_{n}^{2}(\bar{b}_{k-1}^{\scriptscriptstyle(i)})^{1-2\alpha},$
(3.39)

and we conclude that

${\mathbb{P}}(\mathcal{D}_{n}^{c})\leq\sigma_{n}^{2}\sum_{k=1}^{\infty}\big{(}(\bar{b}_{k-1}^{\scriptscriptstyle(1)})^{1-2\alpha}+(\bar{b}_{k-1}^{\scriptscriptstyle(2)})^{1-2\alpha}\big{)}.$
(3.40)

The claim now follows from Lemma 3.4 and the fact that $\sigma_{n}^{2}\leq
b(b-1)^{2}$ remains uniformly bounded. ∎

#### Completion of the proof

Recall (3.14). Let $\mathcal{G}_{n}=\mathcal{C}_{n}\cap\mathcal{D}_{n}$ be the
good event. By (3.20) and Lemma 3.5,

$\lim_{r\rightarrow\infty}\limsup_{n\rightarrow\infty}{\mathbb{P}}(|\partial
B_{r}^{\scriptscriptstyle(G_{n})}(o_{1})|,|\partial
B_{r}^{\scriptscriptstyle(G_{n})}(o_{2})|\geq
r,o_{1}\longleftrightarrow{/}\hskip 7.74998pto_{2};\mathcal{G}_{n}^{c})=0,$
(3.41)

so that it suffices to investigate ${\mathbb{P}}(|\partial
B_{r}^{\scriptscriptstyle(G_{n})}(o_{1})|,|\partial
B_{r}^{\scriptscriptstyle(G_{n})}(o_{2})|\geq
r,o_{1}\longleftrightarrow{/}\hskip 7.74998pto_{2};\mathcal{G}_{n})$. On
$\mathcal{G}_{n}$ (recall (3.18)),

$|\partial B_{\bar{k}_{n}}^{\scriptscriptstyle(G_{n})}(o_{2})|-|{\sf
BP}_{\bar{k}_{n}}^{\scriptscriptstyle(2)}|\geq-(\bar{m}_{n}^{2}/\ell_{n})^{1+\delta}.$
(3.42)

Further, on $\mathcal{G}_{n}$ (recall (3.16)),

$|\partial B_{\underline{k}_{n}}^{\scriptscriptstyle(G_{n})}(o_{1})|-|{\sf
BP}_{\underline{k}_{n}}^{\scriptscriptstyle(1)}|=0.$ (3.43)

There are two possibilities: either
$B_{\underline{k}_{n}}^{\scriptscriptstyle(G_{n})}(o_{1})\cap
B_{\bar{k}_{n}}^{\scriptscriptstyle(G_{n})}(o_{2})\neq\varnothing$, in which
case $o_{1}\longleftrightarrow o_{2}$, so this does not contribute to
${\mathbb{P}}(|\partial B_{r}^{\scriptscriptstyle(G_{n})}(o_{1})|,|\partial
B_{r}^{\scriptscriptstyle(G_{n})}(o_{2})|\geq
r,o_{1}\longleftrightarrow{/}\hskip 7.74998pto_{2};\mathcal{G}_{n})$; or
$B_{\underline{k}_{n}}^{\scriptscriptstyle(G_{n})}(o_{1})\cap
B_{\bar{k}_{n}}^{\scriptscriptstyle(G_{n})}(o_{2})=\varnothing$. In this case,
by Lemma 3.4 and when $\bar{m}_{n}^{2}/\ell_{n}\rightarrow\infty$ sufficiently
slowly, $|\partial
B_{\underline{k}_{n}}^{\scriptscriptstyle(G_{n})}(o_{1})|=\Theta(\underline{m}_{n})$
and $|\partial
B_{\bar{k}_{n}}^{\scriptscriptstyle(G_{n})}(o_{2})|=\Theta(\bar{m}_{n})$.
Thus, the probability that $\partial
B_{\underline{k}_{n}}^{\scriptscriptstyle(G_{n})}(o_{1})$ is not directly
connected to $\partial B_{\bar{k}_{n}}^{\scriptscriptstyle(G_{n})}(o_{2})$
vanishes when $\underline{m}_{n}\bar{m}_{n}\gg n$. As a result, as
$n\rightarrow\infty$,

${\mathbb{P}}(|\partial B_{r}^{\scriptscriptstyle(G_{n})}(o_{1})|,|\partial
B_{r}^{\scriptscriptstyle(G_{n})}(o_{2})|\geq
r,o_{1}\longleftrightarrow{/}\hskip 7.74998pto_{2};\mathcal{G}_{n})=o(1),$
(3.44)

as required. ∎

###  3.3 Small-world nature of configuration model

In this section, we use the above proof to study the typical distances in
${\rm CM}_{n}(\boldsymbol{d})$. Such distances have attracted considerable
attention, see e.g., [29, 30, 40, 41, 42]. Here, we partially reprove a result
from [40]:

######  Theorem 3.6 (Typical distances in ${\rm CM}_{n}(\boldsymbol{d})$ for
finite-variance degrees).

Consider the configuration model ${\rm CM}_{n}(\boldsymbol{d})$ subject to
Conditions 3.1(a)-(b) and where
${\mathbb{E}}[D_{n}^{2}]\rightarrow{\mathbb{E}}[D^{2}]<\infty$ with

$\nu\in(1,\infty).$ (3.45)

Then, conditionally on ${\rm dist}_{\scriptscriptstyle{\rm
CM}_{n}(\boldsymbol{d})}(o_{1},o_{2})<\infty$,

${\rm dist}_{\scriptscriptstyle{\rm
CM}_{n}(\boldsymbol{d})}(o_{1},o_{2})/\log{n}\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}1/\log{\nu}.$
(3.46)

###### Proof.

The proof in (3.41)–(3.44) also shows that, whp as first $n\rightarrow\infty$
followed by $r\rightarrow\infty$,

${\rm dist}_{\scriptscriptstyle{\rm
CM}_{n^{\prime}}(\boldsymbol{d}^{\prime})}(o_{1},o_{2})\leq\underline{k}_{n}+\bar{k}_{n}+1=\frac{\log{n}}{\log{\nu_{n}^{\prime}}}(1+o_{\scriptscriptstyle{\mathbb{P}}}(1)).$
(3.47)

Indeed, Lemma 3.4 implies that
$\underline{k}_{n}=(1+o_{\scriptscriptstyle{\mathbb{P}}}(1))\log{\underline{m}_{n}}/\log{\nu_{n}^{\prime}}$
and
$\bar{k}_{n}=(1+o_{\scriptscriptstyle{\mathbb{P}}}(1))\log{\bar{m}_{n}}/{\log{\nu_{n}^{\prime}}}$
on the event $\mathcal{G}_{n}=\mathcal{C}_{n}\cap\mathcal{D}_{n}$, so that

$\underline{k}_{n}+\bar{k}_{n}+1=(1+o_{\scriptscriptstyle{\mathbb{P}}}(1))\log{(\underline{m}_{n}\bar{m}_{n})}/{\log{\nu_{n}^{\prime}}}=(1+o_{\scriptscriptstyle{\mathbb{P}}}(1))\log{n}/{\log{\nu_{n}^{\prime}}}$
(3.48)

when $\underline{m}_{n}\bar{m}_{n}/n\rightarrow\infty$ slowly enough. The
giants $\mathscr{C}_{\rm max}^{\prime}$ in ${\rm
CM}_{n^{\prime}}(\boldsymbol{d}^{\prime})$ and $\mathscr{C}_{\rm max}$ in
${\rm CM}_{n}(\boldsymbol{d})$ satisfy that $|\mathscr{C}_{\rm
max}^{\prime}\Delta\mathscr{C}_{\rm max}|\leq\varepsilon n$ whp for $b$
sufficiently large, where $\Delta$ denotes the symmetric difference between
sets. Further, $\nu_{n}-\varepsilon\leq\nu^{\prime}_{n}\leq\nu_{n}$, so that,
for every $\varepsilon>0$,

${\mathbb{P}}({\rm dist}_{\scriptscriptstyle{\rm
CM}_{n}(\boldsymbol{d})}(o_{1},o_{2})/\log{n}\leq(1+\varepsilon)/\log{\nu})=1-o(1).$
(3.49)

The reverse inequality applies more generally, and follows from the fact that

${\mathbb{P}}({\rm dist}_{\scriptscriptstyle{\rm
CM}_{n^{\prime}}(\boldsymbol{d}^{\prime})}(o_{1},o_{2})\leq
k)={\mathbb{E}}[|B^{\scriptscriptstyle(G_{n})}_{k}(o_{1})|/n],$ (3.50)

together with the fact that

${\mathbb{E}}[|B^{\scriptscriptstyle(G_{n})}_{k}(o_{1})|]\leq(\nu_{n}^{\prime})^{k}$
(3.51)

by [47, Lemma 5.1]. Thus,

${\mathbb{P}}({\rm dist}_{\scriptscriptstyle{\rm
CM}_{n^{\prime}}(\boldsymbol{d}^{\prime})}(o_{1},o_{2})\leq(1-\varepsilon)\log{n}/{\log{\nu_{n}^{\prime}}}k)\leq
n^{-\varepsilon}=o(1),$ (3.52)

as required. ∎

##  4 Discussion and open problems

In this section, we discuss our proof and results, and state some open
problems.

#### Minimal conditions for the proof

Inspection of the proof of Corollary 2.1 and Theorem 2.2 shows that
$Z_{\scriptscriptstyle\geq
k}/n\stackrel{{\scriptstyle\scriptscriptstyle{\mathbb{P}}}}{{\longrightarrow}}\zeta_{\geq
k}$, with $\zeta_{\geq k}\searrow\zeta$ suffices to obtain Theorem 2.2 (see in
particular (2.5) and (2.13)). Theorem 2.4 requires a little more (see (2.32)),
while only Theorem 2.5 requires the full local convergence in probability. The
use of $Z_{\scriptscriptstyle\geq k}$ to study connected components
(particularly close to criticality) has a long history, and is implicitly
present in [26], while being formally introduced in the high-dimensional
percolation context in [24], see [25, 44, 45] for applications to percolation
on the $n$-cube. [37] used it to study the critical behavior for randk-1
inhomogeneous random graphs, and [38] for the phase transition on the Erdős-
Rényi random graph.

#### Related models

We use the configuration model as a proof of concept for the method in this
paper. We believe that our approach is quite versatile. For example, in [39,
Section 2.5], the method is performed for the Erdős-Rényi random graph. That
proof can easily be adapted to finite-type inhomogeneous random graphs as
studied in the seminal paper by Bollobás, Janson and Riordan [19]. In turn,
such an approach would also yield the type distribution of the giant, as it
was identified in greater generality in [51, Lemma 4.10].

#### Local convergence

There are many models for which local convergence has been established, and
thus our results might be applied. For inhomogeneous random graphs, local
convergence was not established explicitly in the seminal paper by Bollobás,
Janson and Riordan [19], but the methodology is very related and does allow
for a simple proof of it (see [39, Chapter 3] for a formal proof, and [27] for
a proof for Erdős-Rényi random graph). For the configuration model, and the
related uniform random graph with prescribed degrees, it was proved explicitly
by Dembo and Montanari [27], see also [22, 28] as well as [39, Chapter 4] for
related proofs. Berger, Borgs, Chayes and Saberi [14] establish local
convergence for preferential attachment models (see also [39, Chapter 5] for
some extensions). A related preferential attachment model with conditionally
independent edges is treated by Dereich and Mörters [31], who again do not
formally prove local convergence, but state a highly related result. Random
intersection graphs are treated by [53], see also [43]. In most of these
models, the size of the giant is established, though mostly in ways that are
quite different from the current proof (see [39] for an extensive overview).
It would be of interest to see whether the current proof simplifies some of
these analyses.

#### Limiting properties that follow from local convergence

As stated in the introduction, local convergence is a versatile tool to prove
various properties of random graphs. The number of connected components, the
clustering coefficient, local neighborhoods, and edge-neighborhoods are all
local quantities (see [39, Chapter 2] for many examples of local quantities).
In some cases, some extra local conditions (typically on the degree
distribution) need to be made in order to be able to use such results. Some
less obvious properties also converge when the graph converges locally. An
important and early example is the Ising model partition function [27]. Also
the PageRank distribution is local [36]. A property that is almost local is
the density of the densest subgraph in a random graph, as shown by Anantharam
and Salez [7]. Lyons [54] shows that the exponential growth rate of the number
of spanning trees of a finite connected graph can be computed through the
local limit. See also [60] for weighted spanning subgraphs, [35] for maximum-
eight independent sets, and [15] for the limiting spectral distribution of the
graph adjacency matrix.

Our approach shows that while the proportion of vertices in the giant is not a
local property, it is almost local in the sense that one extra condition does
guarantee that the proportion of vertices in the giant is what one would
expect it to be on the basis of the local limit. It would be interesting to
investigate whether the idea of ‘almost local’ properties can be extended to
other properties as well. For example, while Theorem 3.6 suggests that also
logarithmic distances are an almost local property, the statement in Theorem
3.6 follows from the proof of Theorem 3.2, rather than from a general ‘almost
local’ result as in Theorem 2.2. It would be interesting to explore this
further, to see whether also related typical distance results might be proved
in a similar way (see [29, 30, 40, 41, 42] for such related results).

#### Percolation on finite graphs

Another area where our results may be useful is percolation on finite graphs.
There, it is often not even clear how to precisely define the critical value
or critical behavior. We refer to Janson and Warnke [52] and Nachmias and
Peres [58] for extensive discussions on the topic. Percolation on random
graphs has also attracted substantial attention, see for example Janson [46]
or Fountoulakis [34] for the derivation of the limiting percolation threshold
for the configuration model. This is related to the locality of the
percolation threshold as investigated by Benjamini, Nachmias and Peres [12] in
the context of $d$-regular graphs that have large girth, and inspired by a
question by Oded Schramm in 2008. Indeed, Schramm conjectured that the
critical percolation threshold on a converging sequence of infinite graphs
$G_{n}$ should converge to that of the graph limit. In a transitive setting,
local convergence can be used also on infinite graphs (as every vertex is
basically the same, thus skipping the necessity of drawing a root uniformly at
random). See also [5, 10, 57] for related work on sharp threshold for the
existence of a giant in the context of expanders.

Recently, Alimohammadi, Borgs and Saberi [4] brought the discussion
significantly forward, by showing that the percolation critical value is is
indeed local for expanders. Further, interestingly, they applied their results
to the Barabási-Albert preferential attachment model [9], in the version of
Bollobás et al. in [21], to show that $p_{c}=0$ and identify the giant for all
$p>0$. The proof relies on a sprinkling argument. It would be interesting to
study the relation between our central assumption in (2.8) and $(G_{n})_{n\geq
1}$ being a sequence of expander graphs. Further, it would be very interesting
to see whether local convergence has consequences for the critical behavior of
percolation on locally convergent graph sequences.

##  Appendix A Further ingredients for configuration model

In this section, we provide some technical ingredients that are useful in the
proof of Theorem 3.2. This section is organised as follows. In Section A.1, we
give some more details of local convergence in probability for the
configuration model. In Section A.2, we discuss a convenient degree-truncation
argument that shows that it suffices to prove Theorem 3.2 for uniformly
bounded degrees. In Section A.3, we present an explicit coupling of the graph
exploration process for ${\rm CM}_{n}(\boldsymbol{d})$ and an $n$-dependent
unimodular branching process.

###  A.1 Local convergence of the configuration model

As mentioned already below Theorem 3.2, there are several ways in which local
convergence in probability, as formalized in (2.2), can be proved. Such proofs
always consist of two steps. In the first, we investigate the expected number
of vertices whose $r$-neighborhood is isomorphic to a specific tree, in the
second, we prove that this number if highly concentrated. Convergence of the
mean follows from the coupling result in Lemma A.2 below (see the discussion
right below it). Concentration can be proved using martingale techniques (by
pairing edges one by one and using Azuma-Hoefding), see [27] or [22].
Alternatively, one can use a second moment method and results similar to Lemma
A.2. See [39, Section 4.1] for such an approach.

###  A.2 A useful degree-truncation argument for the configuration model

In this section, we present a useful degree-truncation argument that allows us
to go from a configuration model with degrees satisfying Conditions
3.1(a)-(b), to degrees that are uniformly bounded. This result makes the proof
of the ‘giant is almost local’ condition in (2.49) simpler, and is interesting
in its own right:

######  Theorem A.1 (Degree truncation for configuration models).

Consider ${\rm CM}_{n}(\boldsymbol{d})$ with general degrees. Fix $b\geq 1$.
There exists a related configuration model ${\rm
CM}_{n^{\prime}}(\boldsymbol{d}^{\prime})$ that is coupled to ${\rm
CM}_{n}(\boldsymbol{d})$ and satisfies that

  * (a)

the degrees in ${\rm CM}_{n^{\prime}}(\boldsymbol{d}^{\prime})$ are truncated
versions of those in ${\rm CM}_{n}(\boldsymbol{d})$, i.e.,
$d_{v}^{\prime}=(d_{v}\wedge b)$ for $v\in[n]$, and $d_{v}^{\prime}=1$ for
$v\in[n^{\prime}]\setminus[n]$;

  * (b)

the total degree in ${\rm CM}_{n^{\prime}}(\boldsymbol{d}^{\prime})$ is the
same as that in ${\rm CM}_{n}(\boldsymbol{d})$, i.e.,
$\sum_{v\in[n^{\prime}]}d_{v}^{\prime}=\sum_{v\in[n]}d_{v}$;

  * (c)

for all $u,v\in[n]$, if $u$ and $v$ are connected in ${\rm
CM}_{n^{\prime}}(\boldsymbol{d}^{\prime})$, then so are $u$ and $v$ in ${\rm
CM}_{n}(\boldsymbol{d})$.

###### Proof.

The proof relies on an ‘explosion’ or ‘fragmentation’ of the vertices $[n]$ in
${\rm CM}_{n}(\boldsymbol{d})$ inspired by [46]. Label the half-edges from 1
to $\ell_{n}$. We go through the vertices $v\in[n]$ one by one. When
$d_{v}\leq b$, we do nothing. When $d_{v}>b$, then we let $d_{v}^{\prime}=b$,
and we keep the $b$ half-edges with the lowest labels. The remaining $d_{v}-b$
half-edges are exploded from vertex $v$, in that they are incident to vertices
of degree 1 in ${\rm CM}_{n^{\prime}}(\boldsymbol{d}^{\prime})$, and are given
vertex labels above $n$. We give the exploded half-edges the remaining labels
of the half-edges incident to $v$. Thus, the half-edges receive labels both in
${\rm CM}_{n}(\boldsymbol{d})$ as well as in ${\rm
CM}_{n^{\prime}}(\boldsymbol{d}^{\prime})$, and the labels of the half-edges
incident to $v\in[n]$ in ${\rm CM}_{n^{\prime}}(\boldsymbol{d}^{\prime})$ are
a subset of those in ${\rm CM}_{n}(\boldsymbol{d})$. In total, we thus create
an extra $n^{+}=\sum_{v\in[n]}(d_{v}-b)_{+}$ ‘exploded’ vertices of degree 1,
and $n^{\prime}=n+n^{+}$.

We then pair the half-edges randomly, in the same way in ${\rm
CM}_{n}(\boldsymbol{d})$ and in ${\rm
CM}_{n^{\prime}}(\boldsymbol{d}^{\prime})$. This means that when the half-edge
with label $x$ is paired to the half-edge with label $y$ in ${\rm
CM}_{n}(\boldsymbol{d})$, the half-edge with label $x$ is also paired to the
half-edge with label $y$ in ${\rm CM}_{n^{\prime}}(\boldsymbol{d}^{\prime})$,
for all $x,y\in[\ell_{n}]$.

We now check parts (a)-(c). Obviously parts (a) and (b) follow. For part (c),
we note that all created vertices have degree 1. Further, for vertices
$u,v\in[n]$, if there exists a path in ${\rm
CM}_{n^{\prime}}(\boldsymbol{d}^{\prime})$ connecting them, then the
intermediate vertices have degree at least 2, so that they cannot correspond
to exploded vertices. Thus, the same path of paired half-edges also exists in
${\rm CM}_{n}(\boldsymbol{d})$, so that also $u$ and $v$ are connected in
${\rm CM}_{n}(\boldsymbol{d})$. ∎

###  A.3 Coupling of configuration neighborhoods and branching processes

We next relate the neighborhood in a random graph to a certain $n$-dependent
unimodular branching process where the root has offspring distribution
$D_{n}$. Such a coupling has previously appeared in [16]. Since the branching
process is unimodular, all other individuals have offspring distribution
$D_{n}^{\star}-1$, where

${\mathbb{P}}(D_{n}^{\star}=k)=\frac{k}{{\mathbb{E}}[D_{n}]}\,{\mathbb{P}}(D_{n}=k),\qquad
k\in{\mathbb{N}},$ (A.1)

is the size-biased distribution of $D_{n}$. Denote this branching process by
$({\sf BP}_{n}(t))_{t\in{\mathbb{N}}_{0}}$. Here, ${\sf BP}_{n}(t)$ denotes
the branching process when it contains precisely $t$ vertices, and we explore
it in the breadth-first order. Clearly, by Conditions 3.1(a)-(b),
$D_{n}\stackrel{{\scriptstyle d}}{{\longrightarrow}}D$ and
$D_{n}^{\star}\stackrel{{\scriptstyle d}}{{\longrightarrow}}D^{\star}$, which
implies that ${\sf BP}_{n}(t)\stackrel{{\scriptstyle
d}}{{\longrightarrow}}{\sf BP}(t)$ for every $t$ finite, where ${\sf BP}(t)$
is the restriction of the unimodular branching process ${\sf BP}$ with root
offspring distribution $(p_{k})_{k\geq 1}$ for which $p_{k}={\mathbb{P}}(D=k)$
to its first $t$ individuals.

We let $({\sf G}_{n}(t))_{t\in{\mathbb{N}}_{0}}$ denote the graph exploration
process from a uniformly chosen vertex $o\in[n]$. Here ${\sf G}_{n}(t)$ is the
exploration up to $t$ vertices, in the breadth-first manner. In particular,
from $({\sf G}_{n}(t))_{t\in{\mathbb{N}}_{0}}$ we can retrieve
$(B_{r}^{\scriptscriptstyle(G_{n})}(o))_{r\in{\mathbb{N}}_{0}}$. The following
lemma proves that we can couple the graph exploration to the branching process
in such a way that $({\sf G}_{n}(t))_{0\leq t\leq m_{n}}$ is equal to $({\sf
BP}_{n}(t))_{0\leq t\leq m_{n}}$ whenever $m_{n}\rightarrow\infty$ arbitrarily
slowly. In the statement, we write $(\widehat{\sf G}_{n}(t),\widehat{\sf
BP}_{n}(t))_{t\in{\mathbb{N}}_{0}}$ for the coupling of $({\sf
G}_{n}(t))_{0\leq t\leq m_{n}}$ and $({\sf BP}_{n}(t))_{0\leq t\leq m_{n}}$:

######  Lemma A.2 (Coupling graph exploration and branching process).

Subject to Conditions 3.1(a)-(b), there exists a coupling $(\widehat{\sf
G}_{n}(t),\widehat{\sf BP}_{n}(t))_{t\in{\mathbb{N}}_{0}}$ of $({\sf
G}_{n}(t))_{0\leq t\leq m_{n}}$ and $({\sf BP}_{n}(t))_{0\leq t\leq m_{n}}$
such that

${\mathbb{P}}\Big{(}(\widehat{\sf G}_{n}(t))_{0\leq t\leq
m_{n}}\neq(\widehat{\sf BP}_{n}(t))_{0\leq t\leq m_{n}}\Big{)}=o(1),$ (A.2)

whenever $m_{n}\rightarrow\infty$ arbitrarily slowly.

Lemma A.2 also implies that the proportion of vertices whose $r$ neighborhood
is isomorphic to a specific tree converges to the probability that the
unimodular branching process with root offspring distribution $(p_{k})_{k\geq
1}$, which is a crucial ingredient in local convergence.

######  Remark A.3 (Extensions).

Here we discuss some extensions of Lemma A.2. First, in its proof, we will see
that any $m_{n}=o(\sqrt{n/d_{\mathrm{max}}})$ is allowed. Here
$d_{\mathrm{max}}=\max_{i\in[n]}d_{i}$ is the maximal vertex degree in the
graph. Secondly, Lemma A.2 can easily be extended to deal with the
explorations from two sources $(o_{1},o_{2})$, where we can still take
$m_{n}=o(\sqrt{n/d_{\mathrm{max}}})$, and the two branching processes to which
we couple the exploration from two sources, denoted by $(\widehat{\sf
BP}_{n}^{\scriptscriptstyle(1)}(t))_{0\leq t\leq m_{n}}$ and $(\widehat{\sf
BP}_{n}^{\scriptscriptstyle(2)}(t))_{0\leq t\leq m_{n}}$, are i.i.d.
$\blacksquare$

###### Proof.

We let the offspring of the root of the branching process $\widehat{D}_{n}$ be
equal to $d_{o}$, which is the number of neighbors of the vertex $o\in[n]$
that is chosen uniformly at random. By construction, $\widehat{D}_{n}=d_{o}$,
so that also $\widehat{\sf G}_{n}(1)=\widehat{\sf BP}_{n}(1)$. We next explain
how to jointly construct $(\widehat{\sf G}_{n}(t),\widehat{\sf
BP}_{n}(t))_{0\leq t\leq m}$ given that we have already constructed
$(\widehat{\sf G}_{n}(t),\widehat{\sf BP}_{n}(t))_{0\leq t\leq m-1}$.

To obtain $(\widehat{\sf G}_{n}(t)_{0\leq t\leq m}$, we take the first
unpaired half-edge $x_{m}$. For the configuration model, this half-edge needs
to be paired to a uniform half-edge that has not been paired so far. We draw a
uniform half-edge $y_{m}$ from the collection of all half-edges, independently
of the past, and we let the $(m-1)$st individual in $(\widehat{\sf
BP}_{n}(t))_{0\leq t\leq m-1}$ have precisely $d_{U_{m}}-1$ children, where
$U_{m}$ is the vertex incident to $y_{m}$. Note that $d_{U_{m}}-1$ has the
same distribution as $D_{n}^{\star}-1$ and, by construction, the collection
$\big{(}d_{U_{t}}-1\big{)}_{t\geq 0}$ is i.i.d. When $y_{m}$ is still free,
i.e., has not yet been paired in $(\widehat{\sf G}_{n}(t))_{0\leq t\leq m-1}$,
then we also let $x_{m}$ be paired to $y_{m}$ for $(\widehat{\sf
G}_{n}(t))_{0\leq t\leq m}$, and we have constructed $(\widehat{\sf
G}_{n}(t))_{0\leq t\leq m}$. However, a problem arises when $y_{m}$ has
already been paired in $(\widehat{\sf G}_{n}(t))_{0\leq t\leq m-1}$, in which
case we draw a uniform unpaired half-edge $y_{m}^{\prime}$ and pair $x_{m}$ to
$y_{m}^{\prime}$ instead. Clearly, this might give rise to a difference
between $(\widehat{\sf G}_{n}(t))_{t\leq m}$ and $(\widehat{\sf
BP}_{n}(t))_{0\leq t\leq m}$. We now provide bounds on the probability that an
error occurs before time $m_{n}$.

There are two sources of differences between $(\widehat{\sf G}_{n}(t))_{t\geq
0}$ and $(\widehat{\sf BP}_{n}(t))_{t\geq 0}$:

Half-edge re-use.

In the above coupling $y_{m}$ had already been paired and is being re-used in
the branching process, and we need to redraw $y_{m}^{\prime}$;

Vertex re-use.

In the above coupling, $y_{m}$ is a half-edge that has not yet been paired in
$(\widehat{\sf G}_{n}(t))_{0\leq t\leq m-1}$, but it is incident to a half-
edge that has already been paired in $(\widehat{\sf G}_{n}(t))_{0\leq t\leq
m-1}$. In particular, the vertex $U_{m}$ to which it is incident has already
appeared in $(\widehat{\sf G}_{n}(t))_{0\leq t\leq m-1}$ and it is being re-
used in the branching process. In this case, a copy of the vertex appears in
$(\widehat{\sf BP}_{n}(t))_{0\leq t\leq m}$, while a cycle appears in
$(\widehat{\sf G}_{n}(t))_{0\leq t\leq m}$.

We continue by providing a bound on both contributions:

#### Half-edge re-use

Up to time $m-1$, exactly $2m-1$ half-edges are forbidden to be used by
$(\widehat{\sf G}_{n}(t))_{t\leq m}$. The probability that the half-edge
$y_{m}$ equals one of these two half-edges is at most

$\frac{2m-1}{\ell_{n}}.$ (A.3)

Hence the expected number of half-edge re-uses before time $m_{n}$ is at most

$\sum_{m=1}^{m_{n}}\frac{2m-1}{\ell_{n}}=\frac{m_{n}^{2}}{\ell_{n}}=o(1),$
(A.4)

when $m_{n}=o(\sqrt{n}).$

#### Vertex re-use

The probability that vertex $i$ is chosen in the $m$th draw is equal to
$d_{i}/\ell_{n}$. The probability that vertex $i$ is drawn twice before time
$m_{n}$ is at most

$\frac{m_{n}(m_{n}-1)}{2}\frac{d_{i}^{2}}{\ell_{n}^{2}}.$ (A.5)

By the union bound, the probability that a vertex re-use has occurred before
time $m_{n}$ is at most

$\frac{m_{n}(m_{n}-1)}{2\ell_{n}}\sum_{i\in[n]}\frac{d_{i}^{2}}{\ell_{n}}\leq
m_{n}^{2}\frac{d_{\mathrm{max}}}{\ell_{n}}=o(1),$ (A.6)

by Condition 3.1(a)-(b) and when $m_{n}=o(\sqrt{n/d_{\mathrm{max}}})$. This
completes the coupling part of Lemma A.2, including the bound on $m_{n}$ as
formulated in Remark A.3. It is straightforward to check that the exploration
can be performed from the two sources $(o_{1},o_{2})$ independently, thus
establishing the requested coupling to two independent $n$-dependent branching
processes claimed in Remark A.3. ∎

Finally, we adapt the above argument to prove Lemma 3.3:

###### Proof of Lemma 3.3..

Define $a_{n}=(\bar{m}_{n}^{2}/\ell_{n})^{1+\delta}$ where $\delta>0$. We
apply a first-moment method and bound

$\displaystyle{\mathbb{P}}(\mathcal{C}_{n}(2)^{c})$
$\displaystyle\leq\frac{1}{a_{n}}{\mathbb{E}}\Big{[}\big{|}|B_{\bar{k}_{n}}^{\scriptscriptstyle(G_{n})}(o_{2})|-|{\sf
BP}_{\bar{k}_{n}}^{\scriptscriptstyle(2)}|\big{|}\Big{]}$ (A.7)
$\displaystyle=\frac{1}{a_{n}}{\mathbb{E}}\Big{[}\big{(}|B_{\bar{k}_{n}}^{\scriptscriptstyle(G_{n})}(o_{2})|-|{\sf
BP}_{\bar{k}_{n}}^{\scriptscriptstyle(2)}|\big{)}_{+}+\big{(}|B_{\bar{k}_{n}}^{\scriptscriptstyle(G_{n})}(o_{2})|-|{\sf
BP}_{\bar{k}_{n}}^{\scriptscriptstyle(2)}|\big{)}_{-}\Big{]}$
$\displaystyle\leq\frac{1}{a_{n}}{\mathbb{E}}\Big{[}\big{(}|\widehat{\sf
G}_{n}(m_{n})|-|\widehat{\sf BP}_{n}(m_{n})|\big{)}_{+}+\big{(}|\widehat{\sf
G}_{n}(m_{n})|-|\widehat{\sf BP}_{n}(m_{n})|\big{)}_{-}\Big{]},$

where the notation is as in Lemma A.2 and $|\widehat{\sf G}_{n}(m_{n})|$ and
$|\widehat{\sf BP}_{n}(m_{n})|$ denote the number of half-edges and
individuals found up to the $m_{n}$th step of the exploration starting from
$o_{2}$, and $m_{n}=(b+1)\bar{m}_{n}$, while $x_{+}=\max\\{0,x\\}$ and
$x_{-}=\max\\{0,-x\\}$.

To bound these expectations, we adapt the proof of Lemma A.2 to our setting.
We start with the first term in (A.7), for which we use the exploration up to
size $\bar{m}_{n}$ used in the proof of Lemma A.2. We note that the only way
that $|\widehat{\sf G}_{n}(t+1)|-|\widehat{\sf G}_{n}(t)|$ can be larger than
$|\widehat{\sf BP}_{n}(t+1)|-|\widehat{\sf BP}_{n}(t)|$ is when a half-edge
re-use occurs, and then the redraw in $|\widehat{\sf
G}_{n}(t+1)|-|\widehat{\sf G}_{n}(t)|$ is larger than then original draw of
$|\widehat{\sf BP}_{n}(t+1)|-|\widehat{\sf BP}_{n}(t)|$. Since all degrees are
bounded by $b$,

$|\widehat{\sf G}_{n}(\bar{m}_{n})|-|\widehat{\sf BP}_{n}(\bar{m}_{n})|\leq
b\\#\\{\text{half-edge re-uses up to time }m_{n}\\}.$ (A.8)

Thus, by (A.4),

${\mathbb{E}}\Big{[}\big{(}|\widehat{\sf G}_{n}(\bar{m}_{n})|-|\widehat{\sf
BP}_{n}(\bar{m}_{n})|\big{)}_{+}\Big{]}\leq b\frac{m_{n}^{2}}{\ell_{n}}.$
(A.9)

We continue with the second term in (A.7), which is similar. We note that
$|\widehat{\sf G}_{n}(t+1)|-|\widehat{\sf G}_{n}(t)|$ can be smaller than
$|\widehat{\sf BP}_{n}(t+1)|-|\widehat{\sf BP}_{n}(t)|$ when a half-edge re-
use occurs, and then the redraw in $|\widehat{\sf G}_{n}(t+1)|-|\widehat{\sf
G}_{n}(t)|$ is smaller than then original draw of $|\widehat{\sf
BP}_{n}(t+1)|-|\widehat{\sf BP}_{n}(t)|$, or when a vertex re-use occurs, when
$|\widehat{\sf G}_{n}(t+1)|-|\widehat{\sf G}_{n}(t)|=0$ and $|\widehat{\sf
BP}_{n}(t+1)|-|\widehat{\sf BP}_{n}(t)|\leq b$ since all degrees are bounded
by $b$. Thus

$|\widehat{\sf BP}_{n}(\bar{m}_{n})|-|\widehat{\sf G}_{n}(\bar{m}_{n})|\leq
b\\#\\{\text{half-edge and vertex re-uses up to time }m_{n}\\}.$ (A.10)

Thus, by (A.4) and (A.6),

${\mathbb{E}}\Big{[}\big{(}|\widehat{\sf G}_{n}(\bar{m}_{n})|-|\widehat{\sf
BP}_{n}(\bar{m}_{n})|\big{)}_{+}\Big{]}\leq(b+b^{2})\frac{m_{n}^{2}}{\ell_{n}}.$
(A.11)

We conclude that

${\mathbb{P}}(\mathcal{C}_{n}(2)^{c})\leq\frac{1}{a_{n}}(2b+b^{2})\frac{m_{n}^{2}}{\ell_{n}}=O\Big{(}\Big{(}\frac{\ell_{n}}{m_{n}^{2}}\Big{)}^{\delta}\Big{)}=o(1),$
(A.12)

by assumption and the fact that $m_{n}=(b+1)\bar{m}_{n}$. ∎

#### Acknowledgements

The work in this paper was supported by the Netherlands Organisation for
Scientific Research (NWO) through Gravitation-grant NETWORKS-024.002.003. I
thank Joel Spencer for proposing the ‘easiest solution’ to the giant component
problem for the Erdős-Rényi random graph, which inspired this paper. I thank
Shankar Bhamidi for useful and inspiring discussions, Souvik Dhara for
literature references, and Christian Borgs for suggestions on local
convergence and encouragement.

## References

  * [1] [author] Aldous, D.D. (2001). The $\zeta(2)$ limit in the random assignment problem. Random Structures Algorithms 18 381–418. 10.1002/rsa.1015 1839499
  * [2] [author] Aldous, D.D. and Lyons, R.R. (2007). Processes on unimodular random networks. Electron. J. Probab. 12 no. 54, 1454–1508. 10.1214/EJP.v12-463 2354165
  * [3] [author] Aldous, D.D. and Steele, J. M.J. M. (2004). The objective method: probabilistic combinatorial optimization and local weak convergence. In Probability on discrete structures. Encyclopaedia Math. Sci. 110 1–72. Springer, Berlin. 10.1007/978-3-662-09444-0_1 2023650 (2005e:60018)
  * [4] [author] Alimohammadi, Y.Y., Borgs, C.C. and Saberi, A.A. (2021). Locality of random digraphs on expanders. arXiv:2103.09952 [math.PR].
  * [5] [author] Alon, N.N., Benjamini, I.I. and Stacey, A.A. (2004). Percolation on finite graphs and isoperimetric inequalities. Ann. Probab. 32 1727–1745. MR2073175 (2005f:05149)
  * [6] [author] Alon, N.N. and Spencer, J.J. (2000). The probabilistic method, second ed. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, New York. MR1885388 (2003f:60003)
  * [7] [author] Anantharam, V.V. and Salez, J.J. (2016). The densest subgraph problem in sparse random graphs. Ann. Appl. Probab. 26 305–327. 10.1214/14-AAP1091 3449319
  * [8] [author] Arratia, R.R., Barbour, ADA. and Tavaré, S.S. (2003). Logarithmic combinatorial structures: a probabilistic approach. European Mathematical Society.
  * [9] [author] Barabási, A. L.A. L. and Albert, R.R. (1999). Emergence of scaling in random networks. Science 286 509–512. MR2091634
  * [10] [author] Benjamini, I.I., Boucheron, S.S., Lugosi, G.G. and Rossignol, R.R. (2012). Sharp threshold for percolation on expanders. Ann. Probab. 40 130–145. 10.1214/10-AOP610 2917769
  * [11] [author] Benjamini, I.I., Lyons, R.R. and Schramm, O.O. (2015). Unimodular random trees. Ergodic Theory Dynam. Systems 35 359–373. 10.1017/etds.2013.56 3316916
  * [12] [author] Benjamini, I.I., Nachmias, A.A. and Peres, Y.Y. (2011). Is the critical percolation probability local? Probab. Theory Related Fields 149 261–269. 10.1007/s00440-009-0251-5 2773031
  * [13] [author] Benjamini, I.I. and Schramm, O.O. (2001). Recurrence of distributional limits of finite planar graphs. Electron. J. Probab. 6 no. 23, 13 pp. (electronic). 10.1214/EJP.v6-96 1873300
  * [14] [author] Berger, N.N., Borgs, C.C., Chayes, J.J. and Saberi, A.A. (2014). Asymptotic behavior and distributional limits of preferential attachment graphs. Ann. Probab. 42 1–40. 10.1214/12-AOP755 3161480
  * [15] [author] Bhamidi, S.S., Evans, S.S. and Sen, A.A. (2012). Spectra of large random trees. J. Theoret. Probab. 25 613–654. 10.1007/s10959-011-0360-9 2956206
  * [16] [author] Bhamidi, S.S., van der Hofstad, R.R. and Hooghiemstra, G.G. (2017). Universality for first passage percolation on sparse random graphs. Ann. Probab. 45 2568–2630. 10.1214/16-AOP1120 3693970
  * [17] [author] Bollobás, B.B. (1980). A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European J. Combin. 1 311–316. MR595929 (82i:05045)
  * [18] [author] Bollobás, B.B. (2001). Random graphs, second ed. Cambridge Studies in Advanced Mathematics 73. Cambridge University Press, Cambridge. MR1864966 (2002j:05132)
  * [19] [author] Bollobás, B.B., Janson, S.S. and Riordan, O.O. (2007). The phase transition in inhomogeneous random graphs. Random Structures Algorithms 31 3–122. MR2337396
  * [20] [author] Bollobás, B.B. and Riordan, O.O. (2015). An old approach to the giant component problem. J. Combin. Theory Ser. B 113 236–260. 3343756
  * [21] [author] Bollobás, B.B., Riordan, O.O., Spencer, J.J. and Tusnády, G.G. (2001). The degree sequence of a scale-free random graph process. Random Structures Algorithms 18 279–290. MR1824277 (2002b:05121)
  * [22] [author] Bordenave, C.C. (2016). Lecture notes on random graphs and probabilistic combinatorial optimization. Version April 8, 2016. Available at http://www.math.univ-toulouse.fr/$\sim$bordenave/coursRG.pdf.
  * [23] [author] Bordenave, C.C. and Caputo, P.P. (2015). Large deviations of empirical neighborhood distribution in sparse random graphs. Probab. Theory Related Fields 163 149–222. 10.1007/s00440-014-0590-8 3405616
  * [24] [author] Borgs, C.C., Chayes, J.J., Hofstad, R. van derR. v. d., Slade, G.G. and Spencer, J.J. (2005). Random subgraphs of finite graphs. I. The scaling window under the triangle condition. Random Structures Algorithms 27 137–184. MR2155704 (2006e:05156)
  * [25] [author] Borgs, C.C., Chayes, J.J., Hofstad, R. van derR. v. d., Slade, G.G. and Spencer, J.J. (2006). Random subgraphs of finite graphs. III. The phase transition for the $n$-cube. Combinatorica 26 395–410. MR2260845
  * [26] [author] Borgs, C.C., Chayes, J. T.J. T., Kesten, H.H. and Spencer, J.J. (1999). Uniform boundedness of critical crossing probabilities implies hyperscaling. Random Structures Algorithms 15 368–413. MR1716769 (2001a:60111)
  * [27] [author] Dembo, A.A. and Montanari, A.A. (2010). Ising models on locally tree-like graphs. The Annals of Applied Probability 20 565–592.
  * [28] [author] Dembo, A.A. and Montanari, A.A. (2010). Gibbs measures and phase transitions on sparse random graphs. Braz. J. Probab. Stat. 24 137–211. 10.1214/09-BJPS027 2643563
  * [29] [author] Dereich, S.S., Mönch, C.C. and Mörters, P.P. (2012). Typical distances in ultrasmall random networks. Adv. in Appl. Probab. 44 583–601. 10.1239/aap/1339878725 2977409
  * [30] [author] Dereich, S.S., Mönch, C.C. and Mörters, P.P. (2017). Distances in scale free networks at criticality. Electron. J. Probab. 22 Paper No. 77, 38. 10.1214/17-EJP92 3710797
  * [31] [author] Dereich, S.S. and Mörters, P.P. (2013). Random networks with sublinear preferential attachment: the giant component. Ann. Probab. 41 329–384. 10.1214/11-AOP697 3059201
  * [32] [author] Durrett, R.R. (2007). Random graph dynamics. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge. MR2271734
  * [33] [author] Erdős, P.P. and Rényi, A.A. (1960). On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 17–61. MR0125031 (23 ##A2338)
  * [34] [author] Fountoulakis, N.N. (2007). Percolation on sparse random graphs with given degree sequence. Internet Math. 4 329–356. 2522948
  * [35] [author] Gamarnik, D.D., Nowicki, T.T. and Swirszcz, G.G. (2006). Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method. Random Structures Algorithms 28 76–106. 10.1002/rsa.20072 2187483
  * [36] [author] Garavaglia, A.A., van der Hofstad, R.R. and Litvak, N.N. (2020). Local weak convergence for PageRank. Ann. Appl. Probab. 30 40–79. 10.1214/19-AAP1494 4068306
  * [37] [author] Hofstad, R. van derR. v. d. (2013). Critical behavior in inhomogeneous random graphs. Random Structures and Algorithms 42 480–508.
  * [38] [author] Hofstad, R. van derR. v. d. (2017). Random graphs and complex networks. Volume 1. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge. 10.1017/9781316779422 3617364
  * [39] [author] Hofstad, R. van derR. v. d. (2021+). Random graphs and complex networks. Vol. 2. In preparation, see http://www.win.tue.nl/$\sim$rhofstad/NotesRGCNII.pdf.
  * [40] [author] Hofstad, R. van derR. v. d., Hooghiemstra, G.G. and Van Mieghem, P.P. (2005). Distances in random graphs with finite variance degrees. Random Structures Algorithms 27 76–123. MR2150017 (2006d:60019)
  * [41] [author] Hofstad, R. van derR. v. d., Hooghiemstra, G.G. and Znamenski, D.D. (2007). Distances in random graphs with finite mean and infinite variance degrees. Electron. J. Probab. 12 703–766 (electronic). MR2318408
  * [42] [author] Hofstad, R. van derR. v. d. and Komjáthy, J.J. (2017). When is a scale-free graph ultra-small? J. Stat. Phys. 169 223–264. 10.1007/s10955-017-1864-1 3704860
  * [43] [author] Hofstad, R. van derR. v. d., Komjáthy, J.J. and Vadon, V.V. (2019). Random intersection graphs with communities. arXiv:1809.02514 [math.PR].
  * [44] [author] Hofstad, R. van derR. v. d. and Nachmias, A.A. (2014). Unlacing hypercube percolation: a survey. Metrika 77 23–50. 10.1007/s00184-013-0473-5 3152019
  * [45] [author] Hofstad, R. van derR. v. d. and Nachmias, A.A. (2017). Hypercube percolation. J. Eur. Math. Soc. (JEMS) 19 725–814. 10.4171/JEMS/679 3612867
  * [46] [author] Janson, S.S. (2009). On percolation in random graphs with given vertex degrees. Electron. J. Probab. 14 no. 5, 87–118. 10.1214/EJP.v14-603 2471661 (2010b:60023)
  * [47] [author] Janson, S.S. (2010). Susceptibility of random graphs with given vertex degrees. J. Comb. 1 357–387. 2799217 (2012c:05278)
  * [48] [author] Janson, S.S., Knuth, D. E.D. E., Łuczak, T.T. and Pittel, B.B. (1993). The birth of the giant component. Random Structures Algorithms 4 231–358. With an introduction by the editors. MR1220220 (94h:05070)
  * [49] [author] Janson, S.S. and Luczak, M.M. (2009). A new approach to the giant component problem. Random Structures Algorithms 34 197–216. 10.1002/rsa.20231 MR2490288 (2010d:05140)
  * [50] [author] Janson, S.S., Łuczak, T.T. and Rucinski, A.A. (2000). Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York. MR1782847 (2001k:05180)
  * [51] [author] Janson, S.S. and Riordan, O.O. (2012). Susceptibility in inhomogeneous random graphs. Electron. J. Combin. 19 Paper 31, 59. 2880662
  * [52] [author] Janson, S.S. and Warnke, L.L. (2018). On the critical probability in percolation. Electron. J. Probab. 23 Paper No. 1, 25. 10.1214/17-EJP52 3751076
  * [53] [author] Kurauskas, V.V. (2015). On local weak limit and subgraph counts for sparse random graphs. arXiv: 1504.08103 [math.PR].
  * [54] [author] Lyons, R.R. (2005). Asymptotic enumeration of spanning trees. Combin. Probab. Comput. 14 491–522. 10.1017/S096354830500684X 2160416
  * [55] [author] Molloy, M.M. and Reed, B.B. (1995). A critical point for random graphs with a given degree sequence. Random Structures Algorithms 6 161–179. MR1370952 (97a:05191)
  * [56] [author] Molloy, M.M. and Reed, B.B. (1998). The size of the giant component of a random graph with a given degree sequence. Combin. Probab. Comput. 7 295–305. MR1664335 (2000c:05130)
  * [57] [author] Nachmias, A.A. (2009). Mean-field conditions for percolation in finite graphs. Geometric And Functional Analysis 19 1171–1194.
  * [58] [author] Nachmias, A.A. and Peres, Y.Y. (2008). Critical random graphs: diameter and mixing time. Ann. Probab. 36 1267–1286. 10.1214/07-AOP358 MR2435849 (2009h:05190)
  * [59] [author] Riordan, O.O. (2012). The phase transition in the configuration model. Combinatorics, Probability and Computing 21 1–35.
  * [60] [author] Salez, J.J. (2013). Weighted enumeration of spanning subgraphs in locally tree-like graphs. Random Structures Algorithms 43 377–397. 10.1002/rsa.20436 3094425