$(1-\varepsilon_{i})m_{i}$ with $m/2$, replace $n_{i-1},\rho_{i-1}$ with
$n_{i_{\ast}},\rho_{i_{\ast}}$, and replace $n_{i}$ by $\tilde{n}$. The latter
holds because $mn_{i_{\ast}}=\tilde{n}$ by (4.39). Then, for some constant
$c>0$, (4.34) turns into

$\displaystyle\mathds{1}_{\\{{\mathcal{A}}_{\mathrm{sub}}(n)\\}}\mathbb{P}\big{(}{\mathcal{H}}_{n}\text{
not conn.}\mid\text{pre-}\widehat{\mathcal{G}}_{\tilde{n}}\big{)}$
$\displaystyle\leq
A^{\prime}m\exp\big{(}-c\rho_{i_{\ast}}^{2}n_{i_{\ast}}^{\zeta+\alpha}\tilde{n}^{-\alpha}m\big{)}.$

By (4.39), $m\leq m_{i_{\ast}+1}$, so the bound (4.21) holds for
$\tilde{n}=mn_{i_{\ast}}$, which gives the first row below. Then,
$\tilde{n}\geq\nu n$ follows by multiplying both sides of (4.40). Moreover,
the prefactor $A^{\prime}m<A^{\prime}n$ can be absorbed by decreasing the
constant prefactor in the exponent. We obtain for some
$c^{\prime}>c^{\prime\prime}>0$

$\displaystyle\mathds{1}_{\\{{\mathcal{A}}_{\mathrm{sub}}(n)\\}}\mathbb{P}\big{(}{\mathcal{H}}_{n}\text{
not connected}\mid\text{pre-}\widehat{\mathcal{G}}_{\tilde{n}}\big{)}$
$\displaystyle\leq
A^{\prime}m\exp\big{(}-c^{\prime}\rho_{i_{\ast}}^{2}\tilde{n}^{\zeta-\delta}\big{)}$
$\displaystyle\leq\tfrac{1}{2}\exp\big{(}-c^{\prime\prime}\rho_{i_{\ast}}^{2}n^{\zeta-\delta}\big{)}.$

The definition of $\rho_{i}$ in (4.14) gives that $\rho_{i_{\ast}}>\rho>0$ for
all $i_{\ast}$, which gives our desired bound for the _(Con)_ -step. Combining
the error bound in (4.42) with this, we obtain that for any $A>0$ sufficiently
large that only depends on the fixed value of the constant $n_{0}$,

$\mathbb{P}\big{(}{\mathcal{A}}_{\mathrm{sub}}(n)\cap\\{{\mathcal{H}}_{n}\mbox{
connected}\\}\big{)}\geq 1-\exp\big{(}-\tfrac{1}{A}n^{\zeta-\delta}\big{)}.$

By (4.43) and the arguments below, connectivity of the auxiliary graph
${\mathcal{H}}_{n}$ means that the large components
${\mathcal{C}}_{i_{\ast},x_{j}}$ in the first $m/2$ $i_{\ast}$-good boxes form
a connected graph. In pre-$\widehat{\mathcal{G}}_{\tilde{n}}$ we only revealed
edges between vertices of mark at most $2n_{i_{\ast}}^{\gamma}<2n^{\gamma}$ by
(4.43). By (4.39) and the assumption that $i_{\ast}>i_{0}$ below (4.39), we
also have $2n_{i_{\ast}}^{\gamma}>n_{0}^{2/(\tau-1)}$. Moreover, on
${\mathcal{A}}_{\mathrm{sub}}(n)\cap\\{{\mathcal{H}}_{n}\mbox{ connected}\\}$,
the $\lceil m/2\rceil$ components of size at least
$\rho_{i_{\ast}}n_{i_{\ast}}$ form a connected graph, and thus
${\mathcal{G}}_{n}[1,2n_{i_{\ast}}^{\gamma})$ contains a component of size at
least

$(m/2)\cdot\rho_{i_{\ast}}n_{i_{\ast}}=\rho_{i_{\ast}}\tilde{n}/2\geq(\nu/2)\rho_{i_{\ast}}n\geq(\nu/2)\rho
n.$

This implies that the largest component must be at least this large as well.
So,

${\mathcal{A}}_{\mathrm{sub}}(n)\cap\\{{\mathcal{H}}_{n}\mbox{
connected}\\}\,\subseteq\,\big{\\{}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}[1,An^{\gamma})|\geq\tfrac{1}{A}n\big{\\}}$
(4.44)

when $A$ is sufficiently large. This finishes the proof of (4.1). We do not
need the _(Mark)_ step here since there is no further iteration. For the Palm
version $\mathbb{P}^{\scriptscriptstyle x}$ the proof is exactly the same. ∎

###### Proof of Proposition 4.1 when $\zeta_{\mathrm{ll}}>0$.

When the vertex is formed by a PPP, we obtain the second statement (4.2) by a
straightforward adaptation of the above proofs. We provide a sketch. When
$\zeta_{\mathrm{ll}}=2-\alpha>0$, we re-define what we call an $i$-good box by
leaving the requirement on the marks in (4.15) out. We now call
${\mathcal{Q}}_{i}(x)$ $i$-good (and $i$-bad otherwise) if it satisfies the
event

${\mathcal{A}}_{\mathrm{i\textnormal{-}good}}(x):=\Big{\\{}\exists\text{
component ${\mathcal{C}}_{i}$ in
}\widehat{\mathcal{G}}_{n_{i}}:|{\mathcal{C}}_{i}|\geq\rho_{i}n_{i}\Big{\\}}.$
(4.45)

Then, we replace $\zeta_{\mathrm{hl}}$ by $\zeta_{\mathrm{ll}}=2-\alpha$ in
all computations and definitions, and we skip the _(Mark)_ -step on each
level. We do this by setting the level-$i$ vertex set to be
$\widehat{\mathcal{V}}_{i}:={\mathcal{V}}_{{\mathcal{Q}}_{i}(x)}[1,n_{0}^{2/(\tau-1)})$.
That is, only the size of the box changes across levels, the mark-truncation
stays put. The _(Sub)_ -step leading to (4.30) carries through unchanged by
the inductive assumption and the concentration of binomial random variables on
the number of level-$(i-1)$ good subboxes. For the _(Con)_ -step, instead of
using high-mark vertices, we estimate the mark of each vertex from below by
$1$ in the large components ${\mathcal{C}}_{i-1,x_{j}}$ and
${\mathcal{C}}_{i-1,x_{k}}$. Using this lower bound, the number of edges
between the two components dominates a binomial random variable. Both
components have size at least $\rho_{i-1}n_{i-1}$ because they are contained
in $(i-1)$-good boxes, and their distance is at most $\sqrt{d}n_{i}^{1/d}$, so
(4.33) simplifies to

$\displaystyle\mathbb{P}\big{(}{\mathcal{C}}_{i-1,x_{j}}\nsim_{\widehat{\mathcal{G}}_{n_{i}}}{\mathcal{C}}_{i-1,x_{k}}\mid\text{pre-}\widehat{\mathcal{G}}_{n_{i}})$
$\displaystyle\leq\Big{(}1-p\big{(}1\wedge\tfrac{\beta}{\sqrt{d}^{d}n_{i}}\big{)}^{\alpha}\Big{)}^{\rho_{i-1}^{2}n_{i-1}^{2}}$
$\displaystyle\leq\exp\big{(}-(p\beta d^{-\alpha
d/2})\cdot\rho_{i-1}^{2}n_{i-1}^{2}n_{i}^{-\alpha}\big{)}=:1-q_{i}.$

Observe that the exponent $n_{i-1}^{2}=n_{i-1}^{\zeta+\alpha}$ since here
$\zeta=2-\alpha$. From here on the computations are identical to those between
(4.34) and (4.35), and since the last term in (4.11) is not present, we
conclude the proof at (4.11) for $\zeta_{\mathrm{ll}}>0$. Along the lines we
also use that all statements of 4.9 remain valid also for
$\zeta=\zeta_{\mathrm{ll}}$, except (4.22). But, (4.22) is only used in the
_(Mark)_ -step which we omit when we consider the case
$\zeta_{\mathrm{ll}}>0$. ∎

##  5\. Sharp bounds on the existence of a giant

The goal of this section is to improve upon the probability of the existence
of the giant component compared to Proposition 4.1, which is formalized in the
next proposition. In Proposition 4.1, the exponent of $n$ in the stretched
exponential decay is $\max(\zeta_{\mathrm{hl}},\zeta_{\mathrm{ll}})-\delta$.
Here we remove the error $\delta$ and ‘append’ $(d-1)/d,\zeta_{\mathrm{hh}}$
to the list in the maximum.

For a regime $\mathrm{type}\in\\{\mathrm{ll},\mathrm{hl},\mathrm{hh}\\}$, and
constants $\rho,\delta\in(0,1)$, we define the event

${\mathcal{A}}_{\mathrm{giant}}^{\mathrm{type}}(\rho):=\begin{dcases}\big{\\{}\exists\mbox{
comp. ${\mathcal{C}}$ in ${\mathcal{G}}_{n}$}:|{\mathcal{C}}|\geq\rho
n,{\mathcal{C}}\supseteq{\mathcal{V}}[n^{(1-\delta)/(\tau-1)},\infty)\big{\\}},&\text{if
}\mathrm{type}\in\\{\mathrm{hl},\mathrm{hh}\\},\\\ \big{\\{}\exists\mbox{
comp. ${\mathcal{C}}$ in ${\mathcal{G}}_{n}$}:|{\mathcal{C}}|\geq\rho
n\big{\\}},&\text{if }\mathrm{type}=\mathrm{ll}.\end{dcases}$ (5.1)

Recall the values $\gamma_{\mathrm{hl}}$ and $\gamma_{\mathrm{hh}}$ from
(2.11) and (2.13), respectively. Define

$\gamma_{\mathrm{ll}}:=(\alpha-1)/(\tau-1),$ (5.2)

which we will only use when $\zeta_{\mathrm{ll}}=2-\alpha>0$. In particular,
we will not use it when $\alpha=\infty$.

######  Proposition 5.1 (Sharp bounds for the giant).

Consider a supercritical KSRG satisfying Assumption 2.2 on a PPP or consider
supercritical long-range percolation on ${\mathbb{Z}}^{d}$. Assume that there
is a $\mathrm{type}\in\\{\mathrm{ll},\mathrm{hl},\mathrm{hh}\\}$ so that
$\zeta_{\mathrm{type}}>0$ and that for a constant $\rho>0$,

$\mathbb{P}\big{(}{\mathcal{A}}_{\mathrm{giant}}^{\mathrm{type}}(\rho)\big{)}\longrightarrow
1,\qquad\text{as }n\to\infty.$ (5.3)

  1. (long)

Then for all $\varepsilon>0$, there exists $A>0$ such that for all $n\geq 1$

$\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}[1,An^{\gamma_{\mathrm{type}}})|<(1-\varepsilon)\rho
n\big{)}\leq\exp\big{(}-\tfrac{1}{A}n^{\zeta_{\mathrm{type}}}\big{)}.$ (5.4)

  2. (short)

Also, for all $\varepsilon>0$, there exists $A>0$ such that for all $n\geq 1$

$\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}[1,A)|<(1-\varepsilon)\rho
n\big{)}\leq\exp\big{(}-\tfrac{1}{A}n^{\zeta_{\mathrm{short}}}\big{)}.$ (5.5)

Proposition 5.1 gives sharp decay for the value of $\zeta_{\mathrm{type}}$
that maximizes
$\\{\zeta_{\mathrm{ll}},\zeta_{\mathrm{hl}},\zeta_{\mathrm{hh}},\zeta_{\mathrm{short}}\\}$,
which is equal to $\zeta_{\star}$ by 2.3. When
$\zeta_{\mathrm{long}}=\max\\{\zeta_{\mathrm{ll}},\zeta_{\mathrm{hl}},\zeta_{\mathrm{hh}}\\}>0$
and $(d-1)/d>0$, the second statement shows that the giant still exists with
stretched exponential error probability even when all vertices with mark above
a constant are deleted from the graph. When $\zeta_{\star}=(d-1)/d$, this
decay is even stronger than (5.4).

The requirement (5.3) corresponds to (Req) in Section 3. It demands _some_
initial density bound $\rho$ on the size of the giant, and for the (hh) and
(hl)-regimes it also demands that the highest-mark vertices are in the giant.
Via edges incident to these high-mark vertices we can connect large components
in subboxes in renormalisation schemes below. We guarantee the presence of
these long edges via the reasoning in Section 2.2. The requirement on high-
mark vertices is not needed in the (ll) regime in (5.1), since we bound all
marks from below by one. Thus, in the (ll)-regime, (5.3) is already satisfied
for a small $\rho$ by Proposition 4.1. At the end of this section we verify
(5.3) also for the (hl) and (hh)-regimes for a small $\rho$ using Proposition
4.1, obtaining Corollary 5.7.

We will apply Proposition 5.1 again in Section 6.3 with density $\rho$ close
to $\theta$, as by then we have proved the weak LLN for
$|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|$ for all parameters satisfying
$\zeta_{\mathrm{long}}>0$. This will result in the upper bound on the right-
hand side of (2.21) in Theorem 2.7. The exponent $\zeta_{\star}$ of the
stretched exponential decay in Proposition 5.1 will also appear in our upper
bounds on $|{\mathcal{C}}_{n}^{\scriptscriptstyle(2)}|$ and the cluster-size
decay for
$\zeta_{\mathrm{type}}\in\\{\zeta_{\mathrm{hl}},\zeta_{\mathrm{ll}}\\}$ in
Theorems 2.9 and 2.10. Instead of Proposition 5.1, Proposition 4.1 could
instead be used as input to obtain (weaker) upper bounds on
$|{\mathcal{C}}_{n}^{\scriptscriptstyle(2)}|$ and the cluster-size decay for
$\zeta_{\mathrm{type}}\in\\{\zeta_{\mathrm{hl}},\zeta_{\mathrm{ll}}\\}$. That
strategy would still give a weak LLN and also Theorem 2.7, but would lead to
the appearance of an error $\delta$ in exponents in Theorems 2.9 and 2.10,
which would then never match the lower bounds in Theorems 2.9 and 2.10. This
explains the benefit of Proposition 5.1.

######  Remark 5.2 (High-level comparison of proofs in Sections 4 and 5).

Section 5 sets up a single-layer renormalisation with carefully chosen number
and size of boxes that lead exactly to (5.4) and (5.5), respectively. It needs
Section 4 as an input, because in each of these boxes a linear-sized component
has to be present whp on truncated mark vertices.

It is natural to ask why one could not use ‘more carefully chosen’ box sizes
already in Section 4 and obtain better bounds already there? The rough answer
is the following: here in Section 5 we shall shortly perform a single-layer
renormalisation. Since it is a single layer, we _can_ afford to lose a small
linear portion of the giant. Thus, we can renormalise to a _supercritical_
Erdős-Rényi random graph (ERRG), and use large deviation results for those.
Then, we have $\Theta(n^{\zeta})$ many boxes, and the probability that a
supercritical ERRG has a too small giant decays exponentially in the the
number of boxes.

On the contrary, Section 4 uses an iterative scheme in order to improve the
initial sublinear bound on the largest component to a linear bound. That is
not possible in a single-layer renormalisation. In an iterative scheme, one
_cannot_ allow to lose a small constant fraction of the largest component in
each step. That would (again) result in a sublinear bound on the largest
component. Therefore, in Section 4 we renormalised to a _connected_ ERRG. For
that we need slightly larger boxes, and thus we have $o(n^{\zeta})$ boxes when
reaching total size $n$. Moreover, the probability of the rare event that such
an ERRG is not connected, decays exponentially in the expected degree, which
is smaller than the total number of boxes. These reasons explain the $-\delta$
term in the exponent in Section 4.

We proceed to the proofs. We start with a claim that allows us to truncate the
vertex marks from above; then we separately present the proof of the two
statements in Proposition 5.1.

######  Claim 5.3.

Consider a supercritical KSRG under the setting of Proposition 5.1. Assume
that $\zeta_{\mathrm{type}}>0$ and (5.3) holds for some $\rho>0$,
$\mathrm{type}\in\\{\mathrm{hl},\mathrm{hh}\\}$, and $\delta\in(0,1)$. Then,
as $n$ tends to infinity,

$\mathbb{P}\Big{(}\exists\mbox{comp. ${\mathcal{C}}$ in
${\mathcal{G}}_{n}\Big{[}1,n^{\tfrac{1}{\tau-1}}\Big{)}$}:{\mathcal{C}}\supseteq{\mathcal{V}}\Big{[}n^{\tfrac{1-\delta}{\tau-1}},n^{\tfrac{1}{\tau-1}}\Big{)},|{\mathcal{C}}|>\rho
n\Big{)}\longrightarrow 1.$ (5.6)

###### Proof.

We abbreviate $\underline{w}=n^{(1-\delta)/(\tau-1)}$,
$\overline{w}=n^{1/(\tau-1)}$ throughout the proof. We start from (5.3) and
distinguish whether ${\mathcal{G}}_{n}$ contains vertices of mark at least
$\overline{w}$: if there are no vertices of mark at least $\overline{w}$, then
${\mathcal{G}}_{n}[1,\overline{w})={\mathcal{G}}_{n}$. Slightly abusing
standard notation, we write here
${\mathcal{C}}\subset{\mathcal{V}}_{n}[1,\underline{w})\cup{\mathcal{V}}_{n}[\underline{w},\infty)$
for a set of vertices that is a _component_ when restricted to marks below
$\underline{w}$. Then we get

$\displaystyle\mathbb{P}$ $\displaystyle\big{(}\exists\mbox{ comp.
${\mathcal{C}}$ in
${\mathcal{G}}_{n}$}:{\mathcal{C}}\supseteq{\mathcal{V}}[\underline{w},\infty),|{\mathcal{C}}|>\rho
n\big{)}$ $\displaystyle=\mathbb{P}\big{(}\\{\exists\mbox{ comp.
${\mathcal{C}}$ in
${\mathcal{G}}_{n}[1,\overline{w})$}:{\mathcal{C}}\supseteq{\mathcal{V}}[\underline{w},\overline{w}),|{\mathcal{C}}|>\rho
n\\}\cap\\{{\mathcal{V}}[\overline{w},\infty)=\emptyset\\}\big{)}$
$\displaystyle\hskip 15.0pt+\mathbb{P}\big{(}\\{\exists\mbox{ comp.
${\mathcal{C}}$ in
${\mathcal{G}}_{n}$}:{\mathcal{C}}\supseteq{\mathcal{V}}[\underline{w},\overline{w}),|{\mathcal{C}}|>\rho
n\\}\cap\\{{\mathcal{V}}[\overline{w},\infty)\neq\emptyset\\}\big{)}.$

Since the vertices are formed by a PPP, ${\mathcal{V}}[\overline{w},\infty)$
is independent of ${\mathcal{V}}[1,\overline{w})$ and thus also of the graph
${\mathcal{G}}_{n}[1,\overline{w})$. So, in the first term on the right-hand
side we can take the product of the probabilities of the two events. Using the
intensity of ${\mathcal{V}}$ in (4.5),
$\mathbb{P}({\mathcal{V}}[\overline{w},\infty)=\emptyset)=1/{\mathrm{e}}$.
Hence, conditioning on $\\{{\mathcal{V}}[\overline{w},\infty)\neq\emptyset\\}$
in the second term on the right-hand side yields

$\displaystyle\mathbb{P}$ $\displaystyle\big{(}\exists\mbox{ comp.
${\mathcal{C}}$ in
${\mathcal{G}}_{n}$}:{\mathcal{C}}\supseteq{\mathcal{V}}[\underline{w},\overline{w}),|{\mathcal{C}}|>\rho
n\big{)}$ $\displaystyle=\frac{1}{{\mathrm{e}}}\mathbb{P}\big{(}\exists\mbox{
comp. ${\mathcal{C}}$ in
${\mathcal{G}}_{n}[1,\overline{w})$}:{\mathcal{C}}\supseteq{\mathcal{V}}[\underline{w},\overline{w}),|{\mathcal{C}}|>\rho
n\big{)}$ $\displaystyle\hskip
15.0pt+\Big{(}1-\frac{1}{{\mathrm{e}}}\Big{)}\mathbb{P}\big{(}\exists\mbox{
comp. ${\mathcal{C}}$ in
${\mathcal{G}}_{n}$}:{\mathcal{C}}\supseteq{\mathcal{V}}[\underline{w},\overline{w}),|{\mathcal{C}}|>\rho
n\mid{\mathcal{V}}[\overline{w},\infty)\neq\emptyset\big{)}.$

Since the left-hand side converges to $1$ as $n$ tends to infinity by the
assumed condition (5.3), the two probabilities on the right-hand side must
converge to $1$ as well. Since the event in the first row on the right-hand
side coincides with (5.6), the claim follows. ∎

###  5.1. When relying on long edges

Before the proof of Proposition 5.1(long), we state a result about the giant
in Erdős-Rényi random graph $G(n,p)$. The result will ‘replace’ 4.7 in the
renormalisation scheme of this section compared to the scheme in Section 4.
The claim follows from a large-deviation principle for the size of the giant
component obtained by O’Connell [68], see also [9]. For our result, we do not
need the exact rate function of this LDP.

######  Claim 5.4 (Large deviations in $G(n,\lambda/n)$).

Consider the largest connected component
$C_{n}^{\scriptscriptstyle(1)}(p_{n})$ of the Erdős-Rényi random graph
$G(n,p_{n})$. Fix $\varepsilon>0$. There exist constants $A>0$,
$\lambda=\lambda(\varepsilon)>1$ such that for all $n\geq 1$

$\mathbb{P}\big{(}|C_{n}^{\scriptscriptstyle(1)}(\lambda/n)|<(1-\varepsilon)n\big{)}\leq\exp\big{(}-\tfrac{1}{A}n\big{)}.$

###### Proof.

Denote by $\varrho_{\lambda}$ the survival probability of a Bienaymé-Galton-
Watson branching process with $\mathrm{Poi}(\lambda)$ offspring. By [68,
Theorem 3.1], for every $\lambda>1$ and $\tilde{\varepsilon}>0$, there exists
a constant $A>0$ such that

$\mathbb{P}\big{(}|C_{n}^{\scriptscriptstyle(1)}(\lambda/n)|<(1-\tilde{\varepsilon})\varrho_{\lambda}n\big{)}\leq\exp\big{(}-\tfrac{1}{A}n\big{)}.$

It is well known that the survival probability $\varrho_{\lambda}$ tends to
one as $\lambda\to\infty$, as $\varrho_{\lambda}$ is the largest solution in
$(0,1)$ to the equation $\varrho_{\lambda}=1-\exp(-\lambda\varrho_{\lambda})$
(see e.g. [70, Example 6.1.10]). Hence, given $\varepsilon>0$, we may choose
$\lambda$ large enough, and $\tilde{\varepsilon}>0$ small enough, so that
$(1-\tilde{\varepsilon})\varrho_{\lambda}\geq(1-\varepsilon)$. The statement
follows. ∎

###### Proof of Proposition 5.1(long).

We give the proof for KSRGs on a Poisson point process. The result for long-
range percolation on ${\mathbb{Z}}^{d}$ follows analogously to the case
$\zeta_{\mathrm{ll}}>0$.

Fix
$\zeta_{\mathrm{type}}\in\\{\zeta_{\mathrm{hl}},\zeta_{\mathrm{hh}},\zeta_{\mathrm{ll}}\\}$
such that $\zeta_{\mathrm{type}}>0$. Let
$\gamma_{\mathrm{type}}\in\\{\gamma_{\mathrm{hl}},\gamma_{\mathrm{hh}},\gamma_{\mathrm{ll}}\\}$
be the corresponding value that solves
$\zeta_{\mathrm{type}}=1-\gamma_{\mathrm{type}}(\tau-1)$ by the definitions of
$\gamma_{\mathrm{hl}}$, $\gamma_{\mathrm{hh}}$, and $\gamma_{\mathrm{ll}}$ in
(2.11), (2.13), and (5.2), respectively. For readability, we omit the
subscript $\mathrm{type}$ throughout the proof.

_Definitions of constants and boxing scheme._ Below we will suitably define a
constant $M>0$ depending on the regime (i.e., high-low, high-high, or low-
low). For simplicity, we assume that $(n^{\zeta}/M)^{1/d}\in{\mathbb{N}}$, so
that we can partition $\Lambda_{n}$ into

$m_{n}:=n^{\zeta}/M$ (5.7)

boxes ${\mathcal{Q}}_{1},\ldots,{\mathcal{Q}}_{m_{n}}$. Using that
$(1-{\zeta})/(\tau-1)=\gamma$, each box has volume

$k_{n}:=n/m_{n}=Mn^{1-\zeta}=\big{(}M^{1/(\tau-1)}n^{\gamma}\big{)}^{\tau-1}.$
(5.8)

Given any $\varepsilon>0$ in Proposition 5.1(long), define the small
$\varepsilon_{1},\varepsilon_{2}>0$ as the solutions of the following
equations:

$1-\varepsilon=(1-\varepsilon_{1})^{2},\qquad\mathbb{P}\big{(}{\mathcal{V}}[\varepsilon_{2}k_{n}^{1/(\tau-1)},\infty)=\emptyset\big{)}=\varepsilon_{1}/4.$
(5.9)

In a box of volume $k_{n}$, the expected number of vertices of mark at least
$\varepsilon_{2}k_{n}^{1/(\tau-1)}$ equals $\varepsilon_{2}^{-(\tau-1)}$ by
(2.4), so $\varepsilon_{2}$ is a constant.

_Good boxes and auxiliary graph._ We write
${\mathcal{V}}_{k_{n},j}:={\mathcal{V}}\cap({\mathcal{Q}}_{j}\times[1,\infty))$
for the vertices in ${\mathcal{Q}}_{j}$, ${\mathcal{G}}_{k_{n},j}$ for the
subgraph of ${\mathcal{G}}_{n}$ induced by the vertices in
${\mathcal{Q}}_{j}$, and similar to (4.31), we set

$\text{pre-}{\mathcal{G}}_{n}:=\cup_{j\leq m_{n}}{\mathcal{G}}_{k_{n},j}.$
(5.10)

We call a box ${\mathcal{Q}}_{j},j\in[m_{n}]$ _good_ if the following event
holds depending on the regime
$\mathrm{type}\in\\{\mathrm{hl},\mathrm{hh},\mathrm{ll}\\}$. When
$\mathrm{type}\in\\{\mathrm{hl},\mathrm{hh}\\}$,

${\mathcal{A}}_{\mathrm{box}}(j)\\!:=\\!\left\\{\,\begin{aligned}
\exists\mbox{comp. ${\mathcal{C}}_{j}$ in
${\mathcal{G}}_{k_{n},j}\big{[}1,k_{n}^{1/(\tau-1)}\big{)}$}:|{\mathcal{C}}_{j}|&\geq\rho
k_{n},\\\
{\mathcal{C}}_{j}&\supseteq{\mathcal{V}}_{k_{n},j}[\varepsilon_{2}k_{n}^{1/(\tau-1)},k_{n}^{1/(\tau-1)})\neq\emptyset\end{aligned}\right\\}.$
(5.11)

When $\mathrm{type}=\mathrm{ll}$,

${\mathcal{A}}_{\mathrm{box}}(j):=\\!\left\\{\,\exists\mbox{comp.
${\mathcal{C}}_{j}$ in
${\mathcal{G}}_{k_{n},j}\big{[}1,k_{n}^{1/(\tau-1)}\big{)}$}:|{\mathcal{C}}_{j}|\geq\rho
k_{n}\right\\}.$

We define the event that there are enough good boxes in $\Lambda_{n}$ (similar
to ${\mathcal{A}}_{\mathrm{sub}}$ in (4.29)):

${\mathcal{A}}_{\mathrm{sub}}:=\bigg{\\{}\sum_{j\in[m_{n}]}\mathds{1}_{\\{{\mathcal{A}}_{\mathrm{box}}(j)\\}}\geq(1-\varepsilon_{1})m_{n}\bigg{\\}},$
(5.12)

The event ${\mathcal{A}}_{\mathrm{sub}}$ is measurable with respect to
pre-${\mathcal{G}}_{n}$ in (5.10).

_Enough subboxes are good._ We estimate
$\mathbb{P}\big{(}\neg{\mathcal{A}}_{\mathrm{sub}}\big{)}$, with
${\mathcal{A}}_{\mathrm{sub}}$ defined in (5.12). For that we analyse the
individual probabilities
$\mathbb{P}\big{(}{\mathcal{A}}_{\mathrm{box}}(j)\big{)}$. By the definition
of $\varepsilon_{1}$ in (5.9) and the hypothesis (5.3), for all $n$
sufficiently large and any $j\in[m_{n}]$

$\mathbb{P}\big{(}{\mathcal{A}}_{\mathrm{box}}(j)\big{)}\geq
1-\varepsilon_{1}/2.$ (5.13)

Since the graphs ${\mathcal{G}}_{k_{n},j}$ are iid across $j\in[m_{n}]$, by a
standard Chernoff bound on binomial random variables, there exists a constant
$c>0$ such that

$\mathbb{P}\big{(}\neg{\mathcal{A}}_{\mathrm{sub}}\big{)}\leq\exp\big{(}-cm_{n}\big{)}.$
(5.14)

_Introducing the auxiliary graph._ Similar to below (4.31) and (4.43), on any
realization of pre-${\mathcal{G}}_{n}$ satisfying
${\mathcal{A}}_{\mathrm{sub}}$, we re-label boxes so that the first
$\lceil(1-\varepsilon_{1})m_{n}\rceil$ many boxes are good. Then we define the
auxiliary graph
${\mathcal{H}}_{n}=({\mathcal{V}}_{{\mathcal{H}}_{n}},{\mathcal{E}}_{{\mathcal{H}}_{n}})$
on $\lceil(1-\varepsilon_{1})m_{n}\rceil$ many vertices, so that vertex
$j\in{\mathcal{V}}_{{\mathcal{H}}_{n}}$ corresponds to the component
${\mathcal{C}}_{j}$ inside ${\mathcal{Q}}_{j}$ in (5.11), and two vertices
$j,\ell$ are connected in ${\mathcal{H}}_{n}$ if the components
${\mathcal{C}}_{j}$ and ${\mathcal{C}}_{\ell}$ are connected by an edge in
${\mathcal{G}}_{n}$. We write
${\mathcal{C}}_{{\mathcal{H}}_{n}}^{\scriptscriptstyle(1)}$ for the largest
component in ${\mathcal{H}}_{n}$. By construction, the induced connected
components
$({\mathcal{C}}_{j})_{j\in{\mathcal{C}}_{{\mathcal{H}}_{n}}^{\scriptscriptstyle(1)}}$
in (5.11) are all contained in the same component in ${\mathcal{G}}_{n}$. So
if the event
${\mathcal{A}}_{\mathrm{sub}}\cap\\{|{\mathcal{C}}_{{\mathcal{H}}_{n}}^{\scriptscriptstyle(1)}|\geq(1-\varepsilon_{1})|{\mathcal{V}}_{{\mathcal{H}}_{n}}|\\}$
holds, then the graph ${\mathcal{G}}_{n}\big{[}1,k_{n}^{1/(\tau-1)}\big{)}$
contains a connected component ${\mathcal{C}}$ with

$|{\mathcal{C}}|\geq\sum_{j\in{\mathcal{C}}_{{\mathcal{H}}_{n}}^{\scriptscriptstyle(1)}}|{\mathcal{C}}_{j}|\geq(1-\varepsilon_{1})^{2}m_{n}\cdot\rho
k_{n}=(1-\varepsilon_{1})^{2}\rho n=(1-\varepsilon)\rho n.$

Here we used that $|{\mathcal{C}}_{j}|\geq\rho k_{n}$ by the event
${\mathcal{A}}_{\mathrm{box}}(j)$, that $k_{n}=n/m_{n}$ by (5.8), and
$(1-\varepsilon_{1})^{2}=1-\varepsilon$ by (5.9). Clearly, the largest
component of ${\mathcal{G}}_{n}[1,k_{n}^{1/(\tau-1)})$ is at least as large as
${\mathcal{C}}$, so

$\displaystyle\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}[1,k_{n}^{1/(\tau-1)})|\leq(1-\varepsilon)\rho
n\big{)}$
$\displaystyle\leq\mathbb{P}\big{(}\neg{\mathcal{A}}_{\mathrm{sub}}\big{)}+\mathbb{P}\big{(}{\mathcal{A}}_{\mathrm{sub}}\cap\\{|{\mathcal{C}}_{{\mathcal{H}}_{n}}^{\scriptscriptstyle(1)}|\leq(1-\varepsilon)|{\mathcal{V}}_{{\mathcal{H}}_{n}}|\\}\big{)}.$
(5.15)

We study the two probabilities on the right-hand side separately.

_Large deviation for the giant of ERRGs._ We turn to the second term on the
right-hand side in (5.15). We rewrite this second term using the law of total
probability: we first reveal pre-${\mathcal{G}}_{n}$, then integrate over
realizations satisfying ${\mathcal{A}}_{\mathrm{sub}}$:

$\mathbb{P}\big{(}{\mathcal{A}}_{\mathrm{sub}}\cap\\{|{\mathcal{C}}_{{\mathcal{H}}_{n}}^{\scriptscriptstyle(1)}|\leq(1-\varepsilon)^{2}m_{n}\big{)}=\mathbb{E}\big{[}\mathds{1}_{\\{{\mathcal{A}}_{\mathrm{sub}}\\}}\mathbb{P}\big{(}|{\mathcal{C}}_{{\mathcal{H}}_{n}}^{\scriptscriptstyle(1)}|\leq(1-\varepsilon_{1})|{\mathcal{V}}_{{\mathcal{H}}_{n}}|\mid\text{pre-}{\mathcal{G}}_{n}\big{)}\big{]}.$
(5.16)

Let $\lambda=\lambda(\varepsilon_{1}),A>0$ be the two constants from 5.4 so
that for all $m\geq 1$,

$\mathbb{P}\big{(}|C_{m}^{\scriptscriptstyle(1)}(\lambda/m)|<(1-\varepsilon_{1})m\big{)}\leq
A\exp\big{(}-\tfrac{1}{A}m\big{)}.$ (5.17)

We will show below that conditionally on the realization
pre-$\widehat{\mathcal{G}}_{n}$ satisfying ${\mathcal{A}}_{\mathrm{sub}}$,

${\mathcal{H}}_{n}\succcurlyeq
G(|{\mathcal{V}}_{{\mathcal{H}}_{n}}|,\lambda(\varepsilon_{1})/|{\mathcal{V}}_{{\mathcal{H}}_{n}}|).$
(5.18)

Suppose we have proven this stochastic domination. Then we can apply (5.17),
and use that
$|{\mathcal{V}}_{{\mathcal{H}}_{n}}|=\lceil(1-\varepsilon_{1})m_{n}\rceil=:\widetilde{m}_{n}$:

$\displaystyle\mathds{1}_{\\{{\mathcal{A}}_{\mathrm{sub}}\\}}\mathbb{P}\big{(}|{\mathcal{C}}_{{\mathcal{H}}_{n}}^{\scriptscriptstyle(1)}|<(1-\varepsilon_{1})|{\mathcal{V}}_{{\mathcal{H}}_{n}}|\mid\widehat{\mathcal{G}}_{n}\big{)}$
$\displaystyle\leq\mathbb{P}\big{(}|C_{\widetilde{m}_{n}}^{\scriptscriptstyle(1)}(\lambda/\widetilde{m}_{n})|<(1-\varepsilon_{1})\widetilde{m}_{n}\big{)}$
$\displaystyle\leq\exp\big{(}-\tfrac{1}{A}|{\mathcal{V}}_{{\mathcal{H}}_{n}}|\big{)}\leq\exp(-\tfrac{1}{A(1-\varepsilon_{1})}m_{n})$

This bound holds uniformly for all realizations of pre-${\mathcal{G}}_{n}$
with ${\mathcal{A}}_{\mathrm{sub}}$ in (5.16). So, combined with (5.14), this
bounds the two terms on the right-hand side in (5.15). Recalling that
$m_{n}=n^{\zeta}/M$,

$\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}[1,k_{n}^{1/(\tau-1)})|<(1-\varepsilon)\rho
n\big{)}\leq\exp\big{(}-\tfrac{c}{M}n^{\zeta}\big{)}+\exp\big{(}-\tfrac{1}{AM(1-\varepsilon_{1})}n^{\zeta}\big{)}.$

The mark bound $k_{n}^{1/(\tau-1)}$ in the largest component on the left-hand
side is equal to $M^{1/(\tau-1)}n^{\gamma}$ by (5.8). Thus, to finish the
proof of (5.4), it remains to prove the stochastic domination in (5.18).

_Showing that the auxiliary graph dominates ERRG._ We now prove (5.18) case-
by-case for the three regimes, for $\zeta$ being either $\zeta_{\mathrm{ll}}$,
$\zeta_{\mathrm{hl}}$, or $\zeta_{\mathrm{hh}}$. We reveal the subgraph
pre-${\mathcal{G}}_{n}$ in (5.10), i.e., all induced subgraphs inside boxes
$({\mathcal{Q}}_{j})_{j\in[m_{n}]}$, and assume that the realization satisfies
${\mathcal{A}}_{\mathrm{sub}}$. The first
$\lceil(1-\varepsilon_{1})m_{n}\rceil$ boxes are good and these labels form
the vertex set ${\mathcal{V}}_{{\mathcal{H}}_{n}}$. Each label corresponds to
a component ${\mathcal{C}}_{j}$ in ${\mathcal{Q}}_{j}$. Edges between these
components $({\mathcal{C}}_{j})_{j\in{\mathcal{V}}_{{\mathcal{H}}_{n}}}$ have
not been revealed yet, and conditional on pre-${\mathcal{G}}_{n}$, they are
present independently of each other. Therefore, it is sufficient to show that
for all $j,\ell\in{\mathcal{V}}_{{\mathcal{H}}_{n}}$,

$\mathbb{P}\big{(}{\mathcal{C}}_{j}\sim_{{\mathcal{G}}_{n}}{\mathcal{C}}_{\ell}\mid\text{pre-}{\mathcal{G}}_{n}\big{)}\geq\frac{\lambda}{|{\mathcal{V}}_{{\mathcal{H}}_{n}}|}.$
(5.19)

We will prove this by suitably choosing the constant $M$ in (5.7), case-by-
case for the possible values of
$\zeta=\zeta_{\mathrm{type}}\in\\{\zeta_{\mathrm{hl}},\zeta_{\mathrm{hh}},\zeta_{\mathrm{ll}}\\}$.

_1\. High-low edges, $\zeta_{\mathrm{type}}=\zeta_{\mathrm{hl}}>0$._ We assume
that $\alpha<\infty$, since $\zeta_{\mathrm{hl}}=(\tau-1)/\alpha-(\tau-2)<0$
otherwise. If a box ${\mathcal{Q}}_{j}$ is good, see (5.11), the large
component ${\mathcal{C}}_{j}$ with size at least $\rho k_{n}$ contains at
least one vertex $v_{j}^{\star}$ of mark at least
$\varepsilon_{2}k_{n}^{1/(\tau-1)}$. If there are more such vertices, choose
one arbitrarily. We estimate the probability that ${\mathcal{C}}_{j}$ and
${\mathcal{C}}_{\ell}$ are connected from below by the probability that either
$v_{j}^{\star}$ connects to any vertex in ${\mathcal{C}}_{\ell}$ or
$v_{\ell}^{\star}$ connects to any vertex in ${\mathcal{C}}_{j}$. We bound
marks in the other component from below by $1$. Any two vertices in
$\Lambda_{n}$ are within distance $\sqrt{d}n^{1/d}$. Since vertex weights are
revealed in pre-${\mathcal{G}}_{n}$, edges are present independently. So, we
obtain from the connectivity probability $\mathrm{p}$ in (4.6):

$\displaystyle\mathbb{P}\big{(}{\mathcal{C}}_{j}\nsim_{{\mathcal{G}}_{n}}{\mathcal{C}}_{\ell}\mid\text{pre-}{\mathcal{G}}_{n}\big{)}$
$\displaystyle\leq\mathbb{P}(\\{v_{j}^{\star}\nsim_{{\mathcal{G}}_{n}}{\mathcal{C}}_{\ell}\\}\cap\\{v_{\ell}^{\star}\nsim_{{\mathcal{G}}_{n}}{\mathcal{C}}_{j}\\}\mid\text{pre-}{\mathcal{G}}_{n}\big{)}$
(5.20)
$\displaystyle=\prod_{u\in{\mathcal{C}}_{j}}(1-\mathrm{p}(u,v_{\ell}^{\star}))\cdot\prod_{\tilde{u}\in{\mathcal{C}}_{\ell}}(1-\mathrm{p}(\tilde{u},v_{j}^{\star}))$
$\displaystyle\leq\Big{(}1-p\Big{(}1\wedge\frac{\beta\varepsilon_{2}k_{n}^{1/(\tau-1)}}{d^{d/2}n}\Big{)}^{\alpha}\Big{)}^{2\rho
k_{n}}$ $\displaystyle\leq\exp\Big{(}-2\rho
k_{n}p(1\wedge\beta^{\alpha}d^{-\alpha
d/2}\varepsilon_{2}^{\alpha}k_{n}^{\alpha/(\tau-1)}n^{-\alpha}\big{)}\Big{)}.$

There are now two cases. If the minimum is attained at $1$ in the last row,
then the right-hand side tends to $0$ since $k_{n}=Mn^{1-\zeta}\to\infty$
since $\zeta<1$. This means that (5.19) holds. If the minimum is not attained
at $1$, some further calculations are required. We set $M$ as the solution of
the equation

$\rho p\beta^{\alpha}d^{-\alpha
d/2}\varepsilon_{2}^{\alpha}=M^{-\alpha/(\tau-1)}\lambda/(1-\varepsilon_{1}).$
(5.21)

Then the last row in (5.20) equals

$\exp\big{(}-2\rho p\beta^{\alpha}d^{-\alpha
d/2}\varepsilon_{2}^{\alpha}k_{n}^{1+\alpha/(\tau-1)}n^{-\alpha}\big{)}=\exp\big{(}-\tfrac{2\lambda}{1-\varepsilon_{1}}k_{n}(k_{n}/M)^{\alpha/(\tau-1)}n^{-\alpha}\big{)}$

We now use that $k_{n}=n/m_{n}$ for the first appearance of $k_{n}$ and that
$k_{n}/M=n^{1-\zeta_{\mathrm{hl}}}$ in the second appearance, see (5.8). The
exponent there is $1-\zeta_{\mathrm{hl}}=(1-1/\alpha)(\tau-1)$, so rewriting
the right-hand side yields that the exponents of $n$ cancel each other. Using
also
$|{\mathcal{V}}_{{\mathcal{H}}_{n}}|=\lceil(1-\varepsilon_{1})m_{n}\rceil$,

$\exp\big{(}-\tfrac{2\lambda}{1-\varepsilon_{1}}(n/m_{n})n^{(1-\zeta_{\mathrm{hl}})\alpha/(\tau-1)}n^{-\alpha}\big{)}=\exp\Big{(}-\frac{2\lambda}{(1-\varepsilon_{1})m_{n}}\Big{)}<1-\frac{\lambda}{|{\mathcal{V}}_{{\mathcal{H}}_{n}}|}$

for all $n$ sufficiently large. This proves the desired bound (5.19) in the
high-low regime.

_2\. High-high edges, $\zeta_{\mathrm{type}}=\zeta_{\mathrm{hl}}>0$, and
$\alpha<\infty$._ As in the high-low regime, we reveal
pre-${\mathcal{G}}_{n}$, and choose in each good box ${\mathcal{Q}}_{j}$ a
vertex $v_{j}^{\star}$ in ${\mathcal{C}}_{j}$ with mark at least
$\varepsilon_{2}k_{n}^{1/(\tau-1)}$, see (5.11). We directly estimate the
probability that $v_{j}^{\star}$ is connected to $v_{\ell}^{\star}$ for
$j,\ell\in{\mathcal{V}}_{{\mathcal{H}}_{n}}$:

$\displaystyle\mathbb{P}\big{(}{\mathcal{C}}_{j}\sim_{{\mathcal{G}}_{n}}{\mathcal{C}}_{\ell}\mid\text{pre-}{\mathcal{G}}_{n}\big{)}$
$\displaystyle\geq\mathbb{P}(v_{j}^{\star}\sim_{{\mathcal{G}}_{n}}v_{\ell}^{\star}\mid\text{pre-}{\mathcal{G}}_{n})$
(5.22) $\displaystyle\geq
p\Big{(}1\wedge\frac{\beta\varepsilon_{2}^{\sigma+1}k_{n}^{(\sigma+1)/(\tau-1)}}{d^{d/2}n}\Big{)}^{\alpha}.$

If the minimum is attained at $1$ on the right-hand side, then (5.19) follows,
so we assume it is attained at the second term. We use that $k_{n}=n/m_{n}$ by
(5.8). The right-hand side equals

$\displaystyle p\beta^{\alpha}d^{-\alpha
d/2}\varepsilon_{2}^{(\sigma+1)\alpha}n^{\alpha(\sigma+1)/(\tau-1)-\alpha}m_{n}^{-\alpha(\sigma+1)/(\tau-1)+1}\frac{1}{m_{n}}$

where we multiplied by a factor $m_{n}/m_{n}$. We use now that
$m_{n}=n^{\zeta_{\mathrm{hh}}}/M$ by (5.7) in the first occurrence of $m_{n}$
above to compute the power of $n$. The above expression equals

$p\beta^{\alpha}d^{-\alpha
d/2}\varepsilon_{2}^{(\sigma+1)\alpha}M^{\alpha(\sigma+1)/(\tau-1)-1}n^{(1-\zeta_{\mathrm{hh}})\alpha(\sigma+1)/(\tau-1)-\alpha+\zeta_{\mathrm{hh}}}\cdot\frac{1}{m_{n}}$

It is an elementary computation to check that the power of $n$ is $0$ using
that $\zeta_{\mathrm{hh}}=(\sigma+1-(\tau-1))/(\sigma+1-(\tau-1)/\alpha)$ in
(2.14). Further, $\zeta_{\mathrm{hh}}$ is only positive when $\sigma>\tau-2$.
This latter inequality implies that $(\sigma+1)/(\tau-1)>1$ and so the
exponent of $M$ is strictly positive for all $\alpha>1$. So, if we choose $M$
large enough then the constant multiplying $1/m_{n}$ in the above formula
becomes arbitrarily large. So, returning to (5.22),

$\mathbb{P}\big{(}{\mathcal{C}}_{j}\sim_{{\mathcal{G}}_{n}}{\mathcal{C}}_{\ell}\mid\text{pre-}{\mathcal{G}}_{n}\big{)}\geq\frac{1}{m_{n}}\cdot
p\beta^{\alpha}d^{-\alpha
d/2}\varepsilon_{2}^{(\sigma+1)\alpha}M^{\alpha(\sigma+1)/(\tau-1)-1}\geq\frac{\lambda}{|{\mathcal{V}}_{{\mathcal{H}}_{n}}|}$

holds for sufficiently large $M$, since
$|{\mathcal{V}}_{{\mathcal{H}}_{n}}|=\lceil(1-\varepsilon_{1})m_{n}\rceil$.
This finishes the proof of (5.18) for the high-high regime with
$\alpha<\infty$.

_3\. High-high edges,
$\zeta_{\mathrm{type}}=\zeta_{\mathrm{hh}}=(\sigma+2-\tau)/(\sigma+1)>0$, and
$\alpha=\infty$._ This case is almost the same as the $\alpha<\infty$ case.
The only difference is that in (5.22) the minimum on the right-hand side
_must_ be attained at $1$, and then the connection probability is $p$,
otherwise it is $0$. So we check whether

$\beta\varepsilon_{2}^{\sigma+1}k_{n}^{(1+\sigma)/(\tau-1)}/(d^{d/2}n)\geq 1$

holds. We use $k_{n}=Mn^{1-\zeta_{\mathrm{hh}}}$ in (5.8) and
$1-\zeta_{\mathrm{hh}}=\gamma_{\mathrm{hh}}(\tau-1)=(\tau-1)/(\sigma+1)$ when
$\alpha=\infty$. Thus, the powers of $n$ cancel each other again. Since
$\tau<2+\sigma$, we can choose $M$ large enough so that

$\beta\varepsilon_{2}^{\sigma+1}M^{(1+\sigma)/(\tau-1)}/d^{d/2}\geq 1.$

The bound (5.19) also follows in this regime.

_4\. Low-low edges, $\zeta_{\mathrm{type}}=\zeta_{\mathrm{ll}}>0$._ We may
assume that $\alpha<\infty$, since otherwise $\zeta_{\mathrm{ll}}=2-\alpha<0$.
By the definition of a good box in (5.11), $|{\mathcal{C}}_{j}|\geq\rho k_{n}$
and each vertex has mark at least $1$. So we compute using the connection
probability $\mathrm{p}$ in (4.6) for
$j,\ell\in{\mathcal{V}}_{{\mathcal{H}}_{n}}$:

$\displaystyle\mathbb{P}\big{(}{\mathcal{C}}_{j}\nsim_{{\mathcal{G}}_{n}}{\mathcal{C}}_{\ell}\mid\text{pre-}{\mathcal{G}}_{n}\big{)}$
$\displaystyle\leq\big{(}1-p\beta^{\alpha}d^{-\alpha
d/2}n^{-\alpha}\big{)}^{|{\mathcal{C}}_{j}|\cdot|{\mathcal{C}}_{\ell}|}$
(5.23) $\displaystyle\leq\exp\big{(}-p\beta^{\alpha}d^{-\alpha
d/2}\rho^{2}k_{n}^{2}n^{-\alpha}\big{)}.$

Since $k_{n}=Mn^{1-\zeta}=Mn^{\alpha-1}$ in (5.8),
$k_{n}^{2}n^{-\alpha}=M^{2}n^{\alpha-2}$. With $m_{n}=n^{2-\alpha}/M$, we may
write $k_{n}^{2}n^{-\alpha}=M/m_{n}$ on the right-hand side above. We choose
$M$ as the solution of the equation

$p\beta^{\alpha}d^{-\alpha d/2}\rho^{2}M=2\lambda/(1-\varepsilon_{1}).$

Now we obtain for $n$ large that, using
$|{\mathcal{V}}_{{\mathcal{H}}_{n}}|=\lceil(1-\varepsilon_{1})m_{n}\rceil$,

$\displaystyle\mathbb{P}\big{(}{\mathcal{C}}_{j}\nsim_{{\mathcal{G}}_{n}}{\mathcal{C}}_{\ell}\mid\text{pre-}{\mathcal{G}}_{n}\big{)}$
$\displaystyle=\exp\big{(}-p\beta^{\alpha}d^{-\alpha
d/2}\rho^{2}M\tfrac{1}{m_{n}}\big{)}\leq\exp\bigg{(}-\frac{2\lambda}{|{\mathcal{V}}_{{\mathcal{H}}_{n}}|}\bigg{)}<1-\frac{\lambda}{|{\mathcal{V}}_{{\mathcal{H}}_{n}}|},$
(5.24)

showing (5.19). The same calculation works for long-range percolation on
${\mathbb{Z}}^{d}$.

_Conclusion for proving ( 5.5)._ We conclude that the bound (5.19) holds
whenever $\zeta$ equals either
$\zeta_{\mathrm{ll}},\zeta_{\mathrm{hl}},\zeta_{\mathrm{hh}}$ for a suitable
choice of $M$ in (5.7). This proves the stochastic domination stated in (5.18)
and finishes the proof of (5.5) in Proposition 5.1. ∎

###  5.2. When relying on constant-length edges

We proceed to proving Proposition 5.1(short). Here, instead of using long
edges to connect boxes and a domination towards an Erdős-Rényi random graph,
we use “relatively short” edges and stochastic domination towards nearest-
neighbour site-bond percolation on ${\mathbb{Z}}^{d}$. In that model, each
vertex $x\in{\mathbb{Z}}^{d}$ is independently _active_ with probability $q$,
and each edge between active neighbouring vertices is _open_ with probability
$r$, independently again. We denote the resulting graph formed by open edges
between active vertices by $\mathrm{NNP}(q,r)$, and write
$L_{n}^{\scriptscriptstyle(1)}(q,r)$ for the largest component inside
$\Lambda_{n}$. We state a combination of two classical results [29, 59,
Theorem 1.1] that will replace 5.4 in this regime.

######  Proposition 5.5 (High-density NNP($q,r$) has a large giant).

Consider nearest-neighbour site-bond percolation $\mathrm{NNP}(q,r)$ on
${\mathbb{Z}}^{d}$ with probabilities $q,r\in(0,1]$. For each $\varepsilon>0$,
there exist constants $q_{0},r_{0}\in(0,1)$, and $A>0$ such that for all
$q\geq q_{0}$, $r\geq r_{0}$, $n\geq 1$,

$\mathbb{P}\big{(}|L_{n}^{\scriptscriptstyle(1)}(q,r)|<(1-\varepsilon)n\big{)}\leq\exp\big{(}-\tfrac{1}{A}n^{(d-1)/d}\big{)}.$

###### Proof.

Fix $\varepsilon>0$. We shall define an
$\varepsilon_{1}=\varepsilon_{1}(\varepsilon)$ and set
$q_{0}:=1-\varepsilon_{1}$ and $r_{0}=1-\varepsilon_{1}$. Let
$\omega\sim\mathrm{NNP}(q_{0},r_{0})$. We couple $\omega$ to iid Bernoulli
bond percolation $\omega^{\star}\sim\mathrm{NNP}(1,1-12d\varepsilon_{1})$ on
${\mathbb{Z}}^{d}$, similarly to [7, 59]. By a union bound over the endpoints
of an edge and the edge itself, each edge in is open in $\omega$ with
_marginal_ probability at least $1-3\varepsilon_{1}$. Consider an edge with
endpoints $(x,y)$ in $\omega$, and let $N_{(x,y)}:=\\{\text{edges incident to
$x$ or $y$ in ${\mathbb{Z}}^{d}$}\\}\setminus\\{(x,y)\\}$. Clearly
$|N_{(x,y)}|=4d-2$. For any set of edges $S\subseteq N_{(x,y)}$, by a union
bound,

$\displaystyle\mathbb{P}((x,y)\text{ open in }\omega\mid\text{all edges in $S$
open in $\omega$})$ $\displaystyle\geq\mathbb{P}((x,y)\text{ open}\text{ and
}\text{all edges in $S$ open})$ $\displaystyle\geq 1-(4d-1)\cdot
3\varepsilon_{1}\geq 1-12d\varepsilon_{1}=:\tilde{p}.$

Edges that do not share a vertex are independently open, so one can iterate
this argument: for every finite set $E$ of edges in ${\mathbb{Z}}^{d}$,
$\mathbb{P}(\text{all edges in $E$ are open})\geq\tilde{p}^{|E|}$. Hence, by
Strassen’s theorem [60] we can couple $\omega$ with an independent bond
percolation $\omega^{\star}$ on ${\mathbb{Z}}^{d}$ with retention-probability
$\tilde{p}$, where every open edge in $\omega^{\star}$ is open in $\omega$.
Let us write $C_{B_{n}}^{\scriptscriptstyle(1)}(\tilde{p})$ for the largest
component of $\omega^{\star}\cap\Lambda_{n}$. Given $\varepsilon>0$, by [29,
Theorem 1.1], there exists a $p_{\star}(\varepsilon)<1$ so that whenever
$\tilde{p}>p_{\star}(\varepsilon)$, for some $A>0$,

$\mathbb{P}\big{(}|C_{B_{n}}^{\scriptscriptstyle(1)}(\tilde{p})|<(1-\varepsilon)n\big{)}\leq\exp\big{(}-\tfrac{1}{A}n^{(d-1)/d}\big{)}.$

Hence, setting $\varepsilon_{1}>(1-p_{\star}(\varepsilon))/12d$ yields
$\tilde{p}>p(\varepsilon)$, and we obtain by the coupling
$\omega\succcurlyeq\omega_{\star}$:

$\mathbb{P}\big{(}|L_{n}^{\scriptscriptstyle(1)}(q,r)|<(1-\varepsilon)n\big{)}\leq\mathbb{P}\big{(}|C_{B_{n}}^{\scriptscriptstyle(1)}(\tilde{p})|<(1-\varepsilon)n\big{)}\leq\exp\big{(}-\tfrac{1}{A}n^{(d-1)/d}\big{)},$

and the result follows for $q_{0}=r_{0}=1-\varepsilon_{1}$, and by
monotonicity for all values $q\geq q_{0}$ and $r\geq r_{0}$. ∎

###### Proof of Proposition 5.1(short).

We give the proof for KSRGs on a Poisson point process. The result for long-
range percolation on ${\mathbb{Z}}^{d}$ follows analogously to the case
$\zeta_{\mathrm{ll}}>0$. By the assumptions in Proposition 5.1), there is a
$\mathrm{type}\in\\{\mathrm{hl},\mathrm{hh},\mathrm{ll}\\}$ so that
$\zeta_{\mathrm{type}}>0$. Positivity will ensure that “relatively long” edges
are present to keep the giant together. Let $M$ be a sufficiently large
constant. We assume for simplicity that $(n/M)^{1/d}\in{\mathbb{N}}$.
Tessellate $\Lambda_{n}$ into $m_{n}:=n/M$ may boxes
${\mathcal{Q}}_{1},\ldots,{\mathcal{Q}}_{m_{n}}$ of volume $M$. Similarly as
before, we write
${\mathcal{V}}_{M,j}:={\mathcal{V}}\cap({\mathcal{Q}}_{j}\times[1,\infty))$
for the vertices in ${\mathcal{Q}}_{j}$, ${\mathcal{G}}_{M,j}$ for the
subgraph of ${\mathcal{G}}_{n}$ induced by these vertices in
${\mathcal{Q}}_{j}$, and pre-${\mathcal{G}}_{n}$ for the union of the
subgraphs ${\mathcal{G}}_{M,j}$, $j\in[m_{n}]$. Fix $\delta>0$ small as in
(5.3).

_Good subboxes._ We call a box ${\mathcal{Q}}_{j},j\in[m_{n}]$ _good_ if the
following event holds. When $\mathrm{type}\in\\{\mathrm{hl},\mathrm{hh}\\}$,
we set

${\mathcal{A}}_{\mathrm{box}}(j)\\!:=\\!\left\\{\,\begin{aligned}
\exists\mbox{comp. ${\mathcal{C}}_{j}$ in
${\mathcal{G}}_{M,j}\big{[}1,M^{1/(\tau-1)}\big{)}$}:|{\mathcal{C}}_{j}|&\geq\rho
M,\\\
{\mathcal{C}}_{j}&\supseteq{\mathcal{V}}_{M,j}[M^{(1-\delta)/(\tau-1)},M^{1/(\tau-1)})\\\
\tfrac{1}{2}M^{\delta}&\leq|{\mathcal{V}}_{M,j}[M^{(1-\delta)/(\tau-1)},M^{1/(\tau-1)})|\end{aligned}\right\\}.$
(5.25)

When $\mathrm{type}=\mathrm{ll}$, we set

${\mathcal{A}}_{\mathrm{box}}(j):=\\!\left\\{\,\exists\mbox{comp.
${\mathcal{C}}_{j}$ in
${\mathcal{G}}_{M,j}\big{[}1,M^{1/(\tau-1)}\big{)}$}:|{\mathcal{C}}_{j}|\geq\rho
M\right\\}.$ (5.26)

This event is measurable with respect to pre-${\mathcal{G}}_{n}$. Our
assumption (5.3) directly implies 5.3, which in turn implies that the first
two requirements in ${\mathcal{A}}_{\mathrm{box}}(j)$ – concerning
${\mathcal{C}}_{j}$ – are satisfied with probability arbitrarily close to $1$
by choosing $M$ sufficiently large. For the third requirement in (5.25) we use
the intensity of the PPP (4.5), and compute for fixed $\delta>0$

$\mathbb{P}\big{(}|{\mathcal{V}}_{M,j}[M^{(1-\delta)/(\tau-1)},M^{1/(\tau-1)})|\geq\tfrac{1}{2}M^{\delta}\big{)}\longrightarrow
1,$

as $M$ tends to infinity. Since the three conditions on the right-hand side
hold with probability arbitrarily close to $1$, we may assume that $M$ is so
large that for a fixed $q\in(0,1)$ and any $j\in[m_{n}]$, independently of all
other boxes,

$\mathbb{P}\big{(}{\mathcal{A}}_{\mathrm{box}}(j)\big{)}>q.$ (5.27)

_The auxiliary graph and LDP for site-bond percolation._ Consider then the
auxiliary graph ${\mathcal{H}}_{n}$, with vertex set
${\mathcal{V}}_{{\mathcal{H}}_{n}}\subset[m_{n}]$. By definition of the
boxing, the set of vertices $[m_{n}]$ can be mapped to the integer points in a
box of side-length $m_{n}^{1/d}$, such that any two adjacent boxes are mapped
to integer points at distance one from each other. We call
$j\in{\mathcal{V}}_{{\mathcal{H}}_{n}}$ active if the box ${\mathcal{Q}}_{j}$
satisfies ${\mathcal{A}}_{\mathrm{box}}(j)$. Two active vertices
$j,\ell\in{\mathcal{V}}_{{\mathcal{H}}_{n}}$ are connected in
${\mathcal{H}}_{n}$ if they are neighbouring vertices in $B_{m_{n}}$, and
there exist vertices $v\in{\mathcal{C}}_{j},\tilde{v}\in{\mathcal{C}}_{\ell}$
such that $v$ is connected by an edge to $\tilde{v}$ in ${\mathcal{G}}_{n}$.
Let us write ${\mathcal{C}}_{{\mathcal{H}}_{n}}^{\scriptscriptstyle(1)}$ for
the largest component in ${\mathcal{H}}_{n}$. Since each ${\mathcal{C}}_{j}$
in a good box ${\mathcal{Q}}_{j}$ has size at least $\rho n$, the event
$\\{|{\mathcal{C}}_{{\mathcal{H}}_{n}}^{\scriptscriptstyle(1)}|\geq(1-\varepsilon)m_{n}\\}$
implies
$\\{|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}[1,M^{1/(\tau-1)})|\geq(1-\varepsilon)\rho
n\\}$. Let $q,r>0$ be such that by Proposition 5.5 for a fixed
$\varepsilon>0$, $A>0$ and all $n\geq 1$,

$\mathbb{P}(|L_{m_{n}}^{\scriptscriptstyle(1)}(q,r)|<(1-\varepsilon)m_{n}\big{)}\leq\exp\big{(}-\tfrac{1}{A}m_{n}^{(d-1)/d}\big{)}.$

We will show that we can choose $M$ sufficiently large (depending on
$\varepsilon$) so that

${\mathcal{H}}_{n}\succcurlyeq\mathrm{NNP}(q,r).$ (5.28)

This domination then implies that
$|{\mathcal{C}}_{{\mathcal{H}}_{n}}^{\scriptscriptstyle(1)}|\succcurlyeq|L_{m_{n}}^{\scriptscriptstyle(1)}(q,r)|$,
and so

$\displaystyle\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}[1,M^{1/(\tau-1)})|<(1-\varepsilon)\rho
n\big{)}$
$\displaystyle\leq\mathbb{P}\big{(}|L_{m_{n}}^{\scriptscriptstyle(1)}(q,r)|<(1-\varepsilon)m_{n}\big{)}$
(5.29) $\displaystyle\leq\exp\big{(}-\tfrac{1}{A}m_{n}^{(d-1)/d}\big{)}$
$\displaystyle=\exp\big{(}-\tfrac{1}{AM^{(d-1)/d}}n^{(d-1)/d}\big{)},$

implying the statement of Proposition 5.1 for a larger value $A$.

_The auxiliary graph dominates site-bond percolation._ It remains to prove the
domination (5.28). By (5.27) and the definition of ${\mathcal{H}}_{n}$ below
(5.27), each vertex $j\in[m_{n}]$ is independently _active_ with probability
at least $q$ for $M$ sufficiently large. Thus, it remains to show that for two
large components ${\mathcal{C}}_{j},{\mathcal{C}}_{\ell}$ in adjacent good
boxes ${\mathcal{Q}}_{j},{\mathcal{Q}}_{\ell}$,

$\mathbb{P}\big{(}{\mathcal{C}}_{j}\nsim_{{\mathcal{G}}_{n}}{\mathcal{C}}_{\ell}\mid\text{pre-}{\mathcal{G}}_{n}\big{)}=\prod_{u\in{\mathcal{C}}_{j},v\in{\mathcal{C}}_{\ell}}(1-\mathrm{p}(u,v))\longrightarrow
0,\qquad\text{as }M\to\infty.$ (5.30)

We write $|{\mathcal{E}}({\mathcal{C}}_{j},{\mathcal{C}}_{\ell})|$ for the
number of edges between the two components. Then

$\mathbb{P}\big{(}{\mathcal{C}}_{j}\nsim_{{\mathcal{G}}_{n}}{\mathcal{C}}_{\ell}\mid\text{pre-}{\mathcal{G}}_{n}\big{)}\leq\exp\bigg{(}-\sum_{u\in{\mathcal{C}}_{j},v\in{\mathcal{C}}_{\ell}}\mathrm{p}(u,v)\bigg{)}=\exp\big{(}-\mathbb{E}[|{\mathcal{E}}({\mathcal{C}}_{j},{\mathcal{C}}_{\ell})|\mid\text{pre-}{\mathcal{G}}_{n}]\big{)}.$

We will show case-by-case for
$\zeta\in\\{\zeta_{\mathrm{hl}},\zeta_{\mathrm{hh}},\zeta_{\mathrm{ll}}\\}$
that
$\mathbb{E}[|{\mathcal{E}}({\mathcal{C}}_{j},{\mathcal{C}}_{\ell})|\mid\text{pre-}{\mathcal{G}}_{n}]\to\infty$
using either high-low, high-high, or low-low connections between two active
neighbouring boxes $j,\ell$. The maximal distance between any two vertices in
neighbouring boxes is $2\sqrt{d}M^{1/d}$.

_1\. Low-low connections help: $\zeta_{\mathrm{ll}}>0$._ We may assume
$\alpha<\infty$ otherwise $\zeta_{\mathrm{ll}}=2-\alpha$ is negative. Every
vertex has mark at least $1$. Thus, from the connection probability
$\mathrm{p}$ in (4.6) it follows that

$\mathbb{E}[|{\mathcal{E}}({\mathcal{C}}_{j},{\mathcal{C}}_{\ell})|\mid\text{pre-}{\mathcal{G}}_{n}]=\Omega\big{(}M^{-\alpha}|{\mathcal{C}}_{j}|\cdot|{\mathcal{C}}_{\ell}|\big{)}=\Omega\big{(}M^{2-\alpha}\big{)}.$
(5.31)

Since by assumption $\zeta_{\mathrm{ll}}=2-\alpha>0$, (5.30) follows for fixed
$\varepsilon$. The same calculation works for long-range percolation on
${\mathbb{Z}}^{d}$.

_2\. High-low connections help: $\zeta_{\mathrm{hl}}>0$._ We may again assume
$\alpha<\infty$ otherwise $\zeta_{\mathrm{hl}}$ is negative. On the event
${\mathcal{A}}_{\mathrm{box}}(j)$, defined in (5.25), the component
${\mathcal{C}}_{j}$ contains at least $M^{\delta}/2$ vertices with mark at
least $M^{(1-\delta)/(\tau-1)}$. Then, using possible edges between a high-
mark vertex in ${\mathcal{C}}_{j}$ and the at least $\rho M$ vertices in
${\mathcal{C}}_{\ell}$ that have mark at least $1$, we obtain

$\displaystyle\mathbb{E}[|{\mathcal{E}}({\mathcal{C}}_{j},{\mathcal{C}}_{\ell})|\mid\text{pre-}{\mathcal{G}}_{n}]$
$\displaystyle=\Omega(M^{\delta+1})\cdot\Omega\bigg{(}1\wedge\Big{(}\frac{M^{(1-\delta)/(\tau-1)}}{M}\Big{)}^{\alpha}\bigg{)}$
$\displaystyle=\Omega(M^{1+\delta})\wedge\Omega(M^{1-\alpha(\tau-2)/(\tau-1)+\delta(1-\alpha/(\tau-1))}).$
(5.32)

When $\zeta_{\mathrm{hl}}=1-(1-1/\alpha)(\tau-1)=(\tau-1)/\alpha-(\tau-2)>0$,
the exponent of $M$ in (5.32) is positive for sufficiently small $\delta>0$.
So (5.30) follows.

_3\. High-high connections help, $\zeta_{\mathrm{hh}}>0$._ We first assume
that $\alpha<\infty$. Using that we only consider good boxes, and that there
are at least $M^{\delta}/2$ many high-mark vertices with mark in the interval
$[M^{(1-\delta)/(\tau-1)},M^{1/(\tau-1)})$ in both ${\mathcal{C}}_{j}$ and
${\mathcal{C}}_{\ell}$, we compute

$\mathbb{E}[|{\mathcal{E}}({\mathcal{C}}_{j},{\mathcal{C}}_{\ell})|\mid\text{pre-}{\mathcal{G}}_{n}]=\Omega(M^{2\delta})\cdot\Omega\bigg{(}1\wedge\Big{(}\frac{M^{(\sigma+1)(1-\delta)/(\tau-1)}}{M}\Big{)}^{\alpha}\bigg{)}.$

From (2.14), $\zeta_{\mathrm{hh}}>0$ only when $\sigma>\tau-2$. So, for
$\delta$ is sufficiently small, the second factor is $\Theta(1)$. Thus, the
right-hand side tends to infinity with $M$ and (5.30) follows. When
$\alpha=\infty$, it follows analogously that
$\mathbb{E}[|{\mathcal{E}}({\mathcal{C}}_{j},{\mathcal{C}}_{\ell})|\mid\widehat{\mathcal{G}}_{n}]=\Omega(M^{2\delta})$
if $\delta$ is sufficiently small since the minimum is taken at $1$ on the
right-hand side above.

_Conclusion._ We conclude that (5.30) follows in all three cases, proving the
stochastic domination (5.28) and finishing the proof of (5.5). ∎

###  5.3. Verification of the requirement

We now verify the requirement (5.3). To do so, we prove the following lemma
that we only need for models with non-trivial vertex marks. We define one more
exponent for each regime $\mathrm{hl,ll,hh}$:

$\eta_{\mathrm{hl}}:=1-\gamma_{\mathrm{hl}}(\tau-1)/\alpha,\qquad\eta_{\mathrm{ll}}:=1/\alpha,\qquad\eta_{\mathrm{hh}}:=1-\sigma\gamma_{\mathrm{hh}}.$
(5.33)

Using the respective values of
$\gamma_{\mathrm{ll}},\gamma_{\mathrm{hl}},\gamma_{\mathrm{hh}}$ in (5.2),
(2.11), and (2.13), it is elementary to verify that if
$\zeta_{\mathrm{type}}=\zeta_{\star}$ for some
$\mathrm{type}\in\\{\mathrm{ll},\mathrm{hl},\mathrm{hh}\\}$, then
$\eta_{\mathrm{type}}>\gamma_{\mathrm{type}}$ holds (see the proof of Lemma
5.6). Then there are values of $\alpha$ such that
$\gamma_{\mathrm{ll}}>\eta_{\mathrm{ll}}$. We write
${\mathcal{C}}_{n}(0)[1,w)$ for the component of the origin spanned on
vertices in ${\mathcal{V}}_{n}[1,w)$.

######  Lemma 5.6 (Poly-logarithmic mark-thresholds).

Consider a supercritical KSRG satisfying Assumption 2.2 on a PPP. Assume for a
$\mathrm{type}\in\\{\mathrm{ll},\mathrm{hl}\\}$ that
$\zeta_{\mathrm{type}}=\max(\zeta_{\mathrm{hl}},\zeta_{\mathrm{ll}})>0$.
Whenever there exist constants $\delta\in[0,\zeta)$, $A^{\prime},\rho>0$, such
that for all $n\geq 1$,

$\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}[1,A^{\prime}n^{\gamma_{\mathrm{type}}})|<\rho
n\big{)}\leq\exp\big{(}-\tfrac{1}{A^{\prime}}n^{\zeta_{\mathrm{type}}-\delta}\big{)},$
(5.34)

then, for all $C>0$, there exists a constant $A>0$ such that for all $n$
sufficiently large,

$\displaystyle\mathbb{P}\big{(}\big{|}{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}\big{[}1,(A\log
n)^{\gamma_{\mathrm{type}}/(\zeta_{\mathrm{type}}-\delta)}\big{)}\big{|}\geq\rho
n\big{)}$ $\displaystyle\geq 1-n^{-C},$ (5.35)

and

$\mathbb{P}\big{(}\exists\mbox{ comp. }{\mathcal{C}}\mbox{ in
}{\mathcal{G}}_{n}:{\mathcal{C}}\supseteq{\mathcal{V}}\big{[}(A\log
n)^{\eta_{\mathrm{type}}/(\zeta_{\mathrm{type}}-\delta)},\infty\big{)},|{\mathcal{C}}|\geq\rho
n\big{)}\geq 1-n^{-C}.$ (5.36)

The statements remain valid for the Palm version
$\mathbb{P}^{\scriptscriptstyle x}$ of $\mathbb{P}$ for any
$x\in{\mathbb{R}}^{d}$.

The proof is an adaptation of [48, Proposition 5.12] and we present it in
Appendix B.3. In a nutshell, we apply a boxing scheme —with box sizes
$\Theta((\log n)^{1/(\zeta-\delta)})$— and apply (5.34) to each box. To form
${\mathcal{C}}$, we connect boxes to each other using high- and/or low-mark
vertices depending on the regime. Then, we connect vertices of mark at least
$(A\log n)^{\eta/(\zeta-\delta)}$ to the constant-mark vertices in
${\mathcal{C}}$. Computations are similar to those in Section 6.1.

The corollaries of Propositions 5.1 and 5.6 motivate the somewhat
counterintuitive formulation of Lemma 5.6, i.e., the requirement (5.34) with
both $\delta>0$ and $\delta=0$ allowed.

######  Corollary 5.7 (A giant with sharper probability).

Consider a supercritical KSRG satisfying Assumption 2.2 on a PPP or consider
supercritical long-range percolation on ${\mathbb{Z}}^{d}$. Assume that
$\zeta_{\mathrm{long}}>0$, and $\zeta_{\star}=\zeta_{\mathrm{type}}$ for some
$\mathrm{type}\in\\{\mathrm{ll},\mathrm{hl},\mathrm{hh},\mathrm{short}\\}$.
Set $\gamma_{\mathrm{short}}:=0$. There exist constants $A_{1}>0$ such that
for all $n\geq 1$,

$\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}[1,A_{1}n^{\gamma_{\mathrm{type}}})|<\tfrac{1}{A_{1}}n\big{)}\leq\exp\big{(}-\tfrac{1}{A_{1}}n^{\max(\zeta_{\mathrm{long}},(d-1)/d)}\big{)}.$
(5.37)

###### Proof.

We first consider KSRGs on a PPP. By 2.3,
$\zeta_{\mathrm{long}}=\max(\zeta_{\mathrm{ll}},\zeta_{\mathrm{hl}},\zeta_{\mathrm{hh}})$.
When $\zeta_{\mathrm{long}}\in\\{\zeta_{\mathrm{ll}},\zeta_{\mathrm{hl}}\\}$,
Proposition 4.1 proves the requirement (5.34) of Lemma 5.6 for some $\delta>0$
and a small value of $\rho>0$. Hence, (5.35)-(5.36) holds for these values of
$\delta$ and $\rho$. This implies the requirement (5.3) of Proposition 5.1.
When $\zeta_{\mathrm{\star}}=\zeta_{\mathrm{hh}}>0$, (5.3) follows from the
combination of the law of large numbers [48, Corollary 2.3], and that
$|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|$ contains all vertices of at
least some polylogarithmic weight in $n$ by [48, Proposition 5.12], which then
gives (5.34) and thus Lemma 5.6. This proves (5.37) when
$\zeta_{\star}\in\\{\zeta_{\mathrm{ll}},\zeta_{\mathrm{hl}},\zeta_{\mathrm{hh}}\\}$,
and gives the requirement (5.3) of Proposition 5.1 whenever
$\zeta_{\mathrm{long}}>0$. Further, the case for
$\zeta_{\star}=\zeta_{\mathrm{short}}$ follows from (5.5). For long-range
percolation on ${\mathbb{Z}}^{d}$, $\zeta_{\mathrm{hl}}$ and
$\zeta_{\mathrm{hh}}$ are negative, so
$\zeta_{\mathrm{long}}=\zeta_{\mathrm{ll}}=2-\alpha$. The requirement (5.34)
of Lemma 5.6 is verified by [14, Theorem 3.2]. ∎

The actual mark-threshold so that _all_ vertices above that mark are in the
giant is as follows.

######  Corollary 5.8 (Poly-logarithmic mark-thresholds).

Consider a supercritical KSRG satisfying Assumption 2.2 on a PPP or consider
long-range percolation on ${\mathbb{Z}}^{d}$. Assume
$\zeta_{\mathrm{type}}=\max(\zeta_{\mathrm{ll}},\zeta_{\mathrm{hl}})>0$ for
some $\mathrm{type}\in\\{\mathrm{ll},\mathrm{hl}\\}$. For all $C>0$, there
exist constants $A,\varepsilon>0$ such that for all $n$ sufficiently large,

$\displaystyle\mathbb{P}\big{(}\big{|}{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}\big{[}1,(A\log
n)^{\gamma_{\mathrm{type}}/\zeta_{\mathrm{type}}}\big{)}\big{|}\geq\varepsilon
n\big{)}$ $\displaystyle\geq 1-n^{-C},$ (5.38)

and

$\mathbb{P}\big{(}\exists\mbox{ comp. }{\mathcal{C}}\mbox{ in
}{\mathcal{G}}_{n}:{\mathcal{C}}\supseteq{\mathcal{V}}_{n}\big{[}(A\log
n)^{\eta_{\mathrm{type}}/\zeta_{\mathrm{type}}},\infty\big{)},|{\mathcal{C}}|\geq\varepsilon
n\big{)}\geq 1-n^{-C}.$ (5.39)

###### Proof.

In Corollary 5.7 we have just shown that the requirement (5.34) in Lemma 5.6
is met with $\delta=0$ for the case
$\zeta_{\mathrm{type}}=\max(\zeta_{\mathrm{ll}},\zeta_{\mathrm{hl}})$. This
yields the first two bounds (5.38)–(5.39) for KSRGs on a PPP. In long-range
percolation, all marks are equal to one, so that ${\mathcal{V}}[(A\log
n)^{\eta_{\mathrm{type}}/\zeta_{\mathrm{type}}},\infty)=\emptyset$, and the
two bounds are implied by Corollary 5.7.∎

In Corollary 5.7 we obtain the sharp decay on the probability of having a
giant, i.e., we obtain the target decay of the lower tail in Theorem 2.7.
However, the proportion of vertices in the giant is not yet close to $\theta$.

##  6\. Lower tail of large deviations

In this section we prove Theorem 2.7. We first show uniqueness of the giant
via an upper bound on the size of the second-largest component
${\mathcal{C}}_{n}^{\scriptscriptstyle(2)}$. In Section 6.2, we extend this
upper bound on $|{\mathcal{C}}_{n}^{\scriptscriptstyle(2)}|$ to the upper
bound on the cluster-size decay in Theorem 2.9 using our previous work [48]. A
Law of Large Numbers for $|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|$ will
follow. Eventually we prove the lower tail of large deviations.

###  6.1. Non-giant components are small

We prove an upper bound on $|{\mathcal{C}}_{n}^{\scriptscriptstyle(2)}|$ when
$\max(\zeta_{\mathrm{hl}},\zeta_{\mathrm{ll}})>0$. When
$\zeta_{\mathrm{hh}}>0$, we proved a similar upper bound in [48] using
different techniques, see Remark 3.2. See also Remark 3.1 on the difficulties
one needs to overcome to extend this result to the case when surface tension
dominates connections, i.e., when $\zeta_{\star}=\zeta_{\mathrm{short}}$.

######  Proposition 6.1 (Upper bound second-largest component).

Consider a supercritical KSRG on a PPP or supercritical long-range percolation
on ${\mathbb{Z}}^{d}$. Assume
$\zeta_{\mathrm{type}}=\max(\zeta_{\mathrm{ll}},\zeta_{\mathrm{hl}})>0$ for
some $\mathrm{type}\in\\{\mathrm{ll},\mathrm{hl}\\}$. There exists a constant
$A>0$ such that for all $n>k$,

$\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(2)}|>k\big{)}\leq(n/k)\exp\big{(}-\tfrac{1}{A}k^{\zeta_{\mathrm{type}}}\big{)},$
(6.1)

The statement remains valid for the Palm version
$\mathbb{P}^{\scriptscriptstyle x}$ of $\mathbb{P}$ for any
$x\in{\mathbb{R}}^{d}$.

The proof of Proposition 6.1 is inspired by Sly and Crawford [24] who obtain a
polylogarithmic upper bound with unidentified exponent on the second-largest
component for long-range percolation. Contrary to long-range percolation, we
have to use the vertex-marks as well when $\tau<\infty$. We present the proof
for KSRGs on Poisson point processes satisfying $\zeta_{\mathrm{hl}}>0$, and
explain the needed changes for $\zeta_{\mathrm{ll}}>0$ and for KSRGs on
${\mathbb{Z}}^{d}$ at the end. We abbreviate
$\gamma=\gamma_{\mathrm{hl}}=1-1/\alpha$ and
$\zeta=\zeta_{\mathrm{hl}}=1-\gamma_{\mathrm{hl}}(\tau-1)=(\tau-1)/\alpha-(\tau-2)$.
Clearly $\zeta_{\mathrm{hl}}>0$ implies $\alpha<\infty$.

We let $A_{\ref{cor:initial-upper}}$ be the constant from (5.37) in Corollary
5.7 so that for all $n\geq 1$,

$\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}[1,A_{\ref{cor:initial-
upper}}n^{\gamma})|\leq\tfrac{1}{A_{\ref{cor:initial-
upper}}}n\big{)}\leq\exp\big{(}-\tfrac{1}{A_{\ref{cor:initial-
upper}}}n^{\zeta}\big{)}.$ (6.2)

For simplicity we assume that $(n/k)^{1/d}\in{\mathbb{N}}$, so that
$\Lambda_{n}$ can be partitioned into volume-$2^{-d}k$ boxes.

######  Definition 6.2 (Boxing scheme).

Fix $k\geq 1$ sufficiently large. Consider the boxes
${\mathcal{Q}}_{1},\ldots,{\mathcal{Q}}_{2^{d}n/k}$ that partition
$\Lambda_{n}$, and that are labelled so that ${\mathcal{Q}}_{j}$ is adjacent
to ${\mathcal{Q}}_{j+1}$ for all $j\in[2^{d}n/k-1]$. We write
${\mathcal{V}}_{k,j}$ for the PPP restricted to the box ${\mathcal{Q}}_{j}$,
${\mathcal{G}}_{k,j}$ for the graph ${\mathcal{G}}$ restricted to
${\mathcal{Q}}_{j}$. We call vertices with mark respectively below and at
least $A_{\ref{cor:initial-upper}}k^{\gamma}$ low-mark and high-mark vertices.
We call ${\mathcal{C}}_{k,j}^{\scriptscriptstyle(1)}[1,A_{\ref{cor:initial-
upper}}k^{\gamma})$ the local low-largest component of ${\mathcal{Q}}_{j}$. We
also define

${\mathcal{U}}_{j}:=\\{v\in{\mathcal{V}}_{k,j}[A_{\ref{cor:initial-
upper}}k^{\gamma},\infty):v\sim{\mathcal{C}}_{k,j}^{\scriptscriptstyle(1)}[1,A_{\ref{cor:initial-
upper}}k^{\gamma})\\}.$ (6.3)

We then define the local giant component of box ${\mathcal{Q}}_{j}$ as

$\mathrm{LG}_{j}:={\mathcal{U}}_{j}\cup{\mathcal{C}}_{k,j}^{\scriptscriptstyle(1)}[1,A_{\ref{cor:initial-
upper}}k^{\gamma}).$ (6.4)

In words, ${\mathcal{U}}_{j}$ is the set of high-mark vertices in
${\mathcal{Q}}_{j}$ that connect by at least one edge to the local low-largest
component in the same box. So, together they form the local giant component
$\mathrm{LG}_{j}$. We mention that ${\mathcal{U}}_{j}$ typically does not
contain all high-mark vertices.

######  Definition 6.3 (Revealment stages).

Consider a KSRG under the same setting as Proposition 6.1 such that
$\zeta_{\mathrm{hl}}>0$, with the boxing scheme from Definition 6.2.
Initially, we reveal the realization of vertex set ${\mathcal{V}}$, and none
of the edges. We define the following four edge-revealment stages:

  1. (1)

Reveal edges between pairs of vertices both in the same box
${\mathcal{Q}}_{j}$.

  2. (2)

Reveal edges between pairs of vertices both in $\cup_{j\leq
2^{d}(n/k)}\mathrm{LG}_{j}$.

  3. (3)

Reveal remaining edges between pairs of vertices both in
${\mathcal{V}}_{n}\setminus\big{(}\cup_{j\leq
2^{d}(n/k)}\mathrm{LG}_{j}\big{)}$

  4. (4)

Reveal all remaining edges.

We write _stage- $j$-${\mathcal{G}}_{n}$_ for the graph obtained after the
$j$th revealment stage for $j\in\\{1,2,3,4\\}$.

Thus, in stage _( 1)_ we reveal all ‘local’ edges between vertices inside the
same box. In stage _( 2)_, edges between local giants of different boxes. In
stage _( 3)_, we reveal edges with both endpoints outside local giants in
different boxes. Finally, in stage _( 4)_ we reveal all remaining edges: edges
in different boxes where one endpoint is in a local giant, and the other
endpoint is outside a local giant. The set $\mathrm{LG}_{j}$, (the local-low
largest component and high-mark vertices connecting to it in the same box) is
determined during stage _( 1)_. So stages _( 2–4)_ are well-defined. These
latter stages reveal edges between _different_ boxes.

######  Definition 6.4 (Stage _(1)_ and _(2)_ good events).

Let $\delta\in(0,1/(2^{d}A_{\ref{cor:initial-upper}}))$ be a small constant.
We call a box ${\mathcal{Q}}_{j}$ 1-good if it satisfies the event

${\mathcal{A}}_{\mathrm{1\textnormal{-}good}}({\mathcal{Q}}_{j}):=\\{{\mathcal{Q}}_{j}\
1\text{-good}\\}:=\big{\\{}|{\mathcal{C}}_{k,j}^{\scriptscriptstyle(1)}[1,A_{\ref{cor:initial-
upper}}k^{\gamma})|>\delta k\big{\\}}\cap\big{\\{}|{\mathcal{U}}_{j}|>\delta
k^{\zeta}\big{\\}}.$ (6.5)

For $j<2^{d}(n/k)$, we call $u\in{\mathcal{U}}_{j}$ box-wedging if
$u\sim\mathrm{LG}_{j+1}$. We say that stage-2-${\mathcal{G}}_{n}$ is $2$-good
if

$\\{\text{stage-2-${\mathcal{G}}_{n}$ 2-good}\\}:=\bigcap_{j\leq
2^{d}(n/k)}{\mathcal{A}}_{\mathrm{1\textnormal{-}good}}({\mathcal{Q}}_{j})\cap\bigcap_{j<2^{d}(n/k)}\big{\\{}\exists
u\in{\mathcal{U}}_{j}:u\sim\mathrm{LG}_{j+1}\big{)}\big{\\}}$ (6.6)

Whether ${\mathcal{Q}}_{j}$ is $1$-good is entirely determined by the revealed
edges in stage _(1)_ , and whether stage-$2$-${\mathcal{G}}_{n}$ is $2$-good,
is entirely determined by edges revealed by the end of stage _(2)_. The second
intersection in (6.6) means that there is at least one box-wedging vertex in
each local giant, implying that all local giants are part of the same
component in ${\mathcal{G}}_{n}$ that we will call the backbone.

######  Claim 6.5 (Stage _( 1)_ error bound).

Consider a KSRG under the same setting as Proposition 6.1 such that
$\zeta_{\mathrm{hl}}>0$. There exists a constant $\varepsilon>0$ such that for
all $k$ sufficiently large, for all $j\leq 2^{d}(n/k)$,

$\mathbb{P}\big{(}{\mathcal{Q}}_{j}\mbox{ is 1-good}\big{)}\geq
1-\exp(-\varepsilon k^{\zeta}).$

###### Proof.

We estimate the probabilities of the two events in (6.5). By Corollary 5.7,

$\mathbb{P}\big{(}{\mathcal{C}}_{k,j}[1,A_{\ref{cor:initial-
upper}}k^{\gamma})\leq\delta
k\big{)}\leq\exp\big{(}-2^{-d\zeta_{\mathrm{hh}}}k^{\zeta_{\mathrm{hh}}}/A_{\ref{cor:initial-
upper}}\big{)}.$ (6.7)

Next, consider $v\in{\mathcal{V}}_{n}[A_{\ref{cor:initial-
upper}}k^{\gamma},\infty)$ in box ${\mathcal{Q}}_{j}$. We use that each vertex
in ${\mathcal{C}}_{k,j}[1,A_{\ref{cor:initial-upper}}k^{\gamma})$ has mark at
least $1$, and that the distance between any two vertices in
${\mathcal{Q}}_{j}$ is at most $\sqrt{d}k^{1/d}$. Thus, by the connection
probability $\mathrm{p}$ in (4.6) (with $\alpha<\infty$), conditional on the
vertex set ${\mathcal{V}}_{n}$ and the subgraph
${\mathcal{C}}_{k,j}[1,A_{\ref{cor:initial-upper}}k^{\gamma})$ having size at
least $\delta k$,

$\displaystyle\mathbb{P}\big{(}v\nsim{\mathcal{C}}_{k,j}[1,A_{\ref{cor:initial-
upper}}k^{\gamma})\,\big{|}\,|{\mathcal{C}}_{k,j}[1,A_{\ref{cor:initial-
upper}}k^{\gamma})|$ $\displaystyle\geq\delta k,{\mathcal{V}}_{n}\big{)}$
$\displaystyle\leq\Big{(}1-p\Big{(}1\wedge\beta A_{\ref{cor:initial-
upper}}\frac{k^{\gamma}}{d^{d/2}k}\Big{)}^{\alpha}\Big{)}^{\delta k}.$

If the minimum is at $1$, then this probability is at most $e^{-p\delta k}$.
If the minimum is at the second expression, we substitute
$\gamma=(\alpha-1)/\alpha$. When we bound $1-x\leq e^{-x}$, the powers of $k$
cancel, and the right-hand side is at most

$\mathbb{P}\big{(}v\notin{\mathcal{U}}_{j}\mid|{\mathcal{C}}_{k,j}[1,A_{\ref{cor:initial-
upper}}k^{\gamma})|\geq\delta k,{\mathcal{V}}_{n}\big{)}\leq\exp(-p\beta
A_{\ref{cor:initial-upper}}^{\alpha}/d^{d/2}).$ (6.8)

In both cases, there is $\delta_{1}>0$ such that any such $v$ connects by an
edge to ${\mathcal{C}}_{k,1}^{\scriptscriptstyle(1)}[1,A_{\ref{cor:initial-
upper}}k^{\gamma})$ with probability at least $\delta_{1}$, independently of
all other vertices. Now, ${\mathcal{V}}_{k,j}\cap[A_{\ref{cor:initial-
upper}}k^{\gamma},\infty)$ is by (4.5) a PPP with intensity
$\mathrm{Leb}\times F_{W}(\mathrm{d}w)$. Therefore, the vertices in
${\mathcal{V}}_{k,1}\cap[A_{\ref{cor:initial-upper}}k^{\gamma},\infty)$ that
connect by an edge to
${\mathcal{C}}_{k,1}^{\scriptscriptstyle(1)}[1,A_{\ref{cor:initial-
upper}}k^{\gamma})$ dominate a Poisson random variable with mean

$\delta_{1}\cdot\mathrm{Vol}({\mathcal{Q}}_{j})(A_{\ref{cor:initial-
upper}}k^{\gamma})^{-(\tau-1)}=\delta_{1}2^{-d}A_{\ref{cor:initial-
upper}}^{-(\tau-1)}k^{1-\gamma(\tau-1)}=\Theta(k^{\zeta}).$

Thus, by Lemma A.1, there exists $\delta=\delta(A_{\ref{cor:initial-
upper}})>0$ small enough so that

$\displaystyle\mathbb{P}\big{(}|{\mathcal{U}}_{j}|\leq\delta
k\,\big{|}\,|{\mathcal{C}}_{k,j}[1,A_{\ref{cor:initial-
upper}}k^{\gamma})|\geq\delta k\big{)}\leq\exp(-\varepsilon k^{\zeta}).$

Combined with (6.7) and the definition of $\\{{\mathcal{Q}}_{1}\mbox{ is
$1$-good}\\}$ in Definition 6.4 this finishes the proof for $k$ sufficiently
large and $\delta,\varepsilon>0$ sufficiently small. ∎

######  Claim 6.6 (Stage _( 2)_ error bound).

Consider a KSRG under the same setting as Proposition 6.1 such that
$\zeta_{\mathrm{hl}}>0$. There exists a constant $\varepsilon>0$ such that for
all $k$ sufficiently large,

$\mathbb{P}\big{(}\mbox{stage-2-}{\mathcal{G}}_{n}\mbox{ is 2-good}\big{)}\geq
1-2^{d+1}(n/k)\exp(-\varepsilon k^{\zeta}).$

###### Proof.

By 6.5, each box ${\mathcal{Q}}_{i}$ is $1$-good with probability at least
$1-\exp(-\varepsilon k^{\zeta})$. Denote the first event in (6.6) that all
boxes ${\mathcal{Q}}_{j}$ are $1$-good by ${\mathcal{A}}_{\mathrm{sub}}$. By a
union bound,

$\mathbb{P}({\mathcal{A}}_{\mathrm{sub}})\geq 1-2^{d}(n/k)\exp(-\varepsilon
k^{\zeta}).$ (6.9)

We move on to estimating the probability of the second event in (6.6)
conditioned on ${\mathcal{A}}_{\mathrm{sub}}$. Fix some $j<2^{d}(n/k)$. Before
Stage  _( 2)_, none of the edges of ${\mathcal{U}}_{j}$ towards vertices in
${\mathcal{Q}}_{j+1}$ have been revealed yet. The maximal Euclidean distance
between two neighbouring boxes is $2\sqrt{d}k^{1/d}/2$, so we can bound the
probability that a single high-mark vertex is box-wedging using (4.6). When
${\mathcal{Q}}_{j+1}$ is $1$-good, by (6.5) there are at least $\delta n$
vertices of mark at least $1$ in $\mathrm{LG}_{j+1}$, so

$\mathbb{P}\big{(}u\in{\mathcal{U}}_{j}\text{ not box-wedging
}\big{|}\,{\mathcal{Q}}_{j+1}\mbox{
$1$-good},{\mathcal{V}}_{n}\big{)}\leq\Big{(}1-p\Big{(}1\wedge\frac{\beta
A_{\ref{cor:initial-
upper}}k^{\gamma}}{d^{d/2}k}\Big{)}^{\alpha}\Big{)}^{\delta k}.$ (6.10)

Then, we can use that there are at least $\delta k^{\zeta}$ candidate vertices
to be box-wedging in a $1$-good ${\mathcal{Q}}_{j}$, and that edges are
present independently given the vertex set ${\mathcal{V}}$. Thus,

$\displaystyle\mathbb{P}\big{(}\nexists u\in{\mathcal{U}}_{j}:u\text{ box-
wedging}\,\big{|}\,{\mathcal{Q}}_{j},{\mathcal{Q}}_{j+1}\mbox{
$1$-good},{\mathcal{V}}_{n}\big{)}$
$\displaystyle\leq\Big{(}1-p\Big{(}1\wedge\frac{\beta A_{\ref{cor:initial-
upper}}k^{\gamma}}{d^{d/2}k}\Big{)}^{\alpha}\Big{)}^{(\delta k)\cdot(\delta
k^{\zeta})}.$ (6.11)

If the minimum on the right-hand side is at $1$, this probability is at most
$\exp(-\varepsilon k^{1+\zeta})$. If the minimum is at the second expression,
using that $1-x\leq\exp(-x)$ and $\gamma=1-1/\alpha$, the powers of $k$
simplify since $(k^{\gamma}/k)^{\alpha}\cdot k=1$, so this probability is at
most $\exp(-\varepsilon k^{\zeta})$ for $\varepsilon>0$ small enough. So,
integrating over the realizations ${\mathcal{V}}_{n}$ and a union bound over
all $2^{d}(n/k)$ boxes, the probability that there is at least one box
${\mathcal{Q}}_{j}$ with no box-wedging vertices is at most
$2^{d}(n/k)\exp(-\varepsilon k^{\zeta})$. Combined with (6.6) and (6.9) the
claim follows. ∎

######  Claim 6.7 (Stage _( 3–4)_ error bound: second-largest component).

Consider a KSRG under the same setting as Proposition 6.1 such that
$\zeta_{\mathrm{hl}}>0$. There exists a constant $\varepsilon>0$ such that for
all $k$ sufficiently large and $n>k$

$\mathbb{P}\big{(}\\{|{\mathcal{C}}_{n}^{\scriptscriptstyle(2)}|>k\\}\cap\mbox{stage-2-}{\mathcal{G}}_{n}\mbox{
is 2-good}\big{)}\leq(n/k)\exp(-\varepsilon k^{\zeta}).$ (6.12)

###### Proof.

We condition on the full realization of the stage-$2$-${\mathcal{G}}_{n}$ that
is $2$-good. By (6.6), any such realization satisfies that all local giants
$(\mathrm{LG}_{j})_{j\leq 2^{d}(n/k)}$ have size at least $\delta k$ and they
are all connected by box-wedging vertices. This gives a component in
${\mathcal{G}}_{n}$ of size at least $\delta n$ that contains these local
giants. We call this component the backbone $\mathrm{BB}=\mathrm{BB}_{n,k}$.
In Stage  _( 3)_ we expose all edges with both endpoints outside the local
giants. If no component of size larger than $k$ except for the backbone
remains after Stage  _( 3)_, then we are done: In stage  _( 4)_ all remaining
edges to be revealed have one endpoint in local giants, hence in
$\mathrm{BB}$, and one outside.

We may interpret now (6.12) as follows: the second-largest component being
larger than $k$ means that there is at least one component above size $k$ that
is not $\mathrm{BB}$. If after Stage  _( 3)_ there is a component
${\mathcal{C}}\neq\mathrm{BB}$ above size $k$, then we aim to show that this
component merges with $\mathrm{BB}$ in Stage  _( 4)_ with probability at least
$1-\exp(-\varepsilon k^{\zeta})$. Since there are at most $(n/k)$ components
above size $k$ after Stage  _( 3)_, a union bound over all such components
will yield (6.12).

So, suppose that there exists a component ${\mathcal{C}}\neq\mathrm{BB}$ of
size larger than $k$ after Stage  _( 3)_ and fix a realization of
stage-$2$-${\mathcal{G}}_{n}$. After Stage  _( 3)_ we revealed already all
within-box edges, but we did not reveal edges between ${\mathcal{C}}$ and
local giants in neighbouring boxes ‘around’ vertices of ${\mathcal{C}}$. Since
the number of boxes is at least $2^{d}(n/k)$ by Definition 6.2, a subbox
always has a neighbouring box. Let $j(v)$ denote index of the box that vertex
$v\in{\mathcal{C}}$ belongs to, which is a.s. unique. Since all boxes are
$1$-good, by (6.5), for each $v\in{\mathcal{C}}$, there are at least $\delta
k^{\zeta}$ high-mark vertices at distance at most $\sqrt{d}k^{1/d}$ from $v$
in the vertex set ${\mathcal{U}}_{j(v)+1}\subseteq\mathrm{LG}_{j(v)+1}$ in the
neighbour ing boxes ${\mathcal{Q}}_{j(v)-1}$ and ${\mathcal{Q}}_{j(v)+1}$.
Each vertex of $v$ has mark at least $1$. Hence, for a given component
${\mathcal{C}}$, by the same calculations as in the proof of 6.6 around
(6.10)–(6.11),

$\displaystyle\mathbb{P}\big{(}{\mathcal{C}}$
$\displaystyle\nsim\mathrm{BB}\,\big{|}\,\mbox{2-good-}{\mathcal{G}}_{n},,{\mathcal{V}}_{n},\mbox{stage-3-}{\mathcal{G}}_{n}\big{)}\leq\Big{(}1-p\Big{(}1\wedge\beta
A_{\ref{cor:initial-
upper}}\frac{k^{\gamma}}{d^{d/2}k}\Big{)}^{\alpha}\Big{)}^{k\cdot(\delta
k^{\zeta})}\leq\exp\big{(}-\varepsilon k^{\zeta}\big{)}.$

for $\varepsilon>0$ sufficiently small. Here we used that $\gamma=1-1/\alpha$
and thus some powers of $k$ cancel. By a union bound over all at most
$|{\mathcal{V}}_{n}|/k$ components of size at least $k$,

$\displaystyle\mathbb{P}\big{(}\\{|{\mathcal{C}}_{n}^{\scriptscriptstyle(2)}|>k\\}\cap\\{\mbox{stage-2-}{\mathcal{G}}_{n}\mbox{
is 2-good}\\}\big{)}$
$\displaystyle\leq\mathbb{E}\big{[}\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(2)}|\geq
k\,\big{|}\,\mbox{2-good-}{\mathcal{G}}_{n},{\mathcal{V}}_{n},\mbox{stage-3-}{\mathcal{G}}_{n}\big{)}\big{]}$
$\displaystyle\leq\mathbb{E}\big{[}|{\mathcal{V}}_{n}|/k]\exp\big{(}-\varepsilon
k^{\zeta}\big{)}\leq(n/k)\exp\big{(}-\varepsilon k^{\zeta}\big{)}.$

This finishes the proof of (6.12). ∎

We are ready to prove Proposition 6.1 that bounds
$\mathbb{P}(|{\mathcal{C}}_{n}^{\scriptscriptstyle(2)}|\geq k)$.

###### Proof of Proposition 6.1 when $\zeta_{\mathrm{hl}}>0$.

By the law of total probability,

$\mathbb{P}(|{\mathcal{C}}_{n}^{\scriptscriptstyle(2)}|\geq
k)\leq\mathbb{P}\big{(}\\{|{\mathcal{C}}_{n}^{\scriptscriptstyle(2)}|\geq
k\\}\cap\mbox{stage-2-}{\mathcal{G}}_{n}\mbox{ is
2-good}\big{)}+\mathbb{P}\big{(}\mbox{stage-2-}{\mathcal{G}}_{n}\mbox{ is
\emph{not} 2-good}\big{)}.$

Proposition 6.1 follows from Claims 6.6–6.7. ∎

We now give a sketch on how to modify the above proof when
$\zeta_{\mathrm{ll}}>0$.

###### Proof of Proposition 6.1 when $\zeta_{\mathrm{ll}}>0$.

The proofs are identical for KSRGs on PPPs and on ${\mathbb{Z}}^{d}$. We
follow the $\zeta_{\mathrm{hl}}$-computations. By Corollary 5.7,

$\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}\big{[}1,A_{\ref{cor:initial-
upper}})|\leq\tfrac{1}{A_{\ref{cor:initial-
upper}}}n\big{)}\leq\exp\big{(}-\tfrac{1}{A_{\ref{cor:initial-
upper}}}n^{\zeta_{\mathrm{ll}}}\big{)}.$ (6.13)

We set
$\mathrm{LG}_{j}:={\mathcal{C}}_{n}^{\scriptscriptstyle(1)}\big{[}1,A_{\ref{cor:initial-
upper}})$ to be the local giant of box ${\mathcal{Q}}_{j}$. We ignore high-
mark vertices here. The revealment scheme in Definition 6.3 is then well-
defined with this $\mathrm{LG}_{j}$. We modify the box being $1$-good in (6.5)
by only requesting the first event
$|\mathrm{LG}_{j}|=|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}\big{[}1,A_{\ref{cor:initial-
upper}})|\geq\delta k$ there. We define $u\in\mathrm{LG}_{j}$ to be box-
wedging if $u\sim\mathrm{LG}_{j+1}$. In the definition of the stage
$2$-${\mathcal{G}}_{n}$ being $2$-good in (6.6), we then require at least one
box-wedging vertex in each box:

$\bigcap_{j<2^{d}(n/k)}\\{\exists
u\in\mathrm{LG}_{j}:u\sim\mathrm{LG}_{j+1}\\}.$

6.5 follows then from Corollary 5.7 as before. We describe how to prove the
equivalent of 6.6 for this regime. Estimating that all boxes are $1$-good goes
as before in (6.9). For the second part, estimating that each box has a box-
wedging vertex, we use only the fact that vertices have weight at least $1$.
We get

$\displaystyle\mathbb{P}\big{(}\nexists
u\in\mathrm{LG}_{j}:u\sim\mathrm{LG}_{j+1}\,$
$\displaystyle\big{|}\,{\mathcal{Q}}_{j},{\mathcal{Q}}_{j+1}\mbox{ are
$1$-good}\big{)}\leq\Big{(}1-p\Big{(}1\wedge\beta\frac{1}{d^{d/2}k}\Big{)}^{\alpha}\Big{)}^{(\delta
k)^{2}}.$

If the first term is the minimum, this probability is at most
$\exp(-\varepsilon k^{2})\leq\exp(-\varepsilon k^{2-\alpha})=\exp(-\varepsilon
k^{\zeta_{\mathrm{ll}}})$ for $\varepsilon>0$ sufficiently small. If the
second term is the minimum, this probability is also at most
$\exp(-\varepsilon k^{2-\alpha})=\exp(-\varepsilon k^{\zeta_{\mathrm{ll}}})$.
The rest of the claim is as for the hl-regime. For 6.7, we use again that each
local giant contains at least $\delta k$ vertices of mark at least $1$. Thus,

$\mathbb{P}\big{(}{\mathcal{C}}\nsim\mathrm{BB}\,\big{|}\,\mbox{2-good-${\mathcal{G}}_{n}$},{\mathcal{V}}_{n}\big{)}\leq\Big{(}1-p\Big{(}1\wedge\beta\frac{1}{d^{d/2}k}\Big{)}^{\alpha}\Big{)}^{(\delta
k)\cdot k}.$

As before, the right-hand side is at most $\exp(-\varepsilon
k^{2-\alpha})=\exp(-\varepsilon k^{\zeta_{\mathrm{ll}}})$. The proof of the
claim is finished as before. ∎

We move towards the proofs of Theorem 2.10. We recall a proposition from our
recent paper to prove the lower bounds. To make notation lighter, we state it
only for the case that $\zeta_{\mathrm{long}}>0$. We recall from (2.16) that
$\max({\mathcal{Z}})$ is the maximum and $\mathfrak{m}_{{\mathcal{Z}}}$ is the
multiplicity of the maximum in the set
${\mathcal{Z}}=\\{\zeta_{\mathrm{short}},\zeta_{\mathrm{ll}},\zeta_{\mathrm{hl}},\zeta_{\mathrm{hh}}\\}$.
We write here ${\mathcal{C}}_{n}(0)[1,A)$ for the component of a vertex with
unknown weight at $0\in{\mathbb{R}}^{d}$ inside the vertex set on
$\Lambda_{n}\times[1,A)$, with the idea that if $w_{0}>A$ then
${\mathcal{C}}_{n}(0)[1,A):=\emptyset$.

######  Proposition 6.8 (Lower bound prerequisite [48, Prop. 7.1]).

Consider a supercritical KSRG on a PPP or on ${\mathbb{Z}}^{d}$ satisfying
Assumption 2.2 with $\zeta_{\mathrm{long}}>0$. Assume that there exist
constants $\eta^{\prime},\rho>0$ such that for all $n$ sufficiently large,

$\displaystyle\mathbb{P}^{\scriptscriptstyle
0}\big{(}\big{|}{\mathcal{C}}_{n}(0)\big{[}1,(\log
n)^{\eta^{\prime}}\big{)}\big{|}\geq\rho n\big{)}\geq\rho.$ (6.14)

Then there exists $A>0$ such that for all $n\in[Ak,\infty]$,

$\mathbb{P}^{\scriptscriptstyle
0}\big{(}|{\mathcal{C}}_{n}(0)|>k,0\notin{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}\big{)}\geq\exp\big{(}-Ak^{\max({\mathcal{Z}})}(\log
k)^{\mathfrak{m}_{\mathcal{Z}}-1}\big{)}.$ (6.15)

Moreover, there exist $\delta,\varepsilon>0$, such that for all $n$
sufficiently large,

$\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(2)}|>\big{(}(\varepsilon\log
n)/(\log\log
n)^{\mathfrak{m}_{\mathcal{Z}}-1}\big{)}^{1/\max({\mathcal{Z}})}\big{)}\geq
1-n^{-\delta}.$ (6.16)

The next claim verifies the requirement (6.14) for applying Proposition 6.8.

######  Claim 6.9 (The prerequisite holds).

Consider a KSRG under the same setting as Theorem 2.10 and Theorem 2.9. There
exist constants $\eta^{\prime},\rho>0$ such that

$\mathbb{P}^{\scriptscriptstyle 0}\big{(}|{\mathcal{C}}_{n}(0)[1,(\log
n)^{\eta^{\prime}}|\geq\rho n\big{)}\geq\rho.$ (6.17)

###### Proof.

We prove the bound (6.17) for KSRGs on a Poisson point process and leave it to
the reader to adapt it to long-range percolation. We rely on Corollary 5.8.
Fix
$(\zeta,\gamma)\in\\{(\zeta_{\mathrm{hl}},\gamma_{\mathrm{hl}}),(\zeta_{\mathrm{ll}},\gamma_{\mathrm{ll}})\\}$
such that $\zeta>0$. Let $A,\varepsilon>0$ be so that (5.38) holds with $C=2$.
For any $u\in{\mathcal{V}}_{n}$, let $\widetilde{\mathcal{C}}_{n}(u)$ be the
component of $u$ in the induced graph in $\Lambda_{n}\times[1,(A\log
n)^{\gamma/\zeta})$; and let $\widetilde{\mathcal{C}}_{2^{d}n,u}(u)$ be the
connected component of $u$ in $\Lambda_{2^{d}n}(u)\times[1,(A\log
n)^{\gamma/\zeta})$. Since $\Lambda_{n}\subseteq\Lambda_{2^{d}n}(u)$, clearly
$\widetilde{\mathcal{C}}_{n}(u)\subseteq\widetilde{\mathcal{C}}_{2^{d}n,u}(u)$.
If the giant of $\Lambda_{n}\times[1,(A\log n)^{\gamma/\zeta})$ has size at
least $\varepsilon n$, then there are at least $\varepsilon n$ vertices in a
component of size at least $\varepsilon n$ in $\Lambda_{n}\times[1,(A\log
n)^{\gamma/\zeta})$. This happens with probability at least $1-n^{-2}$ by
(5.38). So,

$(1-n^{-2})\varepsilon
n\leq\mathbb{E}\bigg{[}\sum_{u\in{\mathcal{V}}_{n}}\mathds{1}_{\\{|\widetilde{\mathcal{C}}_{n}(u)|\geq\varepsilon
n\\}}\bigg{]}\leq\mathbb{E}\bigg{[}\sum_{u\in{\mathcal{V}}_{n}}\mathds{1}_{\\{|\widetilde{\mathcal{C}}_{2^{d}n,u}(u)|\geq\varepsilon
n\\}}\bigg{]}.$ (6.18)

We now show that

$\mathbb{E}\bigg{[}\sum_{u\in{\mathcal{V}}_{n}}\mathds{1}_{\\{\widetilde{\mathcal{C}}_{2^{d}n,u}(u)|\geq\varepsilon
n\\}}\bigg{]}=n\mathbb{P}^{\scriptscriptstyle
0}\big{(}{\mathcal{C}}_{2^{d}n}(0)[1,(A\log n)^{\gamma/\zeta})|\geq\varepsilon
n\big{)}.$ (6.19)

For this, we use an alternative KSRG construction. Consider the collection
$\bm{U}=(U_{ij})_{j>i\geq 1}$ of independent $\mathrm{Unif}[0,1]$ random
variables, independent of the PPP ${\mathcal{V}}_{n}$. We can use $\bm{U}$ to
encode the presence of edges: given the PPP ${\mathcal{V}}$, order the points
with respect to their distance to the origin, and include an edge between the
$i$th and $j$th vertex $u_{i}$ and $u_{j}$ if
$U_{ij}\leq\mathrm{p}(u_{i},u_{j})$. The function
$\mathds{1}_{\\{|\widetilde{\mathcal{C}}_{2^{d}n,u}|\geq\varepsilon n\\}}$ is
determined by the realization of the PPP ${\mathcal{V}}_{n}$ and $\bm{U}$
(i.e., it is measurable w.r.t. the sigma-algebras generated by these
processes/collections). By Mecke’s formula and Fubini’s theorem,

$\displaystyle\mathbb{E}\bigg{[}\sum_{u\in{\mathcal{V}}_{n}}\mathds{1}_{\\{\widetilde{\mathcal{C}}_{2^{d}n,u}(u)|\geq\varepsilon
n\\}}\bigg{]}$
$\displaystyle=\mathbb{E}\bigg{[}\mathbb{E}\bigg{[}\sum_{u\in{\mathcal{V}}_{n}}\mathds{1}_{\\{\widetilde{\mathcal{C}}_{2^{d}n,u}(u)|\geq\varepsilon
n\\}}\mid\bm{U}\bigg{]}\bigg{]}$
$\displaystyle=\mathbb{E}\bigg{[}\int_{x\in\Lambda_{n}}\mathbb{P}^{\scriptscriptstyle
x}\big{(}\widetilde{\mathcal{C}}_{2^{d}n,u}(u)|\geq\varepsilon
n\mid\bm{U},x_{u}=x\big{)}\mathrm{d}x\bigg{]}$
$\displaystyle=\int_{x\in\Lambda_{n}}\mathbb{P}^{\scriptscriptstyle
x}\big{(}\widetilde{\mathcal{C}}_{2^{d}n,u}(u)|\geq\varepsilon n\mid
x_{u}=x\big{)}\mathrm{d}x.$

The box $\Lambda_{2^{d}n}(u)$ is centered at $u$. So, by translation
invariance, the integrand is constant and equal to
$\mathbb{P}^{\scriptscriptstyle
0}\big{(}\widetilde{\mathcal{C}}_{2^{d}n}(0)|\geq\varepsilon n\big{)}$. Since
$\widetilde{\mathcal{C}}_{2^{d}n}(0)={\mathcal{C}}_{2^{d}n}(0)[1,(A\log
n)^{\gamma/\zeta})$ by definition above (6.18), this proves (6.19). Combined
with (6.18), this proves (6.17) for any $\eta^{\prime}>\gamma/\zeta$,
$\rho=2^{-d}\varepsilon$, and any $n$ sufficiently large. The statement is
trivial for smaller $n$ by decreasing $\rho$, finishing the proof. ∎

We are ready to prove Theorem 2.10 on the second-largest component.

###### Proof of Theorem 2.10.

We give the proof for KSRGs on PPPs only: the proof for long-range percolation
${\mathbb{Z}}^{d}$ is identical to the proof of the
$\zeta_{\mathrm{ll}}$-regime for KSRGs. Assume $\zeta_{\mathrm{hl}}$ or
$\zeta_{\mathrm{ll}}$ is strictly positive and maximal in
${\mathcal{Z}}=\\{\zeta_{\mathrm{short}},\zeta_{\mathrm{ll}},\zeta_{\mathrm{hl}},\zeta_{\mathrm{hh}}\\}$.
The lower bound holds by Proposition 6.8, since its prerequisite (6.14) is
satisfied by 6.9. The upper bound follows from Proposition 6.1, substituting
$k=k_{n}=(A\log n)^{1/\max(\zeta_{\mathrm{hl}},\zeta_{\mathrm{ll}})}$ for a
large constant $A=A(\delta)>0$. ∎

###  6.2. Cluster-size decay and law of large numbers

We proceed to the proof of Theorem 2.9 on the cluster-size decay. The upper
bound (6.1) is the main prerequisite (6.20) of the following general
proposition. We proved this proposition for KSRGs in general in [48]. We
recall that $\mathbb{P}^{\scriptscriptstyle x}$ is the Palm measure of the PPP
with a vertex at $x$.

######  Proposition 6.10 (Prerequisites for cluster-size decay [48,
Proposition 6.1]).

Consider a supercritical KSRG on a PPP or on ${\mathbb{Z}}^{d}$ satisfying
Assumption 2.2. Assume that there exist $\zeta$, $\eta^{\prime}$, $c$,
$c^{\prime}$, $M_{c}>0$, and a function $n_{0}(k)=O(k^{1+c^{\prime}})$ such
that for all $k$ sufficiently large and whenever $n\in[n_{0}(k),\infty)$, with
$\overline{w}(n,c):=M_{c}(\log n)^{\eta^{\prime}}$ it holds for all
$x\in\Lambda_{n}$,

$\displaystyle\mathbb{P}^{\scriptscriptstyle
x}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(2)}|>k\big{)}$
$\displaystyle\leq n^{c^{\prime}}\exp\big{(}-ck^{\zeta}\big{)},$ (6.20)
$\displaystyle\mathbb{P}^{\scriptscriptstyle
x}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|<n^{c}\big{)}$
$\displaystyle\leq n^{-1-c},$ (6.21)
$\displaystyle\mathbb{P}^{\scriptscriptstyle x}\big{(}\exists
v\in{\mathcal{V}}_{n}[\overline{w}(n,c),\infty):v\notin{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}\big{)}$
$\displaystyle\leq n^{-c}.$ (6.22)

Then there exists a constant $A>0$ such that for all $k$ sufficiently large
and $n\in[n_{0}(k),\infty]$,

$\mathbb{P}^{\scriptscriptstyle
0}\big{(}|{\mathcal{C}}_{n}(0)|>k,0\notin{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}\big{)}\leq\exp\big{(}-\tfrac{1}{A}k^{\zeta}\big{)},$
(6.23)

and

$\frac{|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|}{n}\overset{\mathbb{P}}{\longrightarrow}\theta(\beta,p,\alpha,\tau,\sigma),\qquad\mbox{as
}n\to\infty.$ (6.24)

In our current setting, (6.1) in Proposition 6.1 proves the first prerequisite
and Corollary 5.8 proves the second, and implies the third prerequisite. We
spell out the details. This is similar to [48, Proposition 5.12].

######  Claim 6.11.

Consider a supercritical KSRG on a PPP satisfying Assumption 2.2 or consider
supercritical long-range percolation on ${\mathbb{Z}}^{d}$. Assume
$\zeta_{\mathrm{type}}=\max(\zeta_{\mathrm{ll}},\zeta_{\mathrm{hl}})>0$ for
some $\mathrm{type}\in\\{\mathrm{ll},\mathrm{hl}\\}$. For each constant $C>0$,
there exists a constant $A>0$ such that all $n$ sufficiently large,

$\mathbb{P}\big{(}\exists v\in{\mathcal{V}}_{n}[(A\log
n)^{\eta_{\mathrm{type}}/\zeta_{\mathrm{type}}},\infty):v\notin{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}\big{)}\leq
n^{-C}.$

The statement remains true for the Palm-version
$\mathbb{P}^{\scriptscriptstyle x}$ for any $x\in{\mathbb{R}}^{d}$.

###### Proof.

We omit the subscript $\mathrm{type}$ in the following proof for
$\mathrm{type}\in\\{\mathrm{ll},\mathrm{hl}\\}$. Let $A=A(C)>0$ be
sufficiently large. Using the upper bound on
$|{\mathcal{C}}_{n}^{\scriptscriptstyle(2)}|$ in Proposition 6.1, and the
lower bound on $|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|$ from Corollary
5.8, we obtain

$\displaystyle\mathbb{P}^{\scriptscriptstyle
x}\big{(}\\{|{\mathcal{C}}_{n}^{\scriptscriptstyle(2)}|\leq(A\log
n)^{1/\zeta}\\}\cap\\{|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|\geq(1/A)n\\}\big{)}\geq
1-o(n^{-C}).$ (6.25)

Hence,

$\displaystyle\mathbb{P}^{\scriptscriptstyle x}\big{(}\exists
v\in{\mathcal{V}}_{n}[(A\log
n)^{\eta/\zeta},\infty):v\notin{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}\big{)}\leq\mathbb{P}^{\scriptscriptstyle
x}\left(\begin{aligned} &\\{\exists v\in{\mathcal{V}}_{n}[(A\log
n)^{\eta/\zeta},\infty):v\notin{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}\\}\\\
&\cap\\{|{\mathcal{C}}_{n}^{\scriptscriptstyle(2)}|\leq(A\log
n)^{1/\zeta}\\}\\\
&\cap\\{|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|\geq\tfrac{1}{A}n\\}\end{aligned}\right)+o(n^{-C}).$

On the intersection of the three events on the right-hand side, there is no
linear-sized component in ${\mathcal{G}}_{n}$ that contains all vertices with
mark above $(A\log n)^{\eta/\zeta}$, which is exactly the negation of the
event in (5.39). This has probability at most $o(n^{-C})$ by (5.39) in
Corollary 5.8, finishing the proof. ∎

Propositions 6.8 and 6.10 give the respective lower and upper bounds for
Theorem 2.9.

###### Proof of Theorem 2.9.

We prove Theorem 2.9 when
$\max(\zeta_{\mathrm{hl}},\zeta_{\mathrm{ll}})>\max(\zeta_{\mathrm{hh}},0)$.
The lower bound follows from (6.15) in Proposition 6.8, since the prerequisite
(6.14) is satisfied by 6.9. For the upper bound we verify the three
prerequisites needed in Proposition 6.10. Prerequisite (6.20) about the
second-largest component is proven in Proposition 6.1; prerequisite (6.21)
requiring that the largest component is at least polynomial in size follows
from Corollary 5.8; prerequisite (6.22) is proven in 6.11. The upper bound in
Theorem 2.9 then follows from (6.23). ∎

###  6.3. Lower tail of Large Deviations

We are ready to combine everything and give the proof of the lower tail of
large deviations for the giant in (2.21). We cite the lower bound from [48].
We write
${\mathcal{Z}}=\\{\zeta_{\mathrm{hh}},\zeta_{\mathrm{hl}},\zeta_{\mathrm{ll}},\zeta_{\mathrm{short}}\\}$,
with maximum value $\zeta_{\star}$, and $\mathfrak{m}_{{\mathcal{Z}}}$ the
multiplicity of the maximum, see (2.16).

######  Theorem 6.12 (Lower bound for the lower tail [48, Theorem 2.7]).

Consider a supercritical KSRG on a PPP satisfying Assumption 2.2 or consider
supercritical long-range percolation on ${\mathbb{Z}}^{d}$. There exists a
constant $A>0$ such that for all $\rho>0$, and $n$ sufficiently large,

$\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|<\rho
n\big{)}\geq\exp\big{(}-\tfrac{1}{A\rho}n^{\zeta_{\star}}(\log
n)^{\mathfrak{m}_{\mathcal{Z}}-1}\big{)}.$

###### Proof of Theorem 2.7.

The lower bound follows from Theorem 6.12, since the above theorem is valid
for all $\rho>0$ (but is far from being sharp when $\rho\geq\theta$). When
$\max(\zeta_{\mathrm{hl}},\zeta_{\mathrm{ll}})>0$ we argue as follows for the
upper bound: since we verified the three prerequisites needed in Proposition
6.10 already in the proof of Theorem 2.9 above, the second conclusion of
Proposition 6.10 gives that

$|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|\big{/}n\overset{\mathbb{P}}{\longrightarrow}\theta.$

Hence, we may choose any $\widetilde{\rho}\in(\rho,\theta)$, and it follows
that $\\{|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|\geq\widetilde{\rho}n\\}$
whp. All highest-mark vertices are in the giant whp by 6.11. This proves the
requirement (5.3) in Proposition 5.1, i.e.,
$\mathbb{P}(A_{\mathrm{giant}}^{\mathrm{type}}(\widetilde{\rho}))\to 1$ holds.
Applying Proposition 5.1 for $\varepsilon>0$ such that
$\rho=(1-\varepsilon)\widetilde{\rho}$ proves the upper bound when
$\max(\zeta_{\mathrm{hl}},\zeta_{\mathrm{ll}})>0$.

When $\zeta_{\mathrm{hh}}>0$, $|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|$
contains all vertices of mark above some polylog of $n$ by [48, Proposition
5.12], and an LLN for $|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|$ also
holds, see [48, Corollary 2.3]. So, the same reasoning as above can be applied
also when $\zeta_{\mathrm{hh}}>0$. Since
$\zeta_{\mathrm{long}}=\max(\zeta_{\mathrm{hl}},\zeta_{\mathrm{hh}},\zeta_{\mathrm{ll}})$
by 2.3, this concludes the proof of Theorem 2.7. ∎

##  7\. Upper tail of large deviations

In this section we deal with the upper tail, that is, with the event of the
giant being too large, and prove Theorem 2.4 and Theorem 2.5 following the
roadmap outlined in Section 3.1. We first show a Law of Large Numbers (LLN)
for components of size $\ell$ that applies to both homogeneous models, i.e.,
$\tau=\infty$, and degree-inhomogeneous models, i.e., $\tau<\infty$.
Afterwards, we obtain bounds on the convergence rate of this LLN. We prove
that the concentration is exponentially fast when $\tau=\infty$, and show that
Theorem 2.4 follows. Then we analyse the effect of the presence of high-mark
vertices (when $\tau<\infty$) to prove Theorem 2.5.

###  7.1. Concentration of size-$\ell$ components

We introduce notation for the probability of the component of the origin being
of size $\ell$, and for the total number of size-$\ell$ components in the
graph induced by vertices with mark at most $\overline{w}_{n}$:

$\theta_{\ell}:=\mathbb{P}^{\scriptscriptstyle
0}\big{(}|{\mathcal{C}}(0)|=\ell\big{)},\quad
S_{n,\ell}(\overline{w}_{n}):=\big{|}\\{\text{comp. }{\mathcal{C}}\text{ in
}{\mathcal{G}}_{n}[1,\overline{w}_{n}):|{\mathcal{C}}|=\ell\\}\big{|},\quad
S_{n,\ell}:=S_{n,\ell}(\infty).$ (7.1)

Clearly $\sum_{1\leq\ell<\infty}\theta_{\ell}=\mathbb{P}^{\scriptscriptstyle
0}(|{\mathcal{C}}(0)|<\infty)=1-\theta$. In models with all marks equal $1$
(e.g. long-range percolation) it holds
$S_{\ell,n}(\overline{w}_{n})=S_{\ell,n}$ for any $\overline{w}_{n}>1$.

######  Lemma 7.1 (LLN for size-$\ell$ components).

Consider a KSRG on a PPP or on ${\mathbb{Z}}^{d}$ satisfying Assumption 2.2.
Let $\underline{w}_{n}=\omega(n^{1/(\tau-1)})$ be a sequence. Then, for every
fixed $\ell\in{\mathbb{N}}$,

$\frac{\ell
S_{n,\ell}(\underline{w}_{n})}{n}\overset{\mathbb{P}}{\longrightarrow}\theta_{\ell},\qquad\text{as
}n\to\infty.$ (7.2)

###### Proof.

We give the proof for KSRGs on a PPP with $\tau<\infty$, i.e., non-constant
marks. The proof is analogous when $\tau=\infty$ or when vertex locations are
given by ${\mathbb{Z}}^{d}$. By the intensity of ${\mathcal{V}}_{n}$ in (4.5),
$\Lambda_{n}$ contains no vertices of mark at least $\underline{w}_{n}$ whp.
If such vertices are absent, then
$S_{n,\ell}(\underline{w}_{n})=S_{n,\ell}(\infty)$. Therefore, for any
$\psi>0$,

$\displaystyle\mathbb{P}\big{(}|\ell
S_{n,\ell}(\underline{w}_{n})/n-\theta_{\ell}|>\psi\big{)}$
$\displaystyle\leq\mathbb{P}\big{(}\\{|\ell
S_{n,\ell}(\infty)/n-\theta_{\ell}|>\psi\\}\cap{\mathcal{V}}_{n}[\underline{w}_{n},\infty)=\emptyset\big{)}$
$\displaystyle\hskip
15.0pt+\mathbb{P}\big{(}{\mathcal{V}}_{n}[\underline{w}_{n},\infty)\neq\emptyset\big{)}$
$\displaystyle\leq\mathbb{P}\big{(}|\ell
S_{n,\ell}(\infty)/n-\theta_{\ell}|>\psi\big{)}+o(1).$ (7.3)

We use local convergence to show that the probability on the right-hand side
vanishes. We refer to [72] for an elaborate discussion on local convergence
and give a short definition.

A rooted graph is a couple $(G,o)$ of a graph $G$ and some, possibly random,
distinguished vertex $o$ of $G$, which we call the root of $G$. A finite
rooted graph $(G,o)$ is said to be uniformly rooted, if $o$ is chosen
uniformly at random among the vertices of $G$. Let ${\mathcal{G}}_{\star}$ be
the space of all rooted locally finite graphs. Let $B_{G}(v,r)$ denote the
induced subgraph of $G$ on all vertices that are at graph distance at most $r$
from a vertex $v$. For $(G_{1},o_{1}),(G_{2},o_{2})\in{\mathcal{G}}_{\star}$,
we define $R(G_{1},G_{2})$ to be the largest value $r\in{\mathbb{N}}$ such
that $B_{G_{1}}(o_{1},r)$ is isomorphic to $B_{G_{2}}(o_{2},r)$: there exists
a bijection $\phi:V(B_{G_{1}}(o_{2},r))\mapsto V(B_{G_{2}}(o_{2},r)$ such that
$\phi(o_{1})=o_{2}$ and $\\{u,v\\}$ is an edge in $B_{G_{1}}(o_{1},r)$ if and
only if $\\{\phi(u),\phi(v)\\}$ is an edge in $B_{G_{2}}(o_{1},r)$. We set
$d((G_{1},o_{1}),(G_{2},o_{2})):=1/(1+R(G_{1},o_{1}),(G_{2},o_{2})))$ for the
distance between two rooted graphs. A sequence of uniformly rooted graphs
$(G_{n},o_{n})_{n\geq 1}$ converges locally in probability towards
$(G_{\infty},o)$ having law $\mu$, if for every bounded and continuous
function $h:{\mathcal{G}}_{\star}\mapsto{\mathbb{R}}$,

$\mathbb{E}\big{[}h(G_{n},o_{n})\mid
G_{n}\big{]}\overset{\mathbb{P}}{\longrightarrow}\mathbb{E}_{\mu}[h(G_{\infty},o)],\qquad\text{as
}n\to\infty,$ (7.4)

where the expectation on the left-hand side is only with respect to the
uniform root. (The limit object $(G_{\infty},o)$ may be random and infinite,
we here omit this discussion).

Considering KSRGs in Definition 2.1, the sequence $({\mathcal{G}}_{n})_{n\geq
1}$ of finite KSRGs converges locally in probability to the infinite graph
${\mathcal{G}}_{\infty}$ conditioned to contain a vertex at the origin, the
root, see [73]. We let
$h(G_{n},o_{n})=\mathds{1}_{\\{|{\mathcal{C}}(o_{n})|=\ell\\}}$ be the
indicator that the component of $o_{n}$ has size $\ell$. Then, $h$ is bounded,
and continuous on the Polish space $({\mathcal{G}}_{\star},d)$: it only
depends on the induced subgraph up to distance $\ell+1$ from the root, so
$h(G_{1},o_{1})=h(G_{2},o_{2})$ for any two rooted graphs
$(G_{1},o_{1}),(G_{2},o_{2})$ within distance at most $1/(\ell+2)$. So (7.4)
applies and the right-hand side there equals $\mathbb{P}^{\scriptscriptstyle
0}(|{\mathcal{C}}(0)|=\ell)=\theta_{\ell}$. Instead of explicitly writing out
the left-hand side, we first notice that
$\sum_{o_{n}\in{\mathcal{V}}_{n}}h(G_{n},o_{n})=\ell S_{n,\ell}(\infty)$.
Therefore,

$\frac{\ell
S_{n,\ell}(\infty)}{n}=\frac{|{\mathcal{V}}_{n}|}{n}\frac{1}{|{\mathcal{V}}_{n}|}\sum_{o_{n}\in{\mathcal{V}}_{n}}h(G_{n},o_{n})=\frac{|{\mathcal{V}}_{n}|}{n}\cdot\mathbb{E}[h(G_{n},o_{n})\mid
G_{n}]\overset{\mathbb{P}}{\longrightarrow}1\cdot\theta_{\ell},$ (7.5)

where we used that the ratio $|{\mathcal{V}}_{n}|/n$ tends to one in
probability. Hence, the probability on the right-hand side in (7.3) tends to
zero as $n$ tends to infinity. This finishes the proof for PPP vertex sets.
When the locations are given by ${\mathbb{Z}}^{d}$, or $\tau=\infty$, the
result follows analogously. ∎

###  7.2. Homogeneous models

We prove a bound on the convergence rate in Lemma 7.1 using a boxing argument.

######  Lemma 7.2 (Concentration for size-$\ell$ components).

Consider long-range percolation with $\alpha>1$ or Bernoulli bond percolation
on ${\mathbb{Z}}^{d}$. For all fixed $\ell\in{\mathbb{N}}$ and $\psi>0$, there
exists a constant $\varepsilon_{\ell,\psi}>0$ such that for all $n\geq 1$,

$\mathbb{P}\Big{(}\big{|}S_{n,\ell}(\infty)/(n\theta_{\ell}/\ell)-1\big{|}\leq\psi\Big{)}\geq
1-\exp\big{(}-\varepsilon_{\ell,\psi}n\big{)}.$ (7.6)

###### Proof.

Let $k$ be a large constant, and w.l.o.g. assume that $\Lambda_{n}$ can be
partitioned into $(n/k)$ volume-$k$ subboxes. Let
$S_{k,\ell}^{\scriptscriptstyle(j)}$ denote the number of size-$\ell$
components in the induced subgraph inside the $j$th box. Then, by Lemma 7.1,
for a small constant $\psi_{1}>0$, independently across boxes it holds that

$\mathbb{P}({\mathcal{A}}_{\ell}(j,k)):=\mathbb{P}\Big{(}|S_{k,\ell}^{\scriptscriptstyle(j)}/(k\theta_{\ell}/\ell)-1|\leq\psi_{1}\Big{)}\geq
1-\psi_{1}/2.$

The number of boxes for which this event holds dominates a binomial random
variable with parameters $n/k$ and $1-\psi_{1}/2$. So if we set

${\mathcal{A}}_{\mathrm{sub}}(k):=\bigg{\\{}\Big{|}\sum_{j\in[n/k]}\mathds{1}_{\\{{\mathcal{A}}_{\ell}(j,k)\\}}-n/k\Big{|}\leq\psi_{1}n/k\bigg{\\}},$

then by a Chernoff bound, there exists a constant $c=c(\psi_{1})>0$ such that

$\mathbb{P}\big{(}\neg{\mathcal{A}}_{\mathrm{sub}}(k)\big{)}\leq\exp\big{(}-c(n/k)\big{)}.$
(7.7)

On ${\mathcal{A}}_{\mathrm{sub}}(k)$, since
$(n/k)k\theta_{\ell}/\ell=n\theta_{\ell}/\ell$, the number of size-$\ell$
components of in the union of the induced subgraphs satisfies

$(1-\psi_{1})^{2}n\theta_{\ell}/\ell\leq\sum_{j\in[n/k]}S_{k,\ell}^{\scriptscriptstyle(j)}\leq(1+\psi_{1})^{2}n\theta_{\ell}/\ell\qquad\mbox{on}\
{\mathcal{A}}_{\mathrm{sub}}(k).$ (7.8)

We now look at edges across subboxes. Let
${\mathcal{V}}_{n}^{\mathrm{cross}}(k)$ denote the set of vertices having an
edge to a vertex in a different subbox. Each vertex in
${\mathcal{V}}_{n}^{\mathrm{cross}}(k)$ changes the number of size-$\ell$
components by at most $1$: indeed, this number increases by one when its
crossing edge(s) form a new component of size-$\ell$, and it decreases by one
if without crossing edges its size was $\ell$. Therefore,

$\Big{|}S_{n,\ell}(\infty)-\sum_{j\in[n/k]}S_{k,\ell}^{\scriptscriptstyle(j)}\Big{|}\leq|{\mathcal{V}}_{n}^{\mathrm{cross}}(k)|.$
(7.9)

Hence, for sufficiently small $\psi_{1}$ depending on $\psi$ and $\ell$, on
the event on
$\\{|{\mathcal{V}}_{n}^{\mathrm{cross}}(k)|<\psi_{1}n\big{\\}}\cap{\mathcal{A}}_{\mathrm{sub}}(k)$,

$(1-\psi)n\theta_{\ell}/\ell\leq(1-\psi_{1})^{2}n\theta_{\ell}/\ell-\psi_{1}n\leq
S_{n,\ell}(\infty)\leq(1+\psi_{1})^{2}n\theta_{\ell}/\ell+\psi_{1}n\leq(1+\psi)n\theta_{\ell}/\ell.$

Combining this with (7.7), the exponential decay in (7.6) holds if

$\forall\psi_{1}>0:\exists
k,n_{0}\in{\mathbb{N}},\varepsilon>0\quad\mbox{s.t.}\quad\forall n\geq
n_{0}:\qquad\mathbb{P}\big{(}|{\mathcal{V}}_{n}^{\mathrm{cross}}(k)|\geq\psi_{1}n\big{)}\leq\exp\big{(}-\varepsilon
n\big{)}.$ (7.10)

For Bernoulli bond percolation on ${\mathbb{Z}}^{d}$, the number of vertices
with a crossing edge in each subbox is deterministically at most
$O(k^{(d-1)/d})$ as $k\to\infty$, so the total number of vertices with a
crossing edge across the $(n/k)$ many subboxes is $nO(k^{-1/d})$. So, given
$\psi_{1}$, we choose $k$ large enough so that $O(k^{-1/d})<\psi_{1}$, and
then (7.10) holds (with error probability $0$).

Consider long-range percolation on ${\mathbb{Z}}^{d}$ with $\alpha>1$. Let
${\mathcal{V}}_{n}^{\mathrm{surf}}(t)$ be the set of vertices within distance
$t$ from the union of the boundaries of all subboxes $j\leq n/k$; and let
${\mathcal{E}}_{n}^{\mathrm{long}}(t)$ denote the edges of length at least $t$
inside $\Lambda_{n}$. Clearly,
$|{\mathcal{V}}_{n}^{\mathrm{surf}}(t)|\leq(n/k)2^{d}k^{(d-1)/d}(2t+1)$. For
any $\psi_{1}>0$, fix $\psi_{2}>0$ such that
$|{\mathcal{V}}_{n}^{\mathrm{surf}}(\psi_{2}k^{1/d})|\leq\psi_{1}n/2$ holds
deterministically for all $k$ sufficiently large (simultaneously). Then, since
each edge has two endpoints,

$|{\mathcal{V}}_{n}^{\mathrm{cross}}(k)|\leq|{\mathcal{V}}_{n}^{\mathrm{surf}}(\psi_{2}k^{1/d})|+2|{\mathcal{E}}_{n}^{\mathrm{long}}(\psi_{2}k^{1/d})|\leq\psi_{1}n/2+2|{\mathcal{E}}_{n}^{\mathrm{long}}(\psi_{2}k^{1/d})|.$

Therefore,

$\mathbb{P}\big{(}|{\mathcal{V}}_{n}^{\mathrm{cross}}(k)|\geq\psi_{1}n\big{)}\leq\mathbb{P}\Big{(}2\big{|}{\mathcal{E}}_{n}^{\mathrm{long}}(\psi_{2}k^{1/d})\big{|}\geq\psi_{1}n/2\Big{)}.$
(7.11)

By a standard isoperimetric inequality, the total number of possible edges
inside $\Lambda_{n}$ with length in the interval
$[r_{i,k},r_{i+1,k}):=[2^{i}\psi_{2}k^{1/d},2^{i+1}\psi_{2}k^{1/d})$ is at
most $n\cdot O(r_{i,k}^{d})$ as $i\to\infty$. Each such edge is present
independently with probability at most $\beta^{\alpha}r_{i,k}^{-\alpha d}$ by
the connection probability (4.6). Hence, there exists a constant $C>0$ such
that for $k$ sufficiently large

$\displaystyle\big{|}{\mathcal{E}}_{n}^{\mathrm{long}}(\psi_{2}k^{1/d})\big{|}$
$\displaystyle\preccurlyeq\sum_{i=0}^{\infty}\mathrm{Bin}\big{(}C\psi_{2}^{d}n2^{id}k,\beta^{\alpha}\psi_{2}^{-\alpha
d}2^{-i\alpha d}k^{-\alpha}\big{)}$

where all binomial random variables in the sum are independent of each other.
Thus,

$\mathbb{P}\big{(}|{\mathcal{V}}_{n}^{\mathrm{cross}}(k)|\geq\psi_{1}n\big{)}\leq\mathbb{P}\bigg{(}2\sum_{i=0}^{\infty}\mathrm{Bin}\big{(}C\psi_{2}^{d}n2^{id}k,\beta^{\alpha}\psi_{2}^{-\alpha
d}(2^{id}k)^{-\alpha}\big{)}\geq\psi_{1}n/2\bigg{)}.$

First we apply $x\mapsto\exp(x/2)$ to both sides of the inequality inside the
probability on the right-hand side, then we use Markov’s inequality and
independence of the random variables:

$\mathbb{P}\big{(}|{\mathcal{V}}_{n}^{\mathrm{cross}}(k)|\geq\psi_{1}n\big{)}\leq{\mathrm{e}}^{-\psi_{1}n/4}\prod_{i=0}^{\infty}\mathbb{E}\Big{[}\exp\Big{(}\mathrm{Bin}\big{(}C\psi_{2}^{d}n2^{id}k,\beta^{\alpha}\psi_{2}^{-\alpha
d}(2^{id}k)^{-\alpha}\big{)}\Big{)}\Big{]}.$

Each factor corresponds to the moment-generating function (MGF) of a binomial
random variable evaluated at 1. The MGF of $\mathrm{Bin}(n,p)$ at 1 equals
$(1+p({\mathrm{e}}-1))^{n}\leq\exp\big{(}({\mathrm{e}}-1)np\big{)}$. Applying
this bound to each of the factors yields

$\mathbb{P}\big{(}|{\mathcal{V}}_{n}^{\mathrm{cross}}(k)|\geq\psi_{1}n\big{)}\leq\exp\bigg{(}-\psi_{1}n/4+({\mathrm{e}}-1)C\beta^{\alpha}\psi_{2}^{d(1-\alpha)}nk^{1-\alpha}\sum_{i=0}^{\infty}2^{id(1-\alpha)}\bigg{)}.$

Since $\alpha>1$ by assumption, the sum converges. When $k$ is sufficiently
large, the right-hand side is at most $\exp(-\psi_{1}n/5)$. This proves (7.10)
for long-range percolation and hence (7.6). ∎

We are ready to prove Theorem 2.4.

###### Proof of Theorem 2.4.

For the lower bound, we observe that
$|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|=n$ when all nearest neighbour
edges are present. Its probability decays as $\exp(-\Theta(n))$. For the upper
bound, we argue as follows. We fix $\rho\in(\theta,1)$, and a small
$\psi<1-(1-\rho)/(1-\theta)$. Since
$\sum_{\ell=1}^{\infty}\theta_{\ell}=1-\theta$, this gives us a constant
$\ell^{\star}=\ell^{\star}(\rho,\psi)$ that satisfies
$(1-\psi)\sum_{\ell=1}^{\ell^{\ast}}\theta_{\ell}>1-\rho$. We shall shortly
show that

$\\{{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}>\rho
n\\}\subseteq\big{\\{}\exists\ell\leq\ell^{\star}+1:S_{n,\ell}(\infty)\leq(1-\psi)n\theta_{\ell}/\ell\big{\\}}=:{\mathcal{A}}_{\mathrm{comp}}.$
(7.12)

If (7.12) holds, then Lemma 7.2 and a union bound over the finite set
$\ell\leq\ell^{\ast}+1$ gives that ${\mathcal{A}}_{\mathrm{comp}}$ occurs with
probability exponentially small in $n$, finishing the proof of the upper
bound. To prove (7.12), we show that
$\neg{\mathcal{A}}_{\mathrm{comp}}\subseteq\\{{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}\leq\rho
n\\}$. Since we excluded the case in LRP that nearest neighbour edges are
present with probability one,
$\theta_{\ell}=\mathbb{P}\big{(}|{\mathcal{C}}(0)|=\ell\big{)}>0$ for all
$\ell\geq 1$. So, for all $n$ sufficiently large, on
$\neg{\mathcal{A}}_{\mathrm{comp}}$, there is at least one component of size
$\ell^{\star}+1$; i.e.,
$|{\mathcal{C}}_{n}^{{\scriptscriptstyle(1)}}|\geq\ell^{\ast}+1$. Hence,
vertices in components of size $\ell\leq\ell^{\star}$ are not in the giant.
Thus,

$n-|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|=|{\mathcal{V}}_{n}\setminus{\mathcal{V}}({\mathcal{C}}_{n}^{\scriptscriptstyle(1)})|\geq\sum_{\ell=1}^{\ell^{\ast}}\ell
S_{n,\ell}(\infty)\geq\sum_{\ell=1}^{\ell^{\ast}}(1-\psi)n\theta_{\ell}>n(1-\rho).$

Rearranging yields that $|{\mathcal{C}}_{n}^{{\scriptscriptstyle(1)}}|<\rho n$
on $\neg{\mathcal{A}}_{\mathrm{comp}}$, finishing the proof. ∎

###  7.3. Inhomogeneous models

Here we start again with the convergence rate of the number of size-$\ell$
components. Since the degree distribution is heavy-tailed, this is more
involved than Lemma 7.2. We write $\mathrm{deg}_{v}$ for the degree of vertex
$v$ in ${\mathcal{G}}_{n}$, and $\mathrm{deg}_{v}[a,b)$ for the number of
neighbours of $v$ in ${\mathcal{G}}_{n}$ with mark in $[a,b)$.

######  Claim 7.3 (Total degree from high-mark vertices).

Consider a KSRG on a PPP satisfying Assumption 2.2 with $\tau<\infty$. For any
constants $\psi,C>0$, there exists $\phi_{0}>0$ such that for all $n$
sufficiently large and $\phi\in(0,\phi_{0})$, writing
$\underline{w}_{n}=n^{(1+\psi)/(\tau-1)}$,

$\mathbb{P}\Bigg{(}\sum_{v\in{\mathcal{V}}_{n}[\underline{w}_{n},\phi
n)}\mathrm{deg}_{v}[1,\phi n)\geq\psi n\Bigg{)}\leq n^{-C}.$ (7.13)

######  Claim 7.4 (High-degree vertices).

Consider a KSRG on a PPP satisfying Assumption 2.2 with $\tau<\infty$. For any
constants $\ell,C>0$, there exist constants $n_{0}$, $C_{1}$ such that for all
$n\geq n_{0}$, and any $\underline{w}_{n}>C_{1}\log n$,

$\mathbb{P}\big{(}\exists
v\in{\mathcal{V}}_{n}[\underline{w}_{n},\infty):\mathrm{deg}_{v}[1,\underline{w}_{n})<\ell\big{)}\leq
n^{-C}.$

######  Claim 7.5 (Crossing edges).

Consider a KSRG on a PPP satisfying Assumption 2.2 with $\tau<\infty$. Let
$\psi>0$ be a constant such that $(1+\psi)/(\tau-1)<1$. Then, for any constant
$C>0$, there exists $n_{0}$ such that for all $n\geq n_{0}$ and any
$\underline{w}_{n}\leq n^{(1+\psi)/(\tau-1)}$,

$\mathbb{P}\big{(}|\\{v\in{\mathcal{V}}_{n}[1,\underline{w}_{n}):v\sim\Lambda_{n}^{\complement}\times[1,\underline{w}_{n})\\}|\geq\psi
n\big{)}\leq n^{-C}.$ (7.14)

The proofs of the three claims are based on concentration inequalities for
Poisson/Binomial random variables and postponed to Appendix C.1. Their
combination gives a _polynomial_ convergence rate for the size-$\ell$
components in Lemma 7.1, which is in stark contrast to the exponential
convergence rate for degree-homogeneous models in Lemma 7.2.

######  Lemma 7.6 (Concentration for size-$\ell$ components).

Consider a KSRG on a PPP satisfying Assumption 2.2 with $\tau<\infty$. For all
constants $\ell,\psi,C>0$, there exist constants $\phi_{0}>0$ and $n_{0}$ such
that for all $n\geq n_{0}$ and all $\phi\in(0,\phi_{0})$,

$\mathbb{P}\big{(}\big{|}S_{n,\ell}(\phi
n)/n-\theta_{\ell}/\ell\big{|}>\psi\big{)}\leq n^{-C}.$ (7.15)

###### Proof.

We first reduce the upper mark threshold $\overline{w}_{n}:=\phi n$ in the
event in (7.15) to a smaller value $\underline{w}_{n}=n^{(1+\psi)/(\tau-1)}$
(we assume w.l.o.g. that $(1+\psi)/(\tau-1)<1$). We use that each vertex with
degree at least $\ell$ is in a component of size at least $\ell+1$, and
distinguish the case that each vertex of mark $\underline{w}_{n}$ is in a
component of size larger than $\ell$, i.e.,

$\displaystyle\mathbb{P}\big{(}\big{|}S_{n,\ell}(\overline{w}_{n})/n-\theta_{\ell}/\ell\big{|}>\psi\big{)}$
$\displaystyle\leq\mathbb{P}\bigg{(}\begin{aligned}
&\\{|S_{n,\ell}(\overline{w}_{n})/n-\theta_{\ell}/\ell|>\psi\\}\\\
&\cap\\{\forall
v\in{\mathcal{V}}_{n}[\underline{w}_{n},\overline{w}_{n}):|{\mathcal{C}}_{n}(v)[1,\overline{w}_{n})|>\ell\\}\end{aligned}\bigg{)}$
(7.16) $\displaystyle\hskip 15.0pt+\mathbb{P}\big{(}\exists
v\in{\mathcal{V}}_{n}[\underline{w}_{n},\overline{w}_{n}):\mathrm{deg}_{v}[1,\overline{w}_{n})\leq\ell\big{)}.$
(7.17)

Now we ‘switch’ $\overline{w}_{n}$ to $\underline{w}_{n}$ in
$S_{n,\ell}(\cdot)$ on the right-hand side. Let $T_{n,\ell}$ denote the number
of size-$\ell$ components in ${\mathcal{G}}_{n}[1,\underline{w}_{n})$ that
have an edge towards a vertex with mark in
$[\underline{w}_{n},\overline{w}_{n})$. The events on the right-hand side of
(7.16) imply that the size-$\ell$ components of
${\mathcal{G}}_{n}[1,\overline{w}_{n})$ do not contain any vertices with mark
at least $\overline{w}_{n}$. So, on those events,
$S_{n,\ell}(\overline{w}_{n})=S_{n,\ell}(\underline{w}_{n})-T_{n,\ell}$.
Distinguishing also whether $T_{n,\ell}/n\leq\psi/2$ or not yields

$\displaystyle\mathbb{P}\big{(}\big{|}S_{n,\ell}(\overline{w}_{n})/n-\theta_{\ell}/\ell\big{|}>\psi\big{)}$
$\displaystyle\leq\mathbb{P}\bigg{(}\begin{aligned}
&\\{|S_{n,\ell}(\underline{w}_{n})/n-T_{n,\ell}/n-\theta_{\ell}/\ell|>\psi\\}\cap\\{T_{n,\ell}/n\leq\psi/2\\}\\\
&\cap\\{\forall
v\in{\mathcal{V}}_{n}[\underline{w}_{n},\overline{w}_{n}):|{\mathcal{C}}_{n}(v)[1,\overline{w}_{n})|>\ell\\}\end{aligned}\bigg{)}$
(7.18) $\displaystyle\hskip
15.0pt+\mathbb{P}\big{(}T_{n,\ell}/n\geq\psi/2\big{)}+\mathbb{P}\big{(}\exists
v\in{\mathcal{V}}_{n}[\underline{w}_{n},\overline{w}_{n}):\mathrm{deg}_{v}[1,\overline{w}_{n})\leq\ell\big{)}.$
(7.19)

The first two events in (7.18) imply that
$\\{|S_{n,\ell}(\underline{w}_{n})/n-\theta_{\ell}/\ell|>\psi/2\\}$. Moreover,
$T_{n,\ell}$ is at most the total number of edges between
${\mathcal{V}}[\underline{w}_{n},\overline{w}_{n})$ and
${\mathcal{V}}_{n}[1,\underline{w}_{n})$, which is at most the total degree of
vertices in ${\mathcal{V}}[\underline{w}_{n},\overline{w}_{n})$. Hence,

$\displaystyle\mathbb{P}\big{(}\big{|}S_{n,\ell}(\overline{w}_{n})/n-\theta_{\ell}/\ell\big{|}>\psi\big{)}$
$\displaystyle\leq\mathbb{P}\big{(}|S_{n,\ell}(\underline{w}_{n})/n-\theta_{\ell}/\ell|>\psi/2\big{)}$
$\displaystyle\hskip
15.0pt+\mathbb{P}\bigg{(}\sum_{v\in{\mathcal{V}}_{n}[\underline{w}_{n},\overline{w}_{n})}\mathrm{deg}_{v}[1,\overline{w}_{n})\geq
n\psi/2\bigg{)}$ $\displaystyle\hskip 15.0pt+\mathbb{P}\big{(}\exists
v\in{\mathcal{V}}_{n}[\underline{w}_{n},\overline{w}_{n}):\mathrm{deg}_{v}[1,\overline{w}_{n})\leq\ell\big{)}.$

By Claim 7.3, the second term can be made at most $n^{-2C}$ if $\phi$ in the
definition of $\overline{w}_{n}=\phi n$ is sufficiently small. Since
$\underline{w}_{n}=n^{(1+\psi)/(\tau-1)}$, the third term is also at most
$n^{-2C}$ by Claim 7.4. So,

$\mathbb{P}\big{(}\big{|}S_{n,\ell}(\overline{w}_{n})/n-\theta_{\ell}/\ell\big{|}>\psi\big{)}\leq\mathbb{P}\big{(}|S_{n,\ell}(\underline{w}_{n})/n-\theta_{\ell}/\ell|>\psi/2\big{)}+o\big{(}n^{-C}\big{)}.$
(7.20)

It remains to bound the first term on the right-hand side with
$\underline{w}_{n}=n^{(1+\psi)/(\tau-1)}$. Let $A$ be a sufficiently large
constant with $(A\log n)^{1/d}\in{\mathbb{N}}$ and partition $\Lambda_{n}$
into boxes ${\mathcal{Q}}_{1},\ldots,{\mathcal{Q}}_{A\log n}$ of volume
$k_{n}:=n/(A\log n)$. Let
$S_{k_{n},\ell}^{\scriptscriptstyle(j)}(\underline{w}_{n})$ denote the number
of components of size exactly $\ell$ in the $j$th box, and
${\mathcal{V}}^{\scriptscriptstyle(j)}_{k_{n}}$ the set of vertices in the
$j$th box.

${\mathcal{A}}^{\scriptscriptstyle(j)}:=\\{|S_{k_{n},\ell}^{\scriptscriptstyle(j)}(\underline{w}_{n})/k_{n}-\theta_{\ell}/\ell|\leq\psi/12\\},$
(7.21)

and otherwise we call it bad. The probability of being good tends to $1$ with
$k_{n}$ by Lemma 7.1, and so it is at least $1-\psi/32$ for all $n$
sufficiently large. Let
$X:=\sum_{j\in[k_{n}]}\mathds{1}_{\\{{\mathcal{A}}^{\scriptscriptstyle(j)}\\}}$
be the number of good boxes. Independence across boxes gives that $X$
dominates a binomial random variable with parameters $A\log n$ and
$1-\psi/32$. So, by a Chernoff bound there exists a constant $c=c(\psi)>0$
such that

$\mathbb{P}\big{(}X\geq(1-\psi/16)A\log n\big{)}\geq 1-\exp\big{(}-cA\log
n\big{)}=1-n^{-cA}.$ (7.22)

Since $k_{n}=n/A\log n$, using concentration for Poisson random variables, for
all $n$ sufficiently large,

$\mathbb{P}\big{(}\forall
j:|{\mathcal{V}}_{k_{n}}^{\scriptscriptstyle(j)}[1,\underline{w}_{n})|/k_{n}<4/3\big{)}\geq
1-(A\log n)\exp\big{(}-\Omega(n/\log n)\big{)}\geq 1-n^{-cA}.$ (7.23)

Thus, in the following, we will find bounds on $S_{n,\ell}(\underline{w}_{n})$
conditional on the event

${\mathcal{A}}_{\mathrm{good}}:=\\{\forall
i:|{\mathcal{V}}_{k_{n}}^{\scriptscriptstyle(j)}[1,\underline{w}_{n})|/k_{n}<4/3\\}\cap\\{X\geq(1-\psi/16)A\log
n\\}.$ (7.24)

We write $S^{\scriptscriptstyle\mathrm{good}}_{n,\ell}$ for the sum of
$S_{k_{n},\ell}^{{\scriptscriptstyle(j)}}$ over $j$ for which the $j$th box is
good, and similarly $S^{\scriptscriptstyle\mathrm{bad}}_{k_{n},\ell}$ for the
same sum over bad boxes. Finally, let
${\mathcal{V}}^{\scriptscriptstyle\mathrm{cross}}_{n}[1,\underline{w}_{n})$
denote the set of vertices incident to an edge that crosses a box-boundary.
Since each edge changes the number of size-$\ell$ components by at most $2$,
similarly to (7.9), it holds that

$|S_{n,\ell}(\underline{w}_{n})-(S^{\scriptscriptstyle\mathrm{good}}_{n,\ell}+S^{\scriptscriptstyle\mathrm{bad}}_{n,\ell})|\leq|{\mathcal{V}}^{\scriptscriptstyle\mathrm{cross}}_{n}[1,\underline{w}_{n})|.$
(7.25)

On the event ${\mathcal{A}}_{\mathrm{good}}$ in (7.24), the at most $A\log n$
good boxes contain together at most $(\theta_{\ell}/\ell+\psi/12)n$ components
of size $\ell$. There are at most $n(\psi/16)4/3=n\psi/12$ vertices in bad
boxes. Assuming the worst case that all of them are in size-$\ell$ components
inside their boxes, we obtain the upper bound
$S^{\scriptscriptstyle\mathrm{bad}}_{n,\ell}\leq n\psi/(12\ell)$. So, by a
triangle inequality on the left-hand side above,

$S_{n,\ell}(\underline{w}_{n})-n\theta_{\ell}/\ell\leq
n\psi/12+n\psi/(12\ell)+|{\mathcal{V}}^{\scriptscriptstyle\mathrm{cross}}_{n}[1,\underline{w}_{n})|\leq
n\psi/6+|{\mathcal{V}}^{\scriptscriptstyle\mathrm{cross}}_{n}[1,\underline{w}_{n})|.$

Similarly, for a lower bound we may assume that there are no size-$\ell$
components in bad boxes. On the event (7.24), this still gives

$S_{n,\ell}(\underline{w}_{n})-n\theta_{\ell}/\ell\geq
n(1-\psi/16)\big{(}\theta_{\ell}/\ell-\psi/12\big{)}-|{\mathcal{V}}_{n}^{\scriptscriptstyle\mathrm{cross}}[1,\underline{w}_{n})|\geq-n\psi
7/48-|{\mathcal{V}}_{n}^{\scriptscriptstyle\mathrm{cross}}[1,\underline{w}_{n})|$

Recalling the bounds (7.20), (7.22), and (7.23), we obtain

$\displaystyle\mathbb{P}\big{(}\big{|}S_{n,\ell}(\overline{w}_{n})/n-\theta_{\ell}/\ell\big{|}>\psi\big{)}$
$\displaystyle\leq
2n^{-cA}+o(n^{-C})+\mathbb{P}\big{(}|{\mathcal{V}}^{\scriptscriptstyle\mathrm{cross}}_{n,\ell}|/n\geq\psi/3\big{)}.$

We bound the probability concerning the crossing edges. By the pigeon-hole
principle, $|{\mathcal{V}}^{\scriptscriptstyle\mathrm{cross}}_{n,\ell}|\geq
n\psi/3$ implies that there exists a box that contains at least
$(\psi/3)k_{n}$ vertices with an outgoing edge towards the complement of the
box. Hence, by translation invariance of the model on ${\mathbb{R}}^{d}$,

$\mathbb{P}\big{(}|{\mathcal{V}}_{n,\ell}^{\scriptscriptstyle\mathrm{cross}}|/n\geq\psi/3\big{)}\leq(A\log
n)\mathbb{P}\big{(}|\\{v\in{\mathcal{V}}_{k_{n}}[1,\underline{w}_{n}):v\sim\Lambda_{k_{n}}^{\complement}\times[1,\underline{w}_{n})\\}|\geq(\psi/3)k_{n}\big{)}.$

7.5 is applicable here for $n_{\ref{claim:crossing-edges}}=k_{n}=n/(A\log n)$,
since $\underline{w}_{n}=n^{(1+\psi)/(\tau-1)}\leq
k_{n}^{(1+\psi^{\prime})/(\tau-1)}$ for any $\psi^{\prime}>\psi$. So the
right-hand side is smaller than $n^{-cA}$ for $n$ sufficiently large. We
conclude that (7.15) follows for $\phi$ small, setting $A\geq C/c$ such that
$(A\log n)^{1/d}\in{\mathbb{N}}$. ∎

We need a last preliminary claim. Recall $\mathrm{hubs}(\rho)$ from (2.17). We
introduce notation for the functions appearing in the upper and lower bound of
Theorem 2.5:

$h_{\mathrm{up}}:=\lceil\mathrm{hubs}(\rho)\rceil,\qquad
h_{\mathrm{lo}}:=\lim_{r\downarrow\rho}\lceil\mathrm{hubs}(r)\rceil=\begin{dcases}\lceil\mathrm{hubs}(\rho)\rceil,&\text{if
}\mathrm{hubs}(\rho)\notin{\mathbb{N}}\text{ or }p=1,\\\
\mathrm{hubs}(\rho)+1,&\text{if }\mathrm{hubs}(\rho)\in{\mathbb{N}}\text{ and
}p<1.\end{dcases}$ (7.26)

Clearly $h_{\mathrm{lo}}\geq h_{\mathrm{up}}\geq\mathrm{hubs}(\rho)$, and for
all $\rho\in(\theta,1)$ and $p<1$ also $h_{\mathrm{lo}}>\mathrm{hubs}(\rho)$
strictly.

######  Claim 7.7 (Truncation of the generating function).

Consider a KSRG on a PPP satisfying Assumption 2.2 with $\tau<\infty$. Let
$\rho\in(\theta,1)$. There exist constants $\psi>0$ and
$\ell_{0}\in{\mathbb{N}}$ such that for all $\ell^{\ast}>\ell_{0}$,

$(1-\psi)^{2}\bigg{(}\theta+\sum_{\ell=1}^{\ell^{\ast}}\big{(}1-(1-p)^{h_{\mathrm{lo}}\ell}\big{)}\theta_{\ell}\bigg{)}>\rho,$
(7.27)

and

$(1-\psi)^{2}\sum_{\ell=1}^{\ell^{\ast}}\theta_{\ell}(1-p)^{(h_{\mathrm{up}}-1)\ell}>1-\rho+\psi.$
(7.28)

We postpone the proof to Appendix C.2 and proceed to the lower bound of
Theorem 2.5.

######  Proposition 7.8 (Lower bound of the upper tail).

Consider a KSRG on a PPP satisfying Assumption 2.2 with $\tau<\infty$. Fix
$\rho\in(\theta,1)$. Assume either supercriticality and
$\zeta_{\mathrm{long}}>0$, or assume $\theta=0$. Then there exists
$A=A(\rho)>0$ such that for all $n\geq 1$,

$\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|>\rho
n\big{)}\geq(1/A)n^{-(\tau-2)h_{\mathrm{lo}}}.$

###### Proof.

The proof is similar in spirit to the proof of Theorem 2.4 on page 7.2, but we
also need to deal with high-mark vertices. See Section 3.2 for an outline that
we make formal now. Let $R,\ell^{\star}$ be two sufficiently large constants,
and let $\phi,\psi>0$ be two small constants so that given
$\rho\in(\theta,1)$, (7.27) holds. Write $T_{n,\ell}$ for the number of
components of size $\ell$ in ${\mathcal{G}}_{n}[1,\phi n)$ that connect by an
edge to the vertices with mark in ${\mathcal{V}}_{n}[Rn,\infty)$. Define the
events

$\displaystyle{\mathcal{A}}_{\mathrm{comp}}$
$\displaystyle:=\big{\\{}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}[1,\phi
n)|/n\geq\theta(1-\psi)\big{\\}}\cap\big{\\{}\forall\ell\leq\ell^{\ast}:S_{n,\ell}(\phi
n)\geq(1-\psi)n\theta_{\ell}/\ell\big{\\}},$ (7.29)
$\displaystyle{\mathcal{A}}_{\mathrm{hub}}$
$\displaystyle:=\big{\\{}|{\mathcal{V}}_{n}[Rn,\infty)|=h_{\mathrm{lo}}\big{\\}}\cap\big{\\{}\forall
v\in{\mathcal{V}}_{n}[Rn,\infty):v\sim{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}[1,\phi
n)\big{\\}},$ (7.30) $\displaystyle{\mathcal{A}}_{\mathrm{conn}}$
$\displaystyle:=\big{\\{}\forall\ell\leq\ell^{\ast}:T_{n,\ell}\geq(1-\psi)\big{(}1-(1-p)^{h_{\mathrm{lo}}\ell}\big{)}\big{(}(1-\psi)n\theta_{\ell}/\ell\big{)}\big{\\}}.$
(7.31)

We shall show that

${\mathcal{A}}_{\mathrm{comp}}\cap{\mathcal{A}}_{\mathrm{hub}}\cap{\mathcal{A}}_{\mathrm{conn}}\subseteq\\{|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|>\rho
n\\}.$ (7.32)

By its definition, $T_{n,\ell}$ many clusters of size $\ell$ connect to the
hubs listed in ${\mathcal{A}}_{\mathrm{hub}}$, which then all are part of the
giant component in the whole graph. Hence, on ${\mathcal{A}}_{\mathrm{hub}}$,
the giant $|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}[1,\phi n)|$ increases by
at least $\ell T_{n,\ell}$ when fully revealing the graph. By the bounds on
$T_{n,\ell}$ and the initial size $(1-\psi)\theta n$ of the giant inside the
events, and (7.27) in 7.7, we obtain that

$\displaystyle|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|/n$
$\displaystyle\geq\theta(1-\psi)+\frac{1}{n}\sum_{\ell=1}^{\ell^{\ast}}\ell
T_{n,\ell}\geq\theta(1-\psi)+(1-\psi)^{2}\sum_{\ell=1}^{\ell^{\ast}}\big{(}1-(1-p)^{h_{\mathrm{lo}}\ell}\big{)}\theta_{\ell}$
$\displaystyle\geq(1-\psi)^{2}\bigg{(}\theta+\sum_{\ell=1}^{\ell^{\ast}}\big{(}1-(1-p)^{h_{\mathrm{lo}}\ell}\big{)}\theta_{\ell}\bigg{)}>\rho,$

so (7.32) holds. We bound from below the probability of the intersection using
the law of total probability:

$\mathbb{P}\big{(}{\mathcal{A}}_{\mathrm{comp}}\cap{\mathcal{A}}_{\mathrm{hubs}}\cap{\mathcal{A}}_{\mathrm{conn}}\big{)}=\mathbb{P}\big{(}{\mathcal{A}}_{\mathrm{comp}}\cap{\mathcal{A}}_{\mathrm{hubs}}\big{)}\mathbb{P}\big{(}{\mathcal{A}}_{\mathrm{conn}}\mid{\mathcal{A}}_{\mathrm{comp}}\cap{\mathcal{A}}_{\mathrm{hubs}}\big{)}.$
(7.33)

To study the first factor, we use the law of total probability again and then
also $\mathbb{P}(A\cap B)\geq\mathbb{P}(A)-\mathbb{P}(\neg B)$ (see
(7.29)-(7.30)):

$\displaystyle\mathbb{P}\big{(}{\mathcal{A}}_{\mathrm{comp}}\cap{\mathcal{A}}_{\mathrm{hubs}}\big{)}$
$\displaystyle\geq\mathbb{P}\Big{(}\forall
v\in{\mathcal{V}}_{n}[Rn,\infty):v\sim{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}[1,\phi
n)\mid{\mathcal{A}}_{\mathrm{comp}}\cap\big{\\{}|{\mathcal{V}}_{n}[Rn,\infty)|=h_{\mathrm{lo}}\big{\\}}\Big{)}$
$\displaystyle\qquad\cdot\Big{(}\mathbb{P}\big{(}|{\mathcal{V}}_{n}[Rn,\infty)|=h_{\mathrm{lo}}\big{)}-\mathbb{P}\big{(}\neg{\mathcal{A}}_{\mathrm{comp}}\big{)}\Big{)}$
(7.34)

For the first term in the row (7.34) we use that
$|{\mathcal{V}}_{n}[Rn,\infty)|\sim\mathrm{Poi}(n(Rn)^{-(\tau-1)})$ by the
intensity in (4.5). Note here that the parameter tends to $0$ since $\tau>2$.
Therefore, since $h_{\mathrm{lo}}$ is a $\rho$-dependent constant that does
not depend on $n$,

$\displaystyle\mathbb{P}\big{(}|{\mathcal{V}}_{n}[Rn,\infty)|=h_{\mathrm{lo}}\big{)}$
$\displaystyle=\exp\big{(}\\!-\\!R^{-(\tau-1)}n^{-(\tau-2)}\big{)}\frac{\big{(}R^{-(\tau-1)}n^{-(\tau-2)}\big{)}^{h_{\mathrm{lo}}}}{h_{\mathrm{lo}}!}\geq
c_{R,\rho}n^{-(\tau-2)h_{\mathrm{lo}}}$ (7.35)

for some constant $c_{R,\rho}>0$. We now bound
$\mathbb{P}(\neg{\mathcal{A}}_{\mathrm{comp}})$ in (7.34).

$\mathbb{P}(\neg{\mathcal{A}}_{\mathrm{comp}})\leq\mathbb{P}\Big{(}\exists\ell\leq\ell^{\ast}:\ell
S_{n,\ell}(\phi
n)/n\leq(1-\psi)\theta_{\ell}\Big{)}+\mathbb{P}(|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}[1,\phi
n)|/n<\theta(1-\psi)).$ (7.36)

Lemma 7.6 and a union bound over the $\ell^{\star}$ many $\ell$ shows that the
first term is at most $n^{-C}$ for arbitrary large $C$ when
$\phi<\phi_{0}(\psi)$. For the second term, there are two cases. Either
$\theta=0$ and then this probability is $0$; or, $\theta$ is non-zero. In the
latter case, when additionally $\zeta_{\mathrm{long}}>0$, our result for the
_lower_ tail of large deviations in Theorem 2.7 guarantees that this event has
stretched exponentially decaying probability in $n$. This is where we use that
the model must be supercritical with $\zeta_{\mathrm{long}}>0$
when666Inspection of the proof of Theorem 2.7 shows that the sprinkling
technique used in Section 4 needs supercriticality. The assumption
$\zeta_{\mathrm{long}}>0$ is the technical condition of Theorem 2.7 that
guarantees enough long edges. $\theta>0$. So, under these conditions, we know
that $\mathbb{P}\big{(}\neg{\mathcal{A}}_{\mathrm{comp}}\big{)}$ is of smaller
order than the lower bound in (7.35) on the first term in (7.34).

We now analyse the conditional probability on the line above (7.34). Take
$R>\sqrt{d}/\beta$. Then a vertex with mark at least $Rn$ connects by an edge
to any other vertex in $\Lambda_{n}$ with probability $p$ by (4.6). The giant
${\mathcal{C}}_{n}^{{\scriptscriptstyle(1)}}[1,\phi n)$ has size at least
$(1-\psi)\theta n$ on the event ${\mathcal{A}}_{\mathrm{comp}}$ in (7.29) in
the conditioning. So, by a union bound, the (conditional) probability that all
the $h_{\mathrm{lo}}$ many vertices of mark at least $Rn$ connect by an edge
to ${\mathcal{C}}_{n}^{{\scriptscriptstyle(1)}}[1,\phi n)$ is at least
$1-h_{\mathrm{lo}}(1-p)^{\Theta(n)}$, which tends to $1$ as $n\to\infty$.
Combining these with (7.34)–(7.35) gives in (7.33)

$\mathbb{P}\big{(}{\mathcal{A}}_{\mathrm{comp}}\cap{\mathcal{A}}_{\mathrm{hubs}}\big{)}\geq
c_{R,\rho}n^{-(\tau-2)h_{\mathrm{lo}}}.$ (7.37)

We show that the other term in (7.33),
$\mathbb{P}\big{(}{\mathcal{A}}_{\mathrm{conn}}\mid{\mathcal{A}}_{\mathrm{comp}}\cap{\mathcal{A}}_{\mathrm{hubs}}\big{)}$
tends to $1$ as $n\to\infty$. Recall these events from (7.29)–(7.31) and that
under the conditioning, $T_{n,\ell}$ denotes the number of size-$\ell$
components of ${\mathcal{G}}_{n}[1,\phi n)$ that connect to one of the
$h_{\mathrm{lo}}$ many vertices of mark at least $Rn$ (the hubs). As before,
each vertex connects independently to these hubs with probability $p$.
Further, the vertex set counted in $T_{n,\ell}$ is disjoint of the vertices in
${\mathcal{C}}_{n}^{{\scriptscriptstyle(1)}}[1,\phi n)$ so their connection to
the hubs is independent of whether the vertices in
${\mathcal{C}}_{n}^{{\scriptscriptstyle(1)}}[1,\phi n)$ connect to the hubs,
which is an event inside the conditioning
${\mathcal{A}}_{\mathrm{comp}}\cap{\mathcal{A}}_{\mathrm{hubs}}$. So, under
the conditioning, each component of size $\ell$ in ${\mathcal{G}}_{n}[1,\phi
n)$ connects to one of the $h_{\mathrm{lo}}$ hubs with probability
$1-(1-p)^{h_{\mathrm{lo}}\ell}$ independently across size-$\ell$ components
and across $\ell<\ell^{\star}$. Hence, given the number of size-$\ell$
components in ${\mathcal{G}}_{n}[1,\psi n)$, $(S_{n,\ell}(\phi
n))_{\ell\leq\ell^{\star}}$, the variables $T_{n,\ell}$ are binomially
distributed with parameters $S_{n,\ell}(\phi n)$ and
$(1-(1-p)^{h_{\mathrm{lo}}\ell})$. Further, under the conditioning in
${\mathcal{A}}_{\mathrm{comp}}$, each $S_{n,\ell}(\phi n)$ is at least
$(1-\psi)n\theta_{\ell}/\ell$, so $T_{n,\ell}$ dominates a binomial random
variable with parameters $(1-\psi)n\theta_{\ell}/\ell$ and
$(1-(1-p)^{h_{\mathrm{lo}}\ell})$ for each $\ell\leq\ell^{\star}$. A union
bound over $\ell\leq\ell^{\star}$ and then a Chernoff bound for each $\ell$
give that
$\mathbb{P}\big{(}{\mathcal{A}}_{\mathrm{conn}}\mid{\mathcal{A}}_{\mathrm{comp}}\cap{\mathcal{A}}_{\mathrm{hubs}}\big{)}\to
1$ as $n\to\infty$. Using this in (7.33) and (7.37) gives in (7.32) that for
some constant $c_{R,\rho}>0$,

$\displaystyle\mathbb{P}({\mathcal{C}}_{n}^{{\scriptscriptstyle(1)}}>\rho
n)\geq\mathbb{P}\big{(}{\mathcal{A}}_{\mathrm{comp}}\cap{\mathcal{A}}_{\mathrm{hubs}}\cap{\mathcal{A}}_{\mathrm{conn}}\big{)}$
$\displaystyle\geq c_{R,\rho}n^{-(\tau-2)h_{\mathrm{lo}}}.\qed$

We proceed to the upper bound of Theorem 2.5.