is monotone non-increasing and initially constant for a sufficiently large
time. The proof is similar to the proof of Lemma 4.4, and therefore given in
Appendix C.

######  Lemma 4.6.

Suppose $l:=l_{k}$ is such that $k^{\alpha}\ll l\ll k$ for some
$\alpha\in(0,1)$ as $k\rightarrow\infty$. Define the boundary sequence

$\displaystyle g_{i,l}^{-}=\left\\{\begin{array}[]{ll}1-\theta&\textrm{if
}i\leq l,\\\ -i^{\gamma}&\textrm{if }i>l,\end{array}\right.$

with $\gamma\in(0,1/2)$. Then, as $k\rightarrow\infty$,

$\displaystyle\mathbb{P}\left(T_{g^{-}}>k\right)\sim\mathbb{P}\left(T_{1-\theta}>k\right).$

From Lemmas 4.4 and 4.6, the following corollary follows directly:

######  Corollary 4.7.

Suppose $l:=l_{k}$ is such that both $k^{\alpha}\ll l\ll k$ for some
$\alpha\in(0,1)$, and the boundary sequence satisfies

$\displaystyle g_{i,l}=\left\\{\begin{array}[]{ll}1-\theta&\textrm{if }i\leq
l,\\\ o(i^{\gamma})&\textrm{if }i>l,\end{array}\right.$

for some $\theta>0$ and $\gamma\in(0,1/2)$. Then, as $k\rightarrow\infty$,

$\displaystyle\mathbb{P}\left(T_{g}>k\right)\sim\mathbb{P}\left(T_{1-\theta}>k\right)\sim\frac{2\theta}{\sqrt{2\pi}}k^{-1/2}.$

####  4.3.2 Proof of Proposition 2.4

To prove Proposition 2.4, we first show that the tail of $\tau_{m}$ behaves
the same as that of $T_{1-\theta}$, after which we use the relation in
Proposition 4.3 to derive the tail of $A_{n,\mathbf{d}}$. In view of (81), we
need to understand the behavior of the random walk

$\displaystyle Y_{i,m}=\sum_{j=1}^{i}(1-L_{j,m}),\hskip 28.45274pt1\leq i\leq
m+1,$

where $Y_{0,m}=0$. In order to apply Corollary 4.7, we therefore need to show
that the random walk is likely to be close to zero for a sufficiently long
time $l$, and within $[-i^{\gamma},i^{\gamma}]$ for all $l\leq i\leq k$ for
some $0<\gamma<1/2$.

######  Proposition 4.8.

Suppose $k=o(m^{\alpha})$ for some $\alpha\in(0,1)$ and
$\gamma\in(\alpha/2,1/2)$. Then, as $m\rightarrow\infty$,

$\displaystyle\mathbb{P}\left(\left|\sum_{j=1}^{i}\left(1-L_{j,m}\right)\right|>i^{\gamma}\textrm{
for some }1\leq i\leq k\right)=o(m^{-1/2}).$

###### Proof.

From Proposition 3.12, it follows that the probability that there are
disconnections when removing less than $o(m^{1/4-\epsilon})$ edges with
$\epsilon\in(0,1/4)$ is of order $o(m^{-1/2})$. Therefore, for every
$l=o(m^{1/4-\epsilon})$ with $\epsilon\in(0,1/4)$, it is likely that
$L_{i,m}=0$ for every $i\leq l$ , and hence

$\displaystyle\mathbb{P}$
$\displaystyle\left(\left|\sum_{j=1}^{i}\left(1-L_{j,m}\right)\right|>i^{\gamma}\textrm{
for some }1\leq i\leq
l\right)\leq\mathbb{P}\left(\left|\sum_{j=1}^{i}\left(1-L_{j,m}\right)\right|\neq
0\textrm{ for some }1\leq i\leq l\right)=o(m^{-1/2}).$

Therefore, to prove the proposition, it suffices to show that for every $k$
for which $m^{1/4-\epsilon}\ll k\ll m^{\alpha}$ for some $\alpha\in(0,1)$ and
$\epsilon\in(0,1/4)$,

$\displaystyle\mathbb{P}\left(\left|\sum_{j=l}^{i}\left(1-L_{j,m}\right)\right|>i^{\gamma}\textrm{
for some }l\leq i\leq k\right)=o(m^{-1/2}),$

where e.g. $l=m^{(1/4-\epsilon)/2}$. Write $\pi_{1}=1$, and

$\displaystyle\pi_{i}=\frac{|\hat{E}_{m}(i-2)|}{m-i+2},\hskip 28.45274pt2\leq
i\leq m+1,$

a random variable representing the probability that edge $e_{i-1}$ is in the
giant. Let ${Ber}(\pi)$ denote a Bernoulli distributed random variable with
success probability $\pi$, and note that

$\displaystyle
L_{i,m}=\left(\frac{1}{\pi_{i}}+\frac{Y_{i-1,m}}{|E_{m}(i-2)|}\right)\textrm{Ber}(\pi_{i})\geq
0.$ (82)

In view of Theorem 2.3, we observe that $\pi_{i}$ is likely to be

$\displaystyle\pi_{i}\geq\frac{m-i+2-(i-2)^{\alpha}}{m-i+2}\geq
1-i^{\alpha-1}.$

More precisely, let $\mathcal{E}=\\{\pi_{i}=1\;\forall i<l,\pi_{i}\geq
1-i^{\alpha-1},\;\forall l\leq i\leq k\\}$. Then,

$\displaystyle\mathbb{P}$
$\displaystyle\left(\left|\sum_{j=1}^{i}\left(1-L_{j,m}\right)\right|>i^{\gamma}\textrm{
for some }l\leq i\leq
k\right)\leq\mathbb{P}\left(\left|\sum_{j=1}^{i}\left(1-L_{j,m}\right)\right|>i^{\gamma}\textrm{
for some }l\leq i\leq
k\,\bigg{|}\,\mathcal{E}\right)+\mathbb{P}(\mathcal{E}^{c}),$

where due to Theorem 2.3, it holds that
$\mathbb{P}(\mathcal{E}^{c})=o(m^{-1/2})$. Next, we show that the summed
probabilities have an exponentially decaying tail. Define the stopping time

$\displaystyle\sigma_{i}=\sup\left\\{j\in\mathbb{N}:j\leq i,Y_{i,m}\geq
0\right\\}.$

We remark that $\sigma_{i}\geq l$. Due to (82), it holds for every $l\leq
i\leq k$,

$\displaystyle\mathbb{P}\left(Y_{i,m}<-i^{\gamma}\bigg{|}\mathcal{E}\right)$
$\displaystyle\leq\sum_{r=l}^{i-1}\mathbb{P}\left(\sum_{j=1}^{i}L_{j,m}>i+i^{\gamma};\sigma_{i}=r\bigg{|}\mathcal{E}\right)$
$\displaystyle\leq\sum_{r=l}^{i-1}\mathbb{P}\left(-Y_{r,m}+\sum_{j=r+1}^{i}\frac{1}{\pi_{i}}\textrm{Ber}(\pi_{i})>(i-r)+i^{\gamma};\sigma_{i}=t\bigg{|}\mathcal{E}\right)(1+o(1))$
$\displaystyle\leq\sum_{r=l}^{i-1}\;\mathbb{P}\left(\sum_{j=r+1}^{i}\frac{1}{\pi_{i}}\textrm{Ber}(\pi_{i})>(i-r)+i^{\gamma}\bigg{|}\mathcal{E}\right)(1+o(1)).$

Applying Chernoff’s bound, we obtain for every $t>0$

$\displaystyle\mathbb{P}$
$\displaystyle\left(\sum_{j=r+1}^{i}\frac{1}{\pi_{i}}\textrm{Ber}(\pi_{i})>(i-r)+i^{\gamma}\bigg{|}\mathcal{E}\right)\leq
e^{-t(i-r+i^{\gamma})}\mathbb{E}\left[\exp\left\\{t\sum_{j=r+1}^{i}\frac{1}{\pi_{j}}\textrm{Ber}(\pi_{j})\right\\}\bigg{|}\mathcal{E}\right].$

Although the random variables $\pi_{1},...,\pi_{i}$ are not independent, they
are conditioned to be close to one and satisfy a Markovian property. Let
$p=1-i^{\alpha-1}$, and note that the conditional event $\mathcal{E}$ implies
that $\pi_{j}\geq p$ for all $1\leq j\leq i$. Define $\mathcal{F}_{i}$ as the
filtration generated by removing $i$ edges uniformly at random. Applying the
law of total expectation and noting that $1+x(e^{t/x}-1)$ is a (strictly)
decreasing function for all $t>0$, we observe that

$\displaystyle\mathbb{E}\left[\exp\left\\{t\sum_{j=1}^{i}\frac{1}{\pi_{j}}\textrm{Ber}(\pi_{j})\right\\}\bigg{|}\mathcal{E}\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[\exp\left\\{t\sum_{j=1}^{i}\frac{1}{\pi_{j}}\textrm{Ber}(\pi_{j})\right\\}\bigg{|}\mathcal{F}_{i-1};\mathcal{E}\right]\right]$
$\displaystyle=\mathbb{E}\left[\exp\left\\{t\sum_{j=1}^{i-1}\frac{1}{\pi_{j}}\textrm{Ber}(\pi_{j})\right\\}\mathbb{E}\left[1+\pi_{i}(e^{t/\pi_{i}}-1)\bigg{|}\mathcal{F}_{i-1};\mathcal{E}\right]\right]$
$\displaystyle\leq\left(1+p(e^{t/p}-1)\right)\mathbb{E}\left[\exp\left\\{t\sum_{j=1}^{i-1}\frac{1}{\pi_{j}}\textrm{Ber}(\pi_{j})\right\\}\bigg{|}\mathcal{E}\right].$

Applying the same argument recursively yields the bound

$\displaystyle\mathbb{P}\left(\sum_{j=r+1}^{i}\frac{1}{\pi_{i}}\textrm{Ber}(\pi_{i})>(i-r)+i^{\gamma}\bigg{|}\mathcal{E}\right)\leq
e^{-t(i-r+i^{\gamma})}\left(1+p(e^{t/p}-1)\right)^{i-r}$

for every $t\geq 0$. We point out that the right-hand side corresponds exactly
to the Chernoff bound that would have been obtained if we consider the sum of
$i-r$ Bernoulli distributed independent random variables with parameter $p$.
It follows that

$\displaystyle\mathbb{P}$
$\displaystyle\left(\sum_{j=r+1}^{i}\frac{1}{\pi_{i}}\textrm{Ber}(\pi_{i})>(i-r)+i^{\gamma}\bigg{|}\mathcal{E}\right)\leq\exp\left\\{-\frac{i^{2\gamma}}{2(i-r)p(1-p)}\right\\}=\exp\left\\{-\frac{1}{2}i^{2\gamma-\alpha}\right\\}(1+o(1)).$

We conclude that

$\displaystyle\mathbb{P}\left(Y_{i,m}<-i^{\gamma}\bigg{|}\mathcal{E}\right)\leq
i\exp\left\\{-\frac{1}{2}i^{2\gamma-\alpha}\right\\}(1+o(1)).$

On the other hand, we can use analogous arguments to bound
$\mathbb{P}\left(Y_{i,m}>i^{\gamma}\big{|}\mathcal{E}\right)$. This would
yield

$\displaystyle\mathbb{P}\left(Y_{i,m}>i^{\gamma}\bigg{|}\mathcal{E}\right)\leq
i\exp\left\\{-\frac{1}{4}i^{2\gamma-\alpha}\right\\}(1+o(1)).$

We conclude that

$\displaystyle\mathbb{P}\left(\left|\sum_{j=l}^{i}\left(1-L_{j,m}\right)\right|>i^{\gamma}\textrm{
for some }l\leq i\leq k\right)$
$\displaystyle\leq\sum_{i=l}^{k}\mathbb{P}\left(\left|\sum_{j=1}^{i}\left(1-L_{j,m}\right)\right|>i^{\gamma}\bigg{|}\mathcal{E}\right)+o(m^{-1/2})$
$\displaystyle\leq\sum_{i=l}^{k}2i\exp\left\\{-\frac{1}{8}i^{2\gamma-\alpha}\right\\}+o(m^{-1/2})=o(m^{-1/2}).$

The tail behavior of $\tau$ follows directly by combining Proposition 4.8 and
Corollary 4.7.

######  Corollary 4.9.

If $k=o(m^{\alpha})$ for some $\alpha\in(0,1)$, then as $m\rightarrow\infty$,

$\displaystyle\mathbb{P}\left(\tau_{m}>k\right)\sim\mathbb{P}\left(T_{1-\theta}>k\right)\sim\frac{2\theta}{\sqrt{2\pi}}k^{-1/2}.$

Proposition 2.4 follows from Corollary 4.9 if we show that conditioning on the
event that $S_{m+1,m}=S_{m+1}=0$ does not change the tail of the stopping time
$\tau_{m}$. Indeed, this turns out to be the case.

###### Proof of Proposition 2.4.

We show that asymptotically the behavior of the conditioned stopping time
$\tau_{m}|S_{m+1}=0$ is determined solely by what happens for the increments
until time $k$. Note that by Proposition 4.3

$\displaystyle\mathbb{P}\left(\hat{A}_{n,\mathbf{d}}\geq\kappa(k)\right)$
$\displaystyle\sim\mathbb{P}\left(S_{i}\geq
1-\theta+\sum_{j=1}^{i}\left(1-L_{j,m}\right),\;\;\;i=1,...,k\bigg{|}\,S_{m+1}=0\right)=\mathbb{P}\left(\tau_{m}>k\big{|}\,S_{m+1}=0\right).$

Fix $\epsilon\in(0,1)$. We bound the probability terms both from above and
below, and show that these bounds asymptotically behave the same as
$\epsilon\downarrow 0$. Denote by $f_{i}(\cdot)$ the density of the random
walk $S_{i}$ at time $i\geq 1$. Since the density of the random walk is
bounded, we point out that it holds that [29]

$\displaystyle\lim_{m\rightarrow\infty}\sup_{x\in\mathbb{R}}\left|\sqrt{m}f_{m}(\sqrt{m}x)-\phi(x)\right|=0,$
(83)

where $\phi(\cdot)$ denotes the standard normal density function. Note that

$\displaystyle\mathbb{P}\left(\tau_{m}>k\big{|}\,S_{m+1}=0\right)$
$\displaystyle=\mathbb{P}\left(\tau_{m}>k;S_{k}\leq\epsilon\sqrt{m}\big{|}\,S_{m+1}=0\right)+\mathbb{P}\left(\tau_{m}>k;S_{k}>\epsilon\sqrt{m}\big{|}\,S_{m+1}=0\right).$

For the first term, we observe

$\displaystyle\mathbb{P}\left(\tau_{m}>k;S_{k}\leq\epsilon\sqrt{m}\big{|}\,S_{m+1}=0\right)$
$\displaystyle=\frac{1}{f_{m+1}(0)}\int_{-\infty}^{\epsilon\sqrt{k}}\mathbb{P}\left(\tau_{m}>k;S_{k}\in
du\right)f_{m+1-k}(-u)$
$\displaystyle\leq\frac{1}{f_{m+1}(0)}\mathbb{P}\left(\tau_{m}>k\right)\sup_{u\in[1-\theta+\sum_{j=1}^{k}\left(1-L_{j,m}\right),\epsilon\sqrt{k}]}f_{m+1-k}(-u).$

Due to (83),

$\displaystyle f_{m+1}(0)=\frac{(1+o(1))}{\sqrt{2\pi m}}$

and

$\displaystyle\sup_{x\in\mathbb{R}}f_{i}(\sqrt{i}x)\leq\frac{1+o(1)}{\sqrt{2\pi
i}}$

as $i\rightarrow\infty$. This yields the upper bound

$\displaystyle\limsup_{m\rightarrow\infty}\frac{\mathbb{P}\left(\tau_{m}>k;S_{k}\leq\epsilon\sqrt{m}\big{|}\,S_{m+1}=0\right)}{\mathbb{P}\left(\tau_{m}>k\right)}\leq\limsup_{m\rightarrow\infty}\frac{\sqrt{2\pi
m}}{\sqrt{2\pi(m+1-k)}}=1.$

For the second term, we show it is negligible. Note that

$\displaystyle\mathbb{P}\left(\tau_{m}>k;S_{k}>\epsilon\sqrt{m}\big{|}\,S_{m+1}=0\right)$
$\displaystyle\leq\frac{\mathbb{P}\left(S_{k}>\epsilon\sqrt{m}\right)}{f_{m+1}(0)}=(1+o(1))\sqrt{2\pi
m}\,\mathbb{P}\left(S_{k}>\epsilon\sqrt{m}\right).$

Applying Chernoff’s bound, it holds for every $t\geq 0$,

$\displaystyle\mathbb{P}\left(S_{k}>\epsilon\sqrt{m}\right)\leq\textrm{exp}\left\\{-t\epsilon\sqrt{m}+kt+k\log\left(\frac{1}{1+t}\right)\right\\}.$

In particular, this holds for $t=\epsilon\sqrt{m}/(k-\epsilon\sqrt{m})>0$ (for
$m$ large enough). Using this choice of $t$ and applying series expansions, we
derive

$\displaystyle\mathbb{P}\left(S_{k}>\epsilon\sqrt{m}\right)$
$\displaystyle\leq\textrm{exp}\left\\{-\left(\frac{\epsilon^{2}m}{k}+\epsilon\sqrt{m}\right)\frac{1}{1-\epsilon\sqrt{m}/k}+k\log\left(1-\frac{\epsilon\sqrt{m}}{k}\right)\right\\}$
$\displaystyle=\textrm{exp}\left\\{-\frac{\epsilon^{2}m+\epsilon\sqrt{m}k}{k}\left(1+\frac{\epsilon\sqrt{m}}{k}+O\left(\frac{m}{k^{2}}\right)\right)-\epsilon\sqrt{m}-\frac{\epsilon^{2}m}{2k}-O\left(\frac{m^{3/2}}{k^{2}}\right)\right\\}$
$\displaystyle=\textrm{exp}\left\\{-\frac{\epsilon^{2}m}{k}+o(1)\right\\}.$

Due to Corollary 4.9,

$\displaystyle\mathbb{P}\left(\tau_{m}>k\right)=\Theta\left(k^{-1/2}\right),$

and hence

$\displaystyle\frac{\mathbb{P}\left(\tau_{m}>k;S_{k}>\epsilon\sqrt{m}\big{|}\,S_{m+1}=0\right)}{\mathbb{P}\left(\tau_{m}>k\right)}=O\left(\sqrt{km}\;\textrm{exp}\left\\{-\frac{\epsilon^{2}m}{k}+o(1)\right\\}\right)=o(1).$

We conclude the upper bound

$\displaystyle\limsup_{m\rightarrow\infty}\frac{\mathbb{P}\left(\tau_{m}>k\big{|}\,S_{m+1}=0\right)}{\mathbb{P}\left(\tau_{m}>k\right)}\leq
1.$

For a lower bound, we observe

$\displaystyle\mathbb{P}\left(\tau_{m}>k\big{|}\,S_{m+1}=0\right)$
$\displaystyle\geq\mathbb{P}\left(\tau_{m}>k;S_{k}\leq\epsilon\sqrt{m}\big{|}\,S_{m+1}=0\right)$
$\displaystyle\geq(1+o(1))\sqrt{2\pi
m}\mathbb{P}\left(\tau_{m}>k\right)\inf_{u\in[1-\theta+\sum_{j=1}^{k}\left(1-L_{j,m}\right),\epsilon\sqrt{k}]}f_{m+1-k}(-u).$

Due to Proposition 4.8, it holds with probability $1-o(m^{-1/2})$ that

$\displaystyle\bigg{|}\sum_{j=1}^{k}\left(1-L_{j,m}\right)\bigg{|}=o(\sqrt{k}).$

Combining this observation with (83) yields

$\displaystyle\inf_{u\in[1-\theta+\sum_{j=1}^{k}\left(1-L_{j,m}\right),\epsilon\sqrt{k}]}f_{m+1-k}(-u)=(1+o(1))\frac{1}{\sqrt{2\pi
m}}e^{-\frac{\epsilon^{2}}{2}}.$

We conclude that

$\displaystyle\liminf_{m\rightarrow\infty}\frac{\mathbb{P}\left(\tau_{m}>k\big{|}\,S_{m+1}=0\right)}{\mathbb{P}\left(\tau_{m}>k\right)}\geq
e^{-\frac{\epsilon^{2}}{2}}.$

As $\epsilon\downarrow 0$, the lower bound tends to one as well. We conclude
that as $m\rightarrow\infty$,

$\displaystyle\mathbb{P}\left(\tau_{m}>k\big{|}\,S_{m+1}=0\right)\sim\mathbb{P}\left(\tau_{m}>k\right)\sim\frac{2\theta}{\sqrt{2\pi}}k^{-1/2}$

due to Corollary 4.9.

###  4.4 Proof of main result

As is laid out in the proof strategy described in Section 2.3, it only remains
to be shown that the stopping times $\upsilon(k)$ and $\varrho(k)$, as defined
in (10) and (11) respectively, are close to $k$. This follows from the
extremely likely events that only a few components disconnect from the giant,
and that such components are relatively small. In particular, it is likely
that $\upsilon(k)=k-o(k)$ and $\varrho(k)=k+o(k)$.

######  Lemma 4.10.

Suppose $k=o(m^{\alpha})$ for some $\alpha\in(0,1)$. Then,

$\displaystyle\mathbb{P}\left(\upsilon(k)\leq
k-k^{\alpha}\right)=o(m^{-1/2}).$

######  Lemma 4.11.

Suppose $k=o(m^{\alpha})$ for some $\alpha\in(0,1)$. Then,

$\displaystyle\mathbb{P}\left(\varrho(k)>k+k^{\frac{\alpha+1}{2}}\right)=o(m^{-1/2}).$

The proofs of these two lemma are fairly straightforward, and given in
Appendix C for completeness. Using these lemmas, we can prove our main result.

###### Proof of Theorem 1.3.

Using the proof strategy as laid out in Section 2.3, we have the upper bound

$\displaystyle\mathbb{P}\left(A_{n,\mathbf{d}}\geq k\right)$
$\displaystyle\leq\mathbb{P}\left(\hat{A}_{n,\mathbf{d}}\geq\kappa(\upsilon(k))\right)\leq\mathbb{P}\left(\hat{A}_{n,\mathbf{d}}\geq\kappa(\upsilon(k))\;\big{|}\;\upsilon(k)\geq
k-k^{\alpha}\right)+\mathbb{P}\left(\upsilon(k)\leq k-k^{\alpha}\right),$

where, due to Proposition 2.4,

$\displaystyle\mathbb{P}\left(\hat{A}_{n,\mathbf{d}}\geq\kappa(\upsilon(k))\;\big{|}\;\upsilon(k)\geq
k-k^{\alpha}\right)$
$\displaystyle\leq\mathbb{P}\left(\hat{A}_{n,\mathbf{d}}\geq\kappa(k-k^{\alpha})\right)\sim\frac{2\theta}{\sqrt{2\pi}}(k-k^{\alpha})^{-1/2}\sim\frac{2\theta}{\sqrt{2\pi}}k^{-1/2}.$

Due to Lemma 4.10,

$\displaystyle\mathbb{P}\left(\upsilon(k)\leq
k-k^{\alpha}\right)=o(m^{-1/2})=o(k^{-1/2}).$

For the lower bound, we observe

$\displaystyle\mathbb{P}$ $\displaystyle\left(A_{n,\mathbf{d}}\geq
k\right)\geq\mathbb{P}\left(\hat{A}_{n,\mathbf{d}}\geq\kappa(\varrho(k))\right)\geq\mathbb{P}\left(\hat{A}_{n,\mathbf{d}}\geq\kappa(\varrho(k))\;\big{|}\;\varrho(k)\leq
k+k^{(\alpha+1)/2}\right)\mathbb{P}\left(\varrho(k)\leq
k+k^{(\alpha+1)/2}\right).$

By Proposition 2.4,

$\displaystyle\mathbb{P}\left(\hat{A}_{n,\mathbf{d}}\geq\kappa(\varrho(k))\;\big{|}\;\varrho(k)\leq
k+k^{(\alpha+1)/2}\right)$
$\displaystyle\geq\mathbb{P}\left(\hat{A}_{n,\mathbf{d}}\geq\kappa\left(k+k^{(\alpha+1)/2}\right)\right)$
$\displaystyle\sim\frac{2\theta}{\sqrt{2\pi}}\left(k+k^{(\alpha+1)/2}\right)^{-1/2}\sim\frac{2\theta}{\sqrt{2\pi}}k^{-1/2},$

and due to Lemma 4.11,

$\displaystyle\mathbb{P}\left(\varrho(k)\leq
k+k^{(\alpha+1)/2}\right)=1-o(m^{-1/2}).$

##  5 Universality principle

Theorem 2.2 described the tail behavior of the failure size in case of
sublinear thresholds. In this section, we consider whether the scale-free
behavior prevails if the threshold is of linear size, i.e. the threshold is of
the same order as the number of vertices/edges. We conjecture that the scale-
free behavior prevails up to a critical point. Also, we provide an explanation
why the scale-free behavior can extend to a wide class of other graphs as
well. We stress that the arguments that are provided in this section are
intuitive in nature, and rigorous proofs of the claims remain to be
established.

The proof of Theorem 2.2 relies on the translation to a first-passage time of
the random walk bridge $S_{i,m}$ over a (moving) boundary that is close to
constant $1-\theta$. We prove that the difference $S_{i,m}-S_{i}$ is small
(Proposition 4.8) if $k$ is sublinear, causing the random walk $S_{i,m}$ to be
asymptotically indistinguishable from $S_{i}$ up to time $k$. That is, the
random walk bridge is asymptotically indistinguishable from the one
corresponding to the star topology. Since $S_{i}$ is a random walk with
independent identically distributed increments with zero mean and finite
variance, it is well-known by Donsker’s theorem that appropriately scaling the
random walk bridge $S_{i}$ yields convergence to a Brownian bridge. Therefore,
the probability that $A_{n,\mathbf{d}}$ exceeds $k$ asymptotically behaves the
same as the probability that a Brownian bridge stays above zero until time
$k$, multiplied by a constant that relates to the translation of the boundary
to any other (constant) boundary. We recall that in case of
$S_{i}=\sum_{j=1}^{i}(1-\textrm{Exp}_{j}(1))$ and a boundary (close to)
$1-\theta$, this constant is given by $\theta$.

When the threshold $k:=k_{m}$ is of the same order as $m$, this analysis does
not follow through. The (maximum) difference between the two random walks up
to time $k$ is likely to become of order $\Theta(\sqrt{k})=\Theta(\sqrt{m})$,
an order of magnitude that affects the asymptotic behavior. Moreover, the
number of edges outside the giant is also no longer likely to be of size
$o(m)$, and hence we need to understand what the failure behavior typically is
in these components as well. The natural question that comes to mind is
whether the scale-free behavior in the failure size tail prevails or not for
linear-sized thresholds. Next, we argue heuristically why this type of
behavior prevails up to a certain critical point.

If we remove $k=\beta m$ edges uniformly at random, where $\beta\in(0,q_{c})$,
then there is a non-vanishing proportion of edges outside the largest (giant)
component [25]. Nevertheless, the sizes of the components outside the giant
are relatively small, i.e. the number of edges in such a component is at most
$O_{\mathbb{P}}(\log m)$. It turns out that this causes it to be likely that
whenever a component detaches from the giant, the cascade stops in the small
component. More specifically, suppose that the edge with the $i$’th smallest
surplus capacity is contained in the giant upon failure, and causes a
component to detach a component from the giant. Due to the way that the total
load surge is defined, we conjecture that it is likely that the total load
surge is close to $i/m+\Theta(1/\sqrt{m})$ upon failure. Since the number of
edges in the smaller component is likely to be $O(\log m)$, all the surplus
capacities of these edges are likely to be at least $i/m+\Omega(1/\log m)$,
which is much larger than the total load surge. That is, all edges are likely
to have sufficient capacity to deal with the load, and no more failures occur
in the smaller detached component. Moreover, even if the cascade continues, it
would contribute at most a logarithmic number of edges to the total failure
size. These observations lead to the claim that the dominant contribution in
the failure size comes from the number of edges that are contained in the
giant upon failure.

To track the failure behavior in the giant component, one can use the sequence
of random walks $S_{i,m}$. That is, the translation of the failure size to the
first-passage time of the random walk bridge over the constant boundary
$1-\theta$ remains (likely to be) true if $k\leq\beta m$ with
$\beta\in(0,q_{c})$. Although the random walk is no longer close to $S_{i}$,
the increments of $S_{i,m}$ do have zero mean and a variance that is likely to
be finite (and non-constant), and hence satisfy a martingale property.
Therefore, we conjecture that the probability that the failure size in the
giant component exceeds $\kappa(k)$ behaves the same as the probability that a
Brownian bridge (with non-constant variance) stays above zero until time $k$,
multiplied by a constant.

Since we argued that it should hold that
$A_{n,\textbf{d}}\approx\hat{A}_{n,\textbf{d}}$, this leads to the following
conclusion. Write $k=\alpha m$ with $\alpha\in(0,1)$. In view of (59), we
observe that for all $i:=i_{m}$ sufficiently smaller than the critical point
$q_{c}$, it holds that $\kappa(i)\approx
m\int_{0}^{i/m}\xi_{\mathbf{d}}(q)\mathrm{d}q$. Write

$\displaystyle\beta_{\alpha}:=\min_{x\in(0,1)}\left\\{\int_{0}^{x}\xi_{\mathbf{d}}(q)\mathrm{d}q=\alpha\right\\}.$
(84)

Then $\varrho(k)\approx\beta_{\alpha}m$, since

$\displaystyle\kappa(\varrho(k))=k=\alpha m\approx\kappa(\beta_{\alpha}m).$

Therefore,

$\displaystyle\mathbb{P}(A_{n,\textbf{d}}\geq
k)\sim\mathbb{P}(\hat{A}_{n,\textbf{d}}\geq
k)\sim\mathbb{P}(\hat{A}_{n,\textbf{d}}\geq\kappa(\beta_{\alpha}m)).$

Summarizing, we have the following conjecture for $\overline{CM}_{n}(d,q)$.
Suppose $k=\alpha m$ with $\alpha\in(0,1)$ such that $\beta_{\alpha}<q_{c}$ is
satisfied. Then,

$\displaystyle\mathbb{P}(A_{n,\textbf{d}}\geq k)\sim f(\alpha)k^{-1/2}.$

Figure 2: Erased configuration model.

To support this conjecture, we performed a Monte-Carlo simulation experiment.
In particular, we tested the conjecture against the erased configuration
model. That is, we create this graph according to the configuration model
mechanism with a prescribed degree sequence. We merge multiple edges and erase
self-loops. Moreover, after sampling such a graph, we remove any smaller
components such that the final graph is a simple connected graph. Due to the
properties of the configuration model, the number of self-loops and multiple
edges is very small (if any), and only a finite number of vertices and edges
are not contained in the giant. As a result, this graph and the configuration
model conditioned on connectivity are indistinguishable asymptotically, and
will lead to the same asymptotic result for the number of edge failures. In
our simulations we choose $n\in\\{500,1000,1500,2000\\}$, and a degree
sequence with $n_{1}=\lceil n^{1/3}\rceil$ vertices of degree one,
$n_{2}=n_{3}=n/2-\lceil n^{1/3}\rceil$ and $n_{4}=\lceil n^{1/3}\rceil$.
Therefore, the number of edges is (close to) $m=5/4n$. The results are
displayed in Figure 2. Indeed, it appears that our conjecture holds in this
case.

Not only do we believe that this conjecture holds for the connected
configuration model, we argue that the scale-free behavior may hold for a
wider range of graphs. In particular, the relevant properties of the
configuration model that we used in the analysis are the following. First, it
is likely that no (significant) disconnections occur at the beginning of the
cascading failure process. For example, in the case of a configuration model,
we showed that the first disconnection is likely to occur after
$\Theta(\sqrt{m})$ edge failures. Secondly, whenever the cascading failure
process causes disconnections to occur, a giant component appears and
disconnections only create relatively small components. It is well-known that
this property is satisfied up to a certain critical threshold $q_{c}$ for the
configuration model, but this holds in fact for many more types of random
graphs. In other words, for our result to prevail in other graph topologies,
the graph should satisfy the following two properties:

  * •

The first disconnection (if any) is only likely to occur after
$\Omega(m^{\delta})$ failures, where $\delta>0$;

  * •

There exists a critical parameter $q_{c}$ such that if $q<q_{c}$, the largest
component of the percolated graph is unique w.h.p. and contains a non-
vanishing proportion of the vertices and edges. Moreover, all other components
are likely to be relatively small for $q<q_{c}$, e.g. the second largest
component contains at most $O_{\mathbb{P}}((\log m)^{c})$ number of edges for
some $c<\infty$.

Whenever a graph $G=(V,E)$ satisfies these two properties, we conjecture that
the number of edge failures $A_{G}$ exhibits scale-free behavior. That is, for
a range of thresholds $k:=k_{m}$, it holds that

$\displaystyle\mathbb{P}\left(A_{G}\geq k\right)\sim f_{G}(\alpha)k^{-1/2},$
(85)

where $f_{G}(\cdot)>0$ and $\alpha=\lim_{m\rightarrow\infty}k/m$. In
particular, $f_{G}(0)=2\theta/\sqrt{2\pi}$. The function $f_{G}$ depends on
the specifics of the graph, such as average degree and more detailed
connectivity properties. The range of values for $k$ for which (85) holds
depends on the critical threshold $q_{c}$ and the typical number of edges that
are outside the giant component.

Figure 3: $\lceil\sqrt{n}\rceil\times\lceil\sqrt{n}\rceil$ square lattice
graph.

To test conjecture (85), we first consider a
$\lceil\sqrt{n}\rceil\times\lceil\sqrt{n}\rceil$ square lattice graph where
the opposite boundaries are not connected with $n\in\\{500,1000,1500,2000\\}$.
On the square lattice it is known that there is a phase transition for the
existence of a giant component when $q_{c}=1/2$ [21]. Moreover, significant
disconnections occur only after quite a significant number of failures have
occurred. Indeed, to disconnect one edge $e$ (not on the boundary) from the
giant we need to remove at least six edges (the ones that share an end-vertex
with $e$). This suggests that since there are roughly $2n$ edges in the graph,
the first time the process produces an edge disconnected from the giant should
be of order $\Theta(n^{5/6})$. Moreover, it is known that in this regime the
second largest component in a box of volume $n$ is polylogarithmic in $n$
[22]. Thus, it satisfies the conditions we conjecture for a graph to be in the
same mean-field universality class as the configuration model. In Figure 3, we
observe that indeed the first significant disconnections happen after a much
longer time than in $CM_{n}(\mathbf{d})$, and the limiting function for
$k^{1/2}\mathbb{P}\left(A_{Lattice}\geq k\right)$ remains very close to the
setting where no disconnection takes place for a relatively long time.

Figure 4: Giant component of the Erdös-Rényi random graph with edge retention
probabability $2/n$, where $m_{ER}=\lambda(1-\eta_{\lambda}^{2})n/2$.

Secondly, we consider the giant component of the Erdös-Rényi random graph.
That is, for every pair of the $n$ vertices, there exists an edge with
probability $\lambda/n$, and we consider the cascading failure process on the
giant component. The giant is uniquely defined asymptotically: it is well-
known that for every $\lambda>1$ there exists a unique giant component
$\mathcal{C}_{\rm max}$ for which holds that [16],

$\displaystyle\frac{|\\{v:v\in\mathcal{C}_{\max}\\}|}{n}\overset{\mathbb{P}}{\longrightarrow}\zeta_{\lambda},$

where $\zeta_{\lambda}=1-\eta_{\lambda}>0$ and $\eta_{\lambda}$ satisfies the
fixed-point equation

$\displaystyle\eta_{\lambda}=\mathbb{E}\left(\eta_{\lambda}^{\textrm{Pois}(\lambda)}\right)=1-e^{-\lambda\eta_{\lambda}}.$

In our simulation experiment, we choose $n\in\\{500,1000,1500,2000\\}$
possible vertices, and $\lambda=2$. Therefore, the graph on which we perform
the cascading failure process is likely to have around $\zeta_{\lambda}n$
vertices and $\lambda(1-\eta_{\lambda}^{2})n/2$ edges (with $\Theta(\sqrt{n})$
fluctuations). From the definition of the Erdös-Rényi random graph it is clear
that if we run a percolation process on it, the resulting graph is again an
Erdös-Rényi random graph, but with a smaller $\lambda$. It is known that for
every $\lambda>1$ all the components outside the giant are at most of size
$\Theta(\log n)$. Therefore, the disintegration of the network is similar to
the one of the configuration model, yet with the critical edge-removal
probability corresponding to $q_{c}=(\lambda-1)/\lambda$ in this case.

However, the first disconnection is likely to occur after finitely many edge
failures, since the number of vertices with degree one in the giant of an
Erdös Rényi graph is likely to be of order $\Theta(n)$. In other words, this
graph violates the condition that the first disconnections should occur after
$\Omega(m^{\delta})$ edge failures for some $\delta>0$. Nevertheless, it
appears from our simulation result that (85) still prevails, see Figure 4. In
other words, the condition on no early disconnections can possibly be relaxed.
The analysis would require significant changes, and particularly, the results
on the distribution of first-passage times over moving boundaries such as
Lemmas 4.4 and 4.6, as the load surge is no longer almost deterministic at the
beginning of the process.

Figure 5: Graph $G=CS(n,4)$.

In contrast, we consider a graph $G=CS(n,4)$ consisting of $n$ star-components
with $4$ edges each, connected by a single path of edges connecting all the
components. This graph thus consists of $5n$ vertices and also $m=5n$ edges.
We observe that as soon as one of the $n$ edges on the single path fails, the
remaining graph is a (connected) tree. Therefore, with high probability, the
graph would disconnect in two components both of order $\Theta(m)$ after
removing only a fixed number of edges. This effect is likely to occur again in
both components when edges are removed uniformly at random in these
components. This violates both properties we needed to prove our result for
the configuration model. We observe in Figure 5 that indeed
$k^{1/2}\mathbb{P}\left(A_{CS}\geq k\right)$ does not seem to converge to a
single function as $n\rightarrow\infty$.

## References

  * [1] P. Bak and C. Tang.  Earthquakes as a self-organized critical phenomenon.  Journal of Geophysical Research: Solid Earth, 94(B11):15635–15637, 1989.
  * [2] P. Bak, C. Tang, and K. Wiesenfeld.  Self-organized criticality: An explanation of the 1/f noise.  Physical Review Letters, 59:381–384, 1987.
  * [3] P. Bak, C. Tang, and K. Wiesenfeld.  Self-organized criticality.  Physical Review A, 38:364–374, 1988.
  * [4] A. Barabási.  The origin of bursts and heavy tails in human dynamics.  Nature, 435(7039):207, 2005.
  * [5] A. Barabási and R. Albert.  Emergence of scaling in random networks.  Science, 286(5439):509–512, 1999.
  * [6] D. Bienstock.  Electrical transmission system cascades and vulnerability - an operations research viewpoint, volume 22 of MOS-SIAM Series on Optimization.  SIAM, 2016.
  * [7] B. A. Carreras, V. E. Lynch, I. Dobson, and D. E. Newman.  Complex dynamics of blackouts in power transmission systems.  Chaos: An Interdisciplinary Journal of Nonlinear Science, 14(3):643–652, 2004.
  * [8] B. K. Chakrabarti.  A fiber bundle model of traffic jams.  Physica A: Statistical Mechanics and its Applications, 372(1):162–166, 2006.
  * [9] A. Clauset, C. R. Shalizi, and M. E. J. Newman.  Power-law distributions in empirical data.  SIAM review, 51(4):661–703, 2009.
  * [10] D. Denisov, A. Sakhanenko, and V. Wachtel.  First-passage times for random walks with nonidentically distributed increments.  Ann. Probab., 46(6):3313–3350, 11 2018.
  * [11] S. Dhara, R. van der Hofstad, J. S. H. van Leeuwaarden, and S. Sen.  Critical window for the configuration model: finite third moment degrees.  Electronic Journal of Probability, 22:Paper No. 16, 33, (2017).
  * [12] R. A. Doney.  Local behaviour of first passage probabilities.  Probability Theory and Related Fields, 152(3):559–588, 2012.
  * [13] L. Federico and R. Hofstad.  Critical window for connectivity in the configuration model.  Combinatorics, Probability and Computing, 26(5):660–680, 2017\.
  * [14] E. N. Gilbert.  Random graphs.  Annals of Mathematical Statistics, 30:1141–1144, (1959).
  * [15] P. E. Greenwood and A. A. Novikov.  One-sided boundary crossing for processes with independent increments.  Theory of Probability & Its Applications, 31(2):221–232, 1987\.
  * [16] R. Hofstad.  Random graphs and complex networks. Volume 1.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, (2017).
  * [17] S. Janson.  The largest component in a subcritical random graph with a power law degree distribution.  The Annals of Applied Probability, 18(4):1651–1668, (2008).
  * [18] S. Janson.  On percolation in random graphs with given vertex degrees.  Electronic Journal of Probability, 14:no. 5, 87–118, (2009).
  * [19] S. Janson.  The probability that a random multigraph is simple.  Combinatorics, Probability and Computing, 18(1-2):205–225, (2009).
  * [20] S. Janson.  The probability that a random multigraph is simple. II.  Journal of Applied Probability, 51A(Celebrating 50 Years of The Applied Probability Trust):123–137, (2014).
  * [21] H. Kesten.  The critical probability of bond percolation on the square lattice equals ${1\over 2}$.  Communications in Mathematical Physics, 74(1):41–59, (1980).
  * [22] H. Kesten and Y. Zhang.  The probability of a large finite cluster in supercritical Bernoulli percolation.  The Annals of Probability, 18(2):537–555, (1990).
  * [23] M. Korkali, J. G. Veneman, B. Tivnan, and P. Hines.  Reducing cascading failure risk by increasing infrastructure network interdependency.  Scientific Reports, 7, 10 2017.
  * [24] T. Łuczak.  Sparse random graphs with a given degree sequence.  In Random graphs, Vol. 2 (Poznań, 1989), Wiley-Intersci. Publ., pages 165–182. Wiley, New York, (1992).
  * [25] M. Molloy and B. Reed.  A critical point for random graphs with a given degree sequence.  In Proceedings of the Sixth International Seminar on Random Graphs and Probabilistic Methods in Combinatorics and Computer Science, “Random Graphs ’93” (Poznań, 1993), volume 6, pages 161–179, (1995).
  * [26] F. Morone and H. A. Makse.  Influence maximization in complex networks through optimal percolation.  Nature, 524(7563):65, 2015.
  * [27] A. E. Motter.  Cascade control and defense in complex networks.  Physical Review Letters, 93:098701, Aug 2004.
  * [28] A. E. Motter and Y. C. Lai.  Cascade-based attacks on complex networks.  Physical Review E, 66(065102), 2002.
  * [29] V. V. Petrov.  Sums of Independent Random Variables.  Ergebnisse der Mathematik und ihrer Grenzgebiete. Springer Berlin Heidelberg, 1975.
  * [30] S. Pradhan, A. Hansen, and B.K. Chakrabarti.  Failure processes in elastic fiber bundles.  Reviews of Modern Physics, 82(1):499–555, 2010.
  * [31] J. Qi, I. Dobson, and S. Mei.  Towards estimating the statistics of simulated cascades of outages with branching processes.  IEEE Transactions on Power Systems, 28(3):3410–3419, Aug 2013.
  * [32] H. A. Simon.  On a clas of skew distribution functions.  Biometrika, 42(3-4):425–440, 12 1955.
  * [33] F. Sloothaak, S. C. Borst, and B. Zwart.  Robustness of power-law behavior in cascading line failure models.  Stochastic Models, 34(1):45–72, 2018.
  * [34] F. Sloothaak, S. C. Borst, and B. Zwart.  The impact of a network split on cascading failure processes.  Stochastic Systems, 9(4):392–416, 2019.
  * [35] F. Sloothaak, V. Wachtel, and B. Zwart.  First-passage time asymptotics over moving boundaries for random walk bridges.  Journal of Applied Probability, 55(2):627–651, 2018.
  * [36] B. Suki, A. Barabási, Z. Hantos, F. Peták, and H. E. Stanley.  Avalanches and power-law behaviour in lung inflation.  Nature, 368(6472):615, 1994.
  * [37] K. Sun, Y. Hou, W. Sun, and J. Qi.  Power System Control Under Cascading Failures: Understanding, Mitigation, and System Restoration.  Wiley-IEEE Press, 2019.
  * [38] V. Wachtel and D. Denisov.  An exact asymptotics for the moment of crossing a curved boundary by an asymptotically stable random walk.  Theory of Probability & Its Applications, 60(3):481–500, 2016\.
  * [39] Z. Wang, A. Scaglione, and R. J. Thomas.  Generating statistically correct random topologies for testing smart grid communication and control networks.  IEEE Transactions on Smart Grid, 1(1):28–39, June 2010.
  * [40] D.J. Watts.  A simple model of global cascades on random networks.  Proceedings of the National Academy of Sciences of the United States of America, 99(9):5766, 2002.
  * [41] J. Zheng, Z. Gao, X. Zhao, and F. Bai-Bai.  Extended fiber bundle model for traffic jams on scale-free networks.  International Journal of Modern Physics C (IJMPC), 19(11):1727–1735, 2008.

##  Appendix A Lists of variables

$n$ |  # vertices
---|---
$\mathbf{d}$ |  (Fixed) degree sequence
$m=m_{n}(\mathbf{d})$ |  # edges in a configuration model with degree sequence $\mathbf{d}$
$CM_{n}(\mathbf{d})$ |  Configuration model with degree sequence $\mathbf{d}$
$\overline{CM}_{n}(\mathbf{d})$ |  Configuration model with degree sequence $\mathbf{d}$ conditioned to be connected
$n_{i}$ |  # vertices with degree $i$
$p_{i}$ |  Fraction of vertices with degree $i$
$D_{n}$ |  Degree of a vertex chosen uniformly at random from $[n]$
$D$ |  Limiting degree variable of $D_{n}$
$d$ |  Average degree of $\mathbf{d}$
$\theta$ |  Disturbance constant
$l_{j}^{m}(i)$ |  Total load surge at edge $j$ after experiencing $i$ load surges in a graph with $m$ edges
$|E_{j}^{m}(i)|$ |  # edges in the component containing edge $j$ after experiencing $i$ load surges
$A_{n,\mathbf{d}}$ |  # edge failures after the cascading failure process
Table 1: List of variables commonly used throughout this chapter. $q$ |  Removal probability in the percolation process
---|---
$CM_{n}(\mathbf{d},q)$ |  Percolated configuration model with removal probability $q$
$\mathcal{C}$ |  Component of a graph, sometimes also denoted as $\mathcal{C}(x)$ when referring to the component that contains vertex or edge $x$
$\mathcal{C}_{\rm max}$ |  Largest component of a graph
$T_{n,\mathbf{d}}$ |  # edges that are sequentially removed uniformly at random for the first disconnection to occur in the connected configuration model
$T$ |  Limiting variable of $m^{1/2}T_{n,\mathbf{d}}$
$|\hat{E}_{m}(i)|$ |  # edges in the giant (largest) component after $i$ edges have been removed uniformly at random
$|\tilde{E}_{m}(i)|$ |  # edges outside the giant (largest) component after $i$ edges have been removed uniformly at random
Table 2: List of variables commonly used in percolation/sequential edge-removal process. $R_{n}$ |  # removed half-edges in the first step of the explosion algorithm
---|---
$\mathbf{d}^{\prime}$ |  Degree sequence of configuration graph in step three of the explosion method ($\mathbf{d}^{\prime}\in\mathbb{N}^{n+R_{n}}$)
$CM_{N}(\mathbf{d}^{\prime})$ |  Configuration model in step three of the explosion method with degree sequence $\mathbf{d}^{\prime}$
$CM_{n}(\mathbf{d},q)$ |  Resulting configuration model in step four of the explosion method, indistinguishable from the percolated configuration model with removal probability $q$
$n_{i}^{\prime}$ |  # vertices of degree $i$ in $CM_{N}(\mathbf{d}^{\prime})$
$p_{i}^{\prime}$ |  $\lim_{n\rightarrow\infty}n_{i}^{\prime}/n$
$n_{l,j}$ |  # vertices of degree $l$ in d that have degree $j$ in $\textbf{d}^{\prime}$
$p_{l,j}$ |  Probability for a vertex of degree $l$ to retain $j$ half-edges after the first step of the explosion algorithm
$L_{k}^{\prime}(n)$ |  # components that are lines of length $k\geq 2$ in $CM_{N}(\mathbf{d}^{\prime})$
$C_{k}^{\prime}(n)$ |  # components that are cycles of length $k\geq 1$ in $CM_{N}(\mathbf{d}^{\prime})$
Table 3: List of variables commonly used in the explosion algorithm. $\hat{A}_{n,\mathbf{d}}$ |  # edges that were contained in the largest component upon failure during the cascade
---|---
$\tilde{A}_{n,\mathbf{d}}$ |  # edges that were contained outside the largest component upon failure during the cascade
$A_{n+1}^{*}$ |  # edge failures in the cascading failure process on a star topology with $n+1$ nodes and $m=n$ edges
$\kappa(i)$ |  # edges that are contained in the largest component upon removal when $i$ edges are sequentially removed uniformly at random
$\upsilon(i)$ |  Minimum # edges that need to be removed uniformly at random for the sum of $\upsilon(i)$ and # edges outside the giant to exceed $i$
$\varrho(i)$ |  # edges that need to be removed uniformly at random such that $i$ edges were contained in the giant component upon failure
$S_{i}$ |  $\sum_{j=1}^{i}\left(1-\textrm{Exp}_{j}(1)\right)$
$L_{i,m}$ |  Scaled perturbed load surge, formally defined as in (80)
$S_{i,m}$ |  Random walk defined as $\sum_{j=1}^{i}L_{j,m}-\textrm{Exp}_{j,m}(1)$
$Y_{i,m}$ |  Random walk $\sum_{j=1}^{i}(1-L_{j,m})$
$\tau_{m}$ |  First-passage time of random walk $S_{i,m}$ to be less than $1-\theta$
$T_{g}$ |  First-passage time of random walk $S_{i}$ to move below a boundary sequence $(g_{i})_{i\in\mathbb{N}}$
Table 4: List of variables commonly used in the failure process.

##  Appendix B Proofs of results on the disintegration of the graph

In this appendix, we present several proofs of results given in Section 3.

###### Proof of Lemma 3.1.

Due to the i.i.d. property of the surplus capacities, it holds that
$\tilde{E}^{\prime}(i)$ has the distribution of $i$ edges chosen uniformly
without repetitions from $[m]$, so
$\mathbb{P}(\tilde{E}^{\prime}(i)=B)=\binom{m}{i}^{-1}$.

Since all edges in $CM_{n}(\mathbf{d},q)$ are removed independently with
probability $q$, it holds for all sets $B\subseteq E$ with $|B|=i$ that

$\displaystyle\mathbb{P}(E^{\prime}(G(q))=B)=q^{i}(1-q)^{m-i},$ (86)

while

$\displaystyle\mathbb{P}(|E^{\prime}(G(q))|=i)=\binom{m}{i}q^{i}(1-q)^{m-i}.$
(87)

Since $\\{E^{\prime}(G(q))=B\\}\subseteq\\{|E^{\prime}(G(q))|=i\\}$, we obtain

$\displaystyle\mathbb{P}(E^{\prime}(G(q))=B\mid|E^{\prime}(G(q))|=i)=\binom{m}{i}^{-1},$
(88)

so (12) holds. From (87) we obtain (13) by concentration of
$\textrm{Bin}(m,q)$ if $qm\to\infty$.

###### Proof of Lemma 3.7.

We use the explosion algorithm from Algorithm 1. To illustrate the type of
arguments we use to prove this statement, we first consider the first moment
only.

Define $\mathcal{V}_{j}$ as the set of all vertices of degree $j$ in
$\mathbf{d}^{\prime}$. Recall the degree sequence $\mathbf{d}^{\prime}$ from
Lemma 3.4, and we define

$\displaystyle
L_{k}=\\{\\{v_{1},v_{2},...,v_{k}\\}:v_{1},v_{k}\in\mathcal{V}_{1};v_{2},...,v_{k-1}\in\mathcal{V}_{2}\\},$

the set of all collections of $k$ vertices that could form a line. Note that

$\displaystyle
L_{k}^{\prime}(n)=\sum_{l\in\mathcal{L}_{k}}\mathbbm{1}_{\\{l\text{ forms a
line}\\}}.$

Due to Lemma 3.4, we observe that

$\displaystyle\mathbb{E}$
$\displaystyle[L_{k}^{\prime}(n)]=\mathbb{E}\left[\sum_{l\in\mathcal{L}_{k}}\mathbbm{1}_{\\{l\text{
forms a line}\\}}\right]$
$\displaystyle=\mathbb{E}\left[\binom{n_{1}^{\prime}}{2}\binom{n_{2}^{\prime}}{k-2}\frac{2k-4}{2m-1}\frac{2k-6}{2m-3}\cdots\frac{2}{2m-2k+5}\frac{1}{2m-2k+3}\right]$
$\displaystyle=\mathbb{E}\left[\frac{{n_{1}^{\prime}}^{2}{n_{2}^{\prime}}^{k-2}}{2(k-2)!}\frac{(2k-4)!!}{(2m)^{k-1}}\right](1+o(1))=\frac{i^{2}}{m}\frac{1}{4}\Big{(}1+\frac{2p_{2}}{d}\Big{)}^{2}\Big{(}\frac{2p_{2}}{d}\Big{)}^{k-2}(1+o(1)).$

Next, we generalize these arguments to higher and mixed moments of the
variables $(L_{k}^{\prime}(n))_{n\geq 2}$. We follow the same approach used in
[13] where the convergence of the number of lines to a sequence of Poisson
variables was proved in the critical window for connectivity. Using the method
of moments, in this case, we need to prove concentration of the number of
vertices and edges in line components.

We prove (39) by induction. With a slight abuse of notation, we start the
induction step at $k=1$, or alternatively, at $k=2$ with $r_{2}=0$. Then, both
sides in (39) are equal to one, and hence the induction hypothesis is
satisfied.

Next, we show how to advance the induction hypothesis. We define

$\displaystyle
W_{k}(\mathbf{r})=\left\\{\bigcup_{j=2}^{k}\\{l_{j}(1),...,l_{j}(r_{j})\\}:l_{j}(h)\in\mathcal{L}_{j}\textrm{
for all }1\leq h\leq r_{j},2\leq j\leq k\right\\},$

the collection of sets of $\sum_{j=2}^{k}r_{j}$ possible lines. Moreover, for
a set $w_{k}(\mathbf{r})\in W_{k}(\mathbf{r})$, we define
$\mathcal{E}(w_{k}(\mathbf{r}))$ as the event that all elements in the set
$w_{k}(\mathbf{r})$ form a line component in $CM_{N}(\mathbf{d}^{\prime})$.
Then, using the tower property, we can rewrite

$\displaystyle\mathbb{E}[L_{2}^{\prime}(n)^{r_{2}}\cdots
L_{k}^{\prime}(n)^{r_{h}}]=\mathbb{E}\left[\sum_{w_{k}(\mathbf{r})\in
W_{k}(\mathbf{r})}\mathbbm{1}_{\mathcal{E}(w_{k}(\mathbf{r}))}\right]$
$\displaystyle=\mathbb{E}\left[\sum_{w_{k-1}(\mathbf{r})}\mathbbm{1}_{\mathcal{E}(w_{k-1}(\mathbf{r}))}\mathbb{E}\left[\sum_{l_{k}(1),\ldots,l_{k}(r_{k})\in\mathcal{L}_{k}}\mathbbm{1}_{l_{k}(1)}\mathbbm{1}_{l_{k}(2)}\cdots\mathbbm{1}_{l_{k}(r_{k})}\mid\mathcal{E}(w_{k-1}(\mathbf{r}))\right]\right],$

where $\mathbbm{1}_{l_{k}(h)}$ denotes the indicator of the event that the set
$l_{k}(h)$ forms a line. Next, we show that for every $w_{k}(\mathbf{r})\in
W_{k}(\mathbf{r})$,

$\displaystyle\Big{(}\frac{m}{i^{2}}\Big{)}^{r_{k}}\sum_{l_{k}(1),\ldots,l_{k}(r_{k})\in\mathcal{L}_{k}}$
$\displaystyle\mathbb{E}[\mathbbm{1}_{l_{k}(1)}\mathbbm{1}_{l_{k}(2)}\cdots\mathbbm{1}_{l_{k}(r_{k})}|\mathcal{E}(w_{k-1}(\mathbf{r}))]$
$\displaystyle=\left(\frac{1}{4}\Big{(}1+\frac{2p_{2}}{d}\Big{)}^{2}\Big{(}\frac{2p_{2}}{d}\Big{)}^{k-2}\right)^{r_{k}}(1+o(1)).$

Note that by induction, this suffices to conclude (39).

First, note that if any of the $l_{k}(j),1\leq j\leq r_{k},$ contains any of
the vertices used in $w_{k-1}(\mathbf{r})$, then it is not possible for it to
form a line of length $k$ as these vertices are already contained in line
components of a smaller length. In that case,
$\mathbb{E}[\mathbbm{1}_{l_{k}(1)}\mathbbm{1}_{l_{k}(2)}\cdots\mathbbm{1}_{l_{k}(r_{k})}\mid\mathcal{E}(w_{k-1}(\mathbf{r}))]=0$.
Therefore, we can consider the part of the graph excluding the line components
in $w_{k-1}(\mathbf{r})$. This part of the graph is also a configuration
model, but with a slightly altered degree sequence. Note that we exclude
finitely many line components of finite length, and hence only exclude
finitely many vertices and edges. With a slight abuse of notation, write
$r^{\prime}=r^{\prime}(l_{k}(1),...,l_{k}(r_{k}))$ as the number of mutually
distinct lines. Then the probability that $r^{\prime}$ mutually distinct lines
can be formed in the graph excluding the line components in
$w_{k-1}(\mathbf{r})$ is given by

$\displaystyle\mathbb{E}[\mathbbm{1}_{l_{k}(1)}\mathbbm{1}_{l_{k}(2)}\cdots\mathbbm{1}_{l_{k}(r_{k})}|\mathcal{E}(w_{k-1}(\mathbf{r}))]=\frac{(2k-4)!!^{r^{\prime}}}{(2m)^{r^{\prime}(k-1)}}(1+o(1)).$

We sum these contributions over the number of possible sets that exist in the
subgraph. Write $C(r_{k},r^{\prime})$ as the number of distinct sets of
$r_{k}$ lines that contain the same set of $r^{\prime}$ mutually distinct
lines of length $k$. Importantly, $C(r_{k},r_{k})=1$ and $C(r_{k},r^{\prime})$
is a finite integer if $1\leq r^{\prime}\leq r_{k}-1$. Recalling Lemma 3.4, we
obtain

$\displaystyle\Big{(}\frac{m}{i^{2}}\Big{)}^{r_{k}}$
$\displaystyle\sum_{l_{k}(1),\ldots,l_{k}(r_{k})\in\mathcal{L}_{k}}\mathbb{E}[\mathbbm{1}_{l_{k}(1)}\mathbbm{1}_{l_{k}(2)}\cdots\mathbbm{1}_{l_{k}(r_{k})}|\mathcal{E}(w_{k-1}(\mathbf{r}))]$
$\displaystyle=\Big{(}\frac{m}{i^{2}}\Big{)}^{r_{k}}\mathbb{E}\left[\sum_{r^{\prime}=1}^{r_{k}}C(r_{k},r^{\prime})\left(\frac{{n_{1}^{\prime}}^{2}{n_{2}^{\prime}}^{k-2}}{2(k-2)!}\frac{(2k-4)!!}{(2m)^{k-1}}\right)^{r^{\prime}}\right](1+o(1))$
$\displaystyle=\left(\frac{1}{4}\Big{(}1+\frac{2p_{2}}{d}\Big{)}^{2}\Big{(}\frac{2p_{2}}{d}\Big{)}^{k-2}\right)^{r_{k}}(1+o(1)),$

concluding the proof.

###### Proof of Corolllary 3.8.

Note that it follows from Lemma 3.7

$\displaystyle\mathbb{E}[L_{k}^{\prime}(n)]$
$\displaystyle=\frac{i^{2}}{m}\frac{1}{4}\Big{(}1+\frac{2p_{2}}{d}\Big{)}^{2}\Big{(}\frac{2p_{2}}{d}\Big{)}^{k-2}(1+o(1)),\hskip
28.45274ptk\geq 2.$

Consequently, for every $\varepsilon>0$ there exists a $N>0$ such that for all
$n\geq N$,

$\displaystyle\frac{m}{i^{2}}\mathbb{E}[L_{k}^{\prime}(n)]\leq\frac{1}{4}\Big{(}1+\frac{2p_{2}+\varepsilon}{d-\varepsilon}\Big{)}^{2}\Big{(}\frac{2p_{2}+\varepsilon}{d-\varepsilon}\Big{)}^{k-2},\hskip
28.45274ptk\geq 2.$

In particular, for $\varepsilon$ small enough
$\frac{2p_{2}+\varepsilon}{d-\varepsilon}<1$ so that the sequence converges to
zero exponentially fast in $k$. We apply dominated convergence to obtain

$\displaystyle\mathbb{E}\Big{[}\frac{m}{i^{2}}\sum_{k=2}^{\infty}kL_{k}^{\prime}(n)\Big{]}$
$\displaystyle\to\frac{(d-p_{2})(d+2p_{2})^{2}}{2d(d-2p_{2})^{2}},$ (89)
$\displaystyle\mathbb{E}\Big{[}\frac{m}{i^{2}}\sum_{k=2}^{\infty}(k-1)L_{k}^{\prime}(n)\Big{]}$
$\displaystyle\to\frac{(d+2p_{2})^{2}}{4(d-2p_{2})^{2}}.$ (90)

In other words, we have derived the expected number of vertices and edges in
line components in $CM_{N}(\mathbf{d}^{\prime})$. Next, we prove (40) for
every $j\geq 2$. We define for a sequence $\mathbf{r}$ of positive integer
values, $|\mathbf{r}|_{1}=\sum_{h=1}^{k}r_{h}$, i.e. its $\ell_{1}$ norm. We
write

$\displaystyle\mathbb{E}\Big{[}\Big{(}\frac{m}{i^{2}}\sum_{k=2}^{\infty}kL_{k}^{\prime}(n)\Big{)}^{j}\Big{]}=\frac{m^{j}}{i^{2j}}\sum_{\mathbf{r}:|\mathbf{r}|_{1}=j}\prod_{h\geq
2}\mathbb{E}[(hL_{h}^{\prime}(n))^{r_{h}}].$

For every $\varepsilon\geq 0$, it holds for all $n$ sufficiently large that

$\displaystyle\Big{(}\frac{m}{i^{2}}\Big{)}^{|\mathbf{r}|_{1}}\prod_{h\geq
2}\mathbb{E}[(L_{h}^{\prime}(n))^{r_{h}}]\leq\frac{1}{4^{|\mathbf{r}|_{1}}}\Big{(}1+\frac{2p_{2}+\varepsilon}{d-\varepsilon}\Big{)}^{2|\mathbf{r}|_{1}}\Big{(}\frac{2p_{2}+\varepsilon}{d-\varepsilon}\Big{)}^{\sum_{h\geq
2}(h-2)r_{h}}.$ (91)

If $\varepsilon$ is small enough, then
$\frac{2p_{2}+\varepsilon}{d-\varepsilon}<1$, and thus the sequence is
decreasing exponentially fast in $\sum_{h\geq 2}hr_{h}$. Applying dominated
convergence thus yields (40).

##  Appendix C Proofs of results on the cascading failure process

###### Proof of Lemma 4.6.

First, we observe that

$\displaystyle\mathbb{P}\left(T_{g^{-}}>k\right)\geq\mathbb{P}\left(T_{1-\theta}>k\right),$

and hence it suffices to show that the reversed inequality holds
asymptotically. Our proof will be similar to the proof of Lemma 4.4, but
adapted to provide an upper bound.

Fix $\epsilon>0$ small as in Lemma 4.4, and define the piecewise constant
boundary

$\displaystyle\hat{h}_{i,k}^{\epsilon}=\left\\{\begin{array}[]{ll}h^{(0)}=1-\theta&\textrm{if
}i\leq t_{0,k}^{\epsilon}=l,\\\ -h^{(j)}&\textrm{if
}t_{j-1,k}^{\epsilon}<i\leq t_{j,k}^{\epsilon},\;1\leq j\leq r-1,\\\
-h^{(r)}&\textrm{if }i>t_{r-1,k}^{\epsilon}.\end{array}\right.$

for $r$, times $t_{j,k}^{\epsilon}$ and levels $h^{(j)}$ defined as in the
proof of Lemma 4.4. We note that for every fixed $\delta>0$,

$\displaystyle\mathbb{P}\left(T_{g^{-}}>k\right)\leq\mathbb{P}\left(T_{\hat{h}^{\epsilon}}>k;S_{t_{j,k}^{\epsilon}}\in\left(\delta\sqrt{t_{j,k}^{\epsilon}},1/\delta\sqrt{t_{j,k}^{\epsilon}}\right),\;\;\;\forall\,0\leq
j\leq r-1\right)$ $\displaystyle\hskip
142.26378pt+\sum_{j=0}^{r}\mathbb{P}\left(T_{g^{-}}>k;S_{t_{j,k}^{\epsilon}}\not\in\left(\delta\sqrt{t_{j,k}^{\epsilon}},1/\delta\sqrt{t_{j,k}^{\epsilon}}\right)\right).$

Using analogous arguments as in Lemma 4.4, we obtain

$\displaystyle\mathbb{P}\left(T_{\hat{h}^{\epsilon}}>k;S_{t_{j,k}^{\epsilon}}\in\left(\delta\sqrt{t_{j,k}^{\epsilon}},1/\delta\sqrt{t_{j,k}^{\epsilon}}\right),\;\;\;\forall\,0\leq
j\leq r-1\right)$ $\displaystyle\hskip
227.62204pt\leq(1+o(1))\mathbb{P}\left(T_{1-\theta}>k\right).$

For the other terms, define the sequence $(\tilde{h}_{i})_{i\in\mathbb{N}}$
with $\tilde{h}_{i}=\min\\{1-\theta,-i^{\gamma}\\}$. Then, due to Theorem 1 of
[10],

$\displaystyle\sum_{j=0}^{r}$
$\displaystyle\mathbb{P}\left(T_{g^{-}}>k;S_{t_{j,k}^{\epsilon}}\not\in\left(\delta\sqrt{t_{j,k}^{\epsilon}},1/\delta\sqrt{t_{j,k}^{\epsilon}}\right)\right)$
$\displaystyle\hskip
56.9055pt\leq\sum_{j=0}^{r-1}\mathbb{P}\left(S_{t_{j,k}^{\epsilon}}\not\in\left(\delta\sqrt{t_{j,k}^{\epsilon}},1/\delta\sqrt{t_{j,k}^{\epsilon}}\right)\big{|}T_{\tilde{h}}>k\right)\mathbb{P}\left(T_{\tilde{h}}>k\right)$
$\displaystyle\hskip
56.9055pt\leq(1+o(1))r\left(1-e^{-\frac{\delta^{2}}{2}}+e^{-\frac{1}{2\delta^{2}}}\right)\mathbb{P}\left(T_{\tilde{h}}>k\right).$

Letting $\delta\downarrow 0$ yields [10]

$\displaystyle\sum_{j=0}^{r}$
$\displaystyle\mathbb{P}\left(T_{g^{-}}>k;S_{t_{j,k}^{\epsilon}}\not\in\left(\delta\sqrt{t_{j,k}^{\epsilon}},1/\delta\sqrt{t_{j,k}^{\epsilon}}\right)\right)=o\left(\mathbb{P}\left(T_{\tilde{h}}>k\right)\right)=o\left(k^{-1/2}\right).$

Since

$\displaystyle\mathbb{P}\left(T_{1-\theta}>k\right)\sim\frac{2\theta}{\sqrt{2\pi}}k^{-1/2},$

we conclude that

$\displaystyle\limsup_{k\rightarrow\infty}\frac{\mathbb{P}\left(T_{g^{-}}>k\right)}{\mathbb{P}\left(T_{1-\theta}>k\right)}\leq
1.$

###### Proof of Lemma 4.10.

This statement is a consequence of Theorem 2.3. Recall that by definition,

$\displaystyle\upsilon(k)+|\tilde{E}_{m}(\upsilon(k))|\geq k,$

and $\upsilon(k)\leq k$. Moreover,

$\displaystyle|\tilde{E}_{m}(\upsilon(k))|=m-\upsilon(k)-|\hat{E}_{m}(\upsilon(k))|\leq\max_{1\leq
j\leq k}\left\\{m-j-|\hat{E}_{m}(j)|\right\\}.$

It follows that

$\displaystyle\mathbb{P}\left(|\tilde{E}_{m}(\upsilon(k))|\geq
k^{\alpha}\right)$ $\displaystyle\leq\mathbb{P}\left(\max_{1\leq j\leq
k}\left\\{m-j-|\hat{E}_{m}(j)|\right\\}\geq k^{\alpha}\right)$
$\displaystyle\leq\mathbb{P}\left(\max_{1\leq j\leq
k}\left\\{m-j-|\hat{E}_{m}(j)|\right\\}\geq j^{\alpha}\right)=o(m^{-1/2})$

by Theorem 2.3. We conclude that

$\displaystyle\mathbb{P}\left(\upsilon(k)\leq
k-k^{\alpha}\right)\leq\mathbb{P}\left(|\tilde{E}_{m}(\upsilon(k))|\geq
k^{\alpha}\right)=o(m^{-1/2}).$

###### Proof of Lemma 4.11.

Again, this is a consequence of Theorem 2.3. We note that for every $1\leq
l\leq m$,

$\displaystyle\kappa(l)=\sum_{i=1}^{s}\textrm{Ber}(\pi_{i+1}),$

where

$\displaystyle\pi_{i}=\frac{|\hat{E}_{m}(i-2)|}{m-i+2}$

is a random variable. Due to Theorem 2.3,

$\displaystyle\mathbb{P}\left(\pi_{i}\leq 1-\frac{i^{\alpha}}{m-i+2}\textrm{
for some }2\leq i\leq k+1\right)=o(m^{-1/2}).$

Since for every $\alpha\in(0,1)$, the function $i^{\alpha-1}/(m-i+1)$ is an
increasing function in $i$, it follows that

$\displaystyle\mathbb{P}\left(\pi_{i}\leq 1-k^{\alpha-1}\textrm{ for some
}2\leq i\leq k+1\right)=o(m^{-1/2}).$

We derive the bound

$\displaystyle\mathbb{P}\left(\varrho(k)>k+k^{\alpha}\right)$
$\displaystyle=\mathbb{P}\left(\kappa\left(k+k^{(\alpha+1)/2}\right)\leq
k\right)\leq\mathbb{P}\left(\sum_{i=1}^{k+k^{(\alpha+1)/2}}\textrm{Ber}(\pi_{i+1})\leq
k\right)$
$\displaystyle\leq\mathbb{P}\left(\sum_{i=1}^{k+k^{(\alpha+1)/2}}\textrm{Ber}(k^{\alpha-1})>k^{(\alpha+1)/2}\right)$
$\displaystyle\leq\exp\left\\{-\frac{1}{2}k^{(1-\alpha)/2}(1+o(1))\right\\}=o(m^{-1/2}),$

where the last inequality is due to the Chernoff bound.