# Large deviations of the giant in supercritical kernel-based spatial random
graphs

Joost Jorritsma1 1Centre for Mathematics & Computer Science (CWI), the
Netherlands; Department of Mathematics and Computer Science, Eindhoven
University of Technology  ,  Júlia Komjáthy2 2Delft Institute of Applied
Mathematics, Delft University of Technology  and  Dieter Mitsche3 3Institut
Camille Jordan, Univ. Jean Monnet, Univ. de Lyon and IMC, Pontifícia Univ.
Católica de Chile<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

We study cluster sizes in supercritical $d$-dimensional inhomogeneous
percolation models with long-range edges —such as long-range percolation—
and/or heavy-tailed degree distributions —such as geometric inhomogeneous
random graphs and the age-dependent random connection model. Our focus is on
large deviations of the size of the largest cluster in the graph restricted to
a finite box as its volume tends to infinity. Compared to nearest-neighbor
Bernoulli bond percolation on ${\mathbb{Z}}^{d}$, we show that long edges can
increase the exponent of the polynomial speed of the lower tail from $(d-1)/d$
to any $\zeta_{\star}\in\big{(}(d-1)/d,1\big{)}$. We prove that this exponent
$\zeta_{\star}$ also governs the size of the second-largest cluster, and the
distribution of the size of the cluster containing the origin
${\mathcal{C}}(0)$.

For the upper tail of large deviations, we prove that its speed is logarithmic
for models with power-law degree distributions. We express the rate function
via the generating function of $|{\mathcal{C}}(0)|$. The upper tail in degree-
homogeneous models decays much faster: the speed in long-range percolation is
_linear_.

Keywords: Cluster-size distribution, large deviation principle, second-largest
component, spatial random graphs, scale-free networks.

MSC Class: 05C80, 60K35.

##  1\. Introduction

For supercritical nearest neighbour Bernoulli bond percolation on
${\mathbb{Z}}^{d}$ (NNP), it is a classical result that the graph restricted
to a volume-$n$ box around the origin contains a _giant_ , i.e., a linear-
sized component ${\mathcal{C}}_{n}^{\scriptscriptstyle(1)}$, with probability
tending to one as $n\to\infty$. Its number of vertices satisfies a Law of
Large Numbers (LLN): $|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|/n$ converges
to $\theta:=\mathbb{P}_{\mathrm{NNP}}(0\leftrightarrow\infty)$ almost surely.
Regarding large deviations of $|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|$,
the speed is known in all dimensions $d\geq 2$, and an interesting discrepancy
occurs: the lower tail decays slower than the upper tail.

For the upper tail, the event
$\\{|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|>(\theta+\varepsilon)n\\}$
requires linearly more edges to be present than expected, which comes at an
exponential cost. So, the speed of large deviations is _linear_ in the volume
of the box: for each $\rho\in(\theta,1)$, there exist constants $C_{\rho}\geq
c_{\rho}>0$ such that for all $n\geq 1$,

$-C_{\rho}\leq\frac{1}{n}\log\mathbb{P}_{\mathrm{NNP}}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|>\rho
n\big{)}\leq-c_{\rho}.$ (1.1)

We refer to [30, 32, 57] for the speed of large deviations a closely related
quantity, and to Theorem 2.4 below for the precise result. For the lower tail,
the $\Omega(n^{(d-1)/d})$ many edges on the “outer surface boundary” of a
linear-sized cluster have to be absent. So, the speed of the lower tail is
_sublinear_ [69]: for each $\rho\in(0,\theta)$, there exist constants
$C_{\rho}^{\prime}\geq c_{\rho}^{\prime}>0$ such that

$-C_{\rho}^{\prime}\leq\frac{1}{n^{(d-1)/d}}\log\mathbb{P}_{\mathrm{NNP}}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|<\rho
n\big{)}\leq-c_{\rho}^{\prime}.$ (1.2)

We can interpret that the speed of the lower tail is caused by _surface
tension_ (more precise results are known for closely related quantities, see
[6, 21, 30, 32] and Section 2 below).

In this paper, we study large deviations of the giant in long-range
percolation [71], and also in models with regularly-varying edge-length– and
degree distributions. Our driving question is:

How do high-degree vertices and long-range edges influence
the tails of large deviations of the giant component?-range (Q)

We describe three new phenomena that encompass the answer. First, high-degree
vertices slow down the upper tail enormously: the speed becomes logarithmic.
Second, long-range edges speed up the lower tail: the speed is still
polynomial, but is no longer determined by surface tension alone. Since the
lower tail decays much faster than the upper tail, the discrepancy of speeds
is the opposite of the one in NNP. Third, we prove that the speed of the lower
tail is closely related to the size of the second-largest connected component,
and to the cluster-size distribution of the origin in the infinite model. We
explain these phenomena after motivating this topic with an application and an
informal model description.

Figure 1. Simulations of 2-dimensional long-range percolation (LRP), a
2-dimensional geometric inhomogeneous random graph (GIRG), and a 1-dimensional
soft Poisson–Boolean model (sPBM). In the sPBM, the $y$-axis reflects the
vertex marks. The presence of long edges in these models leads to delocalized
components, and affects the distributions of the sizes of three components:
the speed of the lower tail of large deviations of the largest component
(blue), the size of the second-largest component (red), and the distribution
of the size of the cluster containing the origin (green) are all governed by
the exponent $\zeta_{\star}$, which is defined in (1.4). The upper tail of
large deviations of the giant’s size has linear speed in (mark)-homogeneous
models as LRP, and logarithmic speed in inhomogeneous models as GIRG and sPBM.

_Motivation._ Many real networks have been found to have underlying geometry,
inhomogeneous degrees, clustering, and long-range connections [5, 66]. In
biological contexts, the component sizes (under percolation of an initial
graph) correspond to the final size of a Reed-Frost or SIR epidemic on the
network [1, 10, 58], and to activity patterns in brain networks [20, 28, 53].
In the statistical physics context, there are many models with long-range
interactions, such as model gravitational and charged systems, turbulent
hydrodynamic systems, dipolar systems, and two-dimensional elasticity, see
among others [19, 25, 26] for examples. In the last decade many random graph
models have been invented to mimic real networks and systems with long-range
interactions, see the next paragraph. For many of these models, an analysis of
basic properties of their component structure —such as their approximate size-
distribution— has been lacking in the literature. In this paper we fill this
gap and develop new, robust proof techniques that allow for the presence of
long-range edges and inhomogeneous degrees.

_Spatial inhomogeneous percolation models._ The most well-known spatial
degree-inhomogeneous models are hyperbolic random graphs [54], geometric
inhomogeneous random graphs [16], the (soft) Poisson–Boolean model with random
radii [34, 42], and the age-dependent random connection model [35]. The
degree-inhomogeneity leads to arbitrarily long edges. While the degree
distribution of long-range percolation (LRP) is light-tailed, LRP also
contains long edges. The presence of long edges leads to components that might
be ‘delocalized in space’, see Figure 1. Our formal setup, introduced
informally now, captures these models all at once.

The vertex sets are formed by a $d$-dimensional ergodic point process: either
${\mathbb{Z}}^{d}$ or a homogeneous Poisson point process (PPP) on
${\mathbb{R}}^{d}$. Each vertex $u\in{\mathcal{V}}$ at location $x_{u}$ is
equipped with an independent and identically distributed (iid) mark $w_{u}\geq
1$, which is Pareto-distributed for degree-inhomogeneous models, and a
constant for long-range percolation. The expected degree of a vertex is
proportional to its mark (sometimes also called ‘weight’). Conditionally on
all vertex locations and marks $\\{(x_{u},w_{u})\\}_{u\in{\mathcal{V}}}$, each
edge $\\{u,v\\}$ is present independently with probability
$\varphi(\beta,w_{u},w_{v},\|x_{u}-x_{v}\|)$. The (model-dependent) _edge-
connectivity function_ $\varphi$ is non-increasing in the distance, non-
decreasing and symmetric in both marks. The parameter $\beta>0$ controls the
edge-density. We often assume that the model is supercritical, i.e.,
$\beta>\beta_{c}$, where $\beta_{c}$ is the infimum over $\beta\geq 0$ such
that the graph contains an infinite connected component almost surely.

_Law of Large Numbers for the size of the giant._ In this general model class,
even the existence of a linear-sized component in finite boxes is not
guaranteed/known in the whole supercritical regime. When $\varphi$ allows for
sufficiently many long edges, we prove existence and uniqueness of the giant
for all $\beta>\beta_{c}$. Its size satisfies a Law of Large Numbers:
$|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|/n\to\theta:=\mathbb{P}(0\leftrightarrow\infty)$
in probability (for some cases the convergence holds almost surely). The long
edges that are necessary for this LLN, come either from a slow decay of the
connectivity function $\varphi$ as $\|x_{u}-x_{v}\|\to\infty$, or from the
presence of high vertex marks, or from a combination of both.

_Upper tail of large deviations._ We now state informally our result on the
upper tail.

######  Meta-theorem 1.1 (High-degree vertices cause slow upper tails).

Consider a spatial inhomogeneous percolation model with regularly-varying
degree distribution, so that $|{\mathcal{C}}_{n}^{{\scriptscriptstyle(1)}}|$,
the size of the giant, satisfies a Law of Large Numbers. The upper tail of
$|{\mathcal{C}}_{n}^{{\scriptscriptstyle(1)}}|$ has logarithmic speed. We
identify the non-negative rate-function $I(\cdot)$ such that for all
$\rho\in(\theta,1)$,

$\displaystyle-\inf_{r>\rho}I(r)$
$\displaystyle\leq\liminf_{n\to\infty}\frac{1}{\log
n}\log\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|>\rho
n\big{)}$ (1.3) $\displaystyle\leq\limsup_{n\to\infty}\frac{1}{\log
n}\log\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|>\rho
n\big{)}=-\inf_{r\geq\rho}I(r)=I(\rho).$

On the contrary, the speed in Bernoulli bond percolation or long-range
percolation on ${\mathbb{Z}}^{d}$ is linear.

We formalize 1.1 in Theorem 2.4 and Theorem 2.5 below. 1.1 is the first result
that identifies the rate function for the size of the giant in a spatial
random graph model. Moreover, the rate function for the giant is not even
known for many classical _non-spatial_ random graph models such as the rank-
one inhomogeneous random graph with iid Pareto weights [22, 67], and the
configuration model with iid Pareto degrees [63]. Some known results for non-
spatial graphs are the following: The LDP of the giant in the configuration
model with _fixed_ degree sequence has linear speed when linear-degree
vertices are absent [13]; in sparse inhomogeneous random graphs with bounded
weights the speed is linear as well [8], similar to sparse Erdős-Rényi random
graphs [9, 68]. A work in progress by the first author and Zwart shows an LDP
for the giant in inhomogeneous random graphs with iid heavy-tailed vertex
weights [50].

We briefly explain the reason for the logarithmic speed: with _polynomially_
decaying probability, the vertex set contains a few hubs: vertices with mark
$\Theta(n)$. These hubs connect to the giant and to linearly many small
components. Small components do not merge with the giant with a probability
that is exponentially small in their size and in the number of hubs. This
allows us to express the rate-function $I(\cdot)$ via the generating function
of the cluster-size distribution of the infinite model.

A similar phenomenon occurs for the sum of $n$ iid (fully asymmetric) Pareto
random variables: this sum also satisfies an LDP with logarithmic speed of the
upper tail. Having a single summand whose value is linear in $n$ comes at a
polynomial cost. On the contrary, the lower tail for such variables has linear
speed because linearly many summands need to be small [65].

_Lower tail of large deviations._ Similar to the sum of iid Pareto random
variables, the lower tail of the size of the giant decays much faster than the
upper tail. However, due to the underlying geometry, the speed is not linear,
but polynomial. Contrary to NNP in (1.2), in models with long-range edges the
speed is not determined by surface tension alone. Instead, the speed is given
by the solution of a variational problem that describes the most likely way
that a box of volume $n$, denoted by $\Lambda_{n}$, is isolated from its
complement $\Lambda_{n}^{\complement}$ [48]. For most edge-connectivity
functions $\varphi$, the probability that $\Lambda_{n}$ is isolated decays as
$\exp(-\Theta(n^{\zeta_{\star}}))$ for some exponent
$\zeta_{\star}\in[0,1)$111For some connectivity functions $\varphi$, slowly-
varying correction factors appear inside the “$\Theta(\cdot)$” in the exp-
function.. The exponent $\zeta^{\star}$ can also be determined via the
expected size of the _downward vertex boundary_ that we define now. We say
that the edge $\\{u,v\\}=\\{(x_{u},w_{u}),(x_{v},w_{v})\\}$ is a ‘downward
edge’ from $u$ if $w_{u}\geq w_{v}$. We define${}^{\ref{note-limit}}$

$\zeta_{\star}:=\lim_{n\to\infty}\frac{\log\mathbb{E}\Big{[}\big{|}\big{\\{}u\in\Lambda_{n}:u\mbox{
has a downward edge to }\Lambda_{n}^{\complement}\big{\\}}\big{|}\Big{]}}{\log
n},$ (1.4)

The restriction of counting vertices with downward edges to
$\Lambda_{n}^{\complement}$ is necessary for some (but not all) edge-
connectivity functions $\varphi$. This excludes counting (potentially many)
vertices on the vertex boundary that are connected by an edge to a small
number of high-mark vertices spatially close to $\Lambda_{n}$. In NNP all
marks are identical and $\zeta_{\star}=(d-1)/d$: the expectation in
$\zeta_{\star}$ is governed by surface tension. As we will see,
$\zeta_{\star}$ provides the right generalization of surface tension to
spatial inhomogeneous percolation models with long edges. For these latter
models, $\zeta_{\star}=\max(\zeta_{\mathrm{long}},(d-1)/d)$, where222The
limits in the definitions of $\zeta_{\star}$ and $\zeta_{\mathrm{long}}$ are
well-defined in the models that we study. We will never use
$\zeta_{\mathrm{long}}$ when it equals $0$. The truncation ensures that the
limit always exists.

$\zeta_{\mathrm{long}}:=\lim_{n\to\infty}\Bigg{(}0\vee\frac{\log\mathbb{E}\Big{[}\big{|}\big{\\{}u\in\Lambda_{n/2}:u\mbox{
has a downward edge to }\Lambda_{n}^{\complement}\big{\\}}\big{|}\Big{]}}{\log
n}\Bigg{)}$ (1.5)

describes the number of vertices incident to long downwards edges; of length
$\Omega(n^{1/d})$. The value of $\zeta_{\mathrm{long}}$ can be explicitly
computed based on the exact model specifications. Importantly,
$\zeta_{\mathrm{long}}$ can be larger than $(d-1)/d$ for any fixed
$d\in{\mathbb{N}}$. In that case, $\zeta_{\star}=\zeta_{\mathrm{long}}$ and
long edges speed up the decay of the lower tail of large deviations.

######  Meta-theorem 1.2 (Long edges speed up the lower tail).

Consider a supercritical spatial inhomogeneous percolation model so that
$|{\mathcal{C}}_{n}^{{\scriptscriptstyle(1)}}|$, the size of the giant,
satisfies a Law of Large Numbers, i.e., $\zeta_{\mathrm{long}}>0$. Assume that
the expected downward vertex boundary in (1.4) has size
$\Theta(n^{\zeta_{\star}})$. For each $\rho\in(0,\theta)$, there exist
constants $C_{\rho}\geq c_{\rho}>0$ such that for all $n\geq 1$,

$-C_{\rho}\leq\frac{1}{n^{\zeta_{\star}}}\log\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|<\rho
n\big{)}\leq-c_{\rho}.$ (1.6)

When the expected downward vertex boundary has slowly-varying correction
factors, (potentially different) slowly-varying correction factors appear in
the lower bound.

We formalize 1.2 in Theorem 2.7. 1.2 implies the existence of the giant with
stretched exponential error probability, which is novel for several spatial
inhomogeneous percolation models mentioned above on page 1. Moreover, this
result includes long-range percolation and improves upon the currently known
best bound there as well, as we explain now.

In long-range percolation, two vertices $x,y\in{\mathbb{Z}}^{d}$ are connected
by an edge independently with probability
$\Theta\big{(}1\wedge\|x-y\|^{-\alpha d}\big{)}$ as $\|x-y\|\to\infty$, for a
long-range parameter $\alpha>1$. An elementary computation shows that
$\zeta_{\mathrm{long}}=2-\alpha$, and $\zeta_{\star}=\max(2-\alpha,(d-1)/d)$.
In [14], Biskup showed that there exists $\delta>0$ such that
$\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|<\delta
n\big{)}\leq\exp\big{(}-n^{2-\alpha-o(1)}\big{)}$. 1.2 improves upon [14] in
two ways when $2-\alpha=\zeta_{\mathrm{long}}>(d-1)/d$. First, the power of
$n$ in the exponent in (1.6) has no $o(1)$-term. Second, the decay in (1.6)
holds for arbitrary $\rho\in(0,\theta)$, instead of a small constant $\delta$.

Returning to the general model setting, we give some intuition why
$\zeta_{\mathrm{long}}$ drives the lower tail when
$\zeta_{\mathrm{long}}>(d-1)/d$. The definition of $\zeta_{\mathrm{long}}$ in
(1.5) tells us that $\Lambda_{n}$ contains about
$\Theta(n^{\zeta_{\mathrm{long}}})$ many vertices that are incident to long
edges of length $\Omega(n^{1/d})$. We partition $\Lambda_{n}$ into subboxes of
size $\Theta(n^{1-\zeta_{\mathrm{long}}})$, so that a subbox typically
contains constantly many vertices incident to these long edges. Then, we
couple the graph with an ERRG with large constant expected degree. In this
coupling, each vertex corresponds to a local giant inside one of the
$\Theta(n^{\zeta_{\mathrm{long}}})$ many subboxes, and we use the long edges
to estimate the probability that two local giants are connected. Then we apply
the LDP on the giant in ERRGs by O’Connell [68]. This LDP has linear speed in
the number of ‘Erdős-Rényi vertices’, and yields that
$\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|<\rho
n\big{)}\leq\exp\big{(}-\Theta(n^{\zeta_{\mathrm{long}}})\big{)}$. We apply
this coupling _after_ proving the LLN, which allows us to choose any
$\rho<\theta$.

The Law of Large Numbers is a crucial ingredient to make this sketch work. The
LLN ensures that local giants in subboxes exist and have the right size. We
first establish the existence of the giant via two multi-scale renormalisation
schemes. To obtain the right size for the giant, it suffices to prove an upper
bound on the cluster-size decay
$\mathbb{P}(k\leq|{\mathcal{C}}_{n}(0)|,0\notin{\mathcal{C}}_{n}^{{\scriptscriptstyle(1)}})$
in finite boxes [44, 48].

_Cluster-size decay and second-largest component._ In our third main result,
we prove that $\zeta_{\star}$ also governs the cluster-size decay of the
origin and the size of the second-largest connected component
$|{\mathcal{C}}_{n}^{\scriptscriptstyle(2)}|$. In [48], we already showed that
both sizes are determined by $\zeta_{\star}$ for some parameter settings of
spatial inhomogeneous percolation models. In this paper, in Theorems 2.9 and
2.10, we prove the same relation for complementary parameter settings.
Combining the present paper and [48], we obtain the following result. Here,
${\mathcal{C}}(0)$ is the cluster of the origin in the model on
${\mathbb{R}}^{d}$.

######  Meta-theorem 1.3 (Cluster-size decay and the second-largest
component).

Consider a supercritical spatial inhomogeneous percolation model with
$\zeta_{\mathrm{long}}>(d-1)/d$. Assume that the expected downward vertex
boundary in (1.4) has size $\Theta(n^{\zeta_{\star}})$. There exist constants
$C\geq c>0$ such that for all $k\geq 1$,

$\displaystyle-C\leq\frac{1}{k^{\zeta_{\star}}}\log\mathbb{P}\big{(}k<|{\mathcal{C}}(0)|<\infty\big{)}\leq-c,\qquad\mathbb{P}\bigg{(}c\leq\frac{|{\mathcal{C}}_{n}^{{\scriptscriptstyle(2)}}|}{(\log
n)^{1/\zeta_{\star}}}\leq C\bigg{)}\overset{n\to\infty}{\longrightarrow}1.$
(1.7)

When the expected downward vertex boundary has slowly-varying correction
factors, (potentially different) slowly-varying correction factors appear in
the lower bound.

For long-range percolation, Crawford and Sly proved a polylogarithmic upper
bound on ${\mathcal{C}}_{n}^{{\scriptscriptstyle(2)}}$ in [24] with some
unspecified exponent. 1.3 finds the correct exponent of this polylog. For
supercritical NNP and other homogeneous percolation models, surface-tension-
driven behavior for the speed of the lower tail, for the cluster-size decay,
and for the second-largest component is known, see Pisztora [69]. Moreover,
when $\zeta_{\mathrm{long}}<(d-1)/d$ (equivalently $\zeta_{\star}=(d-1)/d$),
we proved in [49] that 1.3 holds for long-range percolation with high edge-
density. That is, for (high edge-density) LRP with $\alpha>1+1/d$, the
cluster-size decay and the size of the second-largest component are both
driven by surface tension.

_Another exponent determining the presence of a supercritical phase._ Combined
with [48], this paper completes the following picture:
$\zeta_{\star}=\max(\zeta_{\mathrm{long}},(d-1)/d)$ in (1.4) is the correct
generalization of the surface-tension exponent $(d-1)/d$ for supercritical
spatial inhomogeneous percolation models. It governs the size of the second-
largest component, the connected component containing a vertex at the origin,
and the lower tail of large deviations of the giant component.

The value of $\zeta_{\mathrm{long}}$, defined in (1.5), is related to the
_effective decay exponent_ $\delta_{\mathrm{eff}}$ defined in [47]. In words,
$2-\delta_{\mathrm{eff}}$ measures the size of the “long-edge” _edge_
-boundary of a large box. To define it, say that $u\in\Lambda_{n}\times[a,b]$
if its location $x_{u}$ is in $\Lambda_{n}$, and its mark $w_{u}$ is in the
interval $[a,b]$, and let $w_{n}^{\scriptscriptstyle\max}$ denote the maximal
_expected_ mark of a vertex in $\Lambda_{n}$.

$2-\delta_{\mathrm{eff}}=\lim_{n\to\infty}\frac{\log\mathbb{E}\Big{[}\big{|}\big{\\{}\text{edges
between }\Lambda_{n/2}\times[0,w_{n}^{\scriptscriptstyle\max}]\text{ and
}\Lambda_{n}^{\complement}\times[0,w_{n}^{\scriptscriptstyle\max}]\big{\\}}\big{|}\Big{]}}{\log
n}.$ (1.8)

When $2-\delta_{\mathrm{eff}}>0$ and $d=1$, [47] proves that the models
studied here admit a supercritical phase, i.e., $\beta_{c}<\infty$. If
$2-\delta_{\mathrm{eff}}<0$ and $d=1$, there is no supercritical phase [47].
For dimensions $d\geq 2$, $\beta_{c}<\infty$ holds in spatial inhomogeneous
percolation models, since such models at high edge-density dominate
supercritical random geometric graphs or Bernoulli bond percolation on
${\mathbb{Z}}^{d}$. Further, when $2-\delta_{\mathrm{eff}}>0$, in this model
class annulus-crossing probabilities do not decay with the size of the
annulus. This is denoted by $\hat{\lambda}_{c}=0$ in the recent works in [46,
47].

By its definition in (1.5), $\zeta_{\mathrm{long}}$ describes the size of the
“long-edge” downward _vertex_ -boundary. Hence, $2-\delta_{\mathrm{eff}}$ has
the same sign as $\zeta_{\mathrm{long}}$ throughout the model class. Combining
this observation with the results in [46, 47], positivity/negativity of
$\zeta_{\star}=\max(\zeta_{\mathrm{long}},(d-1)/d)$ also gives finiteness of
$\beta_{c}$ and $\hat{\lambda}_{c}=0$ in this model class.

The difference between $\zeta_{\mathrm{long}}$ and $2-\delta_{\mathrm{eff}}$
becomes apparent as soon as degrees are inhomogeneous. High-degree vertices
can have many edges leaving the box. Edges leaving the maximal vertex mark in
$\Lambda_{n}$ can form the dominating contribution to the _edge_ -boundary. In
this case, the formula in (1.8) is sensitive to the mark truncation and to the
actual presence of the high-mark vertex. This is expressed in the non-
concentration of the size of the edge-boundary around
$\Theta(n^{2-\delta_{\mathrm{eff}}})$. On the contrary, the size of the
downward vertex boundary is robust to random fluctuations of the maximal
degree, and its size concentrates around $\Theta(n^{\zeta_{\mathrm{long}}})$.
Summarizing, we observe that regarding presence/absence of supercritical
phase, $\delta_{\mathrm{eff}}$ may be replaced by $\zeta_{\star}$ (or
$\zeta_{\mathrm{long}}$), and that $\zeta_{\star}$ also drives the behaviour
of the three important distributions mentioned above in Meta-theorems 1.2 and
1.3. In the following section we formalize Meta-theorems 1.1–1.3 that answer
the question (Q).

##  2\. Formal statements of model and main results

###  2.1. Kernel-based spatial random graphs

We give a formal definition of a large class of spatial inhomogeneous
percolation models. This class appeared under various names in the literature.
The first general version of the model appeared in [52], called _general
geometric inhomogeneous random graphs_ , and independently in [36] where it
was called _weight-dependent random connection model_. Afterwards, it was
called _spatial inhomogeneous random graphs_ in [73]. Due to the important
role of a _kernel function_ driving the connection probabilities, we called
them _kernel-based spatial random graphs_ in [48]. Since this paper ties in
with [48], we keep this last name here. This model class includes classical
homogeneous models such as Bernoulli bond percolation on ${\mathbb{Z}}^{d}$
[17], long-range percolation [71], and random geometric graphs [33, 41]. It
also includes (degree-) inhomogeneous models such as hyperbolic random graphs
[54], the Poisson-Boolean model with random radii [42], geometric
inhomogeneous random graphs [16], scale-free percolation [27], the age-
dependent random connection model [35], and the scale-free Gilbert model [43].
We give now a formal definition.

######  Definition 2.1 (Kernel-based spatial random graphs (KSRG)).

Fix a dimension $d\geq 1$. A KSRG is then a random graph defined as follows.
Let the vertex set $V$ be formed by an ergodic point process: either
${\mathbb{Z}}^{d}$ or a unit-intensity Poisson point process (PPP) on
${\mathbb{R}}^{d}$. Given $V$, we equip each vertex $u\in V$ with an
independent mark $w_{u}\geq 1$ following distribution $F_{W}$. Let
$\kappa:{\mathbb{R}}_{+}^{2}\to{\mathbb{R}}_{+}$ be a symmetric function,
called the kernel function. Let $\varphi:{\mathbb{R}}_{+}\to[0,1]$ be non-
decreasing, called the profile function, and let $\beta>0$. Conditionally on
the realization of the marked vertex set
${\mathcal{V}}:=\\{(x_{u},w_{u})\\}_{u\in
V}\subset{\mathbb{R}}^{d}\times{\mathbb{R}}_{+}$, the edge $\\{u,v\\}\in
V^{2}$ is present in the edge-set ${\mathcal{E}}$ independently of other edges
with probability

$\mathrm{p}(u,v):=\mathbb{P}_{W,\kappa,\varphi,\beta}\big{(}u\text{ connected
by an edge to
}v\mid{\mathcal{V}}\,\big{)}=\varphi\Big{(}\beta\cdot\frac{\kappa(w_{u},w_{v})}{\|x_{u}-x_{v}\|^{d}}\Big{)}.$
(2.1)

We denote the obtained infinite graph by
${\mathcal{G}}=({\mathcal{V}},{\mathcal{E}})$, and by
${\mathcal{G}}_{n}=({\mathcal{V}}_{n},{\mathcal{E}}_{n})$ the graph induced by
vertices in $\Lambda_{n}:=[-n^{1/d}/2,n^{1/d}/2]^{d}$. We write
${\mathcal{C}}_{n}^{{\scriptscriptstyle(i)}}$ for the $i$th largest component
of ${\mathcal{G}}_{n}$, and ${\mathcal{C}}_{n}(0)$ and ${\mathcal{C}}(0)$ for
the component containing a vertex at the origin in ${\mathcal{G}}_{n}$ and in
${\mathcal{G}}$, respectively. We write $\mathbb{P}^{\scriptscriptstyle x}$
for the Palm-measure when the vertex set of a unit-intensity Poisson point
process is conditioned to contain a vertex at location $x\in{\mathbb{R}}^{d}$
with unknown mark.

We omit the subscripts $W,\kappa,\varphi$ of $\mathbb{P}$ as they are fixed
and always clear from the context. Sometimes we emphasize the dependency of
$\mathbb{P}$ on the edge-density parameter $\beta$ by writing
$\mathbb{P}_{\beta}$. We define

$\theta=\theta(\beta):=\mathbb{P}_{\beta}^{{\scriptscriptstyle
0}}(0\leftrightarrow\infty)=\mathbb{P}_{\beta}^{\scriptscriptstyle
0}(|{\mathcal{C}}(0)|=\infty)>0.$ (2.2)

Then, the critical edge-density $\beta_{c}$ is given by

$\beta_{c}:=\inf\big{\\{}\beta\geq 0:\theta(\beta)>0\big{\\}}.$ (2.3)

We call the model subcritical if $\beta<\beta_{c}$, critical if
$\beta=\beta_{c}$, and supercritical if $\beta>\beta_{c}$. For a fixed choice
of $W,\varphi,\kappa$, and $d$, some phases may not exist [37, 38].

Definition 2.1 allows for general kernel and profile functions. In the rest of
the paper we restrict them to a few choices that are commonly used, and which
cover the specific models in the introduction [16, 27, 35, 42, 43, 54, 71].
Our results remain valid for (or can be extended to) other sufficiently
similar kernels, profile functions, and mark distributions. Including slowly
varying functions is possible, but would cause lower-order correction terms in
the results below. We follow the notation of our previous work [48]. We write
for any $a,b,\in{\mathbb{R}}$, $a\wedge b$ for $\min(a,b)$, and $a\vee b$ for
$\max(a,b)$.

######  Assumption 2.2.

We assume that the mark distribution is either $W_{v}\equiv 1$ for all $v$, or
a Pareto distribution with parameter $\tau>2$:

$1-F_{W}(w):=\mathbb{P}\big{(}W_{v}\geq w\big{)}=w^{-(\tau-1)},\qquad w\geq
1.$ (2.4)

We assume that the profile function $\varphi$ is either threshold or
polynomial: for constants $p\in(0,1]$, $\alpha>1$, let

$\varphi_{\mathrm{thres}}(s):=p\mathds{1}_{\\{s\geq 1\\}},\qquad\text{or
}\qquad\varphi_{\mathrm{pol}}(s):=p\big{(}1\wedge s^{-\alpha}\big{)},$ (2.5)

and we assume that the kernel $\kappa$ is one of the following:

$\kappa_{\mathrm{sum}}(w_{1},w_{2})=\big{(}w_{1}^{1/d}+w_{2}^{1/d}\big{)}^{d},\qquad\text{or}\qquad\kappa_{\sigma}(w_{1},w_{2})=(w_{1}\vee
w_{2})(w_{1}\wedge w_{2})^{\sigma},$ (2.6)

for a parameter $\sigma\geq 0$. By abuse of notation, when $W_{v}\equiv 1$ for
all $v\in V$ we say that $\tau=\infty$; when
$\varphi=\varphi_{\mathrm{thres}}$ we say that $\alpha=\infty$; when
$\kappa=\kappa_{\mathrm{sum}}$ we say that $\sigma=0$.

Assumption 2.2 ensures that the model is parametrized so that the expected
degree of a vertex is proportional to its mark when $\sigma\leq\tau-1$. The
restrictions $\tau>2$ and $\alpha>1$ ensure that the graph is locally finite.
Increasing $\tau$ and/or $\alpha$ leads to less inhomogeneity (lighter-tailed
degrees and fewer long edges, respectively). All our results below for
$\tau=\infty$ except Theorem 2.4 can be directly extended to all distributions
$F_{W}$ with lighter tail than any power-law in (2.4). The parameter $p$ in
(2.5) makes the model closed under Bernoulli percolation of the edges, while
the parameter $\sigma$ controls assortativity: increasing $\sigma$ makes it
more likely that high-degree vertices are connected by an edge. The parameter
$\sigma$ allows us to continuously interpolate between well-known models that
are special cases. Therefore, we call $\kappa_{\sigma}$ the _interpolation
kernel_ , see more in [48].

Our earlier work [48] as well as the papers [36, 73] describe how the above
models can be reconstructed as special cases. In short, in long-range
percolation, the vertex set is ${\mathbb{Z}}^{d}$, and the marks are a
constant, i.e., $\tau=\infty$, and $\alpha<\infty$. The kernel $\kappa_{1}$,
corresponding to the product $w_{1}w_{2}$, is used to obtain hyperbolic random
graphs, geometric inhomogeneous random graphs, and scale-free percolation [16,
27, 54], $\kappa_{\tau-2}$ to obtain the age-dependent random connection model
[35], and $\kappa_{\mathrm{sum}}$, with additionally $p=1$, to obtain the
(soft) Poisson–Boolean model [42]. The soft Poisson–Boolean model uses the
polynomial profile $\varphi_{\mathrm{pol}}$, while the classical
Poisson–Boolean model uses the threshold profile $\varphi_{\mathrm{thres}}$.
The kernel $\kappa_{0}$ is sometimes called the max-kernel, and is closely
related to $\kappa_{\mathrm{sum}}$, as
$\kappa_{0}\leq\kappa_{\mathrm{sum}}\leq 2\kappa_{0}$. Since the latter two
kernels are qualitatively similar, we simply set $\sigma=0$ for
$\kappa_{\mathrm{sum}}$; we never prove333The corresponding results are
straightforward, in lower/upper bounds we use the corresponding bound from
$\kappa_{0}\leq\kappa_{\mathrm{sum}}\leq 2\kappa_{0}$, and constant factors do
not matter in our calculations. explicitly results for
$\kappa_{\mathrm{sum}}$.

###  2.2. Dominant connection types

To make Statements 1.1–1.3 formal, we give the values of $\zeta_{\star}$ in
(1.4) and $\zeta_{\mathrm{long}}$ in (1.5) in terms of the model parameters
for KSRGs satisfying Assumption 2.2. We follow the notation of [48], and write
$\zeta_{\star}$ and $\zeta_{\mathrm{long}}$ as a maximum of simple expressions
of the parameters $d,\tau,\alpha,\sigma$. As we will show below, they take the
form

$\zeta_{\star}=\max(\zeta_{\mathrm{short}},\zeta_{\mathrm{ll}},\zeta_{\mathrm{hl}},\zeta_{\mathrm{hh}}),\qquad\zeta_{\mathrm{long}}=\max(\zeta_{\mathrm{ll}},\zeta_{\mathrm{hl}},\zeta_{\mathrm{hh}}).$
(2.7)

Each term inside the maxima describes the expected number of vertices with a
certain type of downward edge leaving $\Lambda_{n}$. Each of these types
contributes to the downward vertex boundary of ${\mathcal{V}}\cap\Lambda_{n}$
in (1.4). If the maximum is unique, the size of the downward vertex boundary
is dominated by exactly one of these four types. If the maximum is non-unique,
we say that the parameters are on a phase-transition boundary. We provide some
back-of-the-envelope calculations to compute $\zeta_{\star}$ in (1.4) and
$\zeta_{\mathrm{long}}$ in (1.5) when $\alpha<\infty$. When $\alpha=\infty$,
one has to take the limit in the expressions below as $\alpha\to\infty$. The
precise computations are given in [48].

_Short edges_ – of constant length: there are roughly $\Theta(n^{(d-1)/d})$
vertices incident to such edges crossing the boundary of $\Lambda_{n}$ in
(1.4), giving the ‘surface-tension’ exponent

$\zeta_{\mathrm{short}}:=(d-1)/d.$ (2.8)

Next, we start counting ‘long edges’, that is, edges of length
$\Theta(n^{1/d})$ crossing the boundary of $\Lambda_{n}$, and thus also
contributing to $\zeta_{\mathrm{long}}$ in (1.5). These edges fall into three
categories.

_Low-low edges_ connect two vertices of constant (low) mark between
$\Lambda_{n/2}$ and $\Lambda_{n}^{\complement}$. The expected number of low-
low edges is $\Theta(n\cdot n\cdot n^{-\alpha})$, and this is the same as the
number of low-mark vertices having a low-low edge. Abbreviating ‘ _low_ -mark
to _low_ -mark’ by ll, we obtain

$\zeta_{\mathrm{ll}}:=2-\alpha.$ (2.9)

The other two types describe long edges incident to ‘high-mark’ vertices in
$\Lambda_{n/2}$. We say a vertex has a high mark if its mark is at least
$n^{\gamma_{\mathrm{long}}}$, where

$\gamma_{\mathrm{long}}:=\min\Big{\\{}\gamma\geq
0:\liminf_{n\to\infty}\mathbb{E}^{\scriptscriptstyle 0}\big{[}|\\{\mbox{edges
between }0\mbox{ and
}\Lambda_{n}^{\complement}\\}|\,\big{|}\,(0,n^{\gamma})\in{\mathcal{V}}\big{]}>0\Big{\\}}.$
(2.10)

Then, a constant proportion of vertices of mark at least
$n^{\gamma_{\mathrm{long}}}$ inside $\Lambda_{n/2}$ contributes to the vertex
boundary. By the Pareto distribution of the marks in (2.4), there are
$\Theta(n^{1-\gamma_{\mathrm{long}}(\tau-1)})$ many high-mark vertices inside
$\Lambda_{n/2}$. The values $\tau$ in (2.4), $\sigma$ in (2.6), and $\alpha$
in (2.5) jointly determine the value of $\gamma_{\mathrm{long}}$. We compute
two possible values of $\gamma_{\mathrm{long}}$, that then yield the two
remaining types.

_High-low edges_ are dominant if the other end-vertex of an edge emanating
from vertex $(0,n^{\gamma})$ to $\Lambda_{n}^{\complement}$ typically has
constant mark. There are $\Theta(n)$ constant-mark vertices at distance
$\Theta(n^{1/d})$. By the connection probability in (2.1) with
$\kappa_{\sigma}$ or $\kappa_{\mathrm{sum}}$ from (2.6) and
$\varphi_{\mathrm{pol}}$ from (2.5), for $\gamma>0$, the expected number of
edges between vertex $(0,n^{\gamma})$ and constant-mark vertices in
$\Lambda_{n}^{\complement}$ is roughly $n(n^{\gamma}/n)^{\alpha}$. As required
in (2.10), this expression is of constant order when

$\gamma=\gamma_{\mathrm{hl}}:=1-1/\alpha,$ (2.11)

which leads to

$\zeta_{\mathrm{hl}}:=1-\gamma_{\mathrm{hl}}(\tau-1)=(\tau-1)/\alpha-(\tau-2).$
(2.12)

_High-high edges_ occur dominantly if the other end-vertex of an edge
emanating from vertex $(0,n^{\gamma})$ in (2.10) typically has a high mark.
There are $\Theta(n^{1-\gamma(\tau-1)})$ many vertices of mark
$\Omega(n^{\gamma})$ at distance $\Theta(n^{1/d})$ from $0$. Using the
interpolation kernel in (2.6), the expected number of edges between
$(0,n^{\gamma})$ and these other vertices is roughly
$n^{1-\gamma(\tau-1)}(n^{\gamma(\sigma+1)}/n)^{\alpha}$. This expression is of
constant order when

$\gamma=\gamma_{\mathrm{hh}}:=\begin{dcases}\frac{1-1/\alpha}{\sigma+1-(\tau-1)/\alpha},&\text{if
}\tau\leq\sigma+2,\\\ \frac{1}{\sigma+1},&\text{if
}\tau>\sigma+2,\end{dcases}$ (2.13)

which leads to

$\zeta_{\mathrm{hh}}:=1-\gamma_{\mathrm{hh}}(\tau-1)=\begin{dcases}\frac{\sigma+2-\tau}{\sigma+1-(\tau-1)/\alpha},&\text{if
}\tau\leq\sigma+2,\\\ \frac{\sigma+2-\tau}{\sigma+1},&\text{if
}\tau>\sigma+2.\end{dcases}$ (2.14)

We will never use the second row for $\gamma_{\mathrm{hh}}$ and
$\zeta_{\mathrm{hh}}$: $\zeta_{\mathrm{hh}}$ is negative there, and some other
connectivity type is dominant. The choice of $\gamma_{\mathrm{hh}}$ in this
second row ensures continuity and monotonicity in the parameters. High-low
connections can be dominant when $\sigma$ is small, for example in the age-
dependent random connection model and the soft Poisson–Boolean model. The
high-high type of connection can be dominant for large values of $\sigma$,
e.g. in geometric inhomogeneous random graphs and random hyperbolic graphs.
The infimum in (2.10) indicates that $\gamma_{\mathrm{long}}$ is the minimum
of $\gamma_{\mathrm{hl}}$ and $\gamma_{\mathrm{hh}}$, and the switch is when
the denominator $\sigma+1-(\tau-1)/\alpha$ crosses $1$. Indeed, the following
claim makes the above back-of-the-envelope computations formal: the integrals
in the definitions of $\zeta_{\star}$ in (1.4) and $\zeta_{\mathrm{long}}$ in
(1.5) are dominated by the above four cases. Vertices incident to edges of
intermediate length $\ell_{n}$ ($1\ll\ell_{n}\ll n^{1/d}$) crossing
$\Lambda_{n}$ do not significantly contribute to the vertex boundary.

######  Claim 2.3 (Phases of $\zeta_{\star}$, [48, Lemma 7.6]).

Consider any KSRG with kernel and profile satisfying Assumption 2.2. Then

$\displaystyle\zeta_{\mathrm{long}}=\max(0,\zeta_{\mathrm{ll}},\zeta_{\mathrm{hl}},\zeta_{\mathrm{hh}}),\qquad\zeta_{\star}=\max(\zeta_{\mathrm{short}},\zeta_{\mathrm{long}}).$
(2.15)

The values of $\zeta_{\star}$ and $\zeta_{\mathrm{long}}$ do not depend on
$p,\beta$, and $\zeta_{\mathrm{long}}$ not even on $d$. We refer to [48] for
phase diagrams that illustrate for which values of the parameters
$(\tau,\alpha,\sigma,d)$ the four different connection types are dominant. We
call the areas in the parameter space corresponding to unique dominant types
the _phases_ of $\zeta_{\star}$. On the boundaries of these phases, multiple
connection types are dominant simultaneously. These cause poly-logarithmic
factors in the expectation in the numerator of $\zeta_{\star}$ in (1.4). These
factors vanish in the limit, but they do appear in some of our lower bounds.
So, for a given parameter setting of $\tau,\alpha,\sigma,d$, we let
$\mathfrak{m}_{\mathcal{Z}}$ count the number of dominant connection types.
Formally, we define the _multiplicity_ of the maximum of
${\mathcal{Z}}:=\\{\zeta_{\mathrm{ll}},\zeta_{\mathrm{hl}},\zeta_{\mathrm{hh}},\zeta_{\mathrm{short}}\\}$
as

$\mathfrak{m}_{\mathcal{Z}}:=\sum_{\zeta\in{\mathcal{Z}}}\mathbbm{1}{\\{\zeta=\max({\mathcal{Z}})\\}}.$
(2.16)

We now formalize Meta-theorems 1.1, 1.2, and 1.3 to answer the question (Q).

###  2.3. Upper tail of large deviations

First we state the upper tail of the giant’s size for LRP on
${\mathbb{Z}}^{d}$ and Bernoulli bond percolation on ${\mathbb{Z}}^{d}$ (NNP),
making (1.1) precise.

######  Theorem 2.4 (Linear speed in degree-homogeneous models).

Consider long-range percolation or Bernoulli bond percolation on
${\mathbb{Z}}^{d}$ with parameters such that $\theta<1$. For all
$\rho\in(\theta,1)$, there exists $A>0$ such that for all $n\geq 1$,

$-A\leq\frac{1}{n}\log\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|>\rho
n\big{)}\leq-1/A.$

Theorem 2.4 applies for _any_ edge density $\beta$, i.e., regardless of
whether the model is supercritical, subcritical or critical. Linear speed for
the upper tail of large deviations of a closely related quantity is known for
NNP [30, 32]: the number of vertices in the intersection of a finite box and
the infinite component.

We proceed to the upper tail for models with power-law degree distributions,
when the speed is logarithmic, heading towards making Meta-theorem 1.1
precise. At an increased cost of technicality our subsequent results can be
extended to KSRGs on ${\mathbb{Z}}^{d}$; in order to keep the proof simpler,
we refrain from this and restrict to Poisson vertex sets for degree-
inhomogeneous KSRGs, i.e., with $\tau<\infty$. To state the rate function, we
introduce some notation. We write ${\mathcal{C}}(0)$ for the cluster of the
origin in the model on ${\mathbb{R}}^{d}$, and recall from Definition 2.1 that
we use the superscript $x$ when the vertex set has a vertex at location $x$
with unknown mark. Let

$H_{{\mathcal{C}}}(z):=\mathbb{E}^{\scriptscriptstyle
0}[z^{|{\mathcal{C}}(0)|}\mathds{1}_{\\{|{\mathcal{C}}(0)|<\infty\\}}]$

be the probability generating function of the size of ${\mathcal{C}}(0)$
restricted to be finite. The function $H_{{\mathcal{C}}}(z)$ is continuous and
increasing, and has range $(0,1-\theta]$ for $z\in(0,1]$. Hence, the inverse
$H_{{\mathcal{C}}}^{(-1)}(y)$ is well-defined and increasing when
$y\in(0,1-\theta]$. For $\rho\in(\theta,1)$, define

$\mathrm{hubs}(\rho):=\begin{dcases}\frac{\log
H_{{\mathcal{C}}}^{(-1)}\big{(}1-\rho\big{)}}{\log(1-p)},&\text{if }p<1,\\\
1,&\text{if }p=1.\end{dcases}$ (2.17)

The distinction based on $p$ ensures that $\log(1-p)$ is well-defined. We
prove that $\lceil\mathrm{hubs}(\rho)\rceil$ many linear-mark vertices are
required to increase the density of the giant from the typical density
$\theta$ to $\rho$, see Section 3.2 below for intuition. The function
$\mathrm{hubs}(\rho)$ is positive, increasing in $\rho$ and tends to infinity
as $\rho\uparrow 1$: similar to [50], it can be shown that
$\mathrm{hubs}(\rho)=\log(1-\rho)/\log(1-p)+o(1)$ as $\rho$ approaches $1$.
The following theorem gives the rate function for the upper tail. Recall
$\zeta_{\mathrm{long}}$ from (1.5).

######  Theorem 2.5 (Logarithmic speed in degree-inhomogeneous models).

Consider a KSRG satisfying Assumption 2.2 with a unit-intensity Poisson point
process as vertex set and power-law mark distribution with $\tau<\infty$. Fix
$\rho\in(\theta,1)$. There exists $A>0$ such that for all $n\geq 1$,

$\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|>\rho
n\big{)}\leq An^{-(\tau-2)\lceil\mathrm{hubs}(\rho)\rceil}.$ (2.18)

If either the model is supercritical with $\zeta_{\mathrm{long}}>0$, or
$\theta=0$, then there exists $A>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)\lim_{r\downarrow\rho}\lceil\mathrm{hubs}(r)\rceil}.$
(2.19)

The formulation of the either/or above (2.19) excludes critical models from
the lower bound with $\theta(\beta_{c})>0$, where $\beta_{c}$ is the critical
edge-density in (2.3). For KSRGs in general it is unknown when
$\theta(\beta_{c})$ is positive: this may sensitively depend on the short
edges of the model [3, 4]. The preprint [64] by Mönch shows that
$\theta(\beta_{c})=0$ for KSRGs in dimensions $d\geq 2$ with
$\zeta_{\mathrm{long}}>0$.

Combining (2.18) and (2.19) gives that when
$\mathrm{hubs}(\rho)\notin{\mathbb{N}}$, we identify the decay rate of
$\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|>\rho n\big{)}$
up to a constant factor. If $\mathrm{hubs}(\rho)\in{\mathbb{N}}$ and $p<1$,
the lower and upper bounds are no longer of the same order, because the
necessary “wiggle room” in the proof of the lower bound is lost. Nevertheless,
Theorem 2.5 gives logarithmic speed for the upper tail with rate function

$I(\rho):=(\tau-2)\lceil\mathrm{hubs}(\rho)\rceil.$

######  Corollary 2.6 (Rate function for the upper tail).

Consider a KSRG satisfying Assumption 2.2 on a unit-intensity Poisson point
process as vertex set and power-law mark distribution with $\tau<\infty$. If
the model is either supercritical with $\zeta_{\mathrm{long}}>0$ or
$\theta=0$, then for all $\rho\in(\theta,1)$,

$\displaystyle-\inf_{r>\rho}I(r)$
$\displaystyle\leq\liminf_{n\to\infty}\frac{1}{\log
n}\log\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|>\rho
n\big{)}$ (2.20) $\displaystyle\leq\limsup_{n\to\infty}\frac{1}{\log
n}\log\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|>\rho
n\big{)}\leq-\inf_{r\geq\rho}I(r).$

###### Proof.

Since $\mathrm{hubs}(\rho)$ in (2.17) is continuous and non-decreasing, both
bounds follow directly from Theorem 2.5. ∎

When we compare this result to Theorem 2.4 we see that the speed drops from
linear to logarithmic when degree-inhomogeneity enters the models. The
assumption $\zeta_{\mathrm{long}}>0$ in (2.19) reflects the aim to study the
influence of degree and edge-length inhomogeneity in (Q). However,
$\zeta_{\mathrm{long}}>0$ is a technical condition here. It comes from our
bounds for the lower tail, which serves as a tool for proving (2.19).

###  2.4. Lower tail of large deviations

Our next result determines the speed of the lower tail of large deviations of
the giant component for supercritical KSRGs, i.e., when $\beta>\beta_{c}$ in
(2.3). This will make 1.2 precise. Contrary to Bernoulli bond percolation, the
lower tail decays faster than the upper tail when $\tau<\infty$: the speed is
polynomial, with exponent
$\zeta_{\star}=\max(\zeta_{\mathrm{long}},\zeta_{\mathrm{short}})$ where
$\zeta_{\mathrm{short}}=(d-1)/d$ and $\zeta_{\mathrm{long}}$ is defined in
(1.5).$\zeta_{\mathrm{long}}>0$. Recall the definition of $\zeta_{\star}$ from
(1.4), its value from 2.3, and the multiplicity $\mathfrak{m}_{\mathcal{Z}}$
from (2.16).

######  Theorem 2.7 (Speed in the lower tail of large deviations for the
giant).

Consider a supercritical KSRG satisfying Assumption 2.2 with a unit-intensity
Poisson point process as vertex set, or consider supercritical long-range
percolation on ${\mathbb{Z}}^{d}$. Assume that the model satisfies
$\zeta_{\mathrm{long}}>0$. Fix $\rho\in(0,\theta)$. There exists a constant
$A>0$ such that for all $n\geq 1$,

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

The lower bound in Theorem 2.7 is proved in our earlier work [48, Theorem
2.5]. When a single connection type is dominant (i.e.,
$\mathfrak{m}_{\mathcal{Z}}=1$, see Section 2.2), the lower and upper bound on
the right-hand side differ by a constant factor, matching 1.2. For such
parameters, Theorem 2.7 determines the exact _speed_ of large deviations for
the lower tail. When $\mathfrak{m}_{\mathcal{Z}}\in\\{2,3,4\\}$, the bounds
differ by a poly-log factor.

We discuss a few related results. For Bernoulli nearest neighbour percolation
on ${\mathbb{Z}}^{d}$ (NNP), the exponent of the polynomial speed of the lower
tail is $\zeta_{\star}=\zeta_{\mathrm{short}}=(d-1)/d$, see (1.2) and [69]. We
expect that Theorem 2.7 remains true444In dimension $d=1$ there is no lower
tail since the model is subcritical when $\zeta_{\mathrm{long}}<0$, see below
(1.8). also for KSRGs with $\zeta_{\mathrm{long}}\leq 0$ in $d\geq 2$. In view
of (Q), this is beyond the scope of our paper. For Bernoulli NNP on
${\mathbb{Z}}^{2}$ or ${\mathbb{Z}}^{3}$, the works [6] and [21] identify the
_rate function_ of the lower tail for the size of the intersection of the
infinite component with $\Lambda_{n}$. Keep in mind that this is not
necessarily the size of the largest component in $\Lambda_{n}$.

For long-range percolation, Biskup proved in [14] that
$\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|<\delta
n\big{)}\leq\exp(-\Theta(n^{2-\alpha-o(1)}))$ for $\delta>0$ sufficiently
small, which is an almost sharp upper bound, see our comment below 1.2.
Hyperbolic random graphs [31, 54] are equivalent to one-dimensional threshold
geometric inhomogeneous random graphs and are a special instance of the KSRGs
[52] by setting $p=1,\sigma=1,\alpha=\infty$ in Assumption 2.2. Independent of
our work, the recent preprint [15] proves the upper bound
$\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|<\delta
n\big{)}\leq\exp(-\Theta(n^{(3-\tau)/2}))$ for $\delta>0$ sufficiently small.
This is a special case of the upper bound here, and $(3-\tau)/2$ matches the
exponent $\zeta_{\mathrm{hh}}$ in our earlier general lower bound in [48] for
$\alpha=\infty$. In comparison, Theorem 2.7 allows (beyond other kernels) for
$p<1$ and long-range profiles. It also shows that $\delta$ can be chosen
arbitrarily close to $\theta$.

The previous three theorems give the _strong_ Law of Large Numbers as a
corollary for KSRGs with finite-variance degree distributions, which is not
known for (specific) models in the KSRG class555While the result seems
folklore to us for Bernoulli NNP, we could not find a reference for the exact
quantity we look at here. We are also not aware of strong LLN for other models
in the class. . For KSRGs with an infinite-variance mark distribution, we
obtain a weak LLN.

######  Corollary 2.8 (Law of Large Numbers).

Consider either supercritical long-range percolation on ${\mathbb{Z}}^{d}$
with $\zeta_{\mathrm{long}}>0$, or Bernoulli nearest neighbour bond
percolation on ${\mathbb{Z}}^{d}$, or a supercritical KSRG satisfying
Assumption 2.2 on a unit-intensity PPP with $\tau>3$ and
$\zeta_{\mathrm{long}}>0$. Then

$\frac{|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|}{n}\overset{\text{a.s.}}{\longrightarrow}\theta=\theta(\beta,p,\alpha,d),\qquad\mbox{as
}n\to\infty.$ (2.22)

For a supercritical KSRG satisfying Assumption 2.2 on a unit-intensity PPP
with $\zeta_{\mathrm{long}}>0$ and $\tau\in(2,3]$,

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

###### Proof.

For NNP, a lower bound follows from the lower tail of large deviations by
Pisztora in [69], an upper bound follows from Theorem 2.4. The weak law of
large numbers follows directly from Theorem 2.4, Theorem 2.5 and Theorem 2.7.
The error terms are summable for LRP, NNP, and KSRGs with $\tau>3$ (in
(2.18)): an application of the Borel–Cantelli Lemma gives the strong law,
while the weak law still holds also for KSRGs with $\tau\in(2,3]$. ∎

_Related work on LLN._ Fountoulakis and Müller in [31] prove the weak LLN for
the giant in hyperbolic random graphs, which is a threshold one-dimensional
KSRG with infinite variance degrees satisfying $\zeta_{\mathrm{hh}}>0$, and is
contained here in (2.23). In [48, Corollary 2.3], we extended the weak LLN of
[31] to general KSRGs on PPPs with $\zeta_{\mathrm{hh}}>0$. Finally, for
general long-range percolation models with $\zeta_{\mathrm{long}}\leq 0$,
Bäumler in [11, Theorem 1.6] recently showed that
$\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|\geq\rho
n\big{)}\to 1$ for any $\rho\in(0,\theta)$. Below, we first prove a weak LLN
when
$\zeta_{\mathrm{long}}=\max(\zeta_{\mathrm{hh}},\zeta_{\mathrm{hl}},\zeta_{\mathrm{ll}})>0$.
This weak LLN serves as a tool to proving Theorems 2.5 and 2.7. When
simultaneously $\zeta_{\mathrm{hh}}\leq 0$ and
$\max(\zeta_{\mathrm{hl}},\zeta_{\mathrm{ll}})>0$, the LLN requires new
methods compared to the methods in [31, 48]. These theorems give the strong
law in some cases.

###  2.5. Cluster-size decay and second-largest component

We proceed to formalizing 1.3. We start with the cluster-size decay of the
origin. Let ${\mathcal{C}}(0)$ denote the cluster of the origin in the
infinite model. Recall $\zeta_{\mathrm{long}}$ from (1.5),
$\zeta_{\mathrm{short}}=(d-1)/d$ and $\mathfrak{m}_{\mathcal{Z}}$ from (2.16).

######  Theorem 2.9 (Cluster-size decay).

Consider a supercritical KSRG satisfying Assumption 2.2 with a unit-intensity
Poisson point process as vertex set, or consider supercritical long-range
percolation on ${\mathbb{Z}}^{d}$. Assume that the model satisfies
$\zeta_{\mathrm{long}}>\max\\{0,\zeta_{\mathrm{hh}}\\}$. Then there exists a
constant $A>0$ such that for all $k\geq 1$ and $n\in[Ak,\infty]$,

$\log\mathbb{P}^{\scriptscriptstyle 0}\big{(}|{\mathcal{C}}_{n}(0)|\geq
k,\;0\notin{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}\big{)}\in\big{(}-Ak^{\max(\zeta_{\mathrm{long}},\zeta_{\mathrm{short}})}(\log
k)^{\mathfrak{m}_{\mathcal{Z}}-1},-\tfrac{1}{A}k^{\zeta_{\mathrm{long}}}\big{)}.$
(2.24)

The result remains valid when $\zeta_{\mathrm{long}}=\zeta_{\mathrm{hh}}$ and
$\sigma\leq\tau-1$ [48, Theorem 2.2(i),(ii)]. When
$\zeta_{\mathrm{long}}=\zeta_{\mathrm{hh}}$ and $\sigma>\tau-1$, the lower
bound on the right-hand side remains valid while the upper bound changes to
$-(1/A)k^{1/(\sigma+1-(\tau-1)/\alpha)}$ [48, Theorem 2.2(i),(iii)].

We proved the bounds for the case $\zeta_{\mathrm{long}}=\zeta_{\mathrm{hh}}$
in our earlier work [48]: then high-high connections are dominant. Theorem 2.9
extends the result for the phases when $\zeta_{\star}$ is either
$\zeta_{\mathrm{ll}}$ in (2.9) and/or $\zeta_{\mathrm{hl}}$ in (2.12). This
corresponds to parameter settings where long-range connections incident to at
least one vertex of small mark dominate the expectation in (1.4). The
techniques for these latter phases are different from those in [48], see
Remark 3.2 on the details.

The lower and upper bound in (2.24) are of the same order if the maximum in
${\mathcal{Z}}$ is unique _and_ $\zeta_{\mathrm{long}}>(d-1)/d$ (excluding the
sub-optimal bound for $\zeta_{\mathrm{long}}=\zeta_{\mathrm{hh}}$ and
$\sigma>\tau-1$). If the maximum is non-unique, i.e.,
$\mathfrak{m}_{\mathcal{Z}}\in\\{2,3,4\\}$ and
$\zeta_{\mathrm{long}}\geq(d-1)/d$, then the two bounds differ by a polylog
factor. The exponent of $k$ in the two bounds only differs when $(d-1)/d$ is
_strictly larger_ than $\zeta_{\mathrm{long}}$. We conjecture that the lower
bound is sharp, and that the correct exponent must be
$\zeta_{\mathrm{short}}=(d-1)/d$ generally in the KSRG class in this regime.
The additional restriction that $\sigma\leq\tau-1$ when
$\zeta_{\mathrm{hh}}=\zeta_{\mathrm{long}}$ comes as a technical assumption
from [48].

_Related work on cluster-size decay_. There are many percolation models where
the cluster-size decay is determined by surface tension. For Bernoulli nearest
neighbour bond percolation on ${\mathbb{Z}}^{d}$, a series of papers [2, 40,
51, 55] showed that the exponent of the decay is $\zeta_{\mathrm{short}}$,
i.e., for some $C_{p}\geq c_{p}>0$,

$\displaystyle-C_{p}\leq\liminf_{k\to\infty}$
$\displaystyle\frac{1}{k^{(d-1)/d}}\log\mathbb{P}\big{(}k<|{\mathcal{C}}(0)|<\infty\big{)}$
(2.25)
$\displaystyle\leq\limsup_{k\to\infty}\frac{1}{k^{(d-1)/d}}\log\mathbb{P}\big{(}k<|{\mathcal{C}}(0)|<\infty\big{)}\leq-
c_{p}.$

For dimension $d\in\\{2,3\\}$, the constants $C_{p}=c_{p}$ above are known,
and determined by the Wulff construction [6, 21]. For Bernoulli percolation on
more general, transitive infinite graphs with polynomial ball-growth, [23, 45]
obtain similar bounds. In [49], we derived (2.25) for high edge-density long-
range percolation when $\zeta_{\star}=(d-1)/d>2-\alpha$, i.e., when short-
range edges are dominant. Our techniques in [49] differ from those here and in
[48], see more on the difficulties when $(d-1)/d=\zeta_{\star}$ in Remark 3.1
below.

_The second-largest component._ Our last result identifies the size
$|{\mathcal{C}}_{n}^{\scriptscriptstyle(2)}|$ of the second largest component
in KSRGs in boxes of volume $n$.

######  Theorem 2.10 (Second-largest component).

Consider the same setting as in Theorem 2.9. There exist constants
$A,\delta>0$ such that for all $n\geq 1$, with probability at least
$1-n^{-\delta}$,

$\bigg{(}\frac{\log n}{A(\log\log
n)^{\mathfrak{m}_{\mathcal{Z}}-1}}\bigg{)}^{1/\max(\zeta_{\mathrm{long}},\zeta_{\mathrm{short}})}\leq|{\mathcal{C}}_{n}^{\scriptscriptstyle(2)}|\leq(A\log
n)^{1/\zeta_{\mathrm{long}}}.$

The result remains valid when $\zeta_{\mathrm{long}}=\zeta_{\mathrm{hh}}$ and
$\sigma\leq\tau-1$ [48, Theorem 2.4(i),(ii)]. When
$\zeta_{\mathrm{long}}=\zeta_{\mathrm{hh}}$ and $\sigma>\tau-1$, the lower
bound on the right-hand side remains valid while the upper bound changes to
$(A\log n)^{\sigma+1-(\tau-1)/\alpha}$ [48, Theorem 2.4(i),(iii)].

Theorem 2.10 accompanies the results from [48, 49] exactly as Theorem 2.9. The
lower and upper bounds are matching exactly when the bounds on the cluster-
size decay are matching, and differ by a “poly-loglog” factor on phase
transition boundaries (excluding the sub-optimal bound for
$\zeta_{\mathrm{long}}=\zeta_{\mathrm{hh}}$ and $\sigma>\tau-1$). Since the
size of ${\mathcal{C}}_{n}^{\scriptscriptstyle(2)}$ is polylogarithmic in $n$,
this theorem implies uniqueness of the giant component. Moreover, it makes a
result by Crawford and Sly [24] sharp: that paper proves a polylogarithmic
upper bound on $|{\mathcal{C}}_{n}^{\scriptscriptstyle(2)}|$ for long-range
percolation with unidentified exponent.

Notation. Let $G=(V,E)$ be a graph. We write $u\leftrightarrow_{G}v$ if there
exists a path between $u,v\in V$, and $|A|$ for the number of vertices in a
set $A$ of vertices, whereas for two subsets $V_{1},V_{2}$ containing (marked)
vertices we write $V_{1}\sim_{G}V_{2}$ if there exist vertices $v_{1}\in
V_{1},v_{2}\in V_{2}$ such that $v_{1}$ is connected by an edge to $v_{2}$ (in
case $V_{1}=\\{v_{1}\\}$ and/or $V_{2}=\\{v_{2}\\}$ we write simply
$v_{1}\sim_{G}V_{2}$, or $v_{1}\sim_{G}v_{2}$, respectively). We also write
$V_{1}\nsim_{G}V_{2}$ if there is no edge between vertex pairs in $V_{1}\times
V_{2}$. If the graph $G$ is clear from the context we omit the subscript. If
${\mathcal{H}}=({\mathcal{V}}_{\mathcal{H}},{\mathcal{E}}_{\mathcal{H}})$ is
(a subgraph of) a KSRG ${\mathcal{G}}=({\mathcal{V}},{\mathcal{E}})$, we write
${\mathcal{H}}[a,b)$ for the induced subgraph of ${\mathcal{H}}$ on vertices
with mark in the half-open interval $[a,b)$, denoted by
${\mathcal{V}}_{\mathcal{H}}[a,b)$. For a set $B\subseteq{\mathbb{R}}^{d}$, we
write ${\mathcal{V}}_{B}$ for the vertices with location in $B$. If
$B=\Lambda_{n}=[-n^{1/d}/2,n^{1/d}/2]^{d}$, we simply write
${\mathcal{V}}_{n}$. For two random variables $X$ and $Y$, we write
$Y\preccurlyeq X$, if $X$ stochastically dominates $Y$, that is,
$\mathbb{P}(X\geq x)\geq\mathbb{P}(Y\geq x)$ for all $x\in{\mathbb{R}}$. For
two random graphs $G_{1}=(V_{1},E_{1}),G_{2}=(V_{2},E_{2})$ we say that
$G_{1}$ stochastically dominates $G_{2}$ if there exists a coupling such that
$\mathbb{P}\big{(}E_{1}\supseteq E_{2},V_{1}\supseteq V_{2}\big{)}=1$. A
sequence of events $({\mathcal{A}}_{n})_{n\geq 1}$ holds with high probability
(whp) if $\mathbb{P}({\mathcal{A}}_{n})\to 1$ as $n\to\infty$. We use standard
Landau notation for asymptotics of functions: for two not necessarily positive
real functions $f(n),g(n)$ we say that $f=O(g)$ if
$\limsup_{n\to\infty}|f(n)/g(n)|<\infty$, $f=o(g)$ if
$\lim_{n\to\infty}|f(n)/g(n)|=0$, $f=\Omega(g)$ if $g=O(f)$, $f=\omega(g)$ if
$g=o(f)$, and $f=\Theta(g)$ if both $f=O(g)$ and $g=O(f)$.

##  3\. Roadmap of the paper

Theorems 2.5–2.10 are closely linked together. We prove them in (almost)
reverse order, in six main steps. All except Step 4 rely on (often multi-
scale) renormalisation techniques. Here we sketch these steps and explain
their relation, the role of the condition $\zeta_{\mathrm{long}}>0$, and the
connection to the methods used in our earlier works [48, 49]. This sketch
assumes a unit-intensity Poisson point process and power-law vertex marks. In
the sections below we make the adaptation for the other settings. We start
with the lower tail of large deviations.

###  3.1. Route to the lower tail of large deviations

The lower bound is given in [48], so we focus on the more involved upper
bound. Using $\zeta_{\mathrm{long}}>0$, for $\rho\in(0,\theta)$ we sketch how
to prove

$\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|<\rho
n\big{)}\leq\exp\big{(}-\Theta\big{(}n^{\zeta_{\star}}\big{)}\big{)}.$ (3.1)

_Step 1. Existence of a giant (Section 4)._ For supercritical settings with
$\max(\zeta_{\mathrm{hl}},\zeta_{\mathrm{ll}})>0$, we prove for a small
constant $\varepsilon>0$ that
$\\{|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|\geq\varepsilon n\\}$ whp. For
$\zeta_{\mathrm{hh}}>0$ this step is already given by the weak law of large
numbers for $|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|$ in our earlier work
[48]. To prove
$\mathbb{P}(|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|\geq\varepsilon n)\to
1$, we first adapt a multi-scale renormalisation technique by Berger [12]
which relies on ergodicity and uniqueness of the infinite component. This
technique yields a polynomial lower bound on
$|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|$. We use this lower bound as the
initialization of another multi-scale renormalisation scheme, inspired by a
method that Biskup introduced for long-range percolation [14]. The two
techniques combined yield that for some $\varepsilon>0$, $A>0$, and
$\gamma\in(0,1)$ satisfying $\zeta=1-\gamma(\tau-1)$,

$\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}[1,An^{\gamma})|<\varepsilon
n\big{)}\leq\exp\big{(}-n^{\max(\zeta_{\mathrm{ll}},\zeta_{\mathrm{hl}})-o(1)}\big{)},$
(3.2)

where ${\mathcal{C}}_{n}^{\scriptscriptstyle(1)}[1,An^{\gamma})$ denotes the
largest connected component in the graph induced on vertices with location in
$\Lambda_{n}$ and mark in $[1,An^{\gamma})$.

_Step 2. Sharp bounds on the giant’s existence (Section 5)._ The inequality
(3.2) is worse than (3.1). In the next step we improve it: we show the
implication that _if_

$\Lambda_{n}$ has whp a giant component of density at least $\rho>0$
containing all vertices with mark at least $n^{(1-o(1))/(\tau-1)}$, (Req)

_then_ for any $\varepsilon^{\prime}>0$ and some
$A^{\prime}=A^{\prime}(\varepsilon^{\prime})>0$,

$\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}[1,A^{\prime}n^{\gamma})|<(\rho-\varepsilon^{\prime})n\big{)}\leq\exp\big{(}-\Theta(n^{\max(\zeta_{\mathrm{ll}},\zeta_{\mathrm{hl}},\zeta_{\mathrm{hh}},(d-1)/d)})\big{)}.$
(3.3)

Compared to (3.2), the $o(1)$ disappeared from the speed-exponent while
$(d-1)/d$ and $\zeta_{\mathrm{hh}}$ entered the maximum. To prove (3.3) when
$\zeta_{\mathrm{long}}>(d-1)/d$, we reduce the event
$\\{|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|<(\rho-\varepsilon^{\prime})n\\}$
to a large-deviation event for Erdős-Rényi random graphs, see below 1.2. When
$(d-1)/d$ is the unique maximum and $\zeta_{\mathrm{long}}>0$, we prove (3.3)
with a different renormalisation. Using boxes of constant volume $M$, the
renormalised model dominates supercritical site-bond percolation on
${\mathbb{Z}}^{d}$. Using long-edges present due to $\zeta_{\mathrm{long}}>0$,
two neighbouring boxes of volume $M$ are connected by an edge with probability
tending to $1$ as $M\to\infty$.

We also prove the condition (Req) of (3.3): all vertices with mark at least
$(\log n)^{\eta^{\prime}}$ for an explicit $\eta^{\prime}>0$ are in the giant
component: using an ‘extra layer’ on the renormalisation leading to (3.2) we
prove in the case $\max(\zeta_{\mathrm{hl}},\zeta_{\mathrm{ll}})>0$ that

$\mathbb{P}\big{(}\exists\text{ component }{\mathcal{C}}\text{ in
}{\mathcal{G}}_{n}:{\mathcal{V}}_{n}[(\log
n)^{\eta^{\prime}},\infty)\supseteq{\mathcal{C}},|{\mathcal{C}}|\geq\varepsilon
n\big{)}\longrightarrow 1.$ (3.4)

We combine this with (3.3), and set
$\rho=\varepsilon,\varepsilon^{\prime}=\varepsilon/2$ when
$\zeta_{\mathrm{long}}=\max(\zeta_{\mathrm{hl}},\zeta_{\mathrm{ll}})$. When
$\zeta_{\mathrm{long}}=\zeta_{\mathrm{hh}}$, we use the results from [48] and
set $\rho=\theta-\varepsilon$. In Section 5 we thus prove that for some
$\varepsilon>0$,

$\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}[1,A^{\prime}n^{\gamma})|<\varepsilon
n\big{)}\leq\exp\big{(}-\Theta(n^{\zeta_{\star}})\big{)}.$ (3.5)

After having proven an improved value of $\rho=\theta-\varepsilon$ in Step 5
below, requirement (Req) shall imply an improved version of (3.5) with the new
density.

_Step 3. Non-giant components are small (Section 6.1)._ In this step we prove
the upper bound on the second-largest component in Theorem 2.10, using (3.5).
For KSRGs with PPP vertex sets, for any $k=k(n)$, we prove

$\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(2)}|\geq k\big{)}\leq
3(n/k)\exp\big{(}-\Theta(k^{\zeta_{\mathrm{long}}})\big{)}=:\mathrm{err}_{n,k}.$
(3.6)

Given (3.6), substitute $k=(A\log n)^{1/\zeta_{\mathrm{long}}}$ for a large
constant $A=A(\delta)$ to obtain the upper bound in Theorem 2.10. The lower
bound there follows by verifying a prerequisite from our earlier work [48].
There we also proved (3.6) when $\zeta_{\mathrm{long}}=\zeta_{\mathrm{hh}}$.
The method in [48] breaks down for the cases when
$\zeta_{\mathrm{long}}\in\\{\zeta_{\mathrm{ll}},\zeta_{\mathrm{hl}}\\}$, see
Remark 3.2. So, we use a new method that we explain now.

We sequentially reveal the graph. After the last revealment stage a _non-
largest_ component of size at least $k$ is present in $\Lambda_{n}$ with
probability at most $\mathrm{err}_{n,k}$. We partition $\Lambda_{n}$ into
boxes of volume $k$. The probability that all boxes contain a linear-sized
component on vertices with mark at most $A^{\prime}k^{\gamma}$ is at least
$1-\tfrac{1}{3}\mathrm{err}_{n,k}$ by (3.5). When
$\zeta_{\mathrm{long}}=\zeta_{\mathrm{hl}}$, we sprinkle in vertices of mark
larger than $A^{\prime}k^{\gamma_{\mathrm{hl}}}$, forming the PPP
${\mathcal{V}}^{{\scriptscriptstyle\mathrm{high}}}$. We say that a vertex
$v\in{\mathcal{V}}^{{\scriptscriptstyle\mathrm{high}}}$ is _box-wedging_ if it
connects to the local giant in its own box and also to the local giant in the
neighbouring box. We prove that the number of box-wedging vertices in each box
is $\Theta(k^{\zeta_{\mathrm{long}}})$: see the back-of-the-envelope
calculations in Section 2.2 for intuition on this. So, all local giants exist
and are in the same connected component in ${\mathcal{G}}_{n}$ via box-wedging
vertices with probability at least $1-\tfrac{2}{3}\mathrm{err}_{n,k}$. We call
this component the _backbone_.

We now take care of small components: in the third stage we reveal edges
between vertices that are not in local giants but in different boxes,
obtaining ${\mathcal{G}}^{{\scriptscriptstyle 3\mathrm{rd}}}_{n}$. In the
fourth revealment stage we reveal edges between the components of
${\mathcal{G}}^{{\scriptscriptstyle 3\mathrm{rd}}}_{n}$ and the backbone. If a
component of ${\mathcal{G}}^{{\scriptscriptstyle 3\mathrm{rd}}}_{n}$ is larger
than $k$, then we show that with probability at least
$1-\exp\big{(}-\Theta(k^{\zeta_{\mathrm{long}}})\big{)}$ it connects to a box-
wedging vertex in the backbone. So, all components of size at least $k$ merge
with the backbone with probability at least $1-\mathrm{err}_{n,k}$.

_Step 4. LLN for the giant, cluster-size decay (Section 6.2)._ In [48,
Proposition 6.1], we showed how the combination of the bounds (3.4), (3.6),
and the whp existence of a polynomially-sized largest component (a weaker
bound than (3.5)), leads to the upper bound on the cluster-size decay in
Theorem 2.9 and the weak LLN

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

_Step 5. Lower tail of large deviations of the giant (Section 6.3)._ The LLN
in (3.7) gives that
$|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|/n\geq\theta-\varepsilon$ holds
whp for any $\varepsilon>0$. So the condition (Req) holds with
$\rho=\theta-\varepsilon$. We can reuse (3.3), combine it with (3.4), so that
the unique giant contains all highest-mark vertices whp. Then combination with
(3.6) results in (3.1).

######  Remark 3.1 (Difficulties when surface tension is dominant).

When $(d-1)/d>\zeta_{\mathrm{long}}$, Theorem 2.7 on the lower tail of LDP is
sharp, while Theorems 2.9 and 2.10 are not sharp. In the proofs we connect
local giants in subboxes via edges with length of the same order as the box-
diameter. These edges are present under the assumption that
$\zeta_{\mathrm{long}}>0$. This is enough to give Theorem 2.7: to be able to
estimate the giant’s size, not every subbox needs to contribute to the global
giant. The condition $\zeta_{\mathrm{long}}>0$ could only be dropped by
developing more information about the position of local giants inside
subboxes. They must come close to the boundary to be able to connect them
without using long edges. This is beyond the scope of this paper.

For proving Theorems 2.9 and 2.10 with $\zeta=(d-1)/d$ in the upper bound, we
need sharper estimates. Between the giant component and any other component of
size at least $k$, we need to find at least $\Omega(k^{(d-1)/d})$ non-
connected vertex pairs within constant distance, with probability at least
$1-n\exp(-\Omega(k^{(d-1)/d}))$. Our techniques do not focus on the geometry
of short missing edges around components, so this case is beyond the scope of
this paper. For NNP, such geometric information is known, see [39] for
references. For high edge-density long-range percolation our recent work [49]
solves this issue, and obtains matching upper and lower bounds for
$|{\mathcal{C}}_{n}^{\scriptscriptstyle(2)}|$ and the cluster-size decay. For
long-range percolation, we refer also to the recent work by Bäumler [11] for
related results.

######  Remark 3.2 (High-high regime is different).

In [48], we proved the bound on $|{\mathcal{C}}_{n}^{\scriptscriptstyle(2)}|$
in (3.6) when $\zeta_{\mathrm{hh}}$ is maximal. When high-high type
connections dominate, the likeliest way to connect two boxes is via edges
between two high-mark vertices. So, building a backbone with error probability
$\mathrm{err}_{n,k}$ in (3.6) is more straightforward than the multi-scale
renormalisation techniques here. However, the sequential revealment method
sketched in Step 3 above breaks down when we look at small components of size
at least $k$. When $\zeta_{\mathrm{hh}}=\zeta_{\star}$, we also need to show
that the giant has $\Theta(k^{\zeta_{\mathrm{hh}}})$ many high-mark vertices
within “connection probability” $\Theta(1)$ to every one of these components,
with probability $\mathrm{err}_{n,k}$. The revealment method from Step 3 does
not guarantee that, since the diameter of the box $\Theta(k^{1/d})$ is a too
crude bound on the distance between previously revealed small components and
high-mark vertices. So, in [48] we developed a geometric method that we call
_cover-expansion_ , which allows us to control this distance based on the
geometry of the cluster. See [48, Section 3] for a comparison.

###  3.2. The upper tail of large deviations (Section 7.1)

First we present the intuition behind the formula of $\mathrm{hubs}(\rho)$ in
(2.17), then we outline the proof of Theorem 2.5 and Theorem 2.4.

_Hubs increase the giant linearly._ We investigate an unlikely event. Take $R$
to be a large constant. When $h$ vertices with mark at least $Rn$ – so called
_hubs_ – are present in a box of volume $n$, the size of the giant increases
linearly in $n$, since each hub connects by an edge to every other vertex in
the box with probability $p$ independently. By the Pareto distribution of the
marks in (2.4), the probability of having $h$ hubs is
$\Theta(n^{-h(\tau-2)})$. For the exact rate function, we need to compute how
the giant’s size increases when there are $h$ hubs present. We reveal the
edges in two stages: first all edges between non-hub vertices, obtaining the
graph ${\mathcal{G}}_{n}[1,Rn)$. Then we reveal all edges incident to hubs,
obtaining ${\mathcal{G}}_{n}$. We capture
$|{\mathcal{C}}_{n}^{{\scriptscriptstyle(1)}}|$ via its complement: small
components of ${\mathcal{G}}_{n}[1,Rn)$ do not merge with the giant in the
second step if none of the vertices in the component connect to the hubs.
Distinguishing all component sizes, we write

$\displaystyle
1-\frac{|{\mathcal{C}}_{n}^{{\scriptscriptstyle(1)}}|}{n}\approx\frac{|{\mathcal{V}}_{n}\setminus{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|}{n}$
$\displaystyle\approx\sum_{v\in{\mathcal{V}}_{n}[1,Rn)}\\!\\!\\!\\!\frac{\mathds{1}_{\\{{\mathcal{C}}_{n}(v)[1,Rn)\nsim\mathrm{hubs}\\}}}{n}=\sum_{\ell\geq
1}\sum_{\begin{subarray}{c}{\mathcal{C}}\in{\mathcal{G}}_{n}[1,Rn):\\\
|{\mathcal{C}}|=\ell\end{subarray}}\frac{\ell\cdot\mathds{1}_{\\{{\mathcal{C}}\nsim\mathrm{hubs}\\}}}{n}.$
(3.8)

The probability that no edge exists between a size-$\ell$ component and the
$h$ hubs is $(1-p)^{h\ell}$. Moreover, by local convergence (see [72] for a
detailed explanation and references), the proportion of vertices in components
of size-$\ell$ converges in probability to $\mathbb{P}^{\scriptscriptstyle
0}(|{\mathcal{C}}(0)|=\ell)$. Therefore, the total number of size-$\ell$
components in $\Lambda_{n}$ concentrates around
$(n/\ell)\cdot\mathbb{P}^{\scriptscriptstyle 0}(|{\mathcal{C}}(0)|=\ell)$.
Hence,

$1-\frac{|{\mathcal{C}}_{n}^{{\scriptscriptstyle(1)}}|}{n}\approx\sum_{\ell\geq
1}\mathbb{P}^{\scriptscriptstyle
0}\big{(}|{\mathcal{C}}(0)|=\ell\big{)}\cdot(1-p)^{h\ell}=\mathbb{E}^{\scriptscriptstyle
0}\big{[}(1-p)^{h|{\mathcal{C}}(0)|}\big{]}.$ (3.9)

On the event $\\{|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|/n>\rho\\}$, the
right-hand side above should be at most $1-\rho$. Thus, letting $h$ to be the
smallest integer satisfying

$\mathbb{E}^{\scriptscriptstyle
0}\big{[}(1-p)^{h|{\mathcal{C}}(0)|}\big{]}\leq 1-\rho,$ (3.10)

the presence of $h$ hubs implies the event
$\\{|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|/n>\rho\\}$. The solution to
(3.10) with equality is exactly $\mathrm{hubs}(\rho)$ in (2.17).

_Concentration on the number of size- $\ell$ components._ To move from (3.8)
to (3.9), we need that the rate of concentration of the number of size-$\ell$
components is $o(n^{-(\tau-2)h}))$. Local convergence (LC) does not provide
any convergence rate. We boost the performance of LC by applying it to
disjoint subboxes of $\Lambda_{n}$, binomial concentration, and a bound on the
number of components containing edges that cross box-boundaries. When vertex-
marks are at most a linear function in $n$, this yields a polynomial
convergence rate with a tunable exponent.

_Linear-scale hubs are required to increase the giant’s size._ For the lower
bound in (2.19), we use that the graph without hubs contains a giant component
of density almost $\theta$ by the lower tail of large deviations. The hubs
connect to this giant with error probability exponential in $n$. When
$\mathrm{hubs}(\rho)\notin{\mathbb{N}}$, our concentration bound on
size-$\ell$-component is strong enough to guarantee that the presence of
$\lceil\mathrm{hubs}(\rho)\rceil$ hubs increases the giant’s size to a value
above $\rho n$. We also show that any event that has fewer than
$\lceil\mathrm{hubs}(\rho)\rceil$ hubs means that too many size-$\ell$
components remain outside of the giant with probability at least
$\Theta\big{(}n^{-(\tau-2)h}\big{)}$. So, the complement of the giant remains
larger than $(1-\rho)n$ on such events. This gives the upper bound.

_Homogeneous percolation models._ In Bernoulli bond percolation or long-range
percolation on ${\mathbb{Z}}^{d}$, the degree-distribution has
(super-)exponential tails, so no linear-scale hubs are present. We show that
the number of size-$\ell$ components concentrate with error probability
exponentially small in $n$ for each constant $\ell\in{\mathbb{N}}$. We capture
the giant’s size by its complement, and Theorem 2.4 follows.

##  4\. Existence of a giant

The main goal of this section is to prove the existence of a giant, i.e., a
linear-sized component, for the whole supercritical regime when
$\max(\zeta_{\mathrm{hl}},\zeta_{\mathrm{ll}})>0$. For
$\zeta_{\mathrm{hh}}>0$, we already proved existence in our recent work [48].
The first proposition corresponds to (3.2) in the roadmap in Section 3.

######  Proposition 4.1 (Existence of a giant).

Consider a supercritical KSRG satisfying Assumption 2.2 with a Poisson point
process as vertex set. Assume that the parameters satisfy
$\max(\zeta_{\mathrm{hl}},\zeta_{\mathrm{ll}})>0$. For each constant
$\delta>0$, there exists a constant $A>0$ such that for all $n\geq 1$,

  * (hl)

when $\zeta_{\mathrm{hl}}>0$,

$\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}[1,An^{\gamma_{\mathrm{hl}}})|\leq\tfrac{1}{A}n\big{)}\leq\exp\big{(}-\tfrac{1}{A}n^{\zeta_{\mathrm{hl}}-\delta}\big{)},$
(4.1)

  * (ll)

when $\zeta_{\mathrm{ll}}>0$,

$\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}[1,A)|\leq\tfrac{1}{A}n\big{)}\leq\exp\big{(}-\tfrac{1}{A}n^{\zeta_{\mathrm{ll}}-\delta}\big{)}.$
(4.2)

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

Proposition 4.1 generalizes [14, Theorem 3.2] by Biskup from long-range
percolation on ${\mathbb{Z}}^{d}$ to a wider class of KSRGs. The presence of
vertex marks in KSRGs, and the truncation of them in the statement of
Proposition 4.1 require new ideas. We will prove Proposition 4.1 via a multi-
scale renormalisation scheme. To initialize this scheme, we need an initial
lower bound on $|{\mathcal{C}}_{n}^{{\scriptscriptstyle(1)}}|$.

######  Lemma 4.2 (Existence of an “almost”-giant).

Consider a supercritical KSRG under the same setting as in Proposition 4.1.
For all $\varepsilon>0$

$\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|\leq
n^{1-\varepsilon}\big{)}\longrightarrow 0,\qquad\mbox{ as }n\to\infty.$ (4.3)

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 this lemma is inspired by a multi-scale renormalisation technique
introduced for long-range percolation by Berger in [12]. When
$\zeta_{\mathrm{ll}}=2-\alpha>0$ and the vertex set is formed by a PPP, [36,
Proposition 3.9] already proves (4.3) using an adaptation of [12]. For the
case $\zeta_{\mathrm{hl}}>0$ we give a new proof in Appendix B that explicitly
relies on the vertex-marks. The rest of this section is devoted to proving
Proposition 4.1. We first introduce some additional preliminaries.

###  4.1. Preliminaries

We describe a sprinkling technique that enables us to reveal the vertex set of
a KSRG on a PPP in multiple stages, so that the graph is supercritical already
before sprinkling.

######  Definition 4.3 (Scaled-thinned KSRG on a PPP).

Consider a KSRG on a PPP. Let $q\in[0,1]$ and $\eta>0$. We write
$\eta{\mathcal{G}}_{n}^{\beta,q}$ for a scaled-thinned KSRG as follows: first,
we keep each vertex of the PPP ${\mathcal{V}}$ independently with probability
$q$. Then we sample the edges according to Definition 2.1 with edge-density
parameter $\beta>0$. Finally, we we assign a new location to each retained
vertex, i.e., we map $u=(x_{u},w_{u})\in{\mathbb{R}}^{d}\times[1,\infty)$ to
$(\eta x_{u},w_{u})$.

It is not hard to see that the scaled-thinned KSRG with $\eta=q$ is
distributed like the original graph with a smaller parameter $\beta$ in a
smaller box. This is the content of the following observation.

######  Observation 4.4 (Sprinkling trick-A).

Consider a supercritical KSRG on a PPP, i.e., with
$\beta>\beta_{c}(p,\alpha,\tau,\sigma)$. Let $q\in(0,1]$. Then the following
distributional identity holds:

$q{\mathcal{G}}_{n}^{\beta,q}\overset{d}{=}{\mathcal{G}}_{qn}^{\beta
q^{d},1}\overset{d}{=}{\mathcal{G}}_{qn}^{\beta q^{d}}$ (4.4)

In particular, the graph $q{\mathcal{G}}_{n}^{\beta,q}$ is supercritical
whenever the new edge-intensity $\beta q^{d}>\beta_{c}$.

###### Proof.

Denote by ${\mathcal{V}}^{(q,q)}$ the marked vertex set of
$q{\mathcal{G}}_{n}^{\beta,q}$. Since the projection of ${\mathcal{V}}$ onto
the spatial dimensions in ${\mathbb{R}}^{d}$ is a PPP with intensity being the
Lebesgue measure, thinning ${\mathcal{V}}$ gives intensity
$q\mathrm{Leb}(\cdot)$. Then, re-scaling with $\eta=q$ maps the box
$\Lambda_{n}$ to $\Lambda_{qn}$. For any set $A\subseteq\Lambda_{qn}$, the
expected number of points in it is
$q\mathrm{Leb}(\eta^{-1}A)=\mathrm{Leb}(A)$. Hence ${\mathcal{V}}^{(q,q)}$ has
the same distribution as ${\mathcal{V}}\cap\Lambda_{qn}$, since the spatial
intensity of the new point process ${\mathcal{V}}^{(q,q)}$ is
$\mathrm{Leb}(\cdot)$ again, and the distribution of the mark-coordinate is
unchanged. We now inspect the connection probabilities in
$q{\mathcal{G}}_{n}^{\beta,q}$. Let us denote the new connectivity function by
$\mathrm{p}^{(q,q)}$. Consider two points $u=(x_{u},w_{u})$ and
$v=(x_{v},w_{v})$ in ${\mathcal{V}}^{(q,q)}$. Since we connect $u$ to $v$ by
an edge in $q{\mathcal{G}}_{n}^{\beta,q}$ iff we connect their inverse points
$(q^{-1}x_{u},w_{u})$ and $(q^{-1}x_{v},w_{v})$ in ${\mathcal{G}}_{n}$ by an
edge, the new connection probability $\mathrm{p}^{(q,q)}$ is given by

$\mathrm{p}^{(q,q)}\big{(}(x_{u},w_{u}),(x_{v},w_{v})\big{)}=\mathrm{p}\big{(}(q^{-1}x_{u},w_{u}),(q^{-1}x_{v},w_{v})\big{)}=\varphi\Big{(}\beta\frac{\kappa(w_{u},w_{v})}{\|q^{-1}(x_{u}-x_{v})\|^{d}}\Big{)}.$

Thus, the new graph has the same distribution as a graph on
${\mathcal{V}}\cap\Lambda_{qn}$ with the same connection probabilities but new
edge-density parameter $\beta^{\prime}=\beta q^{d}$. This graph is denoted by
${\mathcal{G}}_{qn}^{\beta^{\prime},1}$, since in this latter notation the
thinning factor is $q=1$, and the box is $\Lambda_{qn}$. The last identity in
(4.4) says that omitting $q=1$ from the superscript is consistent with the
notation. Finally, the new graph is supercritical whenever the new edge-
intensity $\beta q^{d}$ is at least $\beta_{c}$ as well. ∎

Throughout the paper we will use the following construction of KSRGs when we
consider PPPs as the underlying vertex set, following the setting of
Assumption 2.2.

######  Definition 4.5 (Alternative KSRG construction on a PPP).

Consider a KSRG on a PPP with parameters and kernel $\kappa$ from Assumption
2.2. If $\beta>\beta_{c}$, let $q\in(0,1]$ be such that $\beta
q^{d}>\beta_{c}$, i.e., the scaled-thinned graph
$q{\mathcal{G}}_{n}^{\beta,q}$ in (4.4) is supercritical. If
$\beta\leq\beta_{c}$, set $q=1$. Let
${\mathcal{V}}^{\scriptscriptstyle\mathrm{base}}$ and
${\mathcal{V}}^{\scriptscriptstyle\mathrm{spr}}$ be two independent PPPs with
intensity $q\mathrm{Leb}\\!\times\\!F_{W}(\mathrm{d}w)$ and
$(1-q)\mathrm{Leb}\\!\times\\!F_{W}(\mathrm{d}w)$, respectively, with $F_{W}$
as in Assumption 2.2. Define

$\overline{\mathcal{V}}:={\mathcal{V}}^{\scriptscriptstyle\mathrm{base}}\cup{\mathcal{V}}^{\scriptscriptstyle\mathrm{spr}},$

which is equal in distribution to a Poisson point process on
${\mathbb{R}}^{d}\times[1,\infty)$ with intensity

$\mathrm{Leb}\times
F_{W}(\mathrm{d}w)=\begin{dcases}\mathrm{d}x\times(\tau-1)w^{-\tau}\mathrm{d}w,&\text{if
}\tau<\infty,\\\ \mathrm{d}x\times\delta_{1}(\mathrm{d}w),&\text{if
}\tau=\infty,\end{dcases}$ (4.5)

where $\delta_{1}(\cdot)$ denotes a Dirac measure at one. Conditionally on the
realization of $\overline{\mathcal{V}}$, let
$\overline{\mathcal{G}}_{n}^{\scriptscriptstyle\beta}$ be the graph on
$\overline{\mathcal{V}}$ where two vertices $u,v\in\overline{\mathcal{V}}$ are
connected by an edge independently with probability

$\mathrm{p}(u,v)=\begin{dcases}p\Big{(}\beta\cdot\frac{\kappa(w_{u},w_{v})}{\|x_{u}-x_{v}\|^{d}}\wedge
1\Big{)}^{\alpha},&\text{if }\alpha<\infty,\\\
p\mathds{1}\big{\\{}\beta\kappa(w_{u},w_{v})\geq\|x_{u}-x_{v}\|^{d}\big{\\}},&\text{if
}\alpha=\infty.\end{dcases}$ (4.6)

Let ${\mathcal{G}}_{n}^{\beta,{\scriptscriptstyle\mathrm{base}}}\ {\buildrel
d\over{=}}\ {\mathcal{G}}_{n}^{\beta,q}$ be the induced subgraph on
${\mathcal{V}}^{\scriptscriptstyle\mathrm{base}}$. If $q<1$, we call
${\mathcal{G}}_{n}^{\scriptscriptstyle\beta,\mathrm{base}}$ the _thinned_
KSRG. We omit the superscript $\beta$ if it is clear from the context.

######  Observation 4.6 (Sprinkling trick-B).

Consider a supercritical KSRG on a PPP, and let
$\overline{\mathcal{G}}_{n}^{{\scriptscriptstyle\beta}}$ and
${\mathcal{G}}_{n}^{\beta,{\scriptscriptstyle\mathrm{base}}}$ be as in
Definition 4.5. Write $\beta^{\prime}:=\beta q^{d}$. Let
${\mathcal{C}}^{\scriptscriptstyle(1)}_{n,{\scriptscriptstyle\mathrm{base}}}$
and ${\mathcal{C}}^{\scriptscriptstyle(1)}_{qn,\beta^{\prime}}$ be the largest
component in ${\mathcal{G}}_{n}^{\beta,{\scriptscriptstyle\mathrm{base}}}$ and
${\mathcal{G}}_{qn}^{\beta^{\prime}}$, respectively. Then

$\overline{\mathcal{G}}_{n}^{\scriptscriptstyle\beta}\overset{d}{=}{\mathcal{G}}_{n}^{\scriptscriptstyle\beta},\qquad{\mathcal{G}}_{n}^{\beta,{\scriptscriptstyle\mathrm{base}}}\overset{d}{=}\tfrac{1}{q}{\mathcal{G}}_{qn}^{\beta^{\prime}},\qquad|{\mathcal{C}}_{qn,\beta^{\prime}}^{\scriptscriptstyle(1)}|\,\overset{d}{=}\,|{\mathcal{C}}_{n,{\scriptscriptstyle\mathrm{base}}}^{\scriptscriptstyle(1)}|.$

###### Proof.

$\overline{\mathcal{G}}_{n}^{\scriptscriptstyle\beta}$ has the same law as
${\mathcal{G}}_{n}^{\scriptscriptstyle\beta}$ since $\overline{\mathcal{V}}$
has the same law as ${\mathcal{V}}$ and the connection probabilities are the
same. ${\mathcal{G}}_{n}^{\beta,{\scriptscriptstyle\mathrm{base}}}$ has the
same law as $1{\mathcal{G}}_{n}^{\beta,q}$ in Definition 4.3, i.e., we just
apply thinning but do not rescale. We write this now as
$q^{-1}(q{\mathcal{G}}_{n}^{\beta,q})$ and apply the identity (4.4) to the
scaled-thinned graph, and we get the second distributional identity above. The
last identity about the largest component holds since edges (and thus
connected components) do not change under rescaling. ∎

Let us also state a well-known statement about the connectivity of Erdős-Rényi
random graphs. We give a short (suboptimal) proof for the sake of
completeness.

######  Claim 4.7 (Connectivity of $G(n,p_{n})$).

Consider the Erdős-Rényi random graph $G(n,p_{n})$ with $np_{n}$ $=\omega(\log
n)$. For all $n\geq 1$,

$\mathbb{P}\big{(}\mbox{$G(n,p_{n})$ is not connected}\big{)}\leq
3({\mathrm{e}}n)^{2}(1-p_{n})^{n/2}.$ (4.7)

###### Proof.

If $G(n,p_{n})$ is not connected, then there must exist a connected component
of size $k$, for some $1\leq k\leq\lfloor n/2\rfloor$. For $k=1$, this
probability is at most
$n(1-p_{n})^{n-1}\leq({\mathrm{e}}n)^{2}(1-p_{n})^{n/2}$ by a union bound over
all vertices. For $k\geq 2$, by Cayley’s formula, there are $k^{k-2}$ spanning
trees on $k$ vertices, and a connected component of size $k$ has to contain
such a tree. So by a union bound over the spanning trees, the probability that
a connected component of size between $2$ and $n/2$ exists without being
connected to the other $n-k$ vertices, is at most

$\sum_{k=2}^{\lfloor
n/2\rfloor}\binom{n}{k}k^{k-2}(1-p_{n})^{k(n-k)}\leq\sum_{k=2}^{\lfloor
n/2\rfloor}\left(\frac{{\mathrm{e}}n}{k}\right)^{k}k^{k-2}(1-p_{n})^{k(n-k)}\leq\sum_{k=2}^{\lfloor
n/2\rfloor}\big{(}({\mathrm{e}}n(1-p_{n})^{n-k}\big{)}^{k}.$

Using $n-k\geq\lceil n/2\rceil$, we get that the right-hand side is bounded
from above by

$\sum_{k=2}^{\lfloor n/2\rfloor}\big{(}({\mathrm{e}}n(1-p_{n})^{\lceil
n/2\rceil}\big{)}^{k}\leq\frac{({\mathrm{e}}n)^{2}(1-p_{n})^{2\lceil
n/2\rceil}}{1-{\mathrm{e}}n(1-p)^{\lceil n/2\rceil}}\leq
2({\mathrm{e}}n)^{2}(1-p_{n})^{n/2}.$

Combining the cases of $k=1$ and $k\geq 2$ we obtain the desired statement. ∎

###  4.2. A linear-sized component (high-low regime)

We turn to the proof of Proposition 4.1 for the hl-regime, so we restrict to
KSRGs on PPPs. We describe the adjustments for the ll-regime at the end of
this section.

####  4.2.1. Multi-scale renormalisation – sketch

We set up an iterative boxing scheme. The initial box size is a constant
$n_{0}$. We check if the largest component of a thinned KSRGs inside a
level-$0$ box has size at least $\rho_{0}n_{0}:=n_{0}^{1-\varepsilon}$. Next,
we sprinkle vertices of sufficiently high (but constant) mark that connect to
this largest component. If both of these steps succeed, we call a level-$0$
box good. This happens with constant probability using Lemma 4.2.

For each iteration $i\geq 1$, we group $m_{i}$ level-$(i-1)$ boxes of volume
$n_{i-1}$ into a larger level-$i$ box $\mathrm{B}$ of volume
$n_{i}:=m_{i}n_{i-1}$. We always work with only the ‘good’ subboxes of the
previous level $i-1$ inside $\mathrm{B}$ to determine whether the level-$i$
box $\mathrm{B}$ is good, and control the probabilities of the following three
events:

  1. _(Sub)_

Using independence across subboxes, at least $(1-\varepsilon_{i})m_{i}$ of the
level-$(i-1)$ subboxes of volume $n_{i-1}$ of $\mathrm{B}$ are
level-$(i-1)$-good with sufficiently large probability. That is, the subboxes
satisfy the next events _(Con), (Mark)_ at level $i-1$: they have a local
component of density at least $\rho_{i-1}$, which contains enough
level-$(i-1)$ high-mark vertices.

  2. _(Con)_

Each good level-$(i\\!-\\!1)$ subbox of $\mathrm{B}$ has enough high-mark
vertices inside a local component by the event _(Mark)_ on the previous level.
We use these high-mark vertices to connect the level-$(i\\!-\\!1)$ subboxes
_to each other_. This is done by a stochastic domination of an Erdős-Rényi
random graph $G\big{(}(1-\varepsilon_{i})m_{i},q_{i}\big{)}$: the giant
component of each good level-$(i-1)$ subbox is represented by a vertex in $G$.
We ensure that $q_{i}$ is above the connectivity threshold of Erdős-Rényi
random graphs. The outcome is that the level-$i$ box $\mathrm{B}$ contains a
connected component of density at least
$\rho_{i}:=\rho_{i-1}(1-\varepsilon_{i})$ with error probability stretched
exponential in $n_{i}$ (and not $n_{i-1}$ that we had on level $i-1$).

  3. _(Mark)_

The sprinkling trick from Section 4.1 allows us to sprinkle level-$i$ high-
mark vertices that were not exposed in previous levels. We make sure enough of
them connect to the large connected component in $\mathrm{B}$ built in the
_Con_ -step. We will then use these vertices in the _Con_ -step of level
$i\\!+\\!1$ later.

If the steps _Con_ and _Mark_ succeed then we call $\mathrm{B}$ level-$i$
good. (The first step _Sub_ is only a tool to control error probabilities of
these latter steps). We will ensure that $\inf_{i}\rho_{i}>0$, so the size of
the connected component we construct in the _Con_ -step is linear in $n_{i}$.
Currently we use Lemma 4.2 for initializing the level-$0$ boxes: this
guarantees local largest components of size $n_{0}^{1-\varepsilon}$, i.e.,
density $n_{0}^{-\varepsilon}$, and error probability tending to $0$ at an
unspecified rate. This proof of Proposition 4.1 here will ‘boost’ the giant to
have density at least of order $n_{0}^{-\varepsilon}n_{i}$, which is linear in
$n_{i}$ (as $i\to\infty$, because $n_{0}$ is a constant), and the error
probability becomes stretched exponential in $n_{i}$. This renormalisation
gives Proposition 4.1 along the subsequence $(n_{i})_{i\geq 0}$ of box sizes.
A final boxing argument will ensure that Proposition 4.1 holds for all $n\geq
1$.

####  4.2.2. Formal setup of the renormalisation

We formalize the boxing scheme with all its parameters. Fix any small constant
$\delta>0$ that appears in the statement of Proposition 4.1. We define an
extra constant, that shall describe the growth rate of the box sizes
$(n_{i})_{i\geq 1}$:

$\xi_{\delta}:=\xi_{\delta}(\zeta)=\frac{\delta/2}{\zeta+(\alpha-1)-\delta/2}.$
(4.8)

The value of $\xi_{\delta}$ is defined both for
$\zeta_{\mathrm{hl}}=(\tau-1)/\alpha-(\tau-2)$ and for
$\zeta_{\mathrm{ll}}=2-\alpha$ whenever these are positive. Since $\alpha>1$,
$\xi_{\delta}>0$ for all $\delta<\zeta$. Unless explicitly stated otherwise,
we abbreviate in the rest of the section

$\gamma=\gamma_{\mathrm{hl}}=1-1/\alpha,\qquad\zeta=\zeta_{\mathrm{hl}}=(\tau-1)/\alpha-(\tau-2).$
(4.9)

We recall the PPPs ${\mathcal{V}}^{\scriptscriptstyle\mathrm{base}}$ and
${\mathcal{V}}^{\scriptscriptstyle\mathrm{spr}}$ with thinning constant $q<1$
from Definition 4.5. We will choose any $q$ with $\beta q^{d}>\beta_{c}$. We
recall the parameters $p,\beta$ from the connectivity function in (4.6). We
define one extra constant depending on $q$:

$\delta^{\prime}:=\tfrac{1}{4}(1-q)(1-2^{-(\tau-1)})\cdot
p\beta^{\alpha}d^{-\alpha d/2}.$ (4.10)

Slightly abusing notation, if ${\mathcal{V}}$ is a set of vertices and
${\mathcal{C}}$ is a component, we write ${\mathcal{V}}\cap{\mathcal{C}}$ for
the set of vertices in ${\mathcal{V}}$ that belong to the component
${\mathcal{C}}$.

######  Definition 4.8 (Renormalisation scheme).

Consider a KSRG under the same setting as in Proposition 4.1. Fix $\zeta>0$,
and $\delta\in(0,\zeta/2)$, and $\xi_{\delta}(\zeta)$ as in (4.8), and a
thinning constant $q<1$ with $\beta q^{d}>\beta_{c}$. Let $n_{0}$ be a large
constant. We iteratively define for $i\geq 1$

$m_{i}:=\left\lfloor n_{i-1}^{\xi_{\delta}/d}\right\rfloor^{d},\qquad
n_{i}:=m_{i}n_{i-1}.$ (4.11)

Let ${\mathcal{Q}}_{i}(x)$ denote a box centered at $x\in{\mathbb{R}}^{d}$ of
volume $n_{i}$. We define the level-$i$ vertex set of ${\mathcal{Q}}_{i}(x)$
to be

$\widehat{\mathcal{V}}_{i}:={\mathcal{V}}^{\scriptscriptstyle\mathrm{base}}_{{\mathcal{Q}}_{i}(x)}\big{[}1,n_{0}^{2/(\tau-1)}\big{)}\cup{\mathcal{V}}^{\scriptscriptstyle\mathrm{spr}}_{{\mathcal{Q}}_{i}(x)}[1,2n_{i}^{\gamma}).$
(4.12)

We write $\widehat{\mathcal{G}}_{n_{i}}$ for the induced subgraph on
$\widehat{\mathcal{V}}_{i}$. Define the sequences

$\displaystyle\varepsilon_{i}$
$\displaystyle:=\begin{dcases}1-n_{0}^{-\delta/4},&\text{if }i=0,\\\
(i+1)^{-2},&\text{if }i\geq 1,\end{dcases}$ (4.13) $\displaystyle\rho_{i}$
$\displaystyle:=\prod_{j=0}^{i}(1-\varepsilon_{j})=n_{0}^{-\delta/4}\prod_{j=2}^{i+1}(1-j^{-2}),\qquad\rho:=\lim_{j\to\infty}\rho_{j}.$
(4.14)

We call ${\mathcal{Q}}_{i}(x)$ $i$-good (and $i$-bad otherwise) if it
satisfies the event (with $\delta^{\prime}$ in (4.10))

$\displaystyle{\mathcal{A}}_{\mathrm{i\textnormal{-}good}}(x):=\Big{\\{}\exists$
$\displaystyle\text{comp.\ ${\mathcal{C}}_{i}$ in
}\widehat{\mathcal{G}}_{n_{i}}:|{\mathcal{C}}_{i}|\geq\rho_{i}n_{i},$ (4.15)
$\displaystyle\qquad|{\mathcal{V}}^{\scriptscriptstyle\mathrm{spr}}_{{\mathcal{Q}}_{i}(x)}[n_{i}^{\gamma},2n_{i}^{\gamma})\cap{\mathcal{C}}_{i}|\geq\delta^{\prime}\rho_{i}n_{i}^{\zeta}\Big{\\}}.$

The definitions of $(m_{i})_{i\geq 0}$ and $(n_{i})_{i\geq 0}$ in (4.11)
ensure that they increase doubly exponentially in $i$: indeed, ignoring
integer parts, $n_{i}\approx n_{i-1}^{1+\xi_{\delta}}$ so $n_{i}\approx
n_{0}^{(1+\xi_{\delta})^{i}}$. This also implies that
$2n_{i-1}^{\gamma}<n_{i}^{\gamma}$, and so for any level-$(i\\!-\\!1)$ subbox
centered at any $y$, $\widehat{\mathcal{V}}_{i-1,y}$ is disjoint of
${\mathcal{V}}^{\scriptscriptstyle\mathrm{spr}}_{{\mathcal{Q}}_{i}(x)}[n_{i}^{\gamma},2n_{i}^{\gamma})$.
Thus, in ${\mathcal{Q}}_{i}(x)$ we sprinkle in _new_ vertices with mark in
$[n_{i}^{\gamma},2n_{i}^{\gamma})$ in level-$i$ compared to previous levels.
Summability of $(\varepsilon_{i})_{i\geq 0}$ in (4.13) implies that $\rho>0$
for any starting value $\varepsilon_{0}(n_{0})$ in (4.13–4.14).

The next claim provides useful bounds on the sequences that will appear in
subsequent computations. Actually, $\xi_{\delta}$ in (4.8) is chosen precisely
such that (4.16)–(4.18) are satisfied below. The label on the inequalities
indicate where we will use the bounds later.

######  Claim 4.9 (Useful bounds).

Fix _any_ $\zeta\in(0,1)$ and then $\xi_{\delta}(\zeta)$ in (4.8). Assume
$\delta\in(0,\zeta/2)$ and consider the quantities in Definition 4.8. For each
constant $C>0$, there exists a constant $n_{0}^{\star}>0$ such that for all
$n_{0}\geq n_{0}^{\star}$ and all $i\geq 1$, the following hold:

$\displaystyle\varepsilon_{i}m_{i}n_{i-1}^{\zeta-\delta}$
$\displaystyle\overset{\mathrm{(Sub)}}{\geq}Cn_{i}^{\zeta-\delta},$ (4.16)
$\displaystyle\rho_{i-1}^{2}m_{i}^{1-\alpha}n_{i-1}^{\zeta}$
$\displaystyle\overset{\mathrm{(Con)}}{\geq}Cn_{i}^{\zeta-\delta},$ (4.17)
$\displaystyle\rho_{i}n_{i}^{\zeta}$
$\displaystyle\overset{\mathrm{(Mark)}}{\geq}Cn_{i}^{\zeta-\delta}.$ (4.18)

Further,

$\displaystyle
n_{i}\in\Big{[}n_{0}^{(1+\xi_{\delta}/2)^{i}},n_{0}^{(1+\xi_{\delta})^{i}}\Big{]},\qquad
m_{i}\in\Big{[}\tfrac{1}{2}n_{0}^{\xi_{\delta}(1+\xi_{\delta}/2)^{i-1}},n_{0}^{\xi_{\delta}(1+\xi_{\delta})^{i-1}}\Big{]},$
(4.19) $\displaystyle\varepsilon_{i}m_{i}^{1-\zeta+\delta}\geq
C,\qquad(n_{i-1}/n_{0})^{\zeta-\delta}\geq
C\log({\mathrm{e}}/\varepsilon_{i}),$ (4.20)

Moreover, for all $m\leq m_{i+1}$ and $n:=n_{i}m$,

$mn_{i}^{\zeta+\alpha}n^{-\alpha}\geq n^{\zeta-\delta}.$ (4.21)

Finally, when $\zeta=\zeta_{\mathrm{hl}}$ and $\gamma=1-1/\alpha$, then

$n_{i}^{\gamma}>2n_{i-1}^{\gamma}.$ (4.22)

We postpone the proof to Appendix B.2.

####  4.2.3. Induction base of the renormalisation

We now carry out the multi-scale renormalisation outlined in Section 4.2.1 by
induction. We first constitute the induction base.

######  Claim 4.10 (Induction base).

Consider a supercritical KSRG under the setting as in Proposition 4.1 and
consider Definition 4.8. There exists a constant $n_{0}^{\star}>0$ such that
for all $n_{0}\geq n_{0}^{\star}$ in Definition 4.8, and all
$x\in{\mathbb{R}}^{d}$,

$\mathbb{P}\big{(}{\mathcal{Q}}_{0}(x)\mbox{ is $0$-bad}\big{)}\leq
1/{\mathrm{e}}^{6}.$

###### Proof.

By translation invariance, we assume w.l.o.g. that $x=0$, and abbreviate
${\mathcal{Q}}_{0}:={\mathcal{Q}}_{0}(0)$. We use the the definition of
$i$-goodness in (4.15) for $i=0$ in Definition 4.8, and substitute
$\rho_{0}=n_{0}^{-\delta/4}$ by (4.14). Then,

$\displaystyle\mathbb{P}\big{(}{\mathcal{Q}}_{0}\mbox{ is
$0$-good}\big{)}=\mathbb{P}\big{(}\exists$ $\displaystyle\text{ component
${\mathcal{C}}$ in $\widehat{\mathcal{G}}_{n_{0}}$: }|{\mathcal{C}}|\geq
n_{0}^{1-\delta/4},$ (4.23) $\displaystyle\qquad\hskip
15.0pt|{\mathcal{C}}\cap{\mathcal{V}}^{\scriptscriptstyle\mathrm{spr}}[n_{0}^{\gamma},2n_{0}^{\gamma})|\geq\delta^{\prime}n_{0}^{-\delta/4}n_{0}^{\zeta}\big{)}.$

Following Definition 4.5, we use the alternative KSRG construction with the
$q$-thinning of the vertex set. Let
${\mathcal{G}}^{\scriptscriptstyle\mathrm{base}}_{n_{0}}$ be the thinned KSRG
restricted to ${\mathcal{Q}}_{0}$, which is a subgraph of
$\widehat{\mathcal{G}}_{n_{0}}$; let
${\mathcal{C}}^{\scriptscriptstyle(1)}_{n_{0},\mathrm{base}}[1,n_{0}^{2/(\tau-1)})$
be the largest component in the induced subgraph on the restricted marks
$[1,n_{0}^{2/(\tau-1)})$ in
${\mathcal{G}}^{\scriptscriptstyle\mathrm{base}}_{n_{0}}$; and let
${\mathcal{C}}_{0}\supseteq{\mathcal{C}}^{\scriptscriptstyle(1)}_{n_{0},\mathrm{base}}[1,n_{0}^{2/(\tau-1)})$
be the component in the whole $\widehat{\mathcal{G}}_{n_{0}}$ containing this
component. We define the event that this latter component is large enough:

${\mathcal{A}}_{\mathrm{large}}^{n_{0}}:=\big{\\{}|{\mathcal{C}}^{\scriptscriptstyle(1)}_{n_{0},\mathrm{base}}[1,n_{0}^{2/(\tau-1)})|\geq
n_{0}^{1-\delta/4}\big{\\}}.$ (4.24)

Conditionally on ${\mathcal{A}}_{\mathrm{large}}^{n_{0}}$, the component
${\mathcal{C}}_{0}$ is large enough to play the role of ${\mathcal{C}}$ in
(4.23). So, by the law of total probability,

$\mathbb{P}\big{(}{\mathcal{Q}}_{0}\mbox{ is
$0$-good}\big{)}\geq\mathbb{P}\big{(}{\mathcal{A}}_{\mathrm{large}}^{n_{0}}\big{)}\cdot\mathbb{P}\big{(}|{\mathcal{C}}_{0}\cap{\mathcal{V}}^{\scriptscriptstyle\mathrm{spr}}_{{\mathcal{Q}}_{0}}[n_{0}^{\gamma},2n_{0}^{\gamma})|\geq\delta^{\prime}n_{0}^{-\delta/4}n_{0}^{\zeta}\mid{\mathcal{A}}_{\mathrm{large}}^{n_{0}}\big{)}.$
(4.25)

We show that both factors on the right-hand side tend to one as
$n_{0}\to\infty$.

_(Con)-step of level- $0$._ We first consider
$\mathbb{P}({\mathcal{A}}_{\mathrm{large}}^{n_{0}})$ with the event defined in
(4.24). If the thinned PPP
${\mathcal{V}}^{\scriptscriptstyle\mathrm{base}}_{n_{0}}$ contains no vertices
of mark at least $n_{0}^{2/(\tau-1)}$, then
${\mathcal{C}}^{\scriptscriptstyle(1)}_{n_{0},\mathrm{base}}[1,n_{0}^{2/(\tau-1)})$
and ${\mathcal{C}}^{\scriptscriptstyle(1)}_{n_{0},\mathrm{base}}$ coincide.
Here ${\mathcal{C}}^{\scriptscriptstyle(1)}_{n_{0},\mathrm{base}}$ is the
largest component of the thinned PPP in ${\mathcal{Q}}_{0}$. By a union bound
over the complementary events, it follows that

$\displaystyle\mathbb{P}({\mathcal{A}}_{\mathrm{large}}^{n_{0}})$
$\displaystyle\geq\mathbb{P}\big{(}|{\mathcal{V}}^{\scriptscriptstyle\mathrm{base}}_{{\mathcal{Q}}_{0}}[n_{0}^{2/(\tau-1)},\infty)|=0,\
|{\mathcal{C}}^{\scriptscriptstyle(1)}_{n_{0},\mathrm{base}}|\geq
n_{0}^{1-\delta/4},\big{)}$ $\displaystyle\geq
1-\mathbb{P}\big{(}|{\mathcal{C}}^{\scriptscriptstyle(1)}_{n_{0},\mathrm{base}}|\leq
n_{0}^{1-\delta/4}\big{)}-\mathbb{P}\big{(}|{\mathcal{V}}^{\scriptscriptstyle\mathrm{base}}_{{\mathcal{Q}}_{0}}[n_{0}^{2/(\tau-1)},\infty)|>0\big{)}.$
(4.26)

By 4.6, ${\mathcal{C}}^{\scriptscriptstyle(1)}_{n_{0},\mathrm{base}}$ has the
same distribution as the largest component of a supercritical KSRG with edge
density $\beta q^{d}>\beta_{c}$ inside the box $\Lambda_{qn_{0}}$, with
$q\in(0,1)$ from Definition 4.5. Hence, by Lemma 4.2, the first probability on
the right-hand side in (4.26) tends to zero as $n_{0}q\to\infty$ (we absorb
the factor $q$ into the exponent $1-\delta/4$ by choosing
$\varepsilon<\delta/4$ in Lemma 4.2). The intensity of
${\mathcal{V}}^{\scriptscriptstyle\mathrm{base}}$ is $q\mathrm{Leb}\times
F_{W}(\mathrm{d}w)=q\mathrm{Leb}\times(\tau-1)w^{-\tau}\mathrm{d}w$ and the
box has volume $n_{0}$. So, the expected number of vertices in
${\mathcal{V}}^{\scriptscriptstyle\mathrm{base}}_{{\mathcal{Q}}_{0}}[n_{0}^{2/(\tau-1)},\infty)$
is $\Theta(n_{0}^{1}n_{0}^{-2})$), which tends to zero. Hence, the second
error term in (4.26) also tends to zero. This shows that
$\mathbb{P}({\mathcal{A}}_{\mathrm{large}}^{n_{0}})\to 1$ in (4.25).

_(Mark) step of level- $0$._ We now carry out the _(Mark)_ -step of level $0$:
We inspect the second factor in (4.25). The vertices
${\mathcal{V}}^{\scriptscriptstyle\mathrm{spr}}_{{\mathcal{Q}}_{0}}[n_{0}^{\gamma},2n_{0}^{\gamma})$
form a PPP with intensity
$(1-q)\mathrm{Leb}\times(\tau-1)w^{-\tau}\mathrm{d}w$ in a box with volume
$n_{0}$. Its expected size is

$\mathbb{E}\big{[}|{\mathcal{V}}^{\scriptscriptstyle\mathrm{spr}}_{{\mathcal{Q}}_{0}}[n_{0}^{\gamma},2n_{0}^{\gamma})|\big{]}=(1-q)(1-2^{-(\tau-1)})n_{0}^{1-\gamma(\tau-1)}=(1-q)(1-2^{-(\tau-1)})n_{0}^{\zeta}.$
(4.27)

Further, ${\mathcal{V}}^{\scriptscriptstyle\mathrm{spr}}$ is independent of
${\mathcal{V}}^{{\scriptscriptstyle\mathrm{base}}}$ and thus also of the graph
${\mathcal{G}}^{\scriptscriptstyle\mathrm{base}}_{n_{0}}[1,n_{0}^{2/(\tau-1)})$,
the graph induced by vertices whose marks are in the interval
$[1,n_{0}^{2/(\tau-1)}$) and the event
${\mathcal{A}}_{\mathrm{large}}^{n_{0}}$. On this event, there are at least
$n_{0}^{1-\delta/4}$ vertices in the above mentioned component, and each
vertex there has mark at least one. We use that the maximal distance between
two vertices in ${\mathcal{Q}}_{0}$ is $\sqrt{d}n_{0}^{1/d}$. Given
${\mathcal{A}}_{\mathrm{large}}^{n_{0}}$, for each vertex $v$ in
${\mathcal{V}}^{\scriptscriptstyle\mathrm{spr}}_{{\mathcal{Q}}_{0}}[n_{0}^{\gamma},2n_{0}^{\gamma})$,

$\displaystyle\mathbb{P}\Big{(}v\sim{\mathcal{C}}_{n_{0},{\scriptscriptstyle\mathrm{base}}}^{\scriptscriptstyle(1)}[1,n_{0}^{2/(\tau-1)})\mid{\mathcal{A}}_{\mathrm{large}}^{n_{0}}\Big{)}$
$\displaystyle\geq 1-\Big{(}1-p\big{(}1\wedge\frac{\beta
n_{0}^{\gamma}}{d^{d/2}n_{0}}\big{)}^{\alpha}\Big{)}^{n_{0}^{1-\delta/4}}$
$\displaystyle\geq 1-\exp\big{(}-p\beta^{\alpha}d^{-\alpha
d/2}n_{0}^{-\delta/4}n_{0}^{\gamma\alpha-(\alpha-1)}\big{)}$
$\displaystyle=1-\exp\big{(}-p\beta^{\alpha}d^{-\alpha
d/2}n_{0}^{-\delta/4}\big{)}.$

We used that $\gamma<1$, so $n_{0}^{\gamma-1}=o(1)$ and the minimum is taken
at the second term for $n_{0}$ sufficiently large to obtain the first
inequality. Then we used that $\gamma=(\alpha-1)/\alpha$ to obtain the second
row. For $n_{0}$ sufficiently large, we use the bound $1-{\mathrm{e}}^{-x}\geq
x/2$ for $x<1$. Therefore, the right-hand side is at least
$p\beta^{\alpha}d^{-\alpha d/2}n_{0}^{-\delta/4}/2$. This is the connectivity
estimate for a single vertex. Since each vertex in
${\mathcal{V}}^{\scriptscriptstyle\mathrm{spr}}_{{\mathcal{Q}}_{0}}[n_{0}^{\gamma},2n_{0}^{\gamma})$
connects independently to
${\mathcal{C}}_{n_{0},\mathrm{base}}^{\scriptscriptstyle(1)}[1,n_{0}^{2/(\tau-1)})$,
the number of connecting vertices is Poisson with mean at least the mean in
(4.27) multiplied with this connectivity estimate. So, using
$\rho_{0}=n_{0}^{-\delta/4}$ in (4.14),

$\displaystyle\mathbb{P}\big{(}$
$\displaystyle|{\mathcal{V}}^{\scriptscriptstyle\mathrm{spr}}_{{\mathcal{Q}}_{0}}[n_{0}^{\gamma},2n_{0}^{\gamma})\cap{\mathcal{C}}_{0}|<\delta^{\prime}\rho_{0}n_{0}^{\zeta}\mid{\mathcal{A}}_{\mathrm{large}}^{n_{0}}\big{)}$
$\displaystyle\leq\mathbb{P}\big{(}\mathrm{Poi}\big{(}(1-q)(1-2^{-(\tau-1)})\cdot\tfrac{1}{2}p\beta^{\alpha}d^{-\alpha
d/2}\cdot
n_{0}^{\zeta-\delta/4}\big{)}<\delta^{\prime}n_{0}^{\zeta-\delta/4}\big{)}.$

By the choice of $\delta^{\prime}$ in (4.10) and concentration of Poisson
variables in Lemma A.1, the right-hand side tends to zero as $n_{0}\to\infty$.
This proves that the second factor in (4.25) tends to $1$ as well. This
finishes the proof of 4.10. ∎

####  4.2.4. Advancing the induction: the iterative step.

4.10 shows that level-$0$ boxes are good with constant probability. In the
next claim we advance the induction by bounding the probabilities of the steps
_(Sub), (Con), (Mark)_ in Section 4.2.1 for level-$i$ boxes.

######  Claim 4.11 (Advancing the induction).

Consider a supercritical KSRG on a PPP with parameters such that
$\zeta_{\mathrm{hl}}>0$. Assume $\delta\in(0,\zeta/2)$. There exists a
constant $n_{0}^{\star}>0$ such that for all $n_{0}\geq n_{0}^{\star}$ in
Definition 4.8, for all $i\geq 0$,

$\mathbb{P}\big{(}{\mathcal{Q}}_{i}(x)\mbox{ is
$i$-bad}\big{)}\leq\exp\big{(}-6(n_{i}/n_{0})^{\zeta-\delta}\big{)}:=\mathrm{err}_{i}.$
(4.28)

###### Proof.

When $i=0$ the statement follows from 4.10. Let $i\geq 1$ and assume that
(4.28) holds for level-$(i-1)$ boxes. We now follow the steps _(Sub), (Con),
(Mark)_ in Section 4.2.1 and bound their error probabilities. Like in 4.10, we
assume w.l.o.g. that $x=0$, and write
${\mathcal{Q}}_{i}:={\mathcal{Q}}_{i}(0)$.

_Enough subboxes are good._ We start with the _(Sub)_ step. Since
$n_{i}=m_{i}n_{i-1}$ by (4.11), we can partition ${\mathcal{Q}}_{i}(x)$ into
$m_{i}$ subboxes of volume $n_{i-1}$. Let $(x_{i})_{i\leq m_{i}}$ denote the
centers of these boxes. Define the event

${\mathcal{A}}_{\mathrm{sub}}:=\Big{\\{}\sum_{j\in[m_{i}]}\mathds{1}_{\\{{\mathcal{Q}}_{i-1}(x_{j})\text{
is $(i-1)$-bad}\\}}<\varepsilon_{i}m_{i}\Big{\\}}.$ (4.29)

In words, ${\mathcal{Q}}_{i}(x)$ contains at least $(1-\varepsilon_{i})m_{i}$
many $(i-1)$-good subboxes. Using that disjoint boxes are i.i.d., the
induction hypothesis yields that the number of bad boxes is stochastically
dominated by a $\mathrm{Bin}(m_{i},\mathrm{err}_{i-1})$ random variable, i.e.,

$\displaystyle\mathbb{P}\big{(}\neg{\mathcal{A}}_{\mathrm{sub}})\leq\mathbb{P}\Big{(}\mathrm{Bin}\big{(}m_{i},\mathrm{err}_{i-1})\big{)}\geq\varepsilon_{i}m_{i}\Big{)}\leq\sum_{k=\lceil\varepsilon_{i}m_{i}\rceil}^{m_{i}}\binom{m_{i}}{k}\mathrm{err}_{i-1}^{k}.$

We use that $\binom{m_{i}}{k}\leq({\mathrm{e}}m_{i}/k)^{k}$, so the binomial
coefficient is at most $({\mathrm{e}}/\varepsilon_{i})^{k}$ for all
$k\geq\varepsilon_{i}m_{i}$. Hence, using the definition of
$\mathrm{err}_{i-1}$ from (4.28),

$\mathbb{P}\big{(}\neg{\mathcal{A}}_{\mathrm{sub}})\leq\sum_{k=\lceil\varepsilon_{i}m_{i}\rceil}^{\infty}\exp\big{(}-k(6(n_{i-1}/n_{0})^{\zeta-\delta}-\log({\mathrm{e}}/\varepsilon_{i}))\big{)}.$

We use that $\varepsilon_{i}=(i+1)^{-2}$ by definition in (4.13): when $i=1$
we compute
$6-\log({\mathrm{e}}/\varepsilon_{1})=6-\log(4{\mathrm{e}})=5-\log(4)>3$; for
$i\geq 2$, by the second inequality in (4.20) for $C=4/6$, we obtain that
$6(n_{i-1}/n_{0})^{\zeta-\delta}-\log({\mathrm{e}}/\varepsilon_{i})>3(n_{i-1}/n_{0})^{\zeta-\delta}$
when $n_{0}$ is sufficiently large. We obtain a geometric series with base
$\exp(-3(n_{i-1}/n_{0})^{\zeta-\delta})$, which is at most $1/2$ for all
$i\geq 2$ by choosing $n_{0}$ sufficiently large. Evaluating the geometric sum
and then using the bound (Sub) in (4.16) yields

$\displaystyle\mathbb{P}\big{(}\neg{\mathcal{A}}_{\mathrm{sub}})$
$\displaystyle\leq\sum_{k=\lceil\varepsilon_{i}m_{i}\rceil}^{\infty}\exp\big{(}-3(n_{i-1}/n_{0})^{\zeta-\delta}\big{)}^{k}\leq\exp\big{(}-3\varepsilon_{i}m_{i}(n_{i-1}/n_{0})^{\zeta-\delta}\big{)}/2$
(4.30)
$\displaystyle\leq\tfrac{1}{3}\exp\big{(}-6(n_{i}/n_{0})^{\zeta-\delta}\big{)}.$

This finishes the _(Sub)_ -step of level-$i$.

_Connectivity: the local giant is big enough._ We now move on to the _(Con)_
-step in Section 4.2.1. In level $i-1$, we used the vertex sets
${\mathcal{V}}^{\scriptscriptstyle\mathrm{base}}_{{\mathcal{Q}}_{i-1}(x_{j})}\big{[}1,n_{0}^{2/(\tau-1)}\big{)}\cup{\mathcal{V}}^{\scriptscriptstyle\mathrm{spr}}_{{\mathcal{Q}}_{i-1}(x_{j})}[1,2n_{i-1}^{\gamma})$
in each subbox $j\in[m_{i}]$, see (4.12). We denote the level-$(i-1)$ graphs
on these vertex sets by $\widehat{\mathcal{G}}_{n_{i-1},x_{j}}$. We now reveal
the realization of $(\widehat{\mathcal{G}}_{n_{i-1},x_{j}})_{j\leq m_{i}}$ for
all $j\leq m_{i}$ in the level-$(i-1)$ subboxes of ${\mathcal{Q}}_{i}(x)$, and
assume that the realization satisfies the event ${\mathcal{A}}_{\mathrm{sub}}$
for ${\mathcal{Q}}_{i}(x)$. We write

$\displaystyle\mathrm{pre\textnormal{-}}\widehat{\mathcal{G}}_{n_{i}}$
$\displaystyle:=\cup_{j\leq
m_{i}}\widehat{\mathcal{G}}_{n_{i-1},x_{j}}\quad\mbox{on}\quad$ (4.31)
$\displaystyle{\mathcal{V}}_{\mathrm{pre}}$ $\displaystyle:=\cup_{j\leq
m_{i}}{\mathcal{V}}^{\scriptscriptstyle\mathrm{base}}_{{\mathcal{Q}}_{i-1}(x_{j})}\big{[}1,n_{0}^{2/(\tau-1)}\big{)}\cup{\mathcal{V}}^{\scriptscriptstyle\mathrm{spr}}_{{\mathcal{Q}}_{i-1}(x_{j})}[1,2n_{i-1}^{\gamma}).$

Since the realization satisfies ${\mathcal{A}}_{\mathrm{sub}}$, at least
$(1-\varepsilon_{i})m_{i}$ many subboxes are $(i-1)$-good. We re-label boxes
so that the boxes with indices $j\leq(1-\varepsilon_{i})m_{i}$ are all
$(i-1)$-good. In $\mathrm{pre\textnormal{-}}\widehat{\mathcal{G}}_{n_{i}}$ we
did not reveal yet whether vertices in _different_ level-$(i-1)$ subboxes are
connected to each other or not. The graph $\widehat{\mathcal{G}}_{n_{i}}$
which contains $\mathrm{pre\textnormal{-}}\widehat{\mathcal{G}}_{n_{i}}$
additionally contains these edges between subboxes.

_The Erdős-Rényi type auxiliary graph._ The definition of $(i-1)$-goodness in
(4.15) gives us components ${\mathcal{C}}_{i-1,x_{j}}$ in each good subbox
with size at least $\rho_{i-1}n_{i-1}$. Consider the auxiliary graph
${\mathcal{H}}=({\mathcal{V}}_{\mathcal{H}},{\mathcal{E}}_{\mathcal{H}})$ in
which the vertex
$j\in{\mathcal{V}}_{\mathcal{H}}:=[\lceil(1-\varepsilon_{i})m_{i}\rceil]$
corresponds to ${\mathcal{C}}_{i-1,x_{j}}$, and two vertices
$j,k\in{\mathcal{V}}_{\mathcal{H}}$ are connected by an edge if the components
${\mathcal{C}}_{i-1,x_{j}}$ and ${\mathcal{C}}_{i-1,x_{k}}$ are connected by
an edge in $\widehat{\mathcal{G}}_{n_{i}}$. If the auxiliary graph
${\mathcal{H}}$ is connected, then ${\mathcal{Q}}_{i}(x)$ contains a component
that has size at least $(1-\varepsilon_{i})m_{i}\cdot\rho_{i-1}n_{i-1}$. Since
$m_{i}n_{i-1}=n_{i}$ and $\rho_{i-1}(1-\varepsilon_{i})=\rho_{i}$ by (4.11)
and (4.14), respectively, this size is at least $\rho_{i}n_{i}$. Therefore, it
satisfies the first criterion for being $i$-good in (4.15). Hence, for all
realizations $\mathrm{pre\textnormal{-}}\widehat{\mathcal{G}}_{n_{i}}$
satisfying ${\mathcal{A}}_{\mathrm{sub}}$,

$\mathbb{P}(\exists\mbox{ component
}{\mathcal{C}}_{i}:|{\mathcal{C}}_{i}|\geq\rho_{i}n_{i}\mid\mathrm{pre\textnormal{-}}\widehat{\mathcal{G}}_{n_{i}})\geq\mathbb{P}({\mathcal{H}}\mbox{
connected}\mid\mathrm{pre\textnormal{-}}\widehat{\mathcal{G}}_{n_{i}}).$
(4.32)

We now prove that ${\mathcal{H}}$ stochastically dominates an Erdős-Rényi
graph. The criteria for being $(i-1)$-good in (4.15) guarantee that the
level-$(i-1)$ good subboxes contain a component ${\mathcal{C}}_{i-1,x_{j}}$
with size at least $\rho_{i-1}n_{i-1}$, _and_ this component contains at least
$\delta^{\prime}\rho_{i-1}n_{i-1}^{\zeta}$ vertices of mark in
$[n_{i-1}^{\gamma},2n_{i-1}^{\gamma})$. We bound the probability that there is
an edge between two such components in different good subboxes by checking
whether any of the potential edges between the
$\delta^{\prime}\rho_{i-1}n_{i-1}^{\zeta}$ many level-$(i-1)$ high mark
vertices in one box and the $\rho_{i-1}n_{i-1}$ many vertices in the component
of mark at least $1$ in the other box is present. Any two vertices in
$Q_{i}(x)$ are at distance at most $\sqrt{d}n_{i}^{1/d}$, so using the
connection probability in (4.6) we compute for any _good_ subboxes with index
$j,k$ that

$\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}}\big{)}$
$\displaystyle\leq\Big{(}1-p\big{(}1\wedge\tfrac{\beta
n_{i-1}^{\gamma}}{\sqrt{d}^{d}n_{i}}\big{)}^{\alpha}\Big{)}^{\delta^{\prime}\rho_{i-1}^{2}n_{i-1}^{1+\zeta}}$
$\displaystyle\leq\exp\big{(}-p\delta^{\prime}\beta^{\alpha}d^{-\alpha
d/2}\rho_{i-1}^{2}n_{i-1}^{1+\zeta+\gamma\alpha}n_{i}^{-\alpha}\big{)}$
$\displaystyle=\exp\big{(}-p\delta^{\prime}\beta^{\alpha}d^{-\alpha
d/2}\rho_{i-1}^{2}n_{i-1}^{\zeta+\alpha}n_{i}^{-\alpha}\big{)}=:1-q_{i},$
(4.33)

where we used that $\gamma=1-1/\alpha$ to get the last row, and also to see
that the minimum is at the second term in the first row, since
$n_{i-1}^{\gamma}/n_{i}$ can be made arbitrarily small by choosing $n_{0}$
sufficiently large, see (4.11). The connectivity between different local large
components is conditionally independent given the realization of
$\mathrm{pre}\textnormal{-}\widehat{\mathcal{G}}_{n_{i}}$, so the auxiliary
graph ${\mathcal{H}}$ dominates an Erdős-Rényi graph
$G(\lceil(1-\varepsilon_{i})m_{i}\rceil,q_{i})$. The reader may verify that
$m_{i}q_{i}\gg\log m_{i}$ for all $i\geq 1$ if $n_{0}$ is sufficiently large,
so by 4.7 on the connectivity of $G$,

$\displaystyle\mathds{1}_{\\{{\mathcal{A}}_{\mathrm{sub}}\\}}\mathbb{P}\big{(}{\mathcal{H}}\text{
not conn.}\mid\text{pre-}\widehat{\mathcal{G}}_{n_{i}}\big{)}$
$\displaystyle\leq
3({\mathrm{e}}m_{i})^{2}(1-q_{i})^{(1-\varepsilon_{i})m_{i}/2}$
$\displaystyle\leq
3({\mathrm{e}}m_{i})^{2}\exp\big{(}-\tfrac{3p\delta^{\prime}\beta^{\alpha}}{8d^{\alpha
d/2}}\rho_{i-1}^{2}n_{i-1}^{\zeta+\alpha}n_{i}^{-\alpha}m_{i}\big{)},$ (4.34)

where we substituted $1-q_{i}$ from (4.33), and used that
$1-\varepsilon_{i}\geq 3/4$ for all $i\geq 1$. We substitute
$n_{i}=m_{i}n_{i-1}$ to obtain the first row below, and then use the
inequality (Con) in (4.17) to see that the $i$-dependent factors together can
be bounded from below by $Cn_{i}^{\zeta-\delta}$ for any constant $C>0$ to get
the second row. Here, we can choose $n_{0}$ sufficiently large so that $C$
cancels out the constant ($\delta^{\prime},\beta,p,d$-dependent) prefactors:

$\displaystyle\mathds{1}_{\\{{\mathcal{A}}_{\mathrm{sub}}\\}}\mathbb{P}\big{(}{\mathcal{H}}\text{
not conn.}\mid\text{pre-}\widehat{\mathcal{G}}_{n_{i}}\big{)}$
$\displaystyle\leq
3({\mathrm{e}}m_{i})^{2}\exp\big{(}-\tfrac{3p\delta^{\prime}\beta^{\alpha}}{8d^{\alpha
d/2}}\rho_{i-1}^{2}n_{i-1}^{\zeta}m_{i}^{1-\alpha}\big{)}.$ $\displaystyle\leq
3({\mathrm{e}}m_{i})^{2}\exp\big{(}-7n_{i}^{\zeta-\delta}\big{)}\leq\tfrac{1}{3}\exp\big{(}-6n_{i}^{\zeta-\delta}\big{)}.$
(4.35)

Returning to (4.32), this shows that the first condition of being level-$i$
good in (4.15), i.e., containing a connected component with size at least
$\rho_{i}n_{i}$, holds with probability at least
$1-\exp(-6n_{i}^{\zeta-\delta})/3$, given ${\mathcal{A}}_{\mathrm{sub}}$. This
finishes the _(Con)_ -step. We summarize it as follows: since
$\mathbb{P}\big{(}\neg{\mathcal{A}}_{\mathrm{sub}})\leq\exp\big{(}-6(n_{i}/n_{0})^{\zeta-\delta}\big{)}/3$
by (4.30),

$\displaystyle\mathbb{P}\big{(}{\mathcal{Q}}_{i}(x)\text{ is $i$-bad}\big{)}$
$\displaystyle\leq\mathbb{P}\big{(}\neg{\mathcal{A}}_{\mathrm{sub}}\big{)}+\mathbb{E}\big{[}\mathds{1}_{\\{{\mathcal{A}}_{\mathrm{sub}}\\}}\mathbb{P}\big{(}{\mathcal{Q}}_{i}(x)\text{
is $i$-bad}\mid\text{pre-}\widehat{\mathcal{G}}_{n_{i}}\big{)}\big{]}$
$\displaystyle\begin{aligned}
&\leq\mathbb{P}\big{(}\neg{\mathcal{A}}_{\mathrm{sub}}\big{)}+\mathbb{E}\big{[}\mathds{1}_{\\{{\mathcal{A}}_{\mathrm{sub}}\\}}\mathbb{P}\big{(}{\mathcal{H}}\text{
not conn.}\mid\text{pre-}\widehat{\mathcal{G}}_{n_{i}}\big{)}\big{]}\\\
&\quad+\mathbb{E}\big{[}\mathds{1}_{\\{{\mathcal{A}}_{\mathrm{sub}}\\}}\mathbb{P}\big{(}{\mathcal{Q}}_{i}(x)\text{
is $i$-bad}\mid\text{pre-}\widehat{\mathcal{G}}_{n_{i}},{\mathcal{H}}\text{
connected}\big{)}\big{]}\end{aligned}$ (4.36)
$\displaystyle\leq\tfrac{2}{3}\exp\big{(}-6(n_{i}/n_{0})^{\zeta-\delta}\big{)}+\mathbb{E}\big{[}\mathds{1}_{\\{{\mathcal{A}}_{\mathrm{sub}}\\}}\mathbb{P}\big{(}{\mathcal{Q}}_{i}(x)\text{
is $i$-bad}\mid\text{pre-}\widehat{\mathcal{G}}_{n_{i}},{\mathcal{H}}\text{
conn.}\big{)}\big{]},$

where the error of the _(Con)_ -step is the first term in the last row, and
the second term still needs to be bounded during the _(Mark)_ step.

_Enough high-mark vertices in level- $i$._ Finally, we treat the _(Mark)_
-step in Section 4.2.1. That is, we bound the conditional probability in the
last row above. This corresponds to the second criterion in (4.15), i.e., the
requirement that ${\mathcal{C}}_{i}$ also contains enough level-$i$ high mark
vertices. On the event ${\mathcal{A}}_{\mathrm{sub}}\cap\\{{\mathcal{H}}\text{
is connected}\\}$, we set ${\mathcal{C}}_{i}$ to be the connected component in
$\widehat{\mathcal{G}}_{n_{i}}$ that contains
$\cup_{j\in{\mathcal{V}}_{\mathcal{H}}}{\mathcal{C}}_{i-1,x_{j}}=:\mathrm{pre\textnormal{-}}{\mathcal{C}}_{i}$.
By the argument leading to (4.32),
$\mathrm{pre\textnormal{-}}{\mathcal{C}}_{i}$ has already size at least
$\rho_{i}n_{i}$. Hence, by the criterion in (4.15), we need to bound

$\displaystyle\mathds{1}_{\\{{\mathcal{A}}_{\mathrm{sub}}\\}}\mathbb{P}\big{(}|{\mathcal{V}}^{\scriptscriptstyle\mathrm{spr}}_{{\mathcal{Q}}_{i}(x)}[n_{i}^{\gamma},2n_{i}^{\gamma})\cap{\mathcal{C}}_{i}|<\delta^{\prime}\rho_{i}n_{i}^{1-\gamma(\tau-1)}$
$\displaystyle\mid\text{pre-}\widehat{\mathcal{G}}_{n_{i}},{\mathcal{H}}\text{
connected}\big{)}.$ (4.37)

We argue similarly as for $i=0$ around and below (4.27). Since
$\mathrm{pre\textnormal{-}}{\mathcal{C}}_{i}\subseteq{\mathcal{V}}_{\mathrm{pre}}$
in (4.31), and $2n_{i-1}^{\gamma}<n_{i}^{\gamma}$ by (4.22), the already
revealed vertex set ${\mathcal{V}}_{\mathrm{pre}}$ is disjoint and thus
independent of
${\mathcal{V}}^{\scriptscriptstyle\mathrm{spr}}_{{\mathcal{Q}}_{i}(x)}[n_{i}^{\gamma},2n_{i}^{\gamma})$.
Hence, the PPP
${\mathcal{V}}^{\scriptscriptstyle\mathrm{spr}}_{{\mathcal{Q}}_{i}(x)}[n_{i}^{\gamma},2n_{i}^{\gamma})$
itself is independent of the conditioning in (4.37). Using the intensity in
(4.5), its expected size is

$\mathbb{E}\big{[}|{\mathcal{V}}^{\scriptscriptstyle\mathrm{spr}}_{{\mathcal{Q}}_{i}(x)}[n_{i}^{\gamma},2n_{i}^{\gamma})|\big{]}=(1-q)(1-2^{-(\tau-1)})n_{i}^{1-\gamma(\tau-1)}=(1-q)(1-2^{-(\tau-1)})n_{i}^{\zeta},$
(4.38)

with $q\in(0,1)$ from the Definition 4.5. There are at least $\rho_{i}n_{i}$
vertices in $\mathrm{pre\textnormal{-}}{\mathcal{C}}_{i}$, each with mark at
least one, and each pair of vertices inside ${\mathcal{Q}}_{i}$ is within
distance $\sqrt{d}n_{i}^{1/d}$. So, we get using the connection probability in
(4.6) that each individual vertex in
${\mathcal{V}}^{\scriptscriptstyle\mathrm{spr}}_{{\mathcal{Q}}_{i}(x)}[n_{i}^{\gamma},2n_{i}^{\gamma})$
connects by an edge to
$\mathrm{pre\textnormal{-}}{\mathcal{C}}_{i}\subseteq{\mathcal{C}}_{i}$ with
probability at least

$\displaystyle 1-\Big{(}1-p\big{(}1\wedge\tfrac{\beta
n_{i}^{\gamma}}{\sqrt{d}^{d}n_{i}}\big{)}^{\alpha}\Big{)}^{\rho_{i}n_{i}}$
$\displaystyle\geq 1-\exp\big{(}-p\beta^{\alpha}d^{-\alpha
d/2}\rho_{i}n_{i}^{\gamma\alpha-(\alpha-1)}\big{)}$
$\displaystyle=1-\exp\big{(}-p\beta^{\alpha}d^{-\alpha d/2}\rho_{i}\big{)}.$

To obtain the second expression, we used that the minimum is at the second
term for $n_{0}$ sufficiently large, and $\gamma=(\alpha-1)/\alpha$ to get the
second row. Since $\rho_{i}=\Theta(n_{0}^{-\delta/4})$ as $n_{0}$ tends to
infinity by (4.14), we may assume that $n_{0}$ is so large so that the bound
$1-e^{-x}\geq x/2$ applies (for all $x\leq 1$), and the right-hand side is at
least $p\beta^{\alpha}d^{-\alpha d/2}\rho_{i}/2$. Since each vertex in
${\mathcal{V}}^{\scriptscriptstyle\mathrm{spr}}_{{\mathcal{Q}}_{i}(x)}[n_{i}^{\gamma},2n_{i}^{\gamma})$
connects independently to $\mathrm{pre\textnormal{-}}{\mathcal{C}}_{i}$, the
number of connecting vertices forms a PPP with mean at least the product of
(4.38) multiplied with this bound. So,

$\displaystyle\mathds{1}_{\\{{\mathcal{A}}_{\mathrm{sub}}\\}}\mathbb{P}\big{(}$
$\displaystyle|{\mathcal{V}}^{\scriptscriptstyle\mathrm{spr}}_{{\mathcal{Q}}_{i}(x)}[n_{i}^{\gamma},2n_{i}^{\gamma})\cap{\mathcal{C}}_{i}|<\delta^{\prime}\rho_{i}n_{i}^{\zeta}\mid\text{pre-}\widehat{\mathcal{G}}_{n_{i}},{\mathcal{H}}\text{
conn.}\big{)}$
$\displaystyle\leq\mathbb{P}\big{(}\mathrm{Poi}\big{(}(1-q)(1-2^{-(\tau-1)})\cdot\tfrac{1}{2}p\beta^{\alpha}d^{-\alpha
d/2}\cdot\rho_{i}n_{i}^{\zeta}\big{)}<\delta^{\prime}\rho_{i}n_{i}^{\zeta}\big{)}.$

The value of $\delta^{\prime}$ in (4.10) is chosen exactly so that
$2\delta^{\prime}$ is the prefactor of $\rho_{i}n_{i}^{\zeta}$ in the mean of
the Poisson variable. Hence, by the concentration of Poisson variables in
Lemma A.1, there exists $c=c(\delta^{\prime})>0$ such that

$\mathds{1}_{\\{{\mathcal{A}}_{\mathrm{sub}}\\}}\mathbb{P}\big{(}|{\mathcal{V}}^{\scriptscriptstyle\mathrm{spr}}_{{\mathcal{Q}}_{i}(x)}[n_{i}^{\gamma},2n_{i}^{\gamma})\cap{\mathcal{C}}_{i}|<\delta^{\prime}\rho_{i}n_{i}^{\zeta}\mid\text{pre-}\widehat{\mathcal{G}}_{n_{i}},{\mathcal{H}}\text{
conn.}\big{)}<\exp\big{(}-c\rho_{i}n_{i}^{\zeta}\big{)},$

Finally, by the bound (Mark) in (4.18), the right-hand side is at most
$\exp\big{(}-6n_{i}^{\zeta-\delta}\big{)}/3$ for $n_{0}$ sufficiently large.
Combining this bound with (4.11) finishes the proof of 4.11. ∎

If the box ${\mathcal{Q}}_{i}(x)$ is $i$-good, then it contains a giant
component on the restricted marks $[1,2n_{i}^{\gamma})$. Thus, Claims 4.10 and
4.11 together prove Proposition 4.1 _along the subsequence_ $n_{i}$, and when
$\zeta=\zeta_{\mathrm{hl}}$. We now prove Proposition 4.1 for arbitrary $n$.

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

W.l.o.g. we may assume that $\delta\in(0,\zeta/2\wedge 1-\zeta)$ in the
statement of the lemma. Let $n_{0}$ be a constant such that Claims 4.10–4.11
hold for all $i\geq 0$. Fix now the sequence $n_{i}$ in (4.11). We may assume
that $n>n_{0}$, since the constant $A$ in the statement of Proposition 4.1 can
be increased to account for values $n\leq n_{0}$. We define

$\displaystyle i_{0}$
$\displaystyle:=\min\\{i:2n_{i}^{\gamma}>n_{0}^{2/(\tau-1)}\\},$
$\displaystyle i_{\ast}$ $\displaystyle:=\max\\{i:n_{i}<n\\},$ (4.39)
$\displaystyle m$ $\displaystyle:=\lfloor(n/n_{i_{\ast}})^{1/d}\rfloor^{d},$
$\displaystyle\tilde{n}$ $\displaystyle:=n_{i_{\ast}}m.$

By increasing the constant $A$ in the statement of Proposition 4.1, we may
assume w.l.o.g. that $i_{\ast}>i_{0}$. Then, there exist $\nu$ such that

$m\geq\nu(n/n_{i_{\ast}}).$ (4.40)

By the definition of $m$ and $\tilde{n}$,
$\Lambda_{\tilde{n}}\subseteq\Lambda_{n}$ can be partitioned into exactly
$m\geq 1$ disjoint boxes of volume $n_{i_{\ast}}$. We denote the boxes of this
partition by
${\mathcal{Q}}_{i_{\ast}}(x_{1}),\ldots,{\mathcal{Q}}_{i_{\ast}}(x_{m})$. From
here on we argue similarly as in the proof of 4.11: we use _(Sub)_ and _Con_
-type steps. We will show that at least half of the boxes are $i_{\ast}$-good,
and afterwards connect the large components in the first $\lceil m/2\rceil$
many $i_{\ast}$-good boxes via a domination to an Erdős-Rényi random graph.

_Enough subboxes are good._ Define

${\mathcal{A}}_{\mathrm{sub}}(n):=\bigg{\\{}\sum_{j\in[m]}\mathds{1}_{\\{{\mathcal{Q}}_{i_{\ast}}(x_{j})\text{
is $i_{\ast}$-bad}\\}}<m/2\bigg{\\}}.$

We follow the calculations from (4.29) until (4.30) and replace
$\varepsilon_{i}$ by $1/2$, $m_{i}$ by $m$ and $n_{i-1}$ by $n_{i_{\ast}}$
there. The bound ${m\choose k}\leq(m/{\mathrm{e}}k)^{k}$ works for all $m\geq
1$ and $k\leq m$. We also use there the second inequality in (4.20) for
$C=4/6$, which also holds for $n_{i_{\ast}}$. So all bounds except the last
row in (4.30) remain valid. Using (4.40) we obtain the bound

$\displaystyle\mathbb{P}\big{(}\neg{\mathcal{A}}_{\mathrm{sub}}(n))$
$\displaystyle\leq\sum_{k=\lceil
m/2\rceil}^{\infty}\exp\big{(}-3(n_{i_{\ast}}/n_{0})^{\zeta-\delta}\big{)}^{k}\leq\exp\big{(}-3(m/2)(n_{i_{\ast}}/n_{0})^{\zeta-\delta}\big{)}/2$
(4.41) $\displaystyle\leq\exp\Big{(}-(\nu/2n_{0}^{\zeta-\delta})\cdot
nn_{i_{\ast}}^{\zeta-\delta-1}\Big{)}.$

As $n>n_{i_{\ast}}$ and $\zeta<1$, it follows that
$n_{i_{\ast}}^{\zeta-\delta-1}>n^{\zeta-\delta-1}$, which, when rearranged
yields that $nn_{i_{\ast}}^{\zeta-\delta-1}>n^{\zeta-\delta}$. Hence,

$\mathbb{P}\big{(}\neg{\mathcal{A}}_{\mathrm{sub}}(n)\big{)}\leq\exp\Big{(}-(\nu/2n_{0}^{\zeta-\delta})\cdot
n^{\zeta-\delta}\Big{)}.$ (4.42)

This finishes the _(Sub)_ -step for general $n$.

_Connecting local-giants of subboxes._ Now we move on to the _(Con)_ -step in
Section 4.2.1. We follow the argument around (4.31), and define the pre-vertex
set ${\mathcal{V}}_{\mathrm{pre}}$ as there, with $n_{i}$ replaced by $n$,
$i-1$ replaced by $i_{\ast}$, and $m_{i}$ replaced by $m$ there:

$\displaystyle\mathrm{pre\textnormal{-}}\widehat{\mathcal{G}}_{\tilde{n}}$
$\displaystyle:=\cup_{j\leq
m}\widehat{\mathcal{G}}_{n_{i_{\ast}},x_{j}}\quad\mbox{on}\quad$ (4.43)
$\displaystyle{\mathcal{V}}_{\mathrm{pre}}(\tilde{n})$
$\displaystyle:=\cup_{j\leq
m}{\mathcal{V}}^{\scriptscriptstyle\mathrm{base}}_{{\mathcal{Q}}_{i_{\ast}}(x_{j})}\big{[}1,n_{0}^{2/(\tau-1)}\big{)}\cup{\mathcal{V}}^{\scriptscriptstyle\mathrm{spr}}_{{\mathcal{Q}}_{i_{\ast}}(x_{j})}[1,2n_{i_{\ast}}^{\gamma}).$

We reveal the realization of
$\mathrm{pre\textnormal{-}}\widehat{\mathcal{G}}_{n}$, satisfying the
${\mathcal{A}}_{\mathrm{sub}}(n)$. Following the argument above (4.32), we
construct the auxiliary graph ${\mathcal{H}}_{n}$ on vertices representing the
first $[\lceil m/2\rceil]$ many $i_{\ast}$-good subboxes. Each vertex $j$
represents a large component ${\mathcal{C}}_{i_{\ast},x_{j}}$ guaranteed by
the first condition in $i$-goodness in (4.15). Two vertices $j,k$ are
connected by an edge in ${\mathcal{H}}_{n}$ if there is an edge between
${\mathcal{C}}_{i_{\ast},x_{j}}$ and ${\mathcal{C}}_{i_{\ast},x_{k}}$. We
follow the computations between (4.32) and (4.34), and replace there