Percolation in simple directed random graphs with a given degree distribution

Abstract

We study site and bond percolation in simple directed random graphs with a given degree distribution. We derive the percolation threshold for the giant strongly connected component and the fraction of vertices in this component as a function of the percolation probability. The results are obtained for degree sequences in which the maximum degree may depend on the total number of nodes n, being asymptotically bounded by $n^{\frac{1}{9}}$.

1. Introduction

Percolation in infinite graphs is typically studied in the setting where edges (or vertices) are removed uniformly at random and some connectivity-related property is being traced as a function of the percolation probability $\pi\in(0,1)$ that a randomly chosen edge (or vertex) is present. Conventionally, this property is chosen to describe connected components: maximal vertex sets in which any pair of vertices is connected with a path. Many results about sizes of connected components are known for percolation in infinite lattices [4] and random graphs [1, 3, 15, 16, 19]. Closely related to percolation are random graph models that depend on a real parameter, such as the well-studied Erdős Rényi random graph $G(n,p)$, and also various models for directed random graphs, often referred to as $D(n,p)$ or $\vec G(n,p)$ [17, 26, 29, 30].

Fountoulakis [16] and Janson [19] studied percolation in undirected random graphs with well-behaved degree sequences using techniques that rely on Molloy and Reed’s existence theorem [22, 23], which indicates whether a simple undirected random graph with a given degree sequence contains a giant component and how large it is. These authors showed that if one starts with a simple random graph generated by the configuration model and then removes edges (vertices) uniformly at random, the resulting percolated graph can again be studied with the configuration model, albeit with a modified degree sequence. In this paper, we introduce a similar argument to directed graphs. Although there are several points of analogy, directed graphs generally require a distinct treatment from that of undirected graphs.

In digraphs, there exist several non-equivalent definitions for a connected component, all of which give rise to an interesting percolation problem. Let $G=(V,E)$ be a simple digraph and $n=|V|$. We say that $\mathcal C \subset V$ is a strongly connected component (SCC) if for all $v_1,v_2\in \mathcal C $, there are directed paths that connect v ₁ with v ₂ and v ₂ with $v_1,$ and no other vertex from V can be added to $\mathcal C$ without losing this property. Suppose G _n is uniformly sampled from the set of all digraphs with a fixed graphic degree sequence

(1)\begin{align} \textbf{d}^{n}:= \left( ({d^-_{1}}, {d^+_{1}}), ({d^-_{2}}, {d^+_{2}}),\dots, ({d^-_{n}}, {d^+_{n}}) \right), \end{align}

where ${d^-_{v}}$ and ${d^+_{v}}$ indicate correspondingly the in- and out-degree of vertex $v\in V$. Let additionally the following limits exist, $\mu:= \lim_{n\to \infty} \mu(n)$ and $\mu_{11}:=\lim_{n\to \infty} \mu_{11}(n),$ with $\mu(n):=n^{-1}\sum_{v\in V}{{d^-_{v}}} =n^{-1}\sum_{v\in V}{{d^+_{v}}}$ being the expected number of edges per vertex and $ \mu_{11}(n):=n^{-1}\sum_{v\in V}{{d^-_{v}}{d^+_{v}}}$.

The existence criteria for the giant strongly connected component (GSCC) in directed graphs was formulated for slightly different models by Cooper and Frieze [10], Bloznelis, Götze, and Jaworski [2], and Penrose [24]. These results have been subsequently improved by weakening the requirement on the degree sequence by Graf [18] and Coulson [11], and more recently, further generalized by Cai and Perarnau [7] and Donderwinkel and Xie [14]. All in all, the abovementioned authors state that if $\mu_{11} - \mu \gt 0,$ the size of the largest SCC $\mathcal{C} (G_n)$ is of the order n,

(2)\begin{align} \lim_{n\to\infty} \frac{|\mathcal{C}(G_n)|}{n}=c \gt 0, \end{align}

under some regularity conditions on the degree sequences $(\textbf{d}^{n})_{n\in \mathbb{N}}$. There are also results about the structure of the giant component [12], its diameter [8], and the properties of the dynamic processes on it [5, 6]. Sizes of weakly connected components were studied in [13].

If the limit in equation (2) holds, we say the random graph contains a GSCC. Likewise, if the sign of the inequality is flipped, $\mu_{11} - \mu \lt 0,$ then the size of all SCCs is $\mathcal{O}\left(1\right)$, and the random graph is said to contain no GSCC. This result points out the existence of two classes of limiting degree sequences, those with the size of largest SCC being $\Theta(n)$ and those for which this size is $\mathcal{O}\left(1\right)$.

In this paper, we study a percolated graph $G_n^\pi$, in which each edge (vertex) in G _n is randomly removed with probability $1-\pi$. We show that if the GSCC exists in the original graph G _n, removing a positive fraction of edges (or vertices) can modify the degree distribution just in the right way to flip the sign of the inequality, while keeping the percolated graph to be uniform in the set of all graphs with a fixed (modified) degree distribution. By combining the latter observation with the theory of Cai and Perarnau [7], we show that the “phase transition” from $\mathcal{O}\left(1\right)$ to $\Theta(n)$ takes place at the critical probability $\pi_c= {\mu}/{\mu_{11}}$, such that only for $\pi \gt \pi_c$, $G_n^\pi$ contains a GSCC with high probability (w.h.p.). The critical threshold π _c is the same for bond and site percolation, whereas the fractions of vertices in GSCC, as defined in Eq. (2), are closely related for bond, $c^{\text{bond}}(\pi)$, and site, $c^{\text{site}}(\pi)$, percolation models: $c^{\text{site}}(\pi) = \pi{c^{\text{bond}}}(\pi)$. This work and the related proofs are inspired by the results for percolation in undirected graphs by Fountoulakis [16] and are based on Chapter 4 of Thesis [28]. Similar conclusions were also obtained heuristically by Graf [18] by applying Janson’s exploding method [19].

2. Main result

This section introduces our main theorems for the percolation threshold of the GSCC. We consider two types of percolation models on a simple digraph $G_n=(V_n,E_n),$ $n=|V_n|$ that result in a random subgraph $G_{n}^{\pi}$ on the same vertex set:

• • Bond percolation, fix percolation probability $\pi \in (0,1)$, then each edge of G _n is removed independently of the other edges with probability $1-\pi$.

• • Site percolation, fix percolation probability $\pi \in (0,1)$, then for each vertex of G _n, all the edges incident to this vertex are removed together with probability $1-\pi$ independently of the other vertices. Such a vertex is referred to as a deleted vertex.

It should be clear from the context which type of percolation is discussed. Strictly speaking, the existence of the GSCC is a limiting property of a sequence of graphs $(G_n)_{n\in \mathbb{N}}$, in which each element is defined by a finite graphic degree sequence dⁿ. Thus, we refer to an infinite sequence of degree sequences, $(\textbf{d}^{n})_{n\in \mathbb{N}},$ as the degree progression, where n is the index and the number of vertices in the nth element of this progression. Although our ultimate goal is to make statements about random graphs satisfying a specific degree distribution in the limit $n\to \infty$, the bulk of the paper is spent on determining whether degree progression $(\textbf{d}^{n})_{n\in \mathbb{N}}$ maintains or acquires some property of interest w.h.p. as $n\to \infty$.

To make valid statements about the GSCC, we need to impose several requirements on the degree progression. We are interested in simple graphs, which indicates that each degree sequence in the progression must be graphic as required by the equivalent of Erdős–Gallai theorem for directed graphs [20, Theorem 4]. In Section 3.1, we progressively add several more technical constraints on $(\textbf{d}^{n})_{n\in \mathbb{N}},$ namely Definitions 3.1, 3.2, and 3.3, which we jointly refer to as the requirements for a proper degree progression. Together, these conditions guarantee sufficient regularity of the degree progression, allowing us to reason about the limiting behavior of the corresponding random graphs and their connected components. In this condition, the most restricting requirement is that the maximum degree must be bounded, $d_{\max} \leq n^{\frac{1}{9}}$.

Definition 2.1. The percolation threshold of a proper degree progression $(\textbf{d}^{n})_{n\in \mathbb{N}}$ is given by

(3)\begin{align} \pi_{c} = \sup\left\{\pi \in (0,1) \bigm \vert \forall \varepsilon \gt 0, \lim_{n \rightarrow \infty} \mathbb{P}\left[ n^{-1}\left\lvert \mathcal{C}(G_{n}^{\pi})\right\rvert \geq \varepsilon \right] = 0 \right\}, \end{align}

with additional superscripts indicating the type of percolation, that is, ${\pi_c^{{\rm bond}}}$ or ${\pi_c^{{\rm site}}}$.

For each n, the probability in this definition is taken with respect to $G_n^\pi$ – the random graph that results from percolation on a uniform simple random graph that obeys $(\textbf{d}^{n})_{n\in \mathbb{N}}$.

The following theorems determine the percolation threshold for the existence of the GSCC, and, if this threshold exists, they additionally identify the fraction of the vertices in this component for bond and site percolation. The theorems can be regarded as the extension of [16, Thm. 1.1] to digraphs.

Theorem 2.2. Consider progression $(\textbf{d}^{n})_{n\in \mathbb{N}}$ is proper and $\mu_{11} \gt \mu $, then the thresholds for the giant component in bond and site percolations are both equal to $ \pi_c = \frac{\mu}{\mu_{11}} \lt 1.$

Let $N_{{j},{k}}\left(n\right)$ be the number of vertices with in-/out-degree (j, k) in $G_n,$ and let $ p_{j,k}:=\lim\limits_{n \rightarrow \infty}\frac{N_{{j},{k}}\left(n\right)}{n} $ exist. Let additionally,

\begin{equation*}U_{\pi}^\text{bond}(x,y) := \sum\limits_{j,k\geq0} p_{j,k} (1-\pi +\pi x)^j (1-\pi +\pi y)^k,\end{equation*}

\begin{equation*}U_{\pi}^-(x) := \left(\pi \mu\right)^{-1}\,\frac{\partial}{\partial y}U_{\pi}^\text{bond}(x,y)|_{y=1}\quad \text{and} \quad U_{\pi}^+(y) := \left(\pi \mu\right)^{-1}\,\frac{\partial}{\partial x}U_{\pi}^\text{bond}(x,y)|_{x=1}\end{equation*}

be formal power series in x and y, having probability $\pi \in(0,1)$ as a parameter. Here $U_{\pi}^\text{bond}(x,y)$ can be interpreted as the generating function of the degree of a randomly chosen vertex, and $U_{\pi}^+(y)$ (correspondingly $U_{\pi}^-(x)$) – the generating function for the degree of a vertex at the end of randomly chosen in- (or out-) edge.

Theorem 2.3. If $(\textbf{d}^{n})_{n\in \mathbb{N}}$ is proper and $\pi \in( \pi_c,1),$ then for all ɛ > 0,

\begin{equation*} \lim\limits_{n \rightarrow \infty} \mathbb{P}\left[ \left|\frac{\left\lvert \mathcal{C}(G_{n}^{\pi})\right\rvert}{n} -c^{{\rm bond}} (\pi)\right|\geq\varepsilon\right] = 0 \end{equation*}

for bond percolation, and

\begin{equation*} \lim\limits_{n \rightarrow \infty} \mathbb{P}\left[\left|\frac{\left\lvert \mathcal{C}(G_{n}^{\pi})\right\rvert}{n} - c^{{\rm site}}(\pi)\right|\geq \varepsilon\right] = 0 \end{equation*}

for site percolation, with

\begin{equation*} c^{\rm{bond}}(\pi) = 1-U_{\pi}^{\rm{bond}}(x^*,1)-U_{\pi}^{\rm bond}(1,y^*)+U_{\pi}^{\rm bond}(x^*,y^*), \qquad c^{{\rm site}}(\pi) = \pi {c^{{\rm bond}}}(\pi) \end{equation*}

and $x^*,y^*$ being the smallest positive solutions of $x^*= U_{\pi}^-(x^*)$ and $y^*= U_{\pi}^+(y^*)$.

The remainder of the paper is structured as follows. Section 3 lays out the technical premise: Section 3.1 introduces different classes of degree progressions. Section 3.2 introduces the link between random digraphs and the directed configuration model by repurposing several theorems available for undirected graphs. Section 3.3 gives the definition of a GSCC and formulates Cai and Perarnau’s existence theorem, Theorem 3.11. In Section 3.4, we derive a concentration inequality, Theorem 3.13, enabling the proof of the main result. Section 4 proves Theorems 2.2 and 2.3 separately for the cases of bond and site percolation in, respectively, Sections 4.1 and 4.2. Both subsections have a similar structure: first, we show that the configuration model introduced in Section 3.2 can be used to study percolated digraphs; second, we find the degree distribution after percolation; third, we show that the corresponding degree progression is almost surely feasible in large graphs, and therefore the existence theory from Section 3.3 is applicable.

3. Random digraphs

3.1. Degree sequence, degree progression, and degree distribution

The degree sequence of a given digraph can be uniquely defined by adopting the lexicographic order, as demonstrated in, for example, [20]. Let $\mathcal{G}_{\textbf{d}^{n}}$ be the set of all directed multigraphs having degree sequence dⁿ. Since we are interested in sampling from $\mathcal{G}_{\textbf{d}^{n}}$, we want to be sure that for given dⁿ, $\mathcal{G}_{\textbf{d}^{n}} \neq \emptyset$. This is always the case for valid degree sequences.

Definition 3.1. A degree sequence dⁿ is called valid if $ m :=\sum_{i=1}^n {d^-_{i}} = \sum_{i=1}^n {d^+_{i}}, $ where $m=|E|$ is the number of edges in graph $G_{\textbf{d}^{n}}$.

If $\mathcal{G}_{\textbf{d}^{n}}$ contains a simple graph, dⁿ is called graphical, and Theorem 4 in [20] gives necessary and sufficient criteria for this property. Suppose dⁿ is graphical and let $G_{\textbf{d}^{n}}\in\mathcal{G}_{\textbf{d}^{n}}$ be a uniformly chosen simple digraph. To be on the safe side, we need to ensure that the subset of simple graphs in $\mathcal{G}_{\textbf{d}^{n}}$ is not vanishing for large n by imposing restrictions on the limiting behavior of dⁿ. Let

\begin{align*} d_{\max}(n) := \max \left\{\max\{{d^-_{1}}, {d^-_{2}}, \ldots, {d^-_{n}}\}, \max\{{d^+_{1}}, {d^+_{2}}, \ldots, {d^+_{n}}\}\right\} \end{align*}

be the largest degree in dⁿ for each index $n\in \mathbb{N}$. We will refer to this quantity as simply $d_{\max}$.

Definition 3.2. A degree progression $(\textbf{d}^{n})_{n\in \mathbb{N}}$ is called feasible if (1) all dⁿ are graphical, (2) the following limits exist yielding bivariate degree distribution $ p_{j,k}:= \lim\limits_{n \rightarrow \infty}({N_{{j},{k}}(n)})/{n}$ with finite partial moments up to order 2:

\begin{equation*} \mu_{ab}:=\lim\limits_{n\rightarrow \infty} \sum_{j,k=0}^\infty \frac{j^ak^bN_{{j},{k}}\left(n\right)}{n} = \sum_{j,k=0}^\infty j^ak^bp_{j,k}\in (0,\infty), \quad 0\leq a+b\leq2, \end{equation*}

and (3) $d_{\max} = \mathcal{O}\left(\sqrt{n}\right)$. Note that according to Definition 3.1, we have $\mu:=\mu_{10}=\mu_{01}$.

We refer to $p_{j,k}$ as the degree distribution of a feasible degree progression. The theorem of Cai and Perarnau [7] holds for feasible degree progressions. However, to show that the degree progression remains feasible after percolation, we need to narrow down the class of initial degree progressions further.

Definition 3.3. A feasible degree progression $(\textbf{d}^{n})_{n\in \mathbb{N}}$ is called proper if $d_{\max} \leq n^{\frac{1}{9}}$.

Thus far, we have defined a chain of classes for $(\textbf{d}^{n})_{n\in \mathbb{N}}$: valid $\supset$ graphical $\supset$ feasible $\supset$ proper, where the definitions of valid and graphical are extended from dⁿ to $(\textbf{d}^{n})_{n\in \mathbb{N}}$ element-wisely.

3.2. Directed configuration model

The behavior of simple random digraphs can be studied with the directed configuration model, as defined below.

Definition 3.4. Let dⁿ be a valid degree sequence. For all vertices enumerated with $ i \in [n]$, let the set of in-stubs ${W^{-}_{i}}$ consist of ${d^-_{i}}$ unique elements and the set out-stubs ${W^{+}_{i}}$ contains ${d^+_{i}}$ elements. Let ${W^{-}} = \cup_{i \in [n]} {W^{-}_{i}}$ and ${W^{+}} = \cup_{i \in [n]}{W^{+}_{i}}$. Then a configuration $\mathcal{M}$ is a random perfect bipartite matching of $W^{-}$ and $W^{+}$, that is a set of tuples (a, b) such that each tuple contains one element from $W^{-}$ and one from $W^{+}$ and each element of $W^{-}$ and $W^{+}$ appears in exactly one tuple.

A configuration $\mathcal{M}$ prescribes a matching between in-subs and out-stubs and hence defines a multigraph $\tilde{G}_{\textbf{d}^{n}}$ with vertex set $V = [n]$ and edge multiset

(4)\begin{align} E = [ (i,j) \mid {W^{+}_{i}} \ni a, {W^{-}_{j}} \ni b\ \text{and}\ (a,b) \in \mathcal{M} ]. \end{align}

Note that multiple configurations may correspond to the same graph. We will now study the probability that the configuration model generates a specific multigraph $\tilde{G}_{\textbf{d}^{n}}$.

Proposition 3.5. Let $\tilde{G}_{\textbf{d}^{n}}$ be a multigraph with degree sequence dⁿ and $\Upsilon_{i,j}$ be the multiplicity of edge (i, j) in $\tilde{G}_{\textbf{d}^{n}}$. Then it holds that

(5)\begin{align} \mathbb{P}\left[CM_{n}\left({\textbf{d}^n}\right) = \tilde{G}_{\textbf{d}^{n}}\right] = \frac{1}{m!}\frac{\prod_{i=1}^n {d^-_{i}}!\prod_{i=1}^n{d^+_{i}}!}{\prod_{1\leq i,j\leq n} \Upsilon_{i,j}!}. \end{align}

Proof. This proof is based on [27, Prop. 7.4] formulated for undirected graphs. There are $m!$ different configurations. As the configuration is chosen uniformly at random,

\begin{align*} \mathbb{P}\left[\text{CM}_{n}\left({\textbf{d}^n}\right) = \tilde{G}_{\textbf{d}^{n}}\right] = \frac{1}{m!}N\left(\tilde{G}_{\textbf{d}^{n}}\right), \end{align*}

with $N\left(\tilde{G}_{\textbf{d}^{n}}\right)$ being the number of distinct configurations inducing $\tilde{G}_{\textbf{d}^{n}}$. It follows from Eq. (4) that permuting the stub labels results in a different configuration that induces the same multigraph. There are $\prod_{i=1}^n {d^-_{i}}!\prod_{i=1}^n{d^+_{i}}!$ such permutations. For $a,a^\prime \in {W^{+}_{i}}$ and $ b,b^\prime \in {W^{-}_{j}}$ with $(a,b), (a^\prime,b^\prime) \in \mathcal{M}$, any permutation swapping a with aʹ and b with bʹ results in the same configuration. We compensate for this by a factor $\Upsilon_{i,j}!$ to obtain

\begin{equation*} N\left(\tilde{G}_{\textbf{d}^{n}}\right) = \frac{\prod_{i=1}^n {d^-_{i}}!\prod_{i=1}^n{d^+_{i}}!}{\prod_{1\leq i,j\leq n} \Upsilon_{ij}!}, \end{equation*}

Corollary 3.6. Conditional on the event that configuration model generates a simple digraph, an element of $\mathcal{G}_{\textbf{d}^{n}}$ is chosen uniformly.

Generally speaking, we are interested in the statements of the form

(6)\begin{equation} \lim_{n \rightarrow \infty} \mathbb{P}\left[ \tilde{G}_{\textbf{d}^{n}} \in \mathcal{A}\left({\textbf{d}^n}\right) \right] =1, \end{equation}

where $\mathcal{A}\left({\textbf{d}^n}\right)$ is the set of all graphs that obey the degree sequence dⁿ and additionally satisfy some desired property. If this limit holds for a given property $\mathcal{A}$, then we say that the random graph has this property w.h.p or asymptotically almost surely (a. almost surely). The goal of the remainder of this section is to show that if Eq. (6) holds, then

\begin{align*} \lim_{n \rightarrow \infty} \mathbb{P}\left[\tilde{G}_{\textbf{d}^{n}} \in \mathcal{A}\left({\textbf{d}^n}\right) \mid \tilde{G}_{\textbf{d}^{n}} \,\text{is simple}\right] =1. \end{align*}

First, we show that the probability that the configuration model generates a simple graph is bounded away from zero.

Proposition 3.7. Chen and Olvera-Cravioto [9, Thm. 4.3]

Let $(\textbf{d}^{n})_{n\in \mathbb{N}}$ be a feasible degree progression. The probability that the configuration model generates a simple graph is asymptotically ${\rm e}^{-\frac{\mu_{11}}{\mu} - \frac{\left(\mu_{20} -\mu \right)\left(\mu_{02}-\mu \right)}{\mu} } \gt 0. $

Proof. The proof follows from the proof of [9, Thm. 4.3]. It suffices to replace Condition 4.1 and Lemma 5.2 from Ref. [9] with the requirement of a feasible degree progression.

Lemma 3.8. Let $(\textbf{d}^{n})_{n\in \mathbb{N}}$ be a feasible degree progression, and let $\mathcal{A}\left({\textbf{d}^n}\right)$ be a set of multigraphs all satisfying dⁿ. Let $\tilde{G}_{\textbf{d}^{n}}$ be a random multigraph generated by the configuration model.

1. (1) If $ \lim\limits_{n \rightarrow \infty} \mathbb{P}\left[ \tilde{G}_{\textbf{d}^{n}} \in \mathcal{A}\left({\textbf{d}^n}\right)\right] =0, $ then $ \lim\limits_{n \rightarrow \infty} \mathbb{P}\left[\tilde{G}_{\textbf{d}^{n}} \in \mathcal{A}\left({\textbf{d}^n}\right) \mid \tilde{G}_{\textbf{d}^{n}} \,\textrm{ is simple}\right] =0. $

2. (2) If $ \lim\limits_{n \rightarrow \infty} \mathbb{P}\left[ \tilde{G}_{\textbf{d}^{n}} \in \mathcal{A}\left({\textbf{d}^n}\right)\right] =1, $ then $ \lim\limits_{n \rightarrow \infty} \mathbb{P}\left[\tilde{G}_{\textbf{d}^{n}} \in \mathcal{A}\left({\textbf{d}^n}\right) \big|\, \tilde{G}_{\textbf{d}^{n}} \,\textrm{ is simple}\right] =1. $

3.3. Giant strongly connected component in a directed graph

A natural definition of a path in a directed graph requires that a path respects edge directions:

Definition 3.9. Let $G=(V,E)$ be a digraph. A pair of vertices $v_1, v_k \in V$ is connected by a directed path if there are distinct vertices $v_2,v_3, \ldots ,v_{k-1} \in V$ such that for all $ i \in\{2,3,\ldots, k\},$ $\left(v_{i-1}, v_i\right) \in E$. We refer to such a sequence as a directed $v_1-v_k$ path.

This definition of connectivity can be extended to define connected components:

Definition 3.10. SCC of a directed graph $G=(V,E)$ is a maximal subset of $C\subset V$ such that for any $u,v \in C$, there are directed paths u − v and v − u.

Let $\mathcal{C} (G_n)$ be the largest SCC. The notion of a giant component is introduced as a limiting property of the sequence of $\mathcal{C} (G_n)$. Let $x^*,y^*$ be the smallest positive solutions of, respectively, $ x^*= U^-(x^*) $ and $ y^*= U^+(y^*) $, where

\begin{align*} U^+(y) & := \mu^{-1}\,\frac{\partial}{\partial x}U(x,y)|_{x=1},\\ U^-(x) & := \mu^{-1}\,\frac{\partial}{\partial y}U(x,y)|_{y=1}, \end{align*}

and $U\left( x, y \right) := \sum_{j,k=0}^{\infty} p_{j,k} {x}^j {y}^k $ is the generating function of $p_{j,k}$. Let further,

\begin{equation*} \zeta := 1-U(x^*,1)-U(1,y^*)+U(x^*,y^*). \end{equation*}

Theorem 3.11. (Existence of GSCC [7, Theorem 1.2])

Consider a feasible degree progression $(\textbf{d}^{n})_{n\in \mathbb{N}}$ and a uniformly random sequence of simple graphs $\left(G_{\textbf{d}^{n}}\right)_{n\in\mathbb{N}}$. Then,

1. (1) If ${\mu_{11}}/{\mu} \lt 1$, the size of any SCC is $\mathcal{O}\left(1\right)$ with high probability.

2. (2) If ${\mu_{11}}/{\mu} \gt 1$, then with high probability, the largest SCC has vertex set of size $|\mathcal{C}(G_n)|\sim\zeta n$.

3.4. Concentration inequality

We introduce a concentration inequality based on McDiarmid’s method of bounded differences, stated below. The inequality is used later in the proof of Theorem 2.2.

Theorem 3.12. [21, Theorem 7.4]

Let $\left(V,d\right)$ be a finite metric space. Suppose there exists a sequence $\mathcal{P}_0, \mathcal{P}_1, \ldots, \mathcal{P}_s$ of increasingly refined partitions, with $\mathcal{P}_0$ being the trivial partition consisting of V and $\mathcal{P}_s$ consisting of singletons. Take a sequence of positive integers $c_1, \ldots, c_s$ such that for all $k \in \{1,2,\ldots, s\}$, whenever $A,B \in \mathcal{P}_k$ and $A,B\subseteq C \in \mathcal{P}_{k-1}$ for some C, there exists a bijection $\phi: A \rightarrow B$ with $d\left(x,\phi(x)\right) \leq c_k$ for all $x \in A$. Let the function $f: V \rightarrow \mathbb{R}$ satisfy $\lvert f(x) - f(y) \rvert \leq d(x,y)$ for all $x,y,\in V$. Then, for X uniformly distributed over V and any t > 0,

\begin{align*} \mathbb{P}\left[\lvert f(X) - \mathbb{E}\left[f(X)\right] \rvert \gt t \right] \leq 2\, \exp\left(-\frac{2t^2}{\sum_{k=1}^s c_k^2}\right). \end{align*}

Theorem 3.13. Consider two finite sets A ₀ and A ₁ with $\lvert A_0 \rvert = a_0$ and $\lvert A_1\rvert = a_1$.

Let $ S:= \cup_{i \in \{0,1\}} \{(x,i) \mid x \in A_i\}$. A subset of S containing b ₀ elements with i = 0 and b ₁ elements with i = 1 is called a $\left(b_0,b_1\right)$-subset of S. Let V be the space of all $\left(b_0,b_1\right)$-subsets of S. Let $f: V \rightarrow \mathbb{R}$ be a function such that for any $B,B^\prime \in V$, it holds $\lvert\ f\left(B\right) - f\left(B^\prime\right)\rvert \leq \lvert B \triangle B^\prime \rvert $. Here, $B \triangle B^\prime$ denotes the symmetric difference, that is, $B \triangle B^\prime = \left(B\cup B^\prime\right) \setminus \left(B \cap B^\prime\right)$. Then, for X distributed uniformly over V and any t > 0,

(7)\begin{align} \mathbb{P}\left[ \left\lvert f(X) - \mathbb{E}\left[f(X)\right] \right\rvert \gt t\right] \leq 2\,\exp\left(-\frac{t^2}{8(b_0+b_1)}\right). \end{align}

Proof. Consider a $\left(b_0,b_1\right)$-subset of S. Assign each element a unique number from the index set $\{1,2,\ldots, b_0+b_1\}$ such that for all elements with i = 0, this number is at most b ₀. We call a $\left(b_0,b_1\right)$-subset of S with such a numbering a $\left(b_0,b_1\right)$-ordering of S. Define W to be the set of all $\left(b_0,b_1\right)$-orderings of S. The function $f: V\rightarrow \mathbb{R}$ naturally gives rise to a function $f:W \rightarrow \mathbb{R}$ by regarding each $\left(b_0,b_1\right)$-ordering as $\left(b_0,b_1\right)$-subset. Note that $\lvert f(x) - f(y)\rvert \leq x \triangle y$, that is, it holds for $x,y \in W$ as well. This is true since for any two orderings $x,y$, their symmetric difference as $\left(b_0,b_1\right)$-orderings is bounded from below by their symmetric difference as $\left(b_0,b_1\right)$-subsets. The next step in proving Eq. (7) is applying Theorem 3.12 to the metric space $\left(W, \triangle \right)$.

We will now define a sequence of refined partitions on W using the notion of an i-prefix. An i-prefix determines the first i elements of an ordering. This allows for all $k \in \{0,1,\ldots, b_0+b_1\}$ to construct the partition $\mathcal{P}_k$ by defining its elements to be the sets of orderings with the same k-prefix. The partition $\mathcal{P}_0$ is the trivial partition consisting of W. The partition $\mathcal{P}_{b_0+b_1}$ will be the partition where each element is a single ordering. Next, the values c _k need to be determined for $k \in \{1,2,\ldots , b_0+b_1\}$. Take $B,D \in \mathcal{P}_k$ with C satisfying $B,D\subset C \in \mathcal{P}_{k-1}$. This implies that any ordering in B has the same k − 1-prefix as an ordering in D. Furthermore, these orderings must differ at the kth element. The remaining $b_0+b_1-k$ elements can be any element that is not present in the k-prefix that leads to a valid ordering. Denote the kth element of any ordering in B by $a_{B,k}$. Similarly, let $a_{D,k}$ denote the kth element of any ordering in D. Define the bijection $\phi: B \rightarrow D$ by taking $x \in B$ and mapping its kth element to $a_{D,k}$. If x contains $a_{D,k}$ at some position l > k, map the lth element of x to $a_{B,k}$. All the other elements are unchanged by the bijection. By definition, this is an element of D.

According to the definition of ϕ, for any $x \in B$, we have $\lvert x \triangle \phi(x) \rvert \leq 4$. Thus, we may take $c_k = 4$ for all $k \in \{1,2,\ldots , b_0+b_1\}$. Applying Theorem 3.12, we find that Eq. (7) holds for any t > 0 and X distributed uniformly over W. Remark that each element in V gives rise to $b_0!+b_1!$ different orderings. All these orderings have the same value under f. Thus, the probability that $f(X) = c$ does not change when we take X to be a uniformly random element of V instead of W. Together with Eq. (7) being valid for a X uniformly random element of W, this proves the claim.

4. Proofs of Theorems 2.2 and 2.3

Theorems 2.2 and 2.3 are proven separately for bond and site percolation using similar techniques as in the proof of [16, Theorem 1.1], which determines the percolation threshold in undirected graphs. Although these theorems are formulated for simple digraphs, we instead prove the statements on random directed multigraphs introduced in Section 3.2. The results on the multigraphs are then transferred to simple digraphs using Lemma 3.8. After percolation with probability π, dⁿ becomes a random variable ${\textbf{D}_{\pi}^n}$, which will be considered separately for bond and site percolation.

4.1. Bond percolation

Bond percolation removes edges in a graph, thus in the configuration, it removes in-stubs together with their matched out-stubs. Let ${W^{-,\pi}}$ and ${W^{+,\pi}}$ denote the in-stubs and out-stubs surviving percolation. Given that the degree sequence after percolation is fixed, ${\textbf{D}_{\pi}^n} = {\textbf{d}^{n}_{\pi}}$, there is a bijection between the configurations on the surviving stubs $\left({W^{-,\pi}},{W^{+,\pi}}\right)$ and the configurations on the stubs of ${\textbf{d}^{n}_{\pi}}$, which we denote $\left({W^{-}_{\textbf{d}^{n}_{\pi}}}, {W^{+}_{\textbf{d}^{n}_{\pi}}}\right)$. Let us fix such a bijection. Now, to show that the perfect matching on the remaining stubs (conditional on the degree sequence after percolation) is uniformly distributed on the set of perfect matchings on the stubs that survive percolation, it is sufficient to show that perfect matchings on $\left({W^{-}_{\textbf{d}^{n}_{\pi}}}, {W^{+}_{\textbf{d}^{n}_{\pi}}}\right)$ appear equally likely. Let $\mathcal{D}_{n}$ be the probability space containing all degree sequences ${\textbf{d}^{n}_{\pi}}$ that can be obtained by applying percolation to a random configuration on $\left({W^{-}}, {W^{+}} \right)$. The probability assigned to each ${\textbf{d}^{n}_{\pi}}$ is the probability that it is induced by $\left({W^{-,\pi}},{W^{+,\pi}}\right)$. The probability space for the degree progression $\left({\textbf{d}^{n}_{\pi}}\right)_{n \in \mathbb{N}}$ is the product space $\mathcal{D} = \prod_{n=1}^\infty \mathcal{D}_{n}$ with the product measure ν.

The remainder of this section is as follows: in Section 4.1.1, we show that conditional on the degree sequence after percolation, each configuration on ${W^{-}_{\textbf{d}^{n}_{\pi}}}$ and ${W^{+}_{\textbf{d}^{n}_{\pi}}}$ is equally likely. In Section 4.1.2, we determine the limit of the expected number of vertices with degree (j, k) after percolation and show the concentration. Combining these results in Section 4.1.3, the proofs of Theorems 2.2 and 2.3 are completed by showing that an element of $\mathcal{D}$ is ν- almost surely feasible, which authorizes applying Theorem 3.11.

4.1.1. A percolated configuration is a uniformly random configuration

In this section, we show that conditional on the degree sequence after percolation, the configuration on $\left({W^{-,\pi}},{W^{+,\pi}}\right)$ is also a uniformly random one. The proof is split into two lemmas.

Lemma 4.1. Apply bond percolation to a uniformly random configuration $\mathcal{M}$ on $\left({W^{-}}, {W^{+}} \right)$. Conditional on the elements of $\left({W^{-,\pi}},{W^{+,\pi}}\right)$, each configuration on these elements is equally likely.

Proof. Choosing the elements of $\left({W^{-,\pi}},{W^{+,\pi}}\right)$ implies that the configuration $\mathcal{M}$ is the union of a configuration on $\left( {W^{-}} \setminus {W^{-,\pi}}, {W^{+}} \setminus {W^{+,\pi}}\right)$ with one on $\left({W^{-,\pi}},{W^{+,\pi}}\right)$. As $\mathcal{M}$ is a uniformly random configuration obeying this split and the elements of $\left({W^{-,\pi}},{W^{+,\pi}}\right)$ are fixed, the configuration on $\left({W^{-,\pi}},{W^{+,\pi}}\right)$ will be a uniformly random one.

Lemma 4.2. Conditional on having degree sequence ${\textbf{d}^{n}_{\pi}}$ after bond percolation, that is, ${\textbf{D}_{\pi}^n} = {\textbf{d}^{n}_{\pi}}$, all configurations of ${W^{-}_{\textbf{d}^{n}_{\pi}}}$ with ${W^{+}_{\textbf{d}^{n}_{\pi}}}$ are equally likely.

Proof. Define $l = \lvert {W^{-, \pi}} \rvert$ and let $S({\textbf{d}^{n}_{\pi}})$ contain all sets of surviving stubs $\left({W^{-,\pi}},{W^{+,\pi}}\right)$ that induce the degrees sequence ${\textbf{d}^{n}_{\pi}}$. Fix a matching $\mathcal{M}^{\pi}$ of $\left({W^{-}_{\textbf{d}^{n}_{\pi}}}, {W^{+}_{\textbf{d}^{n}_{\pi}}}\right)$. Then, using the bijection between $\left({W^{-,\pi}}, {W^{+,\pi}}\right)$ and $\left({W^{-}_{\textbf{d}^{n}_{\pi}}}, {W^{+}_{\textbf{d}^{n}_{\pi}}}\right)$,

\begin{align*} \mathbb{P}\left[\mathcal{M}^{\pi} | {\textbf{D}_{\pi}^n} = {\textbf{d}^{n}_{\pi}}\right] = \sum_{\left(A,B\right)\in S({\textbf{d}^{n}_{\pi}})} & \mathbb{P}\left[\mathcal{M}^{\pi} | {\textbf{D}_{\pi}^n} = {\textbf{d}^{n}_{\pi}}, \left({W^{-,\pi}}, {W^{+,\pi}}\right) = \left(A,B\right) \right] \times \\ &\mathbb{P}\left[ \left({W^{-,\pi}}, {W^{+,\pi}}\right) = \left(A,B\right)| {\textbf{D}_{\pi}^n} = {\textbf{d}^{n}_{\pi}} \right]. \end{align*}

Remark that $\mathbb{P}\left[\mathcal{M}^{\pi} | {\textbf{D}_{\pi}^n} = {\textbf{d}^{n}_{\pi}}, \left({W^{-,\pi}}, {W^{+,\pi}}\right) = \left(A,B\right) \right] = \mathbb{P}\left[\mathcal{M}^{\pi} | \left({W^{-,\pi}}, {W^{+,\pi}}\right) = \left(A,B\right) \right]$ by definition of $S({\textbf{d}^{n}_{\pi}})$. Using Lemma 4.1, we find

\begin{equation*}\mathbb{P}\left[\mathcal{M}^{\pi} | \left({W^{-,\pi}}, {W^{+,\pi}}\right) = \left(A,B\right) \right] = \frac{1}{l!}.\end{equation*}

Furthermore, combining these observations with

\begin{equation*}\sum_{\left(A,B\right)\in S({\textbf{d}^{n}_{\pi}})} \mathbb{P}\left[\left({W^{-,\pi}}, {W^{+,\pi}}\right)= \left(A,B\right) | {\textbf{D}_{\pi}^n} = {\textbf{d}^{n}_{\pi}} \right] = 1\end{equation*}

following from the definition of $S({\textbf{d}^{n}_{\pi}})$, we obtain

\begin{align*} \mathbb{P}\left[\mathcal{M}^{\pi} | {\textbf{D}_{\pi}^n} = {\textbf{d}^{n}_{\pi}}\right] &= \frac{1}{l!} \sum_{\left(A,B\right)\in S({\textbf{d}^{n}_{\pi}})} \mathbb{P}\left[ \left({W^{-,\pi}}, {W^{+,\pi}}\right) = \left(A,B\right)| {\textbf{D}_{\pi}^n} = {\textbf{d}^{n}_{\pi}} \right] = \frac{1}{l!}, \end{align*}

completing the proof.

4.1.2. The expected number of vertices with degree (j, k) after bond percolation

In this section, we derive an expression for the degree distribution after bond percolation. This uses the following auxiliary lemma.

Lemma 4.3. Let l out of m edges survive bond percolation applied to a uniformly random configuration $\mathcal{M}$ on $\left({W^{-}}, {W^{+}} \right)$. Then the surviving stubs ${W^{-, \pi}} {\subset} {W^{-}}$ and ${W^{+, \pi}} \subset {W^{+}}$ are uniformly distributed among all pairs of subsets of $W^{-}$ and $W^{+}$ of size l.

Proof. The graph contains m matches of which $l=\lvert {W^{-, \pi}} \rvert = \lvert {W^{+, \pi}} \rvert $ survive percolation. Thus, the probability that l matches remain is $\frac{1}{{m \choose l}}$. It is left to investigate the probability that all stubs in ${W^{-,\pi}}$ have their match in ${W^{+,\pi}}$, that is, that $\mathcal{M}$ can be decomposed into a perfect bipartite matching of ${W^{-,\pi}}$ with ${W^{+,\pi}}$ and a perfect bipartite matching of ${W^{-}} \setminus {W^{-, \pi}} $ with ${W^{+}} \setminus {W^{+, \pi}} $. Between two sets of size l, there are $l!$ perfect bipartite matchings; hence, the probability that $\mathcal{M}$ decomposes as desired is $l!(m-l)! / m!$. Thus, the probability that $\left({W^{-,\pi}}, {W^{+,\pi}}\right)$ are the stubs surviving percolation is $ \frac{l!\, (m-l)!}{m!}\frac{1}{{m\choose l}} = \frac{1}{{m\choose l}^2}. $ This is the probability that ${W^{-, \pi}} \!\subset{W^{-}}$ and ${W^{+, \pi}}\!\subset{W^{+}}$ are uniformly random subsets both of size l.

Lemma 4.4. Let $N_{{j},{k}}^{\pi}\left(n\right)$ be the number of vertices in the bond-percolated graph (or configuration) with in-degree j and out-degree k. The following limit exists

(8)\begin{align} {p^{{\rm bond}}_{{j}, {k}}}:=\lim_{n\rightarrow \infty} \frac{\mathbb{E}\left[N_{{j},{k}}^{\pi}\left(n\right)\right]}{n} \quad \text{for } j,k\in\mathbb{N}_0 \end{align}

and

(9)\begin{align} {p^{{\rm bond}}_{{j}, {k}}} = \sum_{d^- = j}^\infty \sum_{d^+ = k}^\infty p_{d^-,d^+} {d^- \choose j}{d^+ \choose k}\pi^{j+k}\left(1-\pi \right)^{d^- - j + d^+ -k}. \end{align}

Proof. When $j,k \gt d_{\max}$, ${p^{{\rm bond}}_{{j}, {k}}}=N_{{j},{k}}^{\pi}\left(n\right)=N_{{j},{k}}\left(n\right) = 0$. Let $j,k \leq d_{\max}$ and remark that

(10)\begin{align} \mathbb{E}\left[N_{{j},{k}}^{\pi}\left(n\right)\right] = \sum_{l=0}^m \mathbb{E}\left[N_{{j},{k}}^{\pi}\left(n\right)| \lvert {W^{-, \pi}} \rvert = l\right]\mathbb{P}\left[\lvert {W^{-, \pi}} \rvert = l\right], \end{align}

which, when conditioned on $\lvert{W^{-, \pi}} \rvert = l$, can be rewritten as

\begin{align*} \mathbb{E}\left[N_{{j},{k}}^{\pi}\left(n\right)| \lvert {W^{-, \pi}} \rvert = l\right] = \sum_{d^- =j}^{d_{\max}} \sum_{d^+ = k}^{d_{\max}} N_{{d^-},{d^+}}\left(n\right)\mathbb{P}\left[ (d^-,d^+) \to (j, k)\,| \lvert {W^{-, \pi}} \rvert = l\right], \end{align*}

where event $(d^-,d^+)\to (j,k)$ is a shorthand for a vertex of degree $(d^-,d^+)$ has degree (j, k) after percolation. Since Lemma 4.3 implies that the surviving stubs are chosen uniformly at random, conditional on $|{W^{-, \pi}} |$, we have

\begin{align*} \mathbb{P}\left[ (d^-,d^+) \to(j, k)| \lvert {W^{-, \pi}} \rvert = l\right]= {d^- \choose j}\frac{{{m-d^-} \choose {l-j}}}{{m \choose l}} {d^+ \choose k} \frac{{{m-d^+} \choose {l-k}}}{{m \choose l}}. \end{align*}

The edges are removed independently of each other; hence, $|{W^{-, \pi}} |$ is the sum of m independent Bernoulli variables, each having expectation π. Let

(11)\begin{equation} I_n := \left[ m\pi - \ln n\sqrt{n}, m\pi + \ln n\sqrt{n}\right], \end{equation}

applying Hoefdding’s inequality shows that $\lvert {W^{-, \pi}} \rvert$ concentrates

(12)\begin{align} \mathbb{P}\left[ \lvert {W^{-, \pi}} \rvert \notin I_n\right] \leq \exp\left[-\Omega (\ln^2n)\right]. \end{align}

Note that as an immediate consequence of this inequality, we have $\mathbb{P}\left[l \notin I_n\right] = o\left(n^\alpha\right)$ for any α < 0. Therefore, we have

\begin{align*} \mathbb{P}\left[ (d^-,d^+) \to(j,k)| \lvert {W^{-, \pi}} \rvert = l\right] = {{d^-}\choose{j}} {{d^+}\choose{k}} \pi^{j+k}\left(1-\pi \right)^{d^- + d^+ - j - k}\left(1 + \mathcal{O}\left(\frac{\ln n}{n^{7/18}}\right)\right), \end{align*}

uniformly for all $d^-,d^+ \leq d_{\max}\leq n^{\frac{1}{9}}$ and $l \in I_n$. In combination with Eq. (10) and the bound $N_{{j},{k}}^{\pi}\left(n\right) \leq n$, we find

(13)\begin{align} \mathbb{E}\left[N_{{j},{k}}^{\pi}\left(n\right)\right] &= \left(1 +\mathcal{O}\left(\frac{\ln n}{n^{7/18}}\right)\right)\sum_{d^-=j}^{d_{\max}} \sum_{d^+=k}^{d_{\max}} N_{{d^-},{d^+}}\left(n\right) {{d^-}\choose{j}} {{d^+}\choose{k}} \pi^{j+k}\left(1-\pi \right)^{d^- + d^+ - j - k} +o\left(\frac{1}{n^3}\right), \end{align}

where we set α = 5 in the estimate for $\mathbb{P}\left[l \notin I_n\right] $ when calculating the error term. We will now show that for all ϵ > 0, there exist $\kappa\left(\epsilon\right)$ and $N\left(\epsilon\right)$ such that for all $n \gt N,$

(14)\begin{align} \frac{1}{n} \sum_{{\substack{(d^-,d^+) = (j,k)\\ d^- \geq \kappa +1\, {\rm or}\, d^+ \geq \kappa +1}}}^{(d_{\max}, d_{\max})} N_{{d^-},{d^+}}\left(n\right) {{d^-} \choose j} {{d^+} \choose k} \pi^{j+k}\left(1-\pi \right)^{d^- + d^+ -j -k} \leq \frac{1}{n} \sum_{{\substack{(d^-,\ d^+) = (j,k)\\ d^- \geq \kappa +1 \,{\rm or}\, d^+ \geq \kappa +1}}}^{(d_{\max}, d_{\max})} N_{{d^-},\ {d^+}}\left(n\right) \lt \epsilon . \end{align}

The left inequality follows from the binomial theorem, and the right – since $\lim\limits_{n\rightarrow \infty}\frac{N_{{j},{k}}\left(n\right)}{n} = p_{j,k}$ for $j,k \geq 0$ and $(p_{j,k})$ is a probability distribution, which follows from the degree progression being proper. When combined together, Eqs. (13) and (14) prove the claim.

Elementary calculations show that ${p^{\text{bond}}_{{j}, {k}}}$ is a probability distribution and has the following moments:

(15)\begin{equation} \begin{aligned} \mu^{\pi, \text{bond}}:=&\sum_{j=0}^\infty \sum_{k=0}^\infty j{p^{\text{bond}}_{{j}, {k}}} = \sum_{j=0}^\infty \sum_{k=0}^\infty k{p^{\text{bond}}_{{j}, {k}}} =\pi \mu,\\ \mu_{11}^{\pi, \text{bond}}:=&\sum_{j,k=0}^\infty jk{p^{\text{bond}}_{{j}, {k}}} = \pi^2\sum_{d^-=0}^\infty \sum_{d^+=0}^\infty d^{-}d^{+}p_{d^-,d^+} = \pi^2 \mu_{11}. \end{aligned} \end{equation}

The generating function $U_{\pi}^\text{bond}$ of ${p^{\text{bond}}_{{j}, {k}}}$ and auxiliary functions $U^+_{\pi},U^-_{\pi}$ analogous to those used in Section 3.3 are given by

(16)\begin{equation} \begin{aligned} &U_{\pi}^\text{bond}(x,y) := U(1-\pi +\pi x,1-\pi +\pi y),\\ & U^+_{\pi}(x):=U^+(1-\pi +\pi x),\\ &U^-_{\pi}(y):=U^-(1-\pi +\pi y). \end{aligned} \end{equation}

The moments (15) and generating functions (16) provide sufficient information for applying Theorem 3.11 to ${p^{\text{bond}}_{{j}, {k}}}$ and hence formally defining the percolation threshold as such a value of $\pi =\hat{\pi}^{\text{bond}}$ that $\mu^{\pi, \text{bond}}= \mu_{11}^{\pi, \text{bond}}$, that is

\begin{align*} \hat{\pi}^{\text{bond}} = \frac{\mu}{\mu_{11}}. \end{align*}

In the following section, we will show that this quantity is indeed the desired threshold for bond percolation, ${\pi_c^{\text{bond}}}=\hat{\pi}^{\text{bond}}$. To this end, we show that ${p^{\text{bond}}_{{j}, {k}}}$ is indeed ν-a.s the limit of the degree distribution of the percolated graph, which itself is a configuration model with the percolated degree sequence.

4.1.3. Determining $\pi_{c}^{{\rm bond}}$ and $c^{{\rm bond}}$

We make use of Lemma 4.2, stating that instead of actually removing edges, one may view the percolated multigraph $\tilde{G}_{\textbf{d}^{n}}^{\pi}$ as a uniformly random configuration obeying the percolated degree sequence ${\textbf{d}^{n}_{\pi}}$. We show that $\left({\textbf{d}^{n}_{\pi}}\right)_{n \in \mathbb{N}}$ is indeed ν- almost surely feasible (Lemma 4.5) and hence, Theorem 3.11 is applicable to $\left(\tilde{G}_{\textbf{d}^{n}}^{\pi}\right)_{n \in \mathbb{N}}$. This means that Theorem 3.11 may be applied to almost all degree progressions $\left({\textbf{d}^{n}_{\pi}}\right)_{n \in \mathbb{N}}$ to determine ${\pi_c^{\text{bond}}}$ and c ^bond for random multigraphs. Conditioning on the graph before percolation being simple will ensure that the percolated graph is simple as well. Finally, we apply a variant of Lemma 3.8 and show that similar assertions hold for a graph progression $\left(G_{n}^{\pi}\right)_{n \in \mathbb{N}}$ for percolated simple graphs obeying $(\textbf{d}^{n})_{n\in \mathbb{N}}$, hence proving Theorem 2.3 for the case of bond percolation. In the remainder of this section, we make the above-stated argument formal.

Lemma 4.5. The degree progression after bond percolation is feasible ν- almost surely

Proof. By definition, sequence $\left({\textbf{d}^{n}_{\pi}}\right)_{n \in \mathbb{N}}$ is graphical. We need to show that it also satisfies the other requirements of Definition 3.2 ν- almost surely. To demonstrate that

(17)\begin{align} \lim_{n\rightarrow \infty} \frac{N_{{j},{k}}^{\pi}\left(n\right)}{n} = {p^{{\rm bond}}_{{j}, {k}}},\; \nu\mathrm{-a.s. }\quad {\rm for\ } j,k\in \mathbb{N}_0, \end{align}

it suffices to show (see, e.g., [25, Lemma 6.8]) that for all $\epsilon \gt 0,$

(18)\begin{align} \sum_{n=1}^\infty \mathbb{P}\left[\left\lvert \frac{1}{n}N_{{j},{k}}^{\pi}\left(n\right) - {p^{{\rm bond}}_{{j}, {k}}}\right\rvert \gt \epsilon\right] \lt \infty. \end{align}

By definition of ${p^{{\rm bond}}_{{j}, {k}}},$ for any fixed ϵ > 0, there is K such that for all n > K

\begin{align*} \left\lvert \frac{1}{n}\mathbb{E}\left[N_{{j},{k}}^{\pi}\left(n\right)\right] - {p^{{\rm bond}}_{{j}, {k}}} \right\rvert \leq \frac{\epsilon}{2}. \end{align*}

This implies that

\begin{align*} \mathbb{P}\left[\left\lvert \frac{1}{n}N_{{j},{k}}^{\pi}\left(n\right) - {p^{{\rm bond}}_{{j}, {k}}}\right\rvert \gt \epsilon\right] \leq \mathbb{P}\left[\frac{1}{n}\left\lvert N_{{j},{k}}^{\pi}\left(n\right) - \mathbb{E}\left[N_{{j},{k}}^{\pi}\left(n\right)\right] \right \rvert \gt \frac{\epsilon}{2}\right]. \end{align*}

Lemma 4.3 states that conditional on $\lvert {W^{-, \pi}} \rvert =l$, the stubs surviving percolation $\left({W^{-,\pi}}, {W^{+,\pi}}\right)$ are uniformly distributed among all pairs of subsets of $\left({W^{-}},{W^{+}} \right)$ of size l. $N_{{j},{k}}^{\pi}\left(n\right)$ is a function of ${W^{-, \pi}} \cup {W^{+, \pi}} $. Furthermore, for two sets ${W^{-, \pi}} \cup {W^{+, \pi}} $ and ${W^{'-, \pi}} \cup {W^{'+, \pi}} $, their values of $N_{{j},{k}}^{\pi}\left(n\right)$ differ by at most the number of elements in their symmetric difference. This implies that the requirements of Theorem 3.13 are fulfilled by setting $A_0 = {W^{-}},\ A_1= {W^{+}}{,}\ b_0=b_1=l$, and $N_{{j},{k}}^{\pi}\left(n\right)$ as function f. Applying this theorem gives

\begin{align*} \mathbb{P}\left[\left\lvert N_{{j},{k}}^{\pi}\left(n\right) - \mathbb{E}\left[N_{{j},{k}}^{\pi}\left(n\right)\right] \right\rvert \gt \frac{n\epsilon}{2} \,\vert\, \lvert {W^{-, \pi}} \rvert = l\right] \leq 2\,\exp\left(-\frac{{\epsilon}^2n^2}{64l^2}\right). \end{align*}

For $l \in I_n$, defined in Eq. (11), this probability is $o\left(\frac{1}{n^3}\right)$. By Eq. (12), the probability that $l \notin I_n$ is $o\left(\frac{1}{n^3}\right)$. Combining these observations, we find that for all ϵ > 0, the terms in Eq. (18) are vanishing:

(19)\begin{align} \mathbb{P}\left[\left\lvert N_{{j},{k}}^{\pi}\left(n\right) - \mathbb{E}\left[N_{{j},{k}}^{\pi}\left(n\right)\right] \right\rvert \gt n\epsilon\right] = o\left(\frac{1}{n^3}\right), \end{align}

which in turn proves that the limit in Eq. (17) holds ν- almost surely

It remains to show that the first, first mixed and second moments of $\frac{N_{{j},{k}}^{\pi}\left(n\right)}{n}$ converge ν- almost surely to those of ${p^{{\rm bond}}_{{j}, {k}}}$. In Section 4.1.2, we showed that $\sum_{j,k=0}^\infty j {p^{{\rm bond}}_{{j}, {k}}}= \sum_{j,k=0}^\infty k {p^{{\rm bond}}_{{j}, {k}}}$, and due to the graph context of the problem, $\sum_{j,k=0}^\infty j N_{{j},{k}}^{\pi}\left(n\right) = \sum_{j,k=0}^\infty k N_{{j},{k}}^{\pi}\left(n\right)$. Therefore, it is sufficient to show that only one of the first moments converges. Define $Q_n^\prime:= \frac{1}{n}\sum_{j,k=0}^\infty j N_{{j},{k}}^{\pi}\left(n\right)$, we will then show that $ Q:=\lim_{n \rightarrow \infty} Q_n^\prime=\pi \mu,\; \nu\text{-a.s.} $ Let $ X_{\kappa,n} := \frac{1}{n}\sum_{j=0}^{\kappa}\sum_{k=0}^{\kappa} j N_{{j},{k}}^{\pi}\left(n\right) $ and remark that $X_{\kappa,n} \leq Q_n^\prime$. Since $(\textbf{d}^{n})_{n\in \mathbb{N}}$ is a proper degree progression, for all ϵ > 0, there exists $\widetilde{\kappa}\left(\epsilon\right), \tilde m\left(\epsilon\right)$ such that for all $ \kappa \gt \widetilde{\kappa}$ and $n \gt \tilde m$

(20)\begin{align} \frac{1}{n} \sum_{{\substack{(j,k) = (0,0),\\ j \gt \kappa \,{\rm or}\, k \gt \kappa}}}^{(d_{\max}, d_{\max})} jN_{{j},{k}}\left(n\right) \lt \epsilon. \end{align}

Thus, for $\kappa \gt \widetilde{\kappa}$, we have $ X_{\kappa,n} \leq Q_n^\prime \leq X_{\kappa,n} + \epsilon$. This implies that if

(21)\begin{align} \tilde{X}_{\kappa}:=\lim_{n\rightarrow \infty } X_{\kappa,n} = \sum_{j=0}^{\kappa}\sum_{k=0}^{\kappa} j{p^{{\rm bond}}_{{j}, {k}}} , \; \nu-\text{a.s.}, \end{align}

then $\lim\limits_{n\rightarrow \infty } Q_n^\prime = Q$ holds ν- almost surely as well [16, (3.5)]. Thus, the goal is to prove Eq. (21). Applying [25, Lemma 6.8], we can show that this limit holds ν- almost surely, if for any ϵ > 0,

(22)\begin{align} \sum_{n=1}^\infty \mathbb{P}\left[\left\lvert X_{\kappa,n} - \tilde{X}_{\kappa} \right \rvert \gt \epsilon\right] \lt \infty. \end{align}

We show this analogously to the proof of Eq. (18). By the definition of $ X_{\kappa,n}$, $\tilde{X}_{\kappa}$, and ${p^{{\rm bond}}_{{j}, {k}}}$, for all ϵ > 0, there exists $\widetilde{N}$ such that for all $n \gt \widetilde{N}$, $ \left\lvert \mathbb{E}\left[X_{\kappa,n}\right] - \tilde{X}_{\kappa} \right\rvert \lt \frac{\epsilon}{2}. $ Combining this with the reverse triangle inequality, we find for any ϵ > 0,

\begin{align*} \mathbb{P}\left[\left\lvert X_{\kappa,n} - \tilde{X}_{\kappa} \right \rvert \gt \epsilon\right] \leq \mathbb{P}\left[\left\lvert X_{\kappa,n} - \mathbb{E}\left[X_{\kappa,n}\right] \right \rvert \gt \frac{\epsilon}{2}\right]. \end{align*}

Remark that $ \left\lvert X_{\kappa,n} - \mathbb{E}\left[X_{\kappa,n}\right] \right \rvert = \frac{1}{n}\sum_{j=0}^\kappa \sum_{k=0}^\kappa j \left(N_{{j},{k}}^{\pi}\left(n\right) - \mathbb{E}\left[N_{{j},{k}}^{\pi}\left(n\right)\right] \right). $ This implies that for $\epsilon^\prime = \frac{\epsilon}{2\sum_{j \leq \kappa}j}$,

\begin{align*} \mathbb{P}\left[\left\lvert X_{\kappa,n} - \mathbb{E}\left[X_{\kappa,n}\right] \right \rvert \gt \frac{\epsilon}{2}\right] \leq \sum_{j\leq \kappa, k \leq \kappa} \mathbb{P}\left[\frac{1}{n}\lvert N_{{j},{k}}^{\pi}\left(n\right) - \mathbb{E}\left[N_{{j},{k}}^{\pi}\left(n\right)\right] \rvert \gt \epsilon '\right]. \end{align*}

Using Eq. (19), we find $ \mathbb{P}\left[\left\lvert X_{\kappa,n} - \mathbb{E}\left[X_{\kappa,n}\right] \right \rvert \gt \frac{\epsilon}{2}\right] \leq \sum_{j\leq \kappa, k \leq \kappa} o\left(\frac{1}{n^3}\right) \leq o\left(\frac{1}{n^{\frac{25}{9}}}\right). $ Here we used the fact that $d_{\max} = O\left(n^{1/9}\right)$ and that $N_{{j},{k}}^{\pi}\left(n\right) = \mathbb{E}\left[N_{{j},{k}}^{\pi}\left(n\right)\right]=0$ when $j \gt d_{\max}$ or $k \gt d_{\max}$ or both. This proves Eq. (22) and hence proves that $Q_n^\prime$ converges ν- almost surely to Q. Similar derivations hold for the first mixed moment and the second moments. That is, all the moments of interest and the distribution itself converge simultaneously ν- almost surely for an element of $\mathcal{D} $. Thus, we have shown that $\left({\textbf{d}^{n}_{\pi}}\right)_{n \in \mathbb{N}}$ is ν- almost surely feasible.

Let $E \subset \mathcal{D} $ be the event over which the degree progression is feasible. Since any element of $\mathcal{D} $ is ν- almost surely feasible, we have $\nu\left(E\right) =1$. For any $\left({\textbf{d}^{n}_{\pi}}\right)_{n \in \mathbb{N}} \in E$, we may apply Theorem 3.11 to a sequence of random multigraphs $\left(\tilde{G}_{\textbf{d}^{n}}^{\pi}\right)_{n \in \mathbb{N}}$ arising from uniformly random configurations. Lemma 4.2 states that if we condition ${\textbf{D}_{\pi}^n} = {\textbf{d}^{n}_{\pi}}$, Theorem 3.11 is applicable for all n. We will now fix $\left({\textbf{d}^{n}_{\pi}}\right)_{n \in \mathbb{N}} \in E$ and apply Theorem 3.11 to $\left(\tilde{G}_{\textbf{d}^{n}}^{\pi}\right)_{n \in \mathbb{N}}$, distinguishing two cases for π: $ \pi \lt \hat{\pi}^{\text{bond}}$ and $ \pi \gt \hat{\pi}^{\text{bond}}$, with $\hat{\pi}^{\text{bond}} = \frac{\mu}{\mu_{11}}$.

Let $ \pi \lt \hat{\pi}^{\text{bond}}$ and pick $\epsilon \in (0,1)$. Define $\mathcal{A}_{\epsilon}\left({\textbf{d}^{n}_{\pi}}\right)$ to be the set of all multigraphs obeying ${\textbf{d}^{n}_{\pi}}$ for which the largest SCC contains no more than $\epsilon n$ vertices. As $\frac{\mu_{11}^{\pi}}{\mu^{\pi}} = \pi \frac{\mu_{11}}{\mu} \lt 1$, Theorem 3.11 states that for all ϵ:

(23)\begin{align} \lim_{n \rightarrow \infty} \mathbb{P}\left[\tilde{G}_{\textbf{d}^{n}}^{\pi} \in \mathcal{A}_{\epsilon}\left({\textbf{d}^{n}_{\pi}}\right) \,\vert\, {\textbf{D}_{\pi}^n} = {\textbf{d}^{n}_{\pi}}\right] = 1. \end{align}

Next consider $ \pi \gt \hat{\pi}^{\text{bond}}$. Define $\mathcal{B}_{\theta}\left({\textbf{d}^{n}_{\pi}}\right)$ to be the set of all graphs whose largest SCC has size in $((\theta - \varepsilon) n,(\theta + \varepsilon) n)$, with $\theta \in (0,1)$ and any vanishing ɛ. Since $\frac{\mu_{11}^{\pi}}{\mu^{\pi}} = \pi \frac{\mu_{11}}{\mu} \gt 1$, Theorem 3.11 states that there exists a unique $\theta=c^{\text{bond}}$ such that

(24)\begin{align} \lim_{n \rightarrow \infty} \mathbb{P}\left[\tilde{G}_{\textbf{d}^{n}}^{\pi} \in \mathcal{B}_{\theta}\left({\textbf{d}^{n}_{\pi}}\right) \,\vert\, {\textbf{D}_{\pi}^n} = {\textbf{d}^{n}_{\pi}} \right] = 1. \end{align}

Moreover, the theorem determines that $c^{\text{bond}} :=1-U_{\pi}^\text{bond}(x^*,1)-U_{\pi}^\text{bond}(1,y^*)+U_{\pi}^\text{bond}(x^*,y^*),$ where $x^*,y^*$ are the smallest positive solutions of

(25)\begin{equation} \begin{aligned} x^*= U^-_{\pi}(x^*),\\ y^*= U^+_{\pi}(y^*), \end{aligned} \end{equation}

and functions $U_{\pi}^+$, $U^-_{\pi}$, and $U_{\pi}^\text{bond}$ are as defined in Eq. (16).

To finalize the proof for Theorems 2.2 and 2.3, we need to supplement Eqs. (23) and (24) with two minor observations. First, the theorem is stated for a percolated multigraph progression $\left(\tilde{G}_{\textbf{d}^{n}}^{\pi}\right)_{n \in \mathbb{N}}$ without conditioning on the degree progression of the percolated graphs. As $\nu\left(E\right) =1$, an analogous argument to that of Fountoulakis [16, p. 348] is applied to show that

• • If $\pi \lt \hat{\pi}^{\text{bond}}, \; \lim \limits_{n \rightarrow \infty} \mathbb{P}\left[\tilde{G}_{\textbf{d}^{n}}^{\pi} \in \mathcal{A}_\epsilon\left({\textbf{d}^{n}_{\pi}}\right)\right] = 1$ for all $\epsilon \in (0,1)$.

• • If $\pi \gt \hat{\pi}^{\text{bond}},\; \lim\limits_{n \rightarrow \infty} \mathbb{P}\left[\tilde{G}_{\textbf{d}^{n}}^{\pi} \in \mathcal{B}_{c^{\text{bond}}}\left({\textbf{d}^{n}_{\pi}}\right)\right] = 1$

  and $ \lim\limits_{n \rightarrow \infty} \mathbb{P}\left[\tilde{G}_{\textbf{d}^{n}}^{\pi} \in \mathcal{B}_{\epsilon}\left({\textbf{d}^{n}_{\pi}}\right)\right] = 0$ for all $\epsilon \in (0,1), \epsilon \neq c^{\text{bond}}$ .

Second, Theorems 2.2 and 2.3 make assertions about uniformly random simple graphs instead of random multigraphs. Lemma 3.8 can also be stated for the graph $\tilde{G}_{\textbf{d}^{n}}^{\pi}$ conditioning on $G_{\textbf{d}^{n}}$ (the graph to which percolation is applied) being simple. Applying this variant of Lemma 3.8 to the above limits, we deduce an equivalent statement as above for $G_{n}^{\pi}$:

• • If $\pi \lt \hat{\pi}^{\text{bond}}, \; \lim\limits_{n \rightarrow \infty} \mathbb{P}\left[G_{n}^{\pi} \in \mathcal{A}_\epsilon\left({\textbf{d}^{n}_{\pi}}\right)\right] = 1$ for all $\epsilon \in (0,1)$.

• • If $\pi \gt \hat{\pi}^{\text{bond}},$ $ \lim\limits_{n \rightarrow \infty} \mathbb{P}\left[G_{n}^{\pi} \in \mathcal{B}_{c^{\text{bond}}}\left({\textbf{d}^{n}_{\pi}}\right)\right] = 1$

  and $ \lim\limits_{n \rightarrow \infty} \mathbb{P}\left[G_{n}^{\pi} \in \mathcal{B}_{\epsilon}\left({\textbf{d}^{n}_{\pi}}\right)\right] = 0$ for all $\epsilon \in (0,1), \epsilon \neq c^{\text{bond}}$.

This completes the proofs of Theorems 2.2 and 2.3 for the case of bond percolation.

4.2. Site percolation

The proof of Theorems 2.2 and 2.3 for site percolation has a similar structure as for bond percolation, and we will refer to Section 4.1 where applicable. The proof again is split into three steps. First, in Section 4.2.1, we show that applying site percolation to a uniformly random configuration results in another uniformly random configuration if we condition on the degree sequence after percolation. Second, we determine the limit of the expected number of vertices with degree (j, k) after site percolation, see Section 4.2.2. The proof is completed in Section 4.2.3 by combining the first two steps with the results of Section 4.1.

As mentioned in Section 2, deleting a vertex means that we remove all edges adjacent to this vertex. In the setting of the configuration model, this translates into removing all stubs attached to a deleted vertex. Let us call these stubs $\left({W^{-, r}}, {W^{+, r}} \right)$. Additionally, the matches of $\left({W^{-, r}}, {W^{+, r}} \right)$ are also removed. The situation is further complicated by the fact that a match of a removed stub itself may or may not be attached to a deleted vertex. That is to say, for a deleted edge, both endpoints may be deleted or only one of them. To avoid double counting, we introduce $\left({W^{-, m}}, {W^{+, m}} \right)$ containing all the genuine matches of stubs in $\left({W^{-, r}}, {W^{+, r}} \right)$ that are not connected to a deleted vertex. Thus, ${W^{-, r}} \cup {W^{-, m}} $ (respectively, ${W^{+, r}} \cup {W^{+, m}} $) are all in-stubs (out-stubs) removed by site percolation. The stubs that survive percolation are denoted by $\left({W^{-,\pi}}, {W^{+,\pi}}\right)$ as before, allowing us to write the full partition of stubs as

(26)\begin{align} {W^{-}} = {W^{-, \pi}} \cup {W^{-, r}} \cup {W^{-, m}} \quad \text{and} \quad {W^{+}} = {W^{+, \pi}} \cup {W^{+, r}} \cup {W^{+, m}}. \end{align}

Hence, the abbreviation is as follows: π – surviving stubs, r – stubs on removed vertices, and m – matches of stubs on removed vertices. These abbreviations will be used throughout the rest of the section.

4.2.1. A site-percolated configuration is a uniformly random configuration

We show in Lemma 4.6 that conditional on the stubs that are removed by the site percolation, the matching on the surviving stubs is uniformly random. This lemma, in turn, allows us to formulate Lemma 4.7 stating that the configuration after percolation is a uniformly random configuration conditional on its degree sequence.

Lemma 4.6. Apply site percolation to a uniformly random configuration $\mathcal{M}$ on $\left({W^{-}}, {W^{+}} \right)$. Conditional on the elements of $\left({W^{-, r}}, {W^{+, r}} \right)$ and $\left({W^{-, m}},{W^{+, m}} \right)$, each configuration on $\left({W^{-,\pi}},{W^{+,\pi}}\right)$ is equally likely.

Proof. According to Eq. (26), fixing the elements of $\left({W^{-, r}}, {W^{+, r}} \right)$ and $\left({W^{-, m}},{W^{+, m}} \right)$ uniquely determines the elements of $\left({W^{-,\pi}},{W^{+,\pi}}\right)$. Choosing the elements of $\left({W^{-, r}}, {W^{+, r}} \right)$ and $\left({W^{-, m}},{W^{+, m}} \right)$ furthermore implies that the configuration $\mathcal{M}$ is the union of a configuration on $\left({W^{-, r}} \cup {W^{-, m}}, {W^{+, r}} \cup {W^{-, m}} \right)$ with the one on $\left({W^{-,\pi}},{W^{+,\pi}}\right)$. As $\mathcal{M}$ is a uniformly random configuration obeying this split and the elements of $\left({W^{-,\pi}},{W^{+,\pi}}\right)$ are fixed, the configuration on $\left({W^{-,\pi}},{W^{+,\pi}}\right)$ will be a uniformly random one.

Lemma 4.7. Apply site percolation to a uniformly random configuration on $\left({W^{-}}, {W^{+}} \right)$. Conditional on ${\textbf{D}_{\pi}^n} = {\textbf{d}^{n}_{\pi}}$, any configuration on $\left({W^{-}_{\textbf{d}^{n}_{\pi}}}, {W^{+}_{\textbf{d}^{n}_{\pi}}}\right)$ is equally likely.

Proof. The proof of this lemma is identical to the proof of Lemma 4.2, replacing Lemma 4.1 with Lemma 4.6.

4.2.2. The expected number of vertices with degree (j, k) after site percolation

The next step in the proof of Theorem 2.2 for the case of site percolation is proving the existence of the limit for $\frac{N_{{j},{k}}^{\pi}\left(n\right)}{n}$, the fraction of vertices in the site-percolated graph with in-degree j and out-degree k. We then show that the value of this limit, distribution ${p^{\text{site}}_{{j}, {k}}}$, is closely related to the corresponding quantity for bond percolation. After this, we determine $\hat{\pi}^{\text{site}}$ and show in Section 4.2.3 that this is indeed the threshold for site percolation.

We introduce the following notation for the sizes of the subsets

\begin{equation*} \begin{aligned} s^-: =& \lvert {W^{-, \pi}} \cup {W^{-, m}}\rvert,\\ s^+: =& \lvert{W^{+, \pi}} \cup {W^{+, m}}\rvert,\\ r^- := &\lvert {W^{-, m}}\rvert,\\ r^+:= &\lvert {W^{+, m}}\rvert. \end{aligned} \end{equation*}

Note that $ \lvert {W^{-, \pi}} \rvert =s^- - r^- = s^+ - r^+ = \lvert {W^{+, \pi}} \rvert $ and the remaining configuration on $\left({W^{-,\pi}}, {W^{+,\pi}}\right)$ forms a directed multigraph. As before, $N_{{d^-},{d^+}}\left(n\right)$ is the number of vertices with degree $(d^-,d^+)$ before percolation. Let $N_{{d^-},{d^+}}^{\pi,r}\left(n\right)$ be the number of vertices of original degree $(d^-,d^+)$ that survive site percolation. Then, $N_{{d^-},{d^+}}\left(n\right)- N_{{d^-},{d^+}}^{\pi,r}\left(n\right)$ is the number of removed vertices of original degree $(d^-,d^+)$. Since each vertex is independently removed with probability $1-\pi$,

(27)\begin{align} &\mathbb{E}\left[N_{{d^-},{d^+}}^{\pi,r}\left(n\right)\right] = \pi N_{{d^-}, {d^+}}\left(n\right), \end{align}

(28)\begin{align} &\mathbb{E}\left[N_{{d^-},{d^+}}\left(n\right)- N_{{d^-},{d^+}}^{\pi,r}\left(n\right)\right] = \left(1-\pi \right)N_{{d^-},{d^+}}\left(n\right). \end{align}

We proceed by formulating two lemmas showing that, with high probability, $s^-,s^+$ remain in some bounded shrinking interval $I^\prime_n$ and $r^-,r^+$ in I _n.

Lemma 4.8. Let $I^\prime_n := \left[m\pi - n^{2/3}\,\ln n,\, m\pi + n^{2/3}\ln n\right] $, then

\begin{equation*}\mathbb{P}\left[ s^-,s^+ \in I^\prime_n \right]=1-{\rm e}^{-\Omega\left(\ln^2 n\right)}\end{equation*}

holds separately for, respectively, $s^-$ and $s^+$.

Proof. By using Eq. (27), we obtain

\begin{equation*} \mathbb{E}\left[s^-\right] = \sum_{d^-=0}^{d_{\max}}\sum_{d^+=0}^{d_{\max}} \pi {d}^-N_{{d^-},{d^+}}\left(n\right) = m\pi \end{equation*}

and

\begin{equation*}\mathbb{E}\left[s^+\right] = \sum_{d^-=0}^{d_{\max}}\sum_{d^+=0}^{d_{\max}} \pi {d}^+ N_{{d^-},{d^+}}\left(n\right) =m\pi.\end{equation*}

Using Hoeffding’s inequality and the bound on the maximum degree, $d_{\max} \leq n^{1/9}$ and, we obtain

(29)\begin{align} \mathbb{P}\left[\left\lvert s^- - \mathbb{E}\left[s^-\right]\right\rvert \gt n^{2/3}\ln n\right] \leq {\rm e}^{-\Omega\left( \ln^2 n\right)} \; \text{and}\; \mathbb{P}\left[\left\lvert s^+ - \mathbb{E}\left[s^+\right]\right\rvert \gt n^{2/3}\ln n\right] \leq {\rm e}^{-\Omega\left( \ln^2 n\right)}, \end{align}

which proves the claim.

Lemma 4.9. Let $I_n := \left[m\pi (1-\pi ) - n^{2/3}\,\ln^2 n,\, m\pi (1-\pi ) + n^{2/3}\,\ln^2 n\right]$, then

\begin{equation*}\mathbb{P}\left[ r^+,r^- \in I_n \mid s^-, s^+ \in I'_n\right]=1-{\rm e}^{-\Omega\left(\ln^2 n\right)}\end{equation*}

holds separately for, respectively, $r^-$ and $r^+$.

Proof. We present the proof for $r^-$. The proof for $r^+$ is then identical up to switching the roles of in-stubs and out-stubs. Since we consider a uniformly random configuration on $\left({W^{-}}, {W^{+}} \right)$, the probability that a given in-stub is matched to an out-stub in ${W^{+, r}} $ is $\frac{m-s^+}{m}= (1-\pi ) \left( 1+ \mathcal{O}\left(n^{-1/3}\,\ln n\right)\right)$ as $s^-,s^+ \in I^\prime_n$. Since $r^-$ equals the number of in-stubs in ${W^{-}} \setminus {W^{-, r}} $ with a match in ${W^{+, r}} $, this implies that

\begin{align*} \mathbb{E}\left[r^-\right] = s^- \frac{m-s^+}{m} = m\pi \left(1-\pi \right) \left(1 + \mathcal{O} \left(n^{2/3}\,\ln n\right)\right). \end{align*}

To complete the proof, we will now show that

\begin{align*} \mathbb{P}\left[\lvert r^- - \mathbb{E}\left[r^-\right] \rvert \gt n^{2/3}\,\ln^2 n \right] \leq {\rm e}^{- \Omega\left(\ln^2 n\right)}. \end{align*}

This is realized by applying Theorem 3.12 to the space of configurations on $\left({W^{-}}, {W^{+}} \right)$ with the symmetric difference as the metric. The value of $r^-$ plays the role of the function f. To partition this space, we order the in-stubs of $W^{-}$. Define an i-prefix to be the first i in-stubs together with their match. An element of the partition $\mathcal{P}_k$ consists of all configurations with the same k-prefix for all $k \in \{0,1,\ldots, m\}$. For any $A,B \in \mathcal{P}_k$ such that $A,B\subset C \in \mathcal{P}_{k-1}$, a bijection $\phi: A \rightarrow B$ can be defined. Denote the kth pair of a configuration in A by $(x,y_A)$ and the kth pair of a configuration in B by $(x,y_B)$. Then ϕ maps $\mathcal{M} \in A$ to the configuration in B with $(x,y_A)$ replaced by $(x,y_B)$ and with y _A the match of the in-stub in $\mathcal{M}$ matched to y _B. By definition of ϕ, it follows that $c_k:=\lvert \mathcal{M} -\phi(\mathcal{M})\rvert = 4 $ for all $k \in \{1,2,\ldots ,m\}$. As the value of $r^-$ changes by at most the symmetric difference of the two matchings, Theorem 3.12 states that

\begin{align*} \mathbb{P}\left[\lvert r^- - \mathbb{E}\left[r^-\right] \rvert \gt n^{2/3}\ln^2 n \right] \leq 2\exp \left(\frac{n^{4/3}\,\ln^2 n}{2m}\right) = {\rm e}^{- \Omega\left(\ln^2 n\right)}, \end{align*}

as $m \leq nd_{\max} \leq n^{10/9}$.

Lemma 4.10. Let $N_{{j},{k}}^{\pi}\left(n\right)$ be the number of vertices in the site-percolated graph (or configuration) with in-degree j and out-degree k. The following limit exists

(30)\begin{align} {p^{{\rm site}}_{{j}, {k}}}:=\lim_{n\rightarrow \infty} \frac{\mathbb{E}\left[N_{{j},{k}}^{\pi}\left(n\right)\right]}{n}, \text{for } j,k\in\mathbb{N}_0 \end{align}

and

(31)\begin{align} {p^{{\rm site}}_{{j}, {k}}} = \begin{cases} \pi {p^{{\rm bond}}_{j, k}},&(j,k)\neq(0,0),\\ \pi {p^{{\rm bond}}_{0, 0}} + 1-\pi,& (j,k)=(0,0), \end{cases} \end{align}

where ${p^{{\rm bond}}_{{j}, {k}}}$ is defined in Lemma 4.4.

Proof. If $j, k \gt d_{\max}$, then ${p^{{\rm site}}_{{j}, {k}}}=N_{{j},{k}}^{\pi}\left(n\right)=N_{{j},{k}}\left(n\right)=0$.

Consider $0\leq j,k \leq d_{\max}$. A removed vertex will have degree $(0,0)$ after percolation with probability 1. Let $P_{j,k}\left(d^-,d^+\right)$ be the probability that a non-removed vertex of degree $(d^-,d^+)$ has degree (j, k) after percolation. For $(j,k) = (0,0)$, we have

(32)\begin{align} \mathbb{E}\left[N_{{0},{0}}^{\pi}\left(n\right)\right] = \sum_{d^- = 0}^{d_{\max}}\sum_{d^+ = 0}^{d_{\max}}\left( \left(1-\pi \right) N_{{d^-},{d^+}}\left(n\right) + \pi P_{0,0}\left(d^-,d^+\right) N_{{d^-},{d^+}}\left(n\right)\right), \end{align}

and otherwise,

(33)\begin{align} \mathbb{E}\left[N_{{j},{k}}^{\pi}\left(n\right)\right] = \sum_{d^- =j}^{d_{\max}}\sum_{d^+ =k}^{d_{\max}} \pi P_{j,k}\left(d^-,d^+\right) N_{{d^-},{d^+}}\left(n\right). \end{align}

Hence, we need to derive the expression for $P_{j,k}\left(d^-,d^+\right)$. Let us determine $P_{j,k}\left(d^-,d^+, s^-, s^+, r^-, r^+\right)$, the probability $P_{j,k}\left(d^-,d^+\right)$ conditional on the values $s^-,s^+,r^-,r^+$. Site percolation combines the independent random processes of removing vertices and creating a uniformly random configuration on $\left({W^{-}}, {W^{+}} \right)$. As these processes are independent, we may first determine the elements of $\left({W^{-, r}},{W^{+, r}} \right)$ and then randomly create a configuration on $\left({W^{-}}, {W^{+}} \right)$. Thus, conditional on the value of $r^-$ (respectively, $r^+$), each subset of ${W^{-}} \setminus {W^{-, r}} $ (respectively, ${W^{+}} \setminus {W^{+, r}} $) of this size is equally likely to be ${W^{-, m}} $ (respectively, ${W^{+, m}} $). Hence,

(34)\begin{align} P_{j,k}\left(d^-,d^+, r^-, r^+, s^-, s^+\right) = {{d^-}\choose {d^- -j}} {{d^+}\choose {d^+ -k}} \frac{{{s^- - d^-}\choose {r^- - d^- +j}}}{{{s^-}\choose{r^-}}}\frac{{{s^+ - d^+}\choose {r^+ - d^+ +k}}}{{{s^+}\choose{r^+}}}. \end{align}

Let intervals $I_n,I_n^\prime$ are as defined in Lemmas 4.8 and 4.9. We have that, uniformly in $r^-,r^+ \in I_n$ and $ s^-,s^+ \in I^\prime_n$,

\begin{align*} {d \choose {d-i}}\frac{{{s - d} \choose {r -d +i}}}{{{s}\choose {r}}} = {d \choose {d-i}} \left(1-\pi \right)^{d-i}\pi^i\left(1 + \mathcal{O}\left(\frac{\ln^2 n}{n^{1/3}}\right)\right). \end{align*}

Plugging this equation into Eq. (34) gives

\begin{align*} P_{j,k}\left(d^-,d^+, r^-, r^+, s^-, s^+\right) = {{d^-}\choose {d^- -j}} {{d^+}\choose {d^+ -k}} \pi^{j+k}\left(1-\pi \right)^{d^-+d^+-j-k} \left(1 + \mathcal{O}\left(\frac{\ln^2 n}{n^{1/3}}\right)\right), \end{align*}

uniformly for all $s^-, s^+ \in I^\prime_n$ and $r^-,r^+ \in I_n$. It turns out that a violation of the latter condition is unlikely, as $\mathbb{P}\left[s^- \notin I^\prime_n \vee s^+ \notin I^\prime_n \vee r^- \notin I_n \vee r^+ \notin I_n\right]$ is small, which in turn helps to bound the value of $\mathbb{E}\left[N_{{j},{k}}^{\pi}\left(n\right)\right]$. By applying Hoeffding’s inequality, we have

(35)\begin{align} \mathbb{P}\left[\rvert N_{{d^-},{d^+}}^{\pi,r}\left(n\right) - \mathbb{E}\left[N_{{d^+},{d^-}}^{\pi,r}\left(n\right)\right] \rvert \gt \sqrt{n}\,\ln n\right] \lt {\rm e}^{-\Omega\left(\ln^2 n\right)}, \end{align}

and in combination with Eq. (27), this gives

\begin{equation*}N_{{d^-},{d^+}}^{\pi,r}\left(n\right) \in I^{\prime\prime}_n(d^-,d^+) := \left[\pi N_{{d^-}, {d^+}}\left(n\right) - \sqrt{n}\,\ln n, \pi N_{{d^-}, {d^+}}\left(n\right) + \sqrt{n}\,\ln n\right],\end{equation*}

with probability $1-{\rm e}^{-\Omega\left(\ln^2 n\right)}$. Combining this with Lemmas 4.8 and 4.9 gives

\begin{align*} &\!\!\!\!\!\!\mathbb{P}\left[s^- \notin I^\prime_n \lor s^+ \notin I^\prime_n \lor r^- \notin I_n \lor r^+ \notin I_n \lor N_{{d^-},{d^+}}^{\pi,r}\left(n\right) \notin I^{\prime\prime}_n\left(d^-,d^+\right)\right] \;\;\\ \leq & \mathbb{P}\left[s^- \notin I^\prime_n\right] + \mathbb{P}\left[s^+ \notin I^\prime_n\right] + \mathbb{P}\left[r^- \notin I_n\right] + \mathbb{P}\left[r^+ \notin I_n\right] + \mathbb{P}\left[N_{{d^-},{d^+}}^{\pi,r}\left(n\right) \notin I^{\prime\prime}_n\left(d^-,d^+\right)\right]\\ = & o\left(\frac{1}{n^3}\right) + \mathbb{P}\left[r^- \notin I_n\right] + \mathbb{P}\left[r^+ \notin I_n\right], \end{align*}

where $\mathbb{P}\left[r^- \notin I_n\right]=o\left(n^{-3}\right)$ and $\mathbb{P}\left[r^+ \notin I_n\right] = o\left(n^{-3}\right)$. Therefore,

(36)\begin{align} \mathbb{P}\left[s^- \notin I^\prime_n \lor s^+ \notin I^\prime_n \lor r^- \notin I_n \lor r^+ \notin I_n \lor N_{{d^-},{d^+}}^{\pi,r}\left(n\right) \notin I^{\prime\prime}_n\left(d^-,d^+\right)\right] = o\left(n^{-3}\right). \end{align}

This allows us to determine a lower and upper bound for the value $\mathbb{E}\left[N_{{j},{k}}^{\pi}\left(n\right)\right]$. Since $N_{{d^-},{d^+}}^{\pi,r}\left(n\right) \leq N_{{d^-},{d^+}}\left(n\right)$ and $(\textbf{d}^{n})_{n\in \mathbb{N}}$ is proper, for all ϵ > 0, there exist $\kappa\left(\epsilon\right)$ and $N\left(\epsilon\right)$ such that for all n > N

(37)\begin{align} \sum_{{\substack{(d^-,d^+) = (0,0)\\ d^- \geq \kappa +1 \,{\rm or}\, d^+ \geq \kappa +1}}}^{(d_{\max}, d_{\max})} P_{j,k}\left(d^-,d^+\right) N_{{d^-},{d^+}}^{\pi,r}\left(n\right) \leq \sum_{{\substack{(d^-,d^+) = (0,0)\\ d^- \geq \kappa +1 \,{\rm or}\, d^+ \geq \kappa +1}}}^{(d_{\max}, d_{\max})} N_{{d^-},{d^+}}\left(n\right) \leq \epsilon n. \end{align}

In combination with Eq. (33), this implies for $(j,k) \neq (0,0)$

(38)\begin{align} \sum_{\substack{d^- =j,\\ d^+ =k}}^{\kappa}P_{j,k}\left(d^-,d^+\right) N_{{d^-},{d^+}}^{\pi,r}\left(n\right) \leq \mathbb{E}\left[N_{{j},{k}}^{\pi}\left(n\right) \right]\leq \sum_{\substack{d^- =j,\\ d^+ =k}}^{\kappa}P_{j,k}\left(d^-,d^+\right) N_{{d^-},{d^+}}^{\pi,r}\left(n\right) + \epsilon n. \end{align}

Using Eq. (36) on the LHS of the above equation, we find

\begin{equation*} \begin{split} \mathbb{E}\left[N_{{j},{k}}^{\pi}\left(n\right)\right] \geq& \sum_{\substack{d^-=j,\\d^+=k}}^{\kappa}\; \sum_{\substack{\tilde r^- \in I^\prime_n,\\\tilde r^+\in I^\prime_n}} \;\sum_{\substack{\tilde s^-\in I_n,\\\tilde s^+ \in I_n}}\;\sum_{\tilde{d}_{d^-,d^+} \in I^{\prime\prime}_n(d^-,d^+)} \tilde{d}_{d^-,d^+}P_{j,k}\left(d^-,d^+,\tilde r^-,\tilde r^+,\tilde s^-,\tilde s^+\right)\\ &\times\mathbb{P}\left[r^-=\tilde r^-, r^+=\tilde r^+, s^- = \tilde s^-, s^+ = \tilde s^+, N_{{d^-},{d^+}}^{\pi,r}\left(n\right) = \tilde{d}_{d^-,d^+}\right] + o \left(\frac{1}{n^2}\right)\\ =&\sum_{\substack{d^- =j,\\ d^+ =k}}^{\kappa}\sum_{\tilde{d}_{d^-,d^+} \in I^{\prime\prime}_n(d^-,d^+)} \tilde{d}_{d^-,d^+}{{d^-}\choose {d^- -j}} {{d^+}\choose {d^+ -k}} \pi^{j+k}\left(1-\pi \right)^{d^-+d^+-j-k} \\ &\times\mathbb{P}\left[N_{{d^-},{d^+}}^{\pi,r}\left(n\right) = \tilde{d}_{d^-,d^+}\right] \left(1 + \mathcal{O}\left(\frac{\ln^2 n}{n^{1/3}}\right)\right)+ o \left(\frac{1}{n^2}\right) \end{split} \end{equation*}

Since Eq. (35) and $N_{d^-,d^+}^{\pi,r}(n)\leq n$ gives

\begin{equation*}\sum_{\tilde{d}_{d^-,d^+} \in I^{\prime\prime}_n(d^-,d^+)}\tilde{d}_{d^-,d^+}\mathbb{P}\left[N_{{d^-},{d^+}}^{\pi,r}\left(n\right) = \tilde{d}_{d^-,d^+}\right] = \mathbb{E}\left[N_{{d^-},{d^+}}^{\pi,r}\left(n\right)\right] + o\left(\frac{1}{n^2}\right),\end{equation*}

we obtain the lower bound

\begin{align*} \mathbb{E}\left[N_{{j},{k}}^{\pi}\left(n\right)\right] \geq o\left(\frac{1}{n^2}\right)+ \pi \sum_{d^-=j}^{\kappa}\sum_{d^+=k}^{\kappa} N_{{d^-},{d^+}}\left(n\right) {{d^-}\choose {d^- -j}} {{d^+}\choose {d^+ -k}} \times\\ \pi^{j+k}\left(1-\pi \right)^{d^-+d^+-j-k} \left(1 + \mathcal{O}\left(\frac{\ln^2 n}{n^{1/3}}\right)\right). \end{align*}

In a similar fashion, using the RHS of Eq. (38) gives the upper bound

\begin{align*} \mathbb{E}\left[N_{{j},{k}}^{\pi}\left(n\right)\right] \leq \epsilon n + o\left(\frac{1}{n^2}\right)+\pi \sum_{d^-=j}^{\kappa}\sum_{d^+=k}^{\kappa} N_{{d^-},{d^+}}\left(n\right) {{d^-}\choose {d^- -j}} {{d^+}\choose {d^+ -k}} \times\\ \pi^{j+k}\left(1-\pi \right)^{d^-+d^+-j-k} \left(1 + \mathcal{O}\left(\frac{\ln^2 n}{n^{1/3}}\right)\right) . \end{align*}

Combining the upper and lower bounds together proves convergence of the limit for $j,k \gt 0$:

(39)\begin{align} {p^{{\rm site}}_{{j}, {k}}}:=\lim_{n\rightarrow \infty} \frac{\mathbb{E}\left[N_{{j},{k}}^{\pi}\left(n\right)\right]}{n} = \pi \sum_{d^- = j}^\infty \sum_{d^+ = k}^\infty p_{d^-,d^+} {d^- \choose j}{d^+ \choose k}\pi^{j+k}\left(1-\pi \right)^{d^- - j + d^+ -k} . \end{align}

For $(j,k) = (0,0)$, we need to use Eq. (32) instead of Eq. (33). Since $N_{{d^-},{d^+}}^{\pi,r}\left(n\right) \leq N_{{d^-},{d^+}}\left(n\right)$ and $(\textbf{d}^{n})_{n\in \mathbb{N}}$ is proper, for all ϵ > 0, there exist $\kappa\left(\epsilon\right)$ and $N\left(\epsilon\right)$ such that for all n > N:

\begin{align*} \sum_{{\substack{(d^-,d^+) = (0,0)\\ d^- \geq \kappa +1 \,{\rm or}\, d^+ \geq \kappa +1}}}^{(d_{\max}, d_{\max})} \left(N_{{d^-},{d^+}}\left(n\right) - N_{{d^-},{d^+}}^{\pi,r}\left(n\right)\right) \leq \sum_{{\substack{(d^-,d^+) = (0,0)\\ d^- \geq \kappa +1 \,{\rm or}\, d^+ \geq \kappa +1}}}^{(d_{\max}, d_{\max})} N_{{d^-},{d^+}}\left(n\right) \leq \epsilon n. \end{align*}

Thus, the equivalent of Eq. (38) for $(j,k) = (0,0)$ becomes

\begin{align*} \sum_{d^- =0}^{\kappa}\sum_{d^+ =0}^{\kappa} \left[ \left(N_{{d^-},{d^+}}\left(n\right) - N_{{d^-},{d^+}}^{\pi,r}\left(n\right)\right )+P_{0,0}\left(d^-,d^+\right) N_{{d^-},{d^+}}^{\pi,r}\left(n\right)\right] \leq \mathbb{E}\left[N_{{0},{0}}^{\pi}\left(n\right) \right] \leq \\ \sum_{d^- =0}^{\kappa}\sum_{d^+ =0}^{\kappa}\left[\left(N_{{d^-},{d^+}}\left(n\right) - N_{{d^-},{d^+}}^{\pi,r}\left(n\right)\right) + P_{0,0}\left(d^-,d^+\right) N_{{d^-},{d^+}}^{\pi,r}\left(n\right)\right] + 2\epsilon n, \end{align*}

and the analogous argument as for $(j,k) \neq (0,0)$ is applied to obtain

(40)\begin{align} \lim_{n\rightarrow \infty} \frac{\mathbb{E}\left[N_{{0},{0}}^{\pi}\left(n\right)\right]}{n} = \left(1-\pi \right) + \pi \sum_{\substack{d^- = j,\\d^+ = k}}^\infty p_{d^-,d^+} {d^- \choose j}{d^+ \choose k}\pi^{j+k}\left(1-\pi \right)^{d^- - j + d^+ -k} = {p^{{\rm site}}_{{0}, {0}}}. \end{align}

Comparing Eqs. (39) and (40) with Eq. (9), we obtain Eq. (31).

From Eq. (31), we can see that ${p^{\text{site}}_{{j}, {k}}}$ is a probability distribution and has moments

(41)\begin{align} \mu^{\pi, \text{site}}: =\mu_{10}^{\pi, \text{site}} =\mu_{01}^{\pi, \text{site}} = \pi \mu^{\pi, \text{bond}} = \pi^2 \mu \quad \text{and} \quad \mu_{11}^{\pi, \text{site}} = \pi \mu_{11}^{\pi, \text{bond}} = \pi^3\mu_{11}. \end{align}

Additionally, the generating function $U_{\pi}^\text{site}(x,y)$ for ${p^{\text{site}}_{{j}, {k}}}$ is given by

(42)\begin{equation} \begin{aligned} U^\text{site}_{\pi}(x,y) := 1-\pi +\pi U(1-\pi +\pi x,1-\pi +\pi y), \end{aligned} \end{equation}

and auxiliary functions $U^+_{\pi},U^-_{\pi}$ are the same as in Eq. (16). It is left to determine $\hat{\pi}^{\text{site}}$. Theorem 3.11 states that the percolation threshold is $\pi =\hat{\pi}^{\text{site}}$ such that $ \sum_{j,k=0}^\infty jk {p^{\text{site}}_{{j}, {k}}} = \sum_{j,k=0}^\infty j{p^{\text{site}}_{{j}, {k}}}. $ Combining this with Eq. (41), we find that the percolation thresholds for site and bond percolation are equal:

\begin{equation*}\hat{\pi}^{\text{site}} = \frac{\mu}{\mu_{11}} = \hat{\pi}^{\text{bond}}.\end{equation*}

This can be explained by noting that the expected degree distribution after site percolation is a rescaled version of the degree distribution after bond percolation, exept for $(0,0)$. Hence, one expects the GSCC to appear under the same conditions. However, the GSCC after site percolation is expected to contain fewer vertices because the probability to find an isolated vertex is larger.

4.2.3. Determining ${\pi_c^{{\rm site}}}$ and $c^{{\rm site}}$

To finalize the proof of Theorems 2.2 and 2.3 for the case of site percolation, it remains to show that ${\pi_c^{\text{site}}} = \hat{\pi}^{\text{site}}$ as well as to determine c ^site, the fraction of vertices in GSCC. This is done by following a similar exposition as in Section 4.1.3, which covers bond percolation. We therefore focus on explaining the necessary adjustments to be made to apply the derivations in Section 4.1.3 to site percolation.

First, we need to replace the distribution ${p^{\text{bond}}_{{j}, {k}}}$ with ${p^{\text{site}}_{{j}, {k}}}$. Lemma 4.7 proves the equivalent statement for site percolation to that of Lemma 4.2 for bond percolation. However, the counterpart of Eq. (22) requires a different proof. Conditional on a certain realization of $\left( {W^{-, r}}, {W^{+, r}} \right)$ and the values $s^-,s^+ \in I'_n$, $r^-,r^+ \in I_n$, the value of $N_{{j},{k}}^{\pi}\left(n\right)$ is determined by the random choice of $\left({W^{-, m}},{W^{+, m}} \right)$. By changing one element of $\left({W^{-, m}},{W^{+, m}} \right)$, the value of $N_{{j},{k}}^{\pi}\left(n\right)$ changes by at most 2. Thus, Theorem 3.13 can be applied to obtain

\begin{align*} \mathbb{P}\left[ \left| N_{{j},{k}}^{\pi}\left(n\right) - \mathbb{E}\left[N_{{j},{k}}^{\pi}\left(n\right)\right] \right| \gt \sqrt{n}\,\ln^2 n \, \mid \,s^-, s^+, r^-, r^+, \left({W^{-, r}}, {W^{+, r}} \right)\right]\\\leq 2\,\exp \left( \frac{n \,\ln^2 n}{\left(m(1-\pi )\pi + n^{2/3}\, \ln^2 n\right)}\right) = {\rm e}^ {-\Omega\left(\ln^2 n\right)}. \end{align*}

Using Lemmas 4.8 and 4.9, it follows that

\begin{align*} \mathbb{P}\left[ \left| N_{{j},{k}}^{\pi}\left(n\right) - \mathbb{E}\left[N_{{j},{k}}^{\pi}\left(n\right)\right] \right| \gt \sqrt{n}\,\ln^2 n\right] = o\left(\frac{1}{n^3}\right), \end{align*}

and, since κ is bounded, this completes the proof of the counterpart of Eq. (22).

The last change is related to the fact that Theorem 3.11 is now applied to a feasible degree progression with ${p^{\text{site}}_{{j}, {k}}}$ as degree distribution instead of ${p^{\text{bond}}_{{j}, {k}}}$. In Section 4.2.2, we found that $\hat{\pi}^{\text{site}} = \frac{\mu}{\mu_{11}}$. Furthermore, in analogy to calculations in Section 4.1.3, we choose $x^*, \;y^*$ to be the solution of Eq. (25) to find that

\begin{equation*} c^{\text{site}}:=1-U_{\pi}^\text{site}(x^*,1)-U_{\pi}^\text{site}(1,y^*)+U_{\pi}^\text{site}(x^*,y^*)=\pi {c^{\text{bond}}}. \end{equation*}

which completes the proof of Theorems 2.2 and 2.3 for site percolation.