# Cluster-size decay in supercritical kernel-based spatial random graphs

Joost Jorritsma1 1Department 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 consider a large class of spatially-embedded random graphs that includes
among others long-range percolation, continuum scale-free percolation and the
age-dependent random connection model. We assume that the parameters are such
that there is an infinite component. We identify the stretch-exponent
$\zeta\in(0,1)$ of the subexponential decay of the cluster-size distribution.
That is, with $|{\mathcal{C}}(0)|$ denoting the number of vertices in the
component of the vertex at $0\in{\mathbb{R}}^{d}$, we prove

$\mathbb{P}(k\leq|{\mathcal{C}}(0)|<\infty)=\exp\big{(}-k^{\zeta+o(1)}\big{)},\qquad\text{as
}k\to\infty.$

The value of $\zeta$ undergoes several phase transitions with respect to three
main model parameters: the Euclidean dimension $d$, the power-law tail
exponent $\tau$ of the degree distribution and a long-range parameter $\alpha$
governing the presence of long edges in Euclidean space. In this paper we
present the proof for the region in the phase diagram where the model is a
generalization of continuum scale-free percolation and/or hyperbolic random
graphs: $\zeta$ in this regime depends both on $\tau,\alpha$. We also prove
that the second-largest component in a box of volume $n$ is of size
$\Theta(\log(n)^{1/\zeta+o(1)})$ with high probability. We develop a
deterministic algorithm as a new methodology: we allocate to each partially
revealed cluster $\mathcal{C}$ a spatial set $\mathcal{K}(\mathcal{C})$ with
volume linear in the number of vertices in $\mathcal{C}$, so that not-yet-
revealed vertices with spatial location in $\mathcal{K}(\mathcal{C})$ have
good connection probability to $\mathcal{C}$. This algorithm makes it possible
to prove that too large components $\mathcal{C}$ – regardless of the spatial
configuration of its vertices – cannot exist outside of the giant component,
enabling us to treat both de-localized and locally dense components in space.

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

MSC Class: 05C80, 60K35.

##  1\. Introduction

In this paper we study component sizes in a large class of spatially embedded
random graph models. For nearest neighbor Bernoulli percolation on
${\mathbb{Z}}^{d}$ [8], it is a result of a sequence of works [2, 4, 10, 29,
44, 51] that in a supercritical model, i.e., for $p>p_{c}({\mathbb{Z}}^{d})$ –
the critical percolation probability on ${\mathbb{Z}}^{d}$– and writing
$|{\mathcal{C}}(0)|$ for the number of vertices in the cluster containing the
origin,

$\mathbb{P}(k\leq|{\mathcal{C}}(0)|<\infty)=\exp\big{(}-\Theta(k^{\zeta})\big{)},$
(1.1)

with $\zeta=(d-1)/d$. Intuitively, the stretched exponential decay with
exponent $(d-1)/d$ emanates from the fact that all the $\Omega(k^{(d-1)/d})$
edges on the boundary of a cluster ${\mathcal{C}}$ with $|{\mathcal{C}}|\geq
k$ need to be absent: the tail decay in (1.1) is determined by _surface
tension_. More recently, these results have been extended to Bernoulli
percolation on general classes of transitive graphs [12, 38].

In the present paper and the accompanying paper [43], we consider
$\mathbb{P}(k\leq|{\mathcal{C}}(0)|<\infty)$ for a large class of spatial
random graph models where the degree distribution and/or the edge-length
distribution have heavy tails. We identify when this _structural inhomogeneity
changes the surface-tension driven behavior of finite clusters_ : in those
cases, the cluster-size decay in (1.1) is still stretched exponential, but the
exponent $\zeta$ changes. Its value (together with our proof techniques)
reflects the structure of the infinite/giant component in spatial graph
models: it describes the size and structure of a “backbone” decorated with
“traps” – almost isolated peninsulas attached to a well-connected component.
This topological description is of independent interest, e.g., it affects the
behavior of random walk [14].

Our starting points are continuum and classical _long-range percolation_ (CLRP
and LRP) [3, 63], examples of models where the edge-length distribution has a
heavy tail, while the degree distribution is light-tailed. Relating to the
distribution of small clusters in supercritical settings as in (1.1), the
authors of [13] gave a polylogarithmic upper bound on the size of the second-
largest component $|{\mathcal{C}}_{n}^{\scriptscriptstyle(2)}|$ for some
regimes of long-range percolation in a box of volume $n$, with unidentified
exponent, which is the only known result in this direction. In long-range
percolation, each potential edge
$\\{u,v\\}\in{\mathbb{Z}}^{d}\times{\mathbb{Z}}^{d}$ is independently present
with probability proportional to $\beta^{\alpha}\|u-v\|^{-d\alpha}$ for some
$\alpha,\beta>0$. Our combined results (below, and [42, 43]) show that, under
the additional assumption that $\beta$ is sufficiently large if
$(d-1)/d>2-\alpha$,

$\mathbb{P}(k\leq|{\mathcal{C}}(0)|<\infty)=\exp\big{(}-k^{\max\\{2-\alpha,(d-1)/d\\}+o(1)}\big{)},\
\ \mbox{and}\ \ |{\mathcal{C}}_{n}^{{\scriptscriptstyle(2)}}|=(\log
n)^{1/\max\\{2-\alpha,(d-1)/d\\}+o(1)}.$

Our main focus is to prove (1.1) for models where both the degree- and the
edge-length distribution are heavy-tailed. Recently, several such spatial
random graph models gained significant interest: scale-free percolation (SFP)
[16]; geometric inhomogeneous random graphs (GIRG) [7], continuum scale-free
percolation (CSFP) [17], hyperbolic random graphs (HRG) [50], the ultra-small
scale-free geometric network [65]; the scale-free Gilbert model (SGM) [32],
the Poisson Boolean model with random radii [22], the age- and the weight-
dependent random connection models (ARCM) [24, 26]. Concerning sizes of small
clusters in these models, the only known result concerns the asymptotic size
of the second-largest component of HRGs [46]. Among the more classical models,
for random geometric graphs and Bernoulli percolation on them, the papers [53,
62] identify $|{\mathcal{C}}_{n}^{{\scriptscriptstyle(2)}}|$.

In this paper we prove the stretched exponential decay and identify the values
of $\zeta$ in (1.1) for (regions of the parameter space of) supercritical
continuum scale-free percolation, geometric inhomogeneous random graphs, and
hyperbolic random graphs (CSFP, GIRG, HRG). We introduce a novel proof
technique, the _cover expansion_ , and give a quantitative backbone-and-traps
description of the giant component which is novel for these models.
Additionally, we unfold the general relation between the cluster-size decay
and the size of the second-largest component. In [43], we establish (1.1) for
the scale-free Gilbert model, for the age-dependent random connection model,
for (continuum) long-range percolation, and other regions of the parameter
space of CSFP, GIRG, and HRG. The results here and in the accompanying paper
[43] together also determine the _speed of the lower tail of large deviations_
for the size of the giant component
$|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|$ for all these models. With the
_same_ $\zeta$ as the one in the cluster-size decay, for all sufficiently
small $\rho>0$,

$\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|<\rho
n\big{)}=\exp\big{(}-n^{\zeta+o(1)}\big{)}.$ (1.2)

Here we present the lower bound for (1.2), and in [43] we present the upper
bound.

We consider a framework unifying these models, which we call _Kernel-Based
Spatial Random Graphs_ (KSRG). Beyond the above models, our framework also
contains classical models: nearest-neighbor bond percolation on
${\mathbb{Z}}^{d}$ (NNP), random geometric graphs (RGG) [56, 60]. The KSRG
framework was essentially present in [49], and then refined in [26]. The
following general definition introduces the relevant parameters of the models
that determine a phase diagram of the exponent $\zeta$ in (1.1).

###  1.1. Kernel-based spatial random graphs (KSRG)

A random graph model in the KSRG class requires four ingredients to be
specified:

  * •

a vertex set $\mathcal{V}$: any stationary ergodic point process embedded in a
metric space with norm $\|\cdot\|$; typically a Poisson point process (PPP)
$\Xi$ on ${\mathbb{R}}^{d}$ or a lattice $\mathbb{Z}^{d}$.

  * •

a mark distribution $W$ for vertices, the mark $W_{u}$ of vertex $u$
describing its ability to form connections.

  * •

a profile function $\varrho$, describing the influence of spatial distance on
the probability of an edge.

  * •

a kernel $\kappa$ that describes how marks _rescale_ the spatial distance
between vertices.

Conditionally on the vertex set and on the marks $W_{u}=w_{u}$, $W_{v}=w_{v}$,
two vertices $u$ and $v$ are connected by an edge independently with a
probability given by the _connectivity function_ , which is the composition of
the kernel and the profile, and a parameter $\beta>0$ that controls the edge
density (high values of $\beta$ correspond to higher edge density):

$\mathbf{Prob}(\text{vertex }u\text{ is connected to vertex }v\text{ by an
edge})=\varrho\big{(}\beta\kappa(w_{u},w_{v})\|u-v\|^{-d}\big{)},$ (1.3)

where $\mathbf{Prob}$ is a measure on $\mathcal{V}\times\mathcal{V}$,
conditionally on $\mathcal{V}$ and $\\{w_{v}\\}_{v\in\mathcal{V}}$. These
components together define a random graph model $G(\mathcal{V},\mathcal{E})$,
where $\mathcal{E}$ is a random set of edges.

The role of marks. Throughout the paper, we will assume that the marks are
power-law distributed with tail-exponent $\tau-1$ for some $\tau>1$, that is,

$\mathbb{P}(W\geq x)\sim x^{-(\tau-1)}.$ (1.4)

We shall see that the mark distribution regulates the tail of the degree-
distribution. Marks have different names in the literature: in geometric
inhomogeneous random graphs [7] and scale-free percolation [16], they are
called ‘vertex-weight’ or ‘fitness’, while for hyperbolic random graphs [50]
the mark corresponds to the ‘radius’ of the location of a vertex in the native
representation of the hyperbolic plane. For the age-dependent random
connection model [24] the mark corresponds to the rescaled ‘age’ of a vertex.
For nearest-neighbor percolation, random geometric graphs and long-range
percolation marks are not used for the formation of the graph: in this case we
set $W\equiv 1$, and $\tau=\infty$.

The role of the profile function. The profile function is generally either
_threshold_ or _long-range_ type in the literature, and two typical choices
are as follows:

$\varrho_{\mathrm{thr}}(t)=\mathbbm{1}_{\\{[1/R,\infty]\\}}(t),\quad\quad\varrho_{\alpha}(t)\sim
t^{\alpha},$ (1.5)

where the latter is meant to hold close as $t$ tends to $0$. Since the inverse
distance $1/\|u-v\|^{d}$ is used in (1.3), $\varrho_{\mathrm{thr}}$
corresponds to connecting all pairs of vertices at distance at most $R^{1/d}$
by an edge, while $\varrho_{\alpha}$ – originating from long-range percolation
[63] – allows for long-range edges. The parameter $\alpha>1$ in (1.5)
calibrates this effect: the smaller $\alpha$, the more long-range edges, and
the condition $\alpha>1$ ensures a locally finite graph. With slight abuse of
notation we say that $\alpha=\infty$ when considering a threshold profile.
Both parameters $\alpha,\tau$ _regulate exceptional connectedness_ , but
differently: $\alpha$ in (1.5) controls the presence of exceptionally long
edges, whereas $\tau$ in (1.4) controls exceptionally high-degree vertices.

The role of the kernel function. The kernel function $\kappa$ in (1.3) is a
symmetric non-negative function that rescales the spatial distance so that
high-mark vertices experience ‘shrinkage of spatial distance’ and hence, the
connection probability increases towards high-mark vertices. Models in the
literature commonly use the _trivial_ , _product_ , _max_ , _sum_ , _min_ ,
and _preferential attachment_ (PA) kernels, the last one mimicking the spatial
preferential attachment model [1, 20], i.e., with $\tau\\!>\\!2$ as in (1.4),

$\displaystyle\kappa_{\text{triv}}(x,y)$ $\displaystyle\equiv
1,\quad\kappa_{\mathrm{prod}}(x,y)=xy,\quad\kappa_{\max}(x,y)=\max(x,y),\quad\kappa_{\mathrm{sum}}(x,y)=x+y,$
(1.6) $\displaystyle\kappa_{\min}$
$\displaystyle=\min(x,y)^{\tau},\quad\kappa_{\mathrm{pa}}(x,y)=\max(x,y)\min(x,y)^{\tau-2}.$

This parametrization of the non-trivial kernels yields for the corresponding
models a power-law degree distribution with the same tail exponent as the
marks [26], establishing the scale-free property often desired in complex
network modeling [5, 19, 59, 58]. The kernel $\kappa$ controls the correlation
between degrees of two endpoints of an edge, called _assortativity_ , which,
as we shall see, will also have an important role in determining the value of
$\zeta$ in (1.1), see Section 1.3. The trivial kernel $\kappa_{\mathrm{triv}}$
includes classical models as bond percolation on ${\mathbb{Z}}^{d}$, the
random geometric graph, and (continuum) long-range percolation to the class of
KSRGs.

Other graph properties, further related work. We refer to Table 1 for an
overview of models and their parameters. Many graph properties and processes
on graphs have been studied on KSRGs with non-trivial kernels in the past
years: the _degree distribution_ in [7, 16, 24, 32, 35, 55, 65]; _graph
distances_ in the giant component in [6, 16, 17, 25, 32, 65]; _first-passage
percolation_ on the giant component in [37, 48, 49]; the _random walk_ on the
giant component [11, 26, 31, 45]; the _contact process_ on the giant component
[23, 54]; the _clustering coefficient_ in [7, 15, 21, 36, 64]; _bootstrap
percolation_ in [9, 47], the existence of subcritical and supercritical phases
in [16, 17, 27, 28], and subcritical phase in the more general model [39] that
allows for dependencies between edges.

###  1.2. Four regimes of $\zeta$ in the phase diagram.

In KSRGs in general, one can determine the value of the exponent $\zeta$ of
the cluster-size decay via the following back-of-the-envelope calculation,
that is based on the lower bound and aims to find a spatially _localized_
component of size $\Theta(k)$. Consider two neighboring boxes
$\Lambda_{k}^{{\scriptscriptstyle(1)}},\Lambda_{k}^{{\scriptscriptstyle(2)}}$
of volume $k$ in ${\mathbb{R}}^{d}$, and compute, as a function of $k$, the
expected number of edges
$\mathbb{E}[|{\mathcal{E}}(\Lambda_{k}^{{\scriptscriptstyle(1)}},\Lambda_{k}^{{\scriptscriptstyle(2)}})|]$
between vertices in these boxes, and also the expected number of vertices in
$\Lambda_{k}^{{\scriptscriptstyle(1)}}$ having _at least one edge_ towards a
vertex in $\Lambda_{k}^{{\scriptscriptstyle(2)}}$,
$\mathbb{E}[|{\mathcal{V}}(\Lambda_{k}^{{\scriptscriptstyle(1)}}\\!\to\\!\Lambda_{k}^{{\scriptscriptstyle(2)}})|]$.
If these two quantities are the same order, and are both $\Theta(k^{\zeta})$,
then the probability that none of the potential edges is present is
$\exp(-\Theta(k^{\zeta}))$. The non-presence of all these edges is necessary
for a large isolated cluster of size $\Theta(k)$ to be confined to its
original box. If, however, we find
$\mathbb{E}[|{\mathcal{V}}(\Lambda_{k}^{{\scriptscriptstyle(1)}}\\!\to\\!\Lambda_{k}^{{\scriptscriptstyle(2)}})|]=o(\mathbb{E}[|{\mathcal{E}}(\Lambda_{k}^{{\scriptscriptstyle(1)}},\Lambda_{k}^{{\scriptscriptstyle(2)}})|])$,
and the former quantity is $\Theta(k^{\zeta})$, then typically there are a few
high-mark vertices that have many edges to the neighboring box. The most
likely way to have a component of size $\Theta(k)$ is then to simply _not have
any of these vertices_ present in the two boxes, again happening with
probability $\exp(-\Theta(k^{\zeta}))$. Clearly, large finite clusters can be
non-localized, so the rigorous version of this argument only gives lower
bounds. Nevertheless, it describes the _most likely way of connectivity_
towards and within the infinite/giant component and gives a conjecture for the
value of $\zeta$.

Based on this intuition, we distinguish four possible _types of connectivity_
that describe how neighboring boxes are connected. We call the type of
connectivity that produces the largest contribution to
$\mathbb{E}[|{\mathcal{V}}(\Lambda_{k}^{{\scriptscriptstyle(1)}}\\!\to\\!\Lambda_{k}^{{\scriptscriptstyle(2)}})|]$
the _dominant_ type. Changes of the dominant type give the phase diagram of
$\zeta$ in the parameter space. We visualize these phases in Figure 1(a) for
models using $\kappa_{\mathrm{prod}}$, $\kappa_{\mathrm{pa}}$, or
$\kappa_{\mathrm{max}}$. All arguments below are meant as $k\to\infty$. We say
that the model shows dominantly

  * (ll)

_low-low_ -type connectivity if the main contribution to
$\mathbb{E}[|{\mathcal{V}}(\Lambda^{\scriptscriptstyle(1)}_{k}\\!\to\\!\Lambda^{\scriptscriptstyle(1)}_{k})|]$
is coming from pairs of _low-mark vertices_ (vertices with mark $\Theta(1)$)
at distance $\Theta(k^{1/d})$ from each other. We find
$\mathbb{E}[|{\mathcal{V}}(\Lambda_{k}^{\scriptscriptstyle(1)}\\!\to\\!\Lambda_{k}^{\scriptscriptstyle(2)})|]=\Theta(\mathbb{E}[|{\mathcal{E}}(\Lambda_{k}^{\scriptscriptstyle(1)},\Lambda_{k}^{\scriptscriptstyle(2)})|)]=\Theta(k^{\zeta_{\mathrm{ll}}})$,
where

$\zeta_{\mathrm{ll}}:=2-\alpha,$ (1.7)

which neither depends on $\kappa$ nor on $\tau$ since low-mark vertices are
not affected by those. Models with parameters falling in this regime behave
qualitatively similarly to long-range percolation. We present proofs for
parameter regimes where $\zeta_{\mathrm{ll}}$ is dominant in [43]. In KSRGs
with kernels in (1.6) this regime may occur if both $\alpha<\tau-1$ and
$\alpha<2$.

  * (lh)

_low-high_ -type connectivity if
$\mathbb{E}[|{\mathcal{E}}(\Lambda_{k}^{\scriptscriptstyle(1)},\Lambda_{k}^{\scriptscriptstyle(2)})]\gg\mathbb{E}[|{\mathcal{V}}(\Lambda_{k}^{\scriptscriptstyle(1)}\\!\to\\!\Lambda_{k}^{\scriptscriptstyle(2)})|]$
and the main contributions are coming from edges between a _high-mark_ and a
low-mark vertex ($\Theta(1)$) at distance $\Theta(k^{1/d})$. A vertex has
high-mark here when its mark is $\Omega(k^{\gamma_{\mathrm{lh}}})$, where

$\gamma_{\mathrm{lh}}:=1-1/\alpha$

is the _smallest_ exponent such that a _linear proportion_ of vertices of mark
$\Omega(k^{\gamma_{\mathrm{lh}}})$ in $\Lambda_{k}^{{\scriptscriptstyle(1)}}$
is connected by an edge to a low-mark vertex in
$\Lambda_{k}^{{\scriptscriptstyle(2)}}$. Vertices of mark
$\Omega(k^{\gamma_{\mathrm{lh}}})$ have to be absent to find a large but
finite component confined to $\Lambda^{\scriptscriptstyle(1)}_{k}$, and since
$\mathbb{E}[|{\mathcal{V}}(\Lambda_{k}^{\scriptscriptstyle(1)}\\!\to\\!\Lambda_{k}^{\scriptscriptstyle(2)})|]=\Theta(k^{1-\gamma_{\mathrm{lh}}(\tau-1)})$,
we obtain

$\zeta_{\mathrm{lh}}:=1-\gamma_{\mathrm{lh}}(\tau-1)=1-(\tau-1)(1-1/\alpha).$
(1.8)

We prove in our accompanying paper [43] that this type of behavior is dominant
in KSRGs with kernels $\kappa_{\mathrm{max}},\kappa_{\mathrm{sum}}$, and
$\kappa_{\mathrm{pa}}$ (e.g. for the age-dependent random connection model
[24] and scale-free Gilbert model [32]) when both
$\alpha\in(\tau-1,(\tau-1)/(\tau-2))$, and $\tau\in(2,3)$ holds.

  * (hh)

_high-high_ -type connectivity if
$\mathbb{E}[|{\mathcal{E}}(\Lambda_{k}^{\scriptscriptstyle(1)},\Lambda_{k}^{\scriptscriptstyle(2)})|]\gg\mathbb{E}[|{\mathcal{V}}(\Lambda_{k}^{\scriptscriptstyle(1)}\to\Lambda_{k}^{\scriptscriptstyle(2)})|]$,
and the main contributions are coming from edges between two _high-mark_
vertices at distance $\Theta(k^{1/d})$. A vertex has high mark here when its
mark is $\Omega(k^{\gamma_{\mathrm{hh}}})$, where $\gamma_{\mathrm{hh}}$ is
the smallest exponent such that a _linear proportion_ of vertices of mark
$\Omega(k^{\gamma_{\mathrm{hh}}})$ in $\Lambda_{k}^{{\scriptscriptstyle(1)}}$
is connected by an edge to a high-mark vertex in
$\Lambda_{k}^{{\scriptscriptstyle(2)}}$. This leads in expectation to
$\Theta(k^{\zeta_{\mathrm{hh}}})$ many high-mark vertices in
$\Lambda_{k}^{\scriptscriptstyle(1)}$ and
$\Lambda_{k}^{\scriptscriptstyle(2)}$ (which have to be absent to find a large
but finite component), where
$\zeta_{\mathrm{hh}}:=1-\gamma_{\mathrm{hh}}(\tau-1)$. The formula of
$\gamma_{\mathrm{hh}}$ depends on the choice of the kernel $\kappa$, see
(1.11) below. In this paper we focus on this phase. We show that this type of
connectivity can be dominant in KSRGs with kernel $\kappa_{\mathrm{prod}}$:
(continuum) scale-free percolation (SFP) [16, 17], geometric inhomogeneous
random graphs (GIRG) [7] and hyperbolic random graphs (HRG) [50]) when
$\tau<3$ and $\alpha\geq\tau-1$.

  * (nn)

_nearest-neighbor_ -type connectivity if
$\mathbb{E}[|{\mathcal{E}}(\Lambda_{k}^{\scriptscriptstyle(1)},\Lambda_{k}^{\scriptscriptstyle(2)})|]=\Theta(\mathbb{E}[|{\mathcal{V}}(\Lambda_{k}^{\scriptscriptstyle(1)}\\!\to\\!\Lambda_{k}^{\scriptscriptstyle(2)})|])$,
and the main contributions are coming from edges of length $\Theta(1)$ between
low-mark vertices close to the shared boundary of the two boxes. The expected
number of such edges and vertices is $\Theta(k^{\zeta_{\mathrm{nn}}})$ where

$\zeta_{\mathrm{nn}}:=(d-1)/d.$ (1.9)

KSRGs with kernel $\kappa_{\mathrm{triv}}$ and threshold profile show this
type of connectivity behavior in their _entire_ parameter space, e.g., random
geometric graphs and nearest-neighbor percolation on ${\mathbb{Z}}^{d}$. KSRGs
with either non-trivial kernel or long-range profile also show this phase in a
region of the parameter space, e.g. long-range percolation when
$\alpha>1+1/d$. The accompanying paper [42] treats sub-regions of this phase
in the $(\alpha,\tau)$ parameter-plane.

In general, we conjecture that for any model belonging to the KSRG framework,
the value of $\zeta$ in (1.1) is determined by whichever connectivity type
yields the largest contribution to
$\mathbb{E}[|{\mathcal{E}}(\Lambda_{k}^{\scriptscriptstyle(1)},\Lambda_{k}^{\scriptscriptstyle(2)})|]$
and
$\mathbb{E}[|{\mathcal{V}}(\Lambda_{k}^{\scriptscriptstyle(1)}\\!\to\\!\Lambda_{k}^{\scriptscriptstyle(2)})|]$.
Formally, we may compute

$\max\\{\zeta_{\mathrm{ll}},\zeta_{\mathrm{lh}},\zeta_{\mathrm{hh}},\zeta_{\mathrm{nn}}\\}=:\zeta,$

yielding the conjectured exponent in (1.1). See also Figure 1(a).

Model | $\bm{{\mathcal{V}}}$ | Kernel | Profile | $\zeta$
---|---|---|---|---
Bond-percolation on ${\mathbb{Z}}^{d}$ [30] | $\mathbb{Z}^{d}$ | $\kappa_{\mathrm{triv}},\kappa_{0,0}$ | $\varrho_{\mathrm{thr}}$ | $\zeta_{\mathrm{nn}}$
Random geometric graph [60] | PPP |  | $\varrho_{\mathrm{thr}}$ | $\zeta_{\mathrm{nn}}$
Long-range percolation [63] | $\mathbb{Z}^{d}$ |  | $\varrho_{\alpha}$ | $\max\\{\zeta_{\mathrm{ll}},\zeta_{\mathrm{nn}}\\}$
Continuum long-range percolation [3] | PPP |  | $\varrho_{\alpha}$ | $\max\\{\zeta_{\mathrm{ll}},\zeta_{\mathrm{nn}}\\}$
Scale-free percolation [16] | $\mathbb{Z}^{d}$ | $\kappa_{\mathrm{prod}},\kappa_{1,1}$ | $\varrho_{\alpha}$ | $\max\\{\zeta_{\mathrm{hh}},\zeta_{\mathrm{ll}},\zeta_{\mathrm{nn}}\\}$
Continuum scale-free percolation [17] | PPP |  | $\varrho_{\alpha}$ | $\max\\{\zeta_{\mathrm{hh}},\zeta_{\mathrm{ll}},\zeta_{\mathrm{nn}}\\}$
Geometric inhomogeneous random graph [7] | PPP |  | $\varrho_{\alpha},\varrho_{\mathrm{thr}}$ | $\max\\{\zeta_{\mathrm{hh}},\zeta_{\mathrm{ll}},\zeta_{\mathrm{nn}}\\}$
Hyperbolic random graph [50] | PPP |  | $\varrho_{\mathrm{thr}}$ | $\zeta_{\mathrm{hh}}$
Age-dependent random connection model [24] | PPP | $\kappa_{\mathrm{pa}},\kappa_{1,\tau-2}$ | $\varrho_{\alpha},\varrho_{\mathrm{thr}}$ | $\max\\{\zeta_{\mathrm{lh}},\zeta_{\mathrm{ll}},\zeta_{\mathrm{nn}}\\}$
Scale-free Gilbert graph [32] | PPP | $\kappa_{\mathrm{max}},\kappa_{1,0}$ | $\varrho_{\mathrm{thr}}$ | $\zeta_{\mathrm{nn}}$
|  |  | $\varrho_{\alpha}$ | $\max\\{\zeta_{\mathrm{lh}},\zeta_{\mathrm{ll}},\zeta_{\mathrm{nn}}\\}$
Ultra-small scale-free geometric network [65] | $\mathbb{Z}^{d}$ | $\kappa_{\mathrm{min}},\kappa_{0,1}$ | $\varrho_{\mathrm{thr}}$ | $\max\\{\zeta_{\mathrm{hh}},\zeta_{\mathrm{nn}}\\}$
Interpolating KSRG | PPP | $\kappa_{1,\sigma}$ | $\varrho_{\alpha},\varrho_{\mathrm{thr}}$ | $\max\\{\zeta_{\mathrm{ll}},\zeta_{\mathrm{lh}},\zeta_{\mathrm{hh}},\zeta_{\mathrm{nn}}\\}$
Table 1.  Models belonging to the KSRG framework, their vertex sets, kernels,
profiles, and the (conjectured) value of their cluster-size decay exponent
$\zeta$. Horizontal lines separate models with different kernels.

###  1.3. An interpolating model (i-KSRG)

We will study models belonging to the KSRG class in a unified manner, using a
parameterized kernel that contains the kernels in (1.6) as special cases. We
call this the _interpolation kernel_ , and the corresponding random graph
models _interpolation KSRGs_. Independently of our work, this kernel appeared
recently in [27, 55] and will be used in [36]. Formally, we define the kernel
as

$\kappa_{\sigma_{1},\sigma_{2}}:=\max(x,y)^{\sigma_{1}}\min(x,y)^{\sigma_{2}};\qquad\mbox{and}\qquad\kappa_{1,\sigma}:=\max(x,y)\min(x,y)^{\sigma},$
(1.10)

for some $\sigma_{1}\geq 0$ and $\sigma_{2}=\sigma\in{\mathbb{R}}$. Non-
negativity of $\sigma_{1}$ ensures the natural requirement that a higher mark
corresponds to a higher expected degree. In models with kernels
$\kappa_{\max},\kappa_{\mathrm{pa}},\kappa_{\mathrm{prod}}$ in (1.6) we set
$\sigma_{1}=1$, while for $\kappa_{\min}$ we set $\sigma_{1}=0$ and
$\sigma_{2}=1$. The kernel $\kappa_{\mathrm{sum}}$ cannot be directly
expressed using the interpolation kernel. However, since $\max(x,y)\leq
x+y\leq 2\max(x,y)$, and all known phase transitions regarding macroscopic
behavior are the same for models with $\kappa_{\mathrm{sum}}$ and with
$\kappa_{\mathrm{max}}$, we consider this a minor restriction. By
appropriately changing the mark distribution, unless $\sigma_{1}=0$, any KSRG
with kernel $\kappa_{\sigma_{1},\sigma_{2}}$ can be re-parameterized to have
$\sigma_{1}=1$. Models with $\sigma_{1}=0$ can be approximated with the kernel
$\kappa_{1,\sigma}$ [41]. The parameter $\sigma$ affects the tail exponent of
the degree distribution, but only when $\sigma>\tau-1$ [55].

Hence, from now on we fix $\sigma_{1}=1$ and set $\sigma:=\sigma_{2}$, i.e.,
we restrict to the second formula in (1.10). Any KSRG model with
$\kappa_{\mathrm{triv}}$ has the same connection probability as a model with
$\kappa_{1,\sigma}$ and all marks identical to $1$, in this case we
artificially set $\tau:=\infty$, see (1.3) and below (1.4).

The parameter $\sigma$ affects _assortativity_ : a larger value of $\sigma$
increases $\min(x,y)^{\sigma}$ in (1.10), and in turn the connection
probability in (1.3). In a natural coupling of these models using common edge-
variables, edges incident to at least one low-mark vertex are barely affected
by changing $\sigma$. However, edges between two high-mark vertices are
created rapidly if $\sigma$ increases. Intuitively, this should imply that
$\zeta$ depends on $\sigma$ _only_ when the high-high-type connectivity is
dominant. We prove this, and find

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

leading to111We will never use the formula for $\zeta_{\mathrm{hh}}$ when it
is negative: then, some other connectivity type is dominant.

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

The interpolation kernel allows for unified proof techniques, and shows how
the possible dominant regimes (ll, lh, hh, and nn) fade into each other as the
interpolation parameter $\sigma$ changes gradually, see Figure 1(b). We then
state our conjecture, visualized in Figure 1, see also Table 1.

######  Conjecture 1.1.

We conjecture that for supercritical KSRGs in ${\mathbb{R}}^{d}$ with kernel
$\kappa_{1,\sigma}$, for all $(\alpha,\tau)\in(1,\infty]\times(2,\infty]$,
(1.1) and (1.2) hold with
$\zeta=\max\\{\zeta_{\mathrm{ll}},\zeta_{\mathrm{lh}},\zeta_{\mathrm{hh}},\zeta_{\mathrm{nn}}\\}$
up to $o(1)$-terms whenever $\zeta>0$. When $\alpha=\infty$ and/or
$\tau=\infty$, the value of $\zeta$ is obtained by taking the corresponding
limit of $\zeta=\zeta(\alpha,\tau)$.

(a) Phase-diagrams of $\zeta=\zeta(\tau,\alpha)$ for models with kernels
$\kappa_{\mathrm{prod}}$, and $\kappa_{\mathrm{pa}}$ or
$\kappa_{\mathrm{max}}$, plotted as a function of $1/(\tau-1)$ and $1/\alpha$.
The $y$-axis (i.e., $1/(\tau-1)=0$) also describes the phase diagram of
(continuum) long-range percolation that has kernel $\kappa_{\mathrm{triv}}$,
while the models on the $x$-axis ($1/\alpha=0$) coincide with models using a
threshold profile function in (1.5). When $1/\alpha>1$ or $1/(\tau-1)>1$, then
${\mathcal{G}}_{\infty}$ is connected and each vertex has infinite degree
almost surely [31]. A white color within the square means that the model is
subcritical for each value $p,\beta$ in (1.3) [27].

(b) Phase-diagrams of $\zeta=\zeta(\sigma,\tau)$ for fixed values of $\alpha$
in (1.5), plotted as a function of $1/(\tau-1)$ on the $x$-axis and
$\sigma/(\tau-1)$ on the $y$-axis. The identity line $y\\!=\\!x$ corresponds
to models using kernel $\kappa_{\mathrm{prod}}\equiv\kappa_{1,1}$, the
$x$-axis to models using $\kappa_{\max}\\!\equiv\\!\kappa_{1,0}$ and the
cross-diagonal $x\\!+\\!y\\!=\\!1$ to models using
$\kappa_{\mathrm{pa}}\\!\equiv\\!\kappa_{1,\tau-2}$. The origin captures
models with $\kappa_{\mathrm{triv}}\\!\equiv\\!\kappa_{0,0}$. Observe that
$\zeta_{\mathrm{lh}}$ (blue) is never dominant above the diagonal $y\geq x$
(equivalently, $\sigma\geq 1$), while $\zeta_{\mathrm{hh}}$ (red) is never
dominant below the cross-diagonal $x\\!+\\!y\\!=\\!1$ (equivalently,
$\sigma\\!\leq\\!\tau\\!-\\!2$). In the quadrant
$x\\!+\\!y\\!\geq\\!1,y\\!\leq\\!x$ all four exponents ‘compete’ for
dominance.

Figure 1. Phase diagrams of the (conjectured) cluster-size decay for kernel-
based spatial random graphs. Theorem 2.2 proves the upper bound in the red
regions, and the lower bounds above the $x+y\geq 1$ line on Figure 1(b), for
all four colors simultaneously, with logarithmic correction terms on phase
boundary lines.

###  1.4. Three related papers

The results in this paper, combined with [43], prove Conjecture 1.1 for
i-KSRGs on Poisson point processes (PPP) whenever
$\max\\{\zeta_{\mathrm{ll}},\zeta_{\mathrm{lh}},\zeta_{\mathrm{hh}}\\}\\!\geq\\!\zeta_{\mathrm{nn}}\\!=\tfrac{d-1}{d}$
and $\sigma\\!\leq\\!\tau\\!-\\!1$ (the non-green regions in Figure 1). When
$\max\\{\zeta_{\mathrm{ll}},\zeta_{\mathrm{lh}}\\}\\!>\\!\zeta_{\mathrm{hh}}$
(the blue and yellow regions in Figure 1), or when the maximum is non-unique
(on region boundaries), we have a $o(1)$ error in the exponent $\zeta$, while
in the open red region our bound is sharp. Regarding the speed of the lower
tail of large deviations (LTLD) for the size of the giant component (as in
(1.2)), we prove Conjecture 1.1 up to a $o(1)$ error whenever
$\max\\{\zeta_{\mathrm{ll}},\zeta_{\mathrm{lh}},\zeta_{\mathrm{hh}}\\}\\!>\\!0$
and $\sigma\\!\leq\\!\tau-1$ (all parameters for which the model can be
supercritical in $d\\!=\\!1$). Thus, up to $o(1)$-errors in some regions,
these results prove Conjecture 1.1 fully for locally finite i-KSRGs on PPPs
when $d\\!=\\!1$ and $\sigma\\!\leq\\!\tau\\!-\\!1$. In dimension $d\geq 2$,
the present paper and [43] leave open (only) the regime where
$\zeta_{\mathrm{nn}}$ is maximal, but we still obtain partial results in this
regime (see the following paragraphs). In [42], we prove Conjecture 1.1 fully
for _long-range percolation_ on ${\mathbb{Z}}^{d}$ whenever the edge density
is sufficiently high, i.e., also when $\zeta_{\mathrm{nn}}$ is maximal.

_Upper bounds._ In this paper we prove the upper bound on the cluster-size
decay and $|{\mathcal{C}}^{\scriptscriptstyle(2)}_{n}|$ for
$\zeta\\!=\\!\zeta_{\mathrm{hh}}$, which is sharp in the red regions in Figure
1, and still non-trivial whenever $\tau\\!<\\!2\\!+\sigma$ (above the cross-
diagonal in Figure 1(b)), using a “backbone construction”. In [43] we show
_upper bounds_ on the speed of LTLD for the size of the giant component using
a renormalization scheme driven by vertex-marks. This yields an upper bound
that matches the conjectured exponent $\zeta$ in (1.2) up to $o(1)$ when
$\max\\{\zeta_{\mathrm{ll}},\zeta_{\mathrm{lh}},\zeta_{\mathrm{hh}}\\}\\!>\\!0$.
In [43] we use this LTLD-type result to construct a backbone (whose
construction is different from the construction in this paper). Using that, we
prove the upper bounds on the cluster-size decay and
$|{\mathcal{C}}^{\scriptscriptstyle(2)}_{n}|$ when
$\zeta\\!\neq\\!\zeta_{\mathrm{nn}}$, obtaining up to $o(1)$-matching upper
bounds for $\zeta\\!\in\\!\\{\zeta_{\mathrm{ll}},\zeta_{\mathrm{lh}}\\}$ in
(1.1) (blue and yellow regions in Figure 1). Only the hh-regime requires
$\sigma\\!\leq\\!\tau\\!-\\!1$. All upper bounds for
$\zeta\\!=\\!\zeta_{\mathrm{ll}}$ extend to i-KSRGs where the vertex locations
are given by ${\mathbb{Z}}^{d}$. In [42] we show the upper bounds for long-
range percolation on ${\mathbb{Z}}^{d}$ when
$\zeta_{\mathrm{nn}}>\zeta_{\mathrm{ll}}$, assuming sufficiently high edge-
density. We use combinatorial methods in [42], since the backbone construction
fails for LRP when $\zeta_{\mathrm{nn}}$ is dominant.

_Lower bounds._ This paper proves, for the whole parameter-space, the lower
bound for the speed of LTLD for the size of the giant component in (1.2). LTLD
is related to the lower bound on the cluster-size decay and
$|{\mathcal{C}}_{n}^{{\scriptscriptstyle(2)}}|$, once we additionally prove
that a box with appropriately restricted vertex-marks still contains a linear-
sized component. Here, we prove this when $\tau\\!<\\!2+\sigma$ using the
backbone construction; the (different) backbone construction in [43] yields it
for $\tau\\!\geq\\!2+\sigma$. In [42], the high edge-density assumption
ensures the existence of a giant in a box. The lower bounds do not require
$\sigma\\!\leq\\!\tau\\!-\\!1$, extend to i-KSRGs on ${\mathbb{Z}}^{d}$, and
do not contain $o(1)$-error terms.

The next section makes definitions and our findings in this paper formal.

##  2\. Model and main results

We start by defining kernel-based random graphs, similar to the definition in
[26], but specifically for the interpolating kernel $\kappa_{1,\sigma}$ in
(1.10). We denote by $\|x-y\|$ the Euclidean distance between
$x,y\in{\mathbb{R}}^{d}$, and for $x\in{\mathbb{R}}^{d},s>0$, we denote a box
of volume $s$ in ${\mathbb{R}}^{d}$ centered at $x$ by

$\Lambda_{s}(x)=\Lambda(x,s):=x+[-s^{1/d}/2,s^{1/d}/2]^{d}$ (2.1)

If $x=0$, we write $\Lambda_{s}$. For a discrete set $V$ we write
$\binom{V}{2}:=\\{\\{u,v\\},u\in V,v\in V,u\neq v\\}$ for the list of
_unordered_ pairs in $V$.

######  Definition 2.1 (Interpolating kernel-based spatial random graph,
i-KSRG).

Fix $\alpha>1,\tau>1,d\in\mathbb{N}$, $\sigma\in{\mathbb{R}}$. Let $\Xi$
denote an inhomogeneous Poisson-point process on
${\mathbb{R}}^{d}\times[1,\infty)$ with intensity measure

$\mu_{\tau}(\mathrm{d}x\times\mathrm{d}w):=\mathrm{Leb}\otimes
F_{W}(\mathrm{d}w):=\mathrm{d}x\times(\tau-1)w^{-\tau}\mathrm{d}w$ (2.2)

For some $p\in(0,1],\beta>0$, we define the connectivity function with
$\kappa_{1,\sigma}$ from (1.10) as

$\mathrm{p}\big{(}(x_{u},w_{u}),(x_{v},w_{v})\big{)}:=\begin{dcases}p\min\bigg{\\{}1,\bigg{(}\beta\frac{\kappa_{1,\sigma}(w_{u},w_{v})}{\|x_{v}-x_{u}\|^{d}}\bigg{)}^{\alpha}\bigg{\\}},&\text{if
}\alpha<\infty,\\\
p\mathbbm{1}\left\\{\beta\frac{\kappa_{1,\sigma}(w_{u},w_{v})}{\|x_{v}-x_{u}\|^{d}}\geq
1\right\\},&\text{if }\alpha=\infty.\end{dcases}$ (2.3)

Conditionally on $\Xi$, the infinite random graph
${\mathcal{G}}_{\infty}=({\mathcal{V}}({\mathcal{G}}_{\infty}),{\mathcal{E}}({\mathcal{G}}_{\infty}))$
is given by ${\mathcal{V}}({\mathcal{G}}_{\infty})=\Xi$ and for each pair
$u=(x_{u},w_{u}),v=(x_{v},w_{v})\in\Xi$ the edge $\\{u,v\\}$ is in
${\mathcal{E}}({\mathcal{G}}_{\infty})$ with probability
$\mathrm{p}\big{(}(x_{u},w_{u}),(x_{v},w_{v})\big{)}$; conditionally
independently given $\Xi$.

Write for $[a,b)\subseteq{\mathbb{R}}_{+}$,
$\Xi_{n}[a,b):=\Xi\cap(\Lambda_{n}\times[a,b))$. For the finite induced
subgraphs of ${\mathcal{G}}_{\infty}$ on $\Xi_{n}[a,b)$ and
$\Xi_{n}:=\Xi_{n}[1,\infty)$, we respectively write

$\displaystyle{\mathcal{G}}_{n}[a,b):=({\mathcal{V}}_{n}[a,b),{\mathcal{E}}_{n}[a,b)),\qquad{\mathcal{G}}_{n}:=({\mathcal{V}}_{n},{\mathcal{E}}_{n}).$
(2.4)

We call $\Xi$ a _realization_ of the vertex set. We denote the measure induced
by the Palm version of $\Xi$ where a vertex at location $x$ is present (with
unknown mark) by $\mathbb{P}^{x}$.

Both the vertex set ${\mathcal{V}}$ and the profile function $\varrho$ in
(2.3) can be replaced to obtain more general KSRGs. We expect that our results
generalize to KSRGs with lattices as vertex sets, although some of our current
proof techniques do not apply, since they make use of the independence
property of PPPs. The projection of the vertex set ${\mathcal{V}}=\Xi$ onto
the spatial dimensions is a unit-intensity Poisson point process. The formula
in (2.3) restricts to models with either a threshold-profile
($\alpha\\!=\\!\infty$) or a specific long-range profile (cf.
$\varrho_{\alpha}(t)$ in (1.5)), for readability. Our results readily extend
to more general regularly varying profiles and fitness distributions, i.e.,
they allow slowly varying functions in (1.5) and (2.2), but then the exponent
$\zeta$ needs to be corrected by an additive $o(1)$ term.

The interpolating KSRG model includes models with kernels
$\kappa_{\mathrm{max}},\kappa_{\mathrm{pa}},\kappa_{\mathrm{prod}}$ as special
cases. The parameter $p$ governs Bernoulli percolation of the edges, and a
higher $\beta$ increases the edge density. While $p,\beta$ do not affect
$\zeta$, they may influence supercriticality for certain values of
$(\alpha,\tau,\sigma,d)$, see [16, 27, 28] on robustness of some KSRGs. See
Section 1.1 above for the role of $(\alpha,\tau,\sigma,d)$.

### Main results

We proceed to the main results of this paper. Define the _multiplicity of the
maximum_ of a finite set ${\mathcal{Z}}\subset{\mathbb{R}}$ as:

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

Recall $\zeta_{\mathrm{ll}}$, $\zeta_{\mathrm{lh}}$, $\zeta_{\mathrm{hh}}$,
and $\zeta_{\mathrm{nn}}$ from (1.7), (1.8), (1.12), and (1.9), respectively.

######  Theorem 2.2 (Subexponential decay).

Consider a supercritical i-KSRG model in Definition 2.1, with parameters
$\alpha>1,\tau\in(2,2+\sigma)$, $\sigma>0$, and $d\in{\mathbb{N}}$. Then there
exists $A>1$ such that, for all $k\geq 1$:

  * (i)

For
${\mathcal{Z}}=\\{\zeta_{\mathrm{ll}},\zeta_{\mathrm{lh}},\zeta_{\mathrm{hh}},\zeta_{\mathrm{nn}}\\}$
and $n\in(Ak,\infty]$

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

  * (ii)

if additionally $\sigma\leq\tau-1$, then for all
$n\in(Ak^{1+\zeta_{\mathrm{hh}}/\alpha},\infty]$

$\displaystyle\mathbb{P}^{\scriptscriptstyle
0}\big{(}|{\mathcal{C}}_{n}(0)|\geq
k,\;0\notin{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}\big{)}\,\leq\,A\exp\big{(}-(1/A)k^{\zeta_{\mathrm{hh}}}\big{)}.$
(2.7)

The results also hold when $\alpha=\infty$ by taking the appropriate limit in
$\zeta_{\mathrm{hh}}(\alpha)$ in (1.12).

We will obtain the following statement as a corollary from Theorem 2.2.

######  Corollary 2.3 (Law of large numbers for the size of the giant
component).

Consider a supercritical i-KSRG model in Definition 2.1, with parameters
$\alpha>1,\tau\in(2,2+\sigma)$, $\sigma\in(0,\tau-1]$, and $d\in{\mathbb{N}}$.
Then,

$\frac{|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|}{n}\overset{\mathbb{P}}{\longrightarrow}\mathbb{P}\big{(}|{\mathcal{C}}_{\infty}(0)|=\infty\big{)},\qquad\mbox{as
}n\to\infty.$ (2.8)

The analogue for the size of the second-largest component in
${\mathcal{G}}_{n}$ is the following theorem.

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

Consider a supercritical i-KSRG model as in Definition 2.1, with parameters
$\alpha>1,\tau\in(2,2+\sigma)$, $\sigma>0$, and $d\in{\mathbb{N}}$. Then the
following hold:

  * (i)

For
${\mathcal{Z}}=\\{\zeta_{\mathrm{ll}},\zeta_{\mathrm{lh}},\zeta_{\mathrm{hh}},\zeta_{\mathrm{nn}}\\}$,
there exist constants $A,\delta,n_{0}>0$, such that for all $n\in[1,\infty)$

$\displaystyle\mathbb{P}\Big{(}|{\mathcal{C}}^{\scriptscriptstyle(2)}_{n}|\geq(1/A)\big{(}\log(n)/((\log\log(n))^{\mathfrak{m}_{\mathcal{Z}}-1}\big{)}^{1/\max({\mathcal{Z}})}\Big{)}\geq
1-n^{-\delta},$ (2.9)

  * (ii)

If additionally $\sigma\leq\tau-1$, then for all $\delta>0$, there exists
$A>0$ such that for all $n\in[1,\infty)$

$\mathbb{P}\big{(}|{\mathcal{C}}^{\scriptscriptstyle(2)}_{n}|\leq
A\log^{1/\zeta_{\mathrm{hh}}}(n)\big{)}\geq 1-n^{-\delta}.$ (2.10)

The results also hold when $\alpha=\infty$ by taking the appropriate limit in
$\zeta_{\mathrm{hh}}(\alpha)$ in (1.12).

We make a few remarks about the two theorems. The assumption
$\tau\\!\in\\!(2,2\\!+\\!\sigma)$, (corresponding to $x+y\geq 1$ on Figure
1(b)) ensures that the model is supercritical for all $p,\beta>0$ in (2.3),
see Proposition 5.14 below, implying that there exists a unique infinite
component ${\mathcal{C}}_{\infty}^{\scriptscriptstyle(1)}$. The condition
$\tau<2+\sigma$ also ensures $\zeta_{\mathrm{hh}}>0$. In part (ii), the
condition $\sigma\\!\leq\\!\tau\\!-1$ is automatically satisfied for models
with kernels $\kappa_{1,\sigma}$ with $\sigma\\!\leq\\!1$, including
$\kappa_{\mathrm{prod}}\equiv\kappa_{1,1}$, because $\tau>2$. While we believe
the restriction $\sigma\\!\leq\\!\tau\\!-\\!1$ is a technical condition, it
reflects the change of the tail exponent of the degree distribution at
$\sigma=\tau-1$: the contribution of higher-fitness vertices to the degree of
a vertex is negligible compared to the total degree only when
$\sigma\\!<\\!\tau\\!-\\!1$ [55]. The assumption
$n>k^{1+\zeta_{\mathrm{hh}}/\alpha}$ in Theorem 2.2(ii) is also a technical
artifact of our proof, and can be relaxed to $n>k^{1+\varepsilon}$ using
results from [43]. The lower bound in (2.6) is the same as in Conjecture 1.1,
here we prove it in the region $\tau\\!\in\\!(2,2\\!+\\!\sigma)$, and in [43]
when $\tau\\!\geq\\!2\\!+\sigma$.

The next theorem shows that the stretch-exponent $\zeta$ is also related to
lower large deviations of the largest component. Contrary to the theorems
above, it holds also for $\tau\geq\sigma+2$.

######  Theorem 2.5 (Speed of lower-tail large deviations of the giant).

Consider a supercritical i-KSRG model as in Definition 2.1, with parameters
$\alpha>1,\tau>2$, $\sigma\geq 0$, and $d\in{\mathbb{N}}$. There exists a
constant $A>0$ such that for all $\rho>0$, and $n$ sufficiently large, with
${\mathcal{Z}}=\\{\zeta_{\mathrm{ll}},\zeta_{\mathrm{lh}},\zeta_{\mathrm{hh}},\zeta_{\mathrm{nn}}\\}$,

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

In [43], we give an almost matching upper bound for the left-hand side in
(2.11) for some $\rho>0$, with an error of $-o(1)$ in the exponent of $n$.
Next, we interpret our results for $\kappa_{\mathrm{prod}}$ models.

######  Example 2.6 (Matching bounds for product-kernel models).

In the _open_ region in the $(\alpha,\tau,\sigma,d)$-phase diagram where
$\zeta_{\mathrm{hh}}$ is the unique maximum – corresponding to the (hh)-regime
– our bounds in (2.6) and (2.7), and in (2.9) and (2.10) are matching. This
gives sharp bounds for _scale-free percolation, geometric inhomogeneous random
graphs, and hyperbolic random graphs_. In these three models $\sigma=1$, and
whenever
$\max\\{\zeta_{\mathrm{ll}},\zeta_{\mathrm{lh}},\zeta_{\mathrm{hh}},\zeta_{\mathrm{nn}}\\}=\zeta_{\mathrm{hh}}=(3-\tau)/(2-(\tau-1)/\alpha)$
(the red region in Figure 1(a)), then

$\displaystyle\mathbb{P}^{\scriptscriptstyle
0}(k\leq|{\mathcal{C}}(0)|<\infty)$
$\displaystyle=\exp(-\Theta(k^{\zeta_{\mathrm{hh}}})),\qquad\quad\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|<\rho
n\big{)}\geq\exp\big{(}-\tfrac{1}{A\rho}n^{\zeta_{\mathrm{hh}}}\big{)},$
$\displaystyle\mathbb{P}\big{(}A^{-1}\log^{1/\zeta_{\mathrm{hh}}}(n)$
$\displaystyle\leq|{\mathcal{C}}^{\scriptscriptstyle(2)}_{n}|\leq
A\log^{1/\zeta_{\mathrm{hh}}}(n)\big{)}\geq 1-n^{-\delta}.$

In [43], we present similar bounds for these $\kappa_{\mathrm{prod}}$-KSRGs
when $\max({\mathcal{Z}})=\zeta_{\mathrm{ll}}=2-\alpha$, which occurs when
$\alpha\in(1,\min\\{\tau-1,1+1/d\\})$ (corresponding to the yellow region in
Figure 1(a)). For $\kappa_{\mathrm{prod}}$ models, $\zeta_{\mathrm{lh}}$ is
never maximal, hence these models present only three phases in their phase
diagram for $\zeta$. For (threshold) hyperbolic random graphs (HRG), [46]
proved that $|{\mathcal{C}}_{n}^{{\scriptscriptstyle(2)}}|=\Theta((\log
n)^{2/(3-\tau)})$, which is included in Theorem 2.4: there is an isomorphism
between HRGs and a $1$-dimensional KSRG model with $\sigma\\!=\\!1$,
$\tau\in(2,3),\alpha=\infty$ (see [7] or [49, Section 9]). Since for HRG we
have $\alpha=\infty$, all small components are localized in space in HRGs.
However, when $\alpha<\infty$, the long-range edges lead to de-localized small
components. This makes proofs of lower bounds somewhat more and upper bounds
significantly more complicated than those in [46] (at least up to our
judgement).

###  2.1. Notation

For a discrete set ${\mathcal{S}}$, we write $|{\mathcal{S}}|$ for the size of
the set. For a subset ${\mathcal{K}}\subseteq{\mathbb{R}}^{d}$, let
$\mathrm{Vol}({\mathcal{K}})$ denote the Lebesgue measure of ${\mathcal{K}}$,
$\partial{\mathcal{K}}$ be its boundary and ${\mathcal{K}}^{c}$ its
complement. We denote the complement of an event $\mathcal{A}$ by
$\neg\mathcal{A}$. Formally we define a vertex $v$ by a pair of location and
mark, i.e., $v:=(x_{v},w_{v})$, but we will sometimes still write
$v\in{\mathcal{K}}$ if $x_{v}\in{\mathcal{K}}$. For two vertices $u,v$, we
write $u\leftrightarrow v$ if $u$ is connected by an edge to $v$ in the graph
${\mathcal{G}}_{\infty}$, and $u\not\leftrightarrow v$ otherwise. We also
write $\\{u,v\\}$ for the same (undirected) edge. Similarly, for a set of
vertices ${\mathcal{S}}$, we write $u\leftrightarrow{\mathcal{S}}$ if there
exists $v\in{\mathcal{S}}$ such that $u\leftrightarrow v$. We write
$X\succcurlyeq Y$ if the random variable $X$ stochastically dominates the
random variable $Y$, i.e., $\mathbb{P}(X\geq x)\geq\mathbb{P}(Y\geq x)$ for
all $x\in{\mathbb{R}}$. A random graph
${\mathcal{G}}_{1}=({\mathcal{V}}_{1},{\mathcal{E}}_{1})$ stochastically
dominates a random graph
${\mathcal{G}}_{2}=({\mathcal{V}}_{2},{\mathcal{E}}_{2})$ if there exists a
coupling such that
$\mathbb{P}\big{(}{\mathcal{V}}_{2}\subseteq{\mathcal{V}}_{1},{\mathcal{E}}_{2}\subseteq{\mathcal{E}}_{1}\big{)}=1$,
and we write ${\mathcal{G}}_{1}\succcurlyeq{\mathcal{G}}_{2}$. We write for
${\mathcal{Q}}\subseteq{\mathbb{R}}^{d}$ and $a\leq b$

$\Xi_{\mathcal{Q}}[a,b):=\Xi\cap\big{(}{\mathcal{Q}}\times[a,b)\big{)},\quad\mbox{and
}\Xi_{s}[a,b):=\Xi_{\Lambda_{s}}[a,b)$ (2.12)

for the restriction of the vertices with mark in $[a,b)$ and location in
${\mathcal{Q}}$ and $\Lambda_{s}$ from (2.1) respectively. We abbreviate
independent and identically distributed as iid. By convention, we set
$(\alpha-1)/\alpha:=1$ if $\alpha=\infty$ throughout the paper.

##  3\. Methodology

###  3.1. Upper bounds

After sketching the strategy for upper bound on the size of the second-largest
component, we explain how to obtain the cluster-size decay from it, then we
sketch the lower bound.

####  3.1.1. Second-largest component

We aim to show an upper bound of the form

$\mathbb{P}\big{(}|{\mathcal{C}}_{n}^{\scriptscriptstyle(2)}|\geq
k\big{)}\leq(n/c)\exp(-ck^{\zeta_{\mathrm{hh}}})=:\mathrm{err}_{n,k}.$ (3.1)

for arbitrary values of $n\geq\mathrm{poly}(k)$ and some constant $c>0$. Such
a bound yields (2.10) when one substitutes
$k=A\log^{1/\zeta_{\mathrm{hh}}}(n)$ for a sufficiently large constant
$A=A(\delta)>0$. Throughout the outline we assume that
$(n/k)^{1/d}\in\mathbb{N}$. The proof consists of four revealment stages,
illustrated in Figure 2.

Step 1. Building a backbone. We set
$w_{\mathrm{hh}}:=\Theta(k^{\gamma_{\mathrm{hh}}})$ with
$\gamma_{\mathrm{hh}}>0$ from (1.11). We partition the volume-$n$ box
$\Lambda_{n}$ into $n/k$ smaller sub-boxes of volume $k$. In this first
revealment step we only reveal the location and edges between vertices in
$\Xi_{n}[w_{\mathrm{hh}},2w_{\mathrm{hh}})$, obtaining the graph
${\mathcal{G}}_{n,1}:={\mathcal{G}}_{n}[w_{\mathrm{hh}},2w_{\mathrm{hh}})$. We
show that ${\mathcal{G}}_{n,1}$ contains a connected component
${\mathcal{C}}_{\mathrm{bb}}$ that contains $\Theta(k^{\zeta_{\mathrm{hh}}})$
many vertices in each subbox, that we call _backbone_ vertices. We show that
this event – say ${\mathcal{A}}_{\mathrm{bb}}$ – has probability at least
$1-\mathrm{err}_{n,k}.$ We do this by ordering the subboxes so that subboxes
with consecutive indices share a $(d-1)$-dimensional face, and by iteratively
connecting $\Theta(k^{\zeta_{\mathrm{hh}}})$ many vertices in the next subbox
to the component we already built, combined with a union bound over all
subboxes. The event ${\mathcal{A}}_{\mathrm{bb}}$ ensures us to show that
_independently_ for all $v\in\Xi_{n}[2w_{\mathrm{hh}},\infty)$,

$\mathbb{P}\big{(}v\leftrightarrow{\mathcal{C}}_{\mathrm{bb}}\mid{\mathcal{A}}_{\mathrm{bb}},v\in\Xi_{n}[2w_{\mathrm{hh}},\infty)\big{)}\geq
1/2,$ (3.2)

regardless of the location of $v$. We call vertices in
$\Xi_{n}[2w_{\mathrm{hh}},\infty)$ _connector_ vertices.

Step 2: Revealing low-mark vertices. We now also reveal all vertices with mark
in $[1,w_{\mathrm{hh}})$, and all their incident edges to
${\mathcal{G}}_{n,1}$ and towards each other, i.e., the graph
${\mathcal{G}}_{n,2}:={\mathcal{G}}_{n}[1,2w_{\mathrm{hh}})\supseteq{\mathcal{G}}_{n,1}$.

Step 3: Pre-sampling randomness to avoid merging of smaller components. To
show (3.1), in the fourth revealment stage below we must _avoid_ _small-to-
large merging_ : when the edges to/from some
$v\in\Xi_{n}[2w_{\mathrm{hh}},\infty)$ are revealed, a set of small
components, each of size smaller than $k$, could merge into a component of
size at least $k$ without connecting to the giant component. If we simply
revealed $\Xi_{n}[2w_{\mathrm{hh}},\infty)$ after Step 2, (3.2) would not be
sufficient to show that small-to-large merging occurs with probability at most
$1-\mathrm{err}_{n,k}$. So, we pre-sample randomness: we split
$\Xi_{n}[2w_{\mathrm{hh}},\infty)$ into two PPPs:

$\Xi_{n}[2w_{\mathrm{hh}},\infty)=\Xi_{n}^{\scriptscriptstyle(\mathrm{sure})}[2w_{\mathrm{hh}},\infty)\cup\Xi_{n}^{\scriptscriptstyle(\mathrm{unsure})}[2w_{\mathrm{hh}},\infty),$

where
$\Xi_{n}^{\scriptscriptstyle(\mathrm{sure})}[2w_{\mathrm{hh}},\infty),\Xi_{n}^{\scriptscriptstyle(\mathrm{unsure})}[2w_{\mathrm{hh}},\infty)$
are _independent_ PPPs with equal intensity: using (3.2) and helping random
variables that encode the presence of edges, we pre-sample whether a connector
vertex connects for _sure_ to ${\mathcal{C}}_{\mathrm{bb}}$ by at least one
edge; forming
$\Xi_{n}^{\scriptscriptstyle(\mathrm{sure})}[2w_{\mathrm{hh}},\infty)$.
Vertices in
$\Xi_{n}^{\scriptscriptstyle(\mathrm{unsure})}[2w_{\mathrm{hh}},\infty)$ might
still connect to ${\mathcal{C}}_{\mathrm{bb}}$ since $1/2$ is only a lower
bound in (3.2), but we ignore that information. We crucially use the property
that thinning a PPP yields two _independent_ PPPs. The adaptation of our
technique to lattices as vertex-set seems non-trivial due to this step. We
reveal now
$\Xi_{n}^{\scriptscriptstyle(\mathrm{unsure})}[2w_{\mathrm{hh}},\infty)$. Let
${\mathcal{G}}_{n,3}\supseteq{\mathcal{G}}_{n,2}$ be the graph induced on the
vertex set

${\mathcal{V}}_{n,3}:=\Xi_{n}[1,2w_{\mathrm{hh}})\cup\Xi_{n}^{\scriptscriptstyle(\mathrm{unsure})}[2w_{\mathrm{hh}},\infty).$
(3.3)

Step 4: Cover expansion, a volume-based argument. We now reveal
$\Xi_{n}^{{\scriptscriptstyle(\mathrm{sure})}}[2w_{\mathrm{hh}},\infty)$ and
merge all components of size at least $k$ with the largest component in
${\mathcal{G}}_{n,3}$ with probability at least $1-\mathrm{err}_{n,k}$. Small-
to-large merging cannot happen since vertices in
$\Xi_{n}^{\scriptscriptstyle(\mathrm{sure})}[2w_{\mathrm{hh}},\infty)$ all
connect to ${\mathcal{C}}_{\mathrm{bb}}$. We argue how to obtain (3.1).

Step 4a: Not too dense components via proper cover. For a component
${\mathcal{C}}\subseteq{\mathcal{G}}_{n,3}$, the _proper cover_
${\mathcal{K}}_{n}({\mathcal{L}})\subseteq\Lambda_{n}$ is the _union of
volume- $1$ boxes_ centered at the vertices of ${\mathcal{C}}$ (the formal
definition below is slightly different). Fixing a constant $\delta>0$, we say
that ${\mathcal{C}}$ is not _too dense_ if

$\mathrm{Vol}({\mathcal{K}}_{n}({\mathcal{C}}))\geq\delta|{\mathcal{C}}|.$
(3.4)

Using the connectivity function $\mathrm{p}$ in (2.3) and
$w_{\mathrm{hh}}=\Theta(k^{\gamma_{\mathrm{hh}}})$, there exists $k_{0}$ such
that for any $k\geq k_{0}$ and _any_ pair of vertices
$u\in{\mathcal{V}}_{n,3}$ in (3.3) and
$v\in\Xi_{n}^{\scriptscriptstyle(\mathrm{sure)}}[2w_{\mathrm{hh}},\infty)$
within the same volume-1 box,

$\mathrm{p}(u,v)\geq p/2.$ (3.5)

Using this bound and that
$\Xi_{n}^{{\scriptscriptstyle\mathrm{(sure)}}}[2w_{\mathrm{hh}},\infty)$ is a
PPP, when $|{\mathcal{C}}|\geq k$, with probability at least
$1-\mathrm{err}_{n,k}$, at least $\Theta(k^{\zeta_{\mathrm{hh}}})$ many
vertices of
$\Xi_{n}^{{\scriptscriptstyle\mathrm{(sure)}}}[2w_{\mathrm{hh}},\infty)$ fall
inside ${\mathcal{K}}_{n}({\mathcal{C}})$ and at least one of them connects to
${\mathcal{C}}$ by an edge. Since these vertices belong to
$\Xi_{n}^{{\scriptscriptstyle\mathrm{(sure)}}}[2w_{\mathrm{hh}},\infty)$, they
connect to ${\mathcal{C}}_{\mathrm{bb}}$ by construction, merging
${\mathcal{C}}$ with the component containing ${\mathcal{C}}_{\mathrm{bb}}$.

Step 4b: Too dense components via cover-expansion. We still need to handle
components ${\mathcal{C}}\subseteq{\mathcal{G}}_{n,3}$ with
$|{\mathcal{C}}|\geq k$ that do not satisfy (3.4). These may exist (outside
the component of ${\mathcal{C}}_{\mathrm{bb}}$) since the PPP $\Xi_{n}$
contains dense areas, e.g., volume-one balls with
$\Theta(\log(n)/\log\log(n))$ vertices. We introduce a deterministic
algorithm, the _‘cover-expansion algorithm’_ , that outputs for any
(deterministic) set ${\mathcal{L}}$ of at least $k$ vertices a set
${\mathcal{K}}^{\mathrm{exp}}({\mathcal{L}})\subset{\mathbb{R}}^{d}$, called
the _expanded cover_ of ${\mathcal{L}}$, that satisfies (3.4) and a bound
similar to (3.5) (provided that $\sigma\\!\leq\\!\tau\\!-\\!1$). In the design
of the set ${\mathcal{K}}^{\mathrm{exp}}({\mathcal{L}})$ we quantify the idea
that a connector vertex can be _farther away in space_ from a too dense subset
${\mathcal{L}}^{\prime}\subseteq{\mathcal{L}}$, while ensuring connection
probability at least $p/2$ to ${\mathcal{L}}^{\prime}$, as if
${\mathcal{L}}^{\prime}$ contains a single vertex. We apply this algorithm
with ${\mathcal{L}}={\mathcal{C}}$ for components of size at least $k$ of
${\mathcal{G}}_{n,3}$ that do not satisfy (3.4) and do not contain
${\mathcal{C}}_{\mathrm{bb}}$. The remainder of the proof is identical to Step
4a. Steps 4a, 4b, and a union bound over all components of size at least $k$
in ${\mathcal{G}}_{n,3}$ yield (3.1).

Figure 2. Upper bound. The $y$-axis represents marks, the $x$-axis represents
space. After Steps 1 and 2 there is a component ${\mathcal{C}}^{\star}$
containing the backbone that is connected to some small components from
${\mathcal{G}}_{n}[1,w_{\mathrm{hh}})$. After Step 3, the unsure-connectors
are revealed: there is small-to-large merging; some unsure-connectors connect
to the backbone. After Step 4, each component of size at least $k$ merged with
the largest component via a sure-connector; unmerged small components and
unsure-connectors outside ${\mathcal{C}}_{n}^{\scriptscriptstyle(1)}$ remain,
all in clusters of size at most $k$.

####  3.1.2. Subexponential decay, upper bound.

Consider $k$ fixed. We obtain the cluster-size decay (2.7) for any
$n\in[\mathrm{poly}(k),n_{k}]$ with
$n_{k}=\exp(\Theta(k^{\zeta_{\mathrm{hh}}}))$ by substituting $n_{k}$ into
(3.1). To extend it to larger $n$, we first identify the lowest mark
$\overline{w}(n)$ such that _all_ vertices with mark at least
$\overline{w}(n)$ belong to the giant component
${\mathcal{C}}_{n}^{\scriptscriptstyle(1)}\subseteq{\mathcal{G}}_{n}$ with
sufficiently high probability (in $n$). Then we embed $\Lambda_{n_{k}}$ in
$\Lambda_{n}$ and show that

$\displaystyle\mathbb{P}^{\scriptscriptstyle
0}\big{(}|{\mathcal{C}}_{n}(0)|\geq k,$ $\displaystyle
0\not\in{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}\big{)}$ (3.6)
$\displaystyle\leq\mathbb{P}\big{(}|{\mathcal{C}}^{\scriptscriptstyle(2)}_{n_{k}}|\geq
k\big{)}+\mathbb{P}\big{(}{\mathcal{C}}^{\scriptscriptstyle(1)}_{n_{k}}\nsubseteq{\mathcal{C}}^{\scriptscriptstyle(1)}_{n}\big{)}+\mathbb{P}^{\scriptscriptstyle
0}\big{(}|{\mathcal{C}}_{n}(0)|\geq
k,\;0\not\in{\mathcal{C}}_{n}^{\scriptscriptstyle(1)},|{\mathcal{C}}_{n_{k}}(0)|<k\big{)}.$

The first term on the right-hand side has the right error bound by (3.1). We
relate the second term to the event that for some $\tilde{n}\in(n_{k},n]$
there is no polynomially-sized largest component or the second-largest
component is too large. The event in the third term implies that one of the at
most $k-1$ vertices in ${\mathcal{C}}_{n_{k}}(0)$ has an edge of length
$\Omega(n_{k}^{1/d}/k)$, which will have probability at most
$\mathrm{err}_{n_{k},k}$, since these vertices have mark at most
$\overline{w}(n_{k})$.

###  3.2. Lower bound

For the subexponential decay, we compute the probability of a specific event
satisfying $k\leq|{\mathcal{C}}(0)|<\infty$. We draw a ball ${\mathcal{B}}$ of
volume $\Theta(k)$ around the origin, and compute an _optimally suppressed
mark-profile_ : the PPP $\Xi$ must fall _below_ a $(d+1)$-dimensional mark-
surface ${\mathcal{M}}:=\\{(x,f(x)),x\in{\mathbb{R}}^{d}\\}$, i.e., $w_{v}\leq
f(x_{v})$ must hold for all $(x_{v},w_{v})\in\Xi$. We write
$\\{\Xi\leq{\mathcal{M}}\\}$ for this event. The value of $f(x)$ is increasing
in $\|x-\partial{\mathcal{B}}\|$ since high-mark vertices close to
$\partial{\mathcal{B}}$ are most likely to have edges crossing
$\partial{\mathcal{B}}$. ${\mathcal{M}}$ is optimized so that
$\mathbb{P}(\Xi\leq{\mathcal{M}})\sim\mathbb{P}({\mathcal{B}}\not\leftrightarrow{\mathcal{B}}^{c}\mid\Xi\leq{\mathcal{M}})$,
where $\\{{\mathcal{B}}\not\leftrightarrow{\mathcal{B}}^{c}\\}$ is the event
that there is no edge present between vertices in ${\mathcal{B}}$ and those in
its complement. Both events occur with probability
$\exp(-\Theta(k^{\max\\{\zeta_{\mathrm{ll}},\zeta_{\mathrm{lh}},\zeta_{\mathrm{hh}},\zeta_{\mathrm{nn}}\\}}))$,
up to logarithmic correction terms. We then find an isolated component of size
at least $k$ inside ${\mathcal{B}}$ using a technique that works when
$\tau<2+\sigma$. We use a boxing argument to extend this argument to the lower
bound on the second-largest component of ${\mathcal{G}}_{n}$, similar to [46],
and to obtain a lower bound on
$\mathbb{P}(|{\mathcal{C}}_{n}^{\scriptscriptstyle(1)}|<\rho n)$.

###  3.3. Generalization of results

Most of our results extend to more general (interpolating) KSRGs than that in
Definition 2.1. In particular, one can replace the spatial location of
vertices to be ${\mathbb{Z}}^{d}$ (or any other lattice), called _i-KSRGs on
${\mathbb{Z}}^{d}$_. To prove this generalization, one needs to replace
concentration inequalities for Poisson random variables by Chernoff bounds for
Binomial random variables and replace integrals over ${\mathbb{R}}^{d}$ by
summations over ${\mathbb{Z}}^{d}$. We believe that Theorems 2.2–2.5 fully
extend to $\sigma>\tau-1$ and i-KSRGs on ${\mathbb{Z}}^{d}$, by pre-sampling
more information (similar to Step 3) already before Step 1. We decided to not
include this, avoiding the extra amount of required technicalities. We
highlight the lemmas and propositions that do _not_ immediately generalize by
adding a $\star$ to their statement (e.g. Proposition 5.1).

Besides that, _all_ results extend to i-KSRGs where the number of vertices is
fixed to be $n$, where each vertex $u$ has an iid mark from distribution
$F_{W}$ in (2.2) in Definition 2.1, and an independent uniform location in the
volume-$n$ box $\Lambda_{n}$.

Moreover, all results (even when restricted to the graph in $\Lambda_{n}$)
extend to the Palm-version $\mathbb{P}^{\scriptscriptstyle x}$ of $\mathbb{P}$
where the vertex set $\Xi$ is conditioned to contain a point at location
$x\in\Lambda_{n}$ with unknown mark (which is not a priori obvious, since the
model restricted to a finite box around the origin is not translation-
invariant). We will omit this in our statements and proofs, and only add the
superscript $x$ to our notation if we explicitly use the Palm version.

### Organization of the paper

In Section 4 we explain the cover expansion from Step 4 in the outline of the
upper bound. This technique is a novel technical contribution and is
interesting in its own right. We use it also in [43]. In Section 5 we prove
the upper bound on the size of the second-largest component. Then in Section 6
we extend it to the cluster-size decay, and show Corollary 2.3. In Section 7
we discuss the lower bounds, including the proof of Theorem 2.5. The first
propositions in Sections 5—7 immediately imply the proofs of Theorems 2.2 and
2.4, as we verify near the end of Section 7.

##  4\. The cover and its expansion

The goal of this section is to develop the cover-expansion technique in Step
4b of Section 3.1.1. The statements apply also to KSRGs on vertex sets other
than a PPP. First we define a desired property for a set of vertices based on
their spatial locations. Recall the definition $\Lambda_{s}(x)=\Lambda(x,s)$
from (2.1).

######  Definition 4.1 ($s$-expandable point-set).

Let ${\mathcal{S}}\subset{\mathbb{R}}^{d}\times[1,\infty)$ be a discrete set
of points, and $s>0$. We call ${\mathcal{S}}$ $s$-expandable if for all
$x\in{\mathbb{Z}}^{d}$ and all
$s^{\prime}\in\\{s+\ell/({\mathrm{e}}d^{d/2}2^{3d}):\ell\in\mathbb{N}\\}$,

$|{\mathcal{S}}\cap\Lambda_{s^{\prime}}(x)|/s^{\prime}\leq{\mathrm{e}}.$

A discrete set ${\mathcal{S}}\subset{\mathbb{R}}^{d}$ is $s$-expandable if
there are no large boxes, centered at any site $z\in{\mathbb{Z}}^{d}$, with
too high ratio of number of vertices in ${\mathcal{S}}$ in the box vs its
volume. Further, if ${\mathcal{S}}$ is $s$-expandable, then any subset of
${\mathcal{S}}$ is $s$-expandable; also, if ${\mathcal{S}}$ is $s$-expandable,
then for all $\tilde{s}\geq s$, ${\mathcal{S}}$ is also
$\tilde{s}$-expandable. The next proposition solves the problem of too-dense
components in space, cf. (3.4).

######  Proposition 4.2 (Covers and expansions for $s$-expandable sets).

Consider an i-KSRG with connection probabilities between vertices given by
(2.3) with kernel $\kappa_{1,\sigma}$ and profile function with parameter
$\alpha>1$ and (arbitrary) marked vertex set
${\mathcal{V}}=\\{(x_{v},w_{v})\\}_{v\in{\mathcal{V}}}$. For a given
$\underline{w}>2^{d}d^{d/2}/\beta$, let $s(\underline{w})>0$ satisfy

$s(\underline{w}):=(2^{d}\beta\underline{w})^{1/(1-1/\alpha)}.$ (4.1)

Then, for any $s(\underline{w})$-expandable
${\mathcal{L}}\subseteq{\mathcal{V}}\cap\Lambda_{n}$ of vertices (for some
$n>0$), there is a set ${\mathcal{K}}_{n}({\mathcal{L}})\subseteq\Lambda_{n}$
with

$\mathrm{Vol}({\mathcal{K}}_{n}({\mathcal{L}}))\geq\frac{1}{2^{4d+1}{\mathrm{e}}d^{d/2}}|{\mathcal{L}}|,$
(4.2)

such that all vertices $v\in{\mathcal{V}}\cap{\mathcal{K}}_{n}({\mathcal{L}})$
with mark $w_{v}\geq\underline{w}$ satisfy independently of each other that

$\mathbb{P}\big{(}v\leftrightarrow{\mathcal{L}}\mid\mathcal{V}\big{)}\geq
p/2.$ (4.3)

We use two different constructions for the set
${\mathcal{K}}_{n}({\mathcal{L}})$. If ${\mathcal{L}}$ is not too dense (see
(3.4)), we will use a _proper cover_ (see Definition 4.6 below). If, however,
the points of ${\mathcal{L}}$ are densely concentrated in small areas, we will
use a new (deterministic) algorithm, the _cover-expansion algorithm_ ,
producing an _expanded cover_ (see Definition 4.7 below) that still satisfies
the connection probability in (4.3). This will prove Proposition 4.2. We start
with some preliminaries:

######  Definition 4.3 (Cells in a volume-$n$ box).

Let $\widetilde{B}_{z}$ be a box of volume $1$ centered around
$z\in{\mathbb{Z}}^{d}$. For any two neighboring boxes
$\widetilde{B}_{z},\widetilde{B}_{z^{\prime}}$, allocate the shared boundary
$\partial\widetilde{B}_{z}\cap\partial\widetilde{B}_{z^{\prime}}$ to precisely
one of the boxes. For each $u\in{\mathbb{Z}}^{d}$ such that
$u\notin\Lambda_{n}$ but $\widetilde{B}_{u}\cap\Lambda_{n}\neq\emptyset$, let
$z(u):=\operatorname*{arg\,min}\\{\|u-z\|:z\in\Lambda_{n}\cap{\mathbb{Z}}^{d}\\}$,
and then define for each $z\in{\mathbb{Z}}^{d}\cap\Lambda_{n}$ the _cell of_
$z$ as

$B_{z}:=\Big{(}\widetilde{B}_{z}\cap\Lambda_{n}\Big{)}\cup\Big{(}\bigcup_{u\in{\mathbb{Z}}^{d}:z(u)=z}\big{(}\widetilde{B}_{u}\cap\Lambda_{n}\big{)}\Big{)}.$

In words, boxes that have their center inside $\Lambda_{n}$ but are not fully
contained in $\Lambda_{n}$ are truncated, while boxes that have their centers
outside $\Lambda_{n}$ but intersect it are merged with the closest box with
center inside $\Lambda_{n}$. Clearly, at every point of $\Lambda_{n}$ at most
$2^{d}$ cells are merged together, and only $1/2$ of the radius in each
coordinate can be truncated. Thus, for each cell $B_{z}$

$\sup\\{\|x-y\|:x,y\in B_{z}\\}\leq 2\sqrt{d};\quad\mbox{and}\quad\quad
2^{-d}\leq\mathrm{Vol}(B_{z})\leq 2^{d}.$ (4.4)

######  Definition 4.4 (Notation for cells containing vertices).

Let ${\mathcal{L}}\subset\Lambda_{n}$ be the set of locations of a set of
vertices in any given realization
$({\mathcal{V}},(w_{v})_{v\in{\mathcal{V}}})$. Let
$\\{B_{z_{i}}\\}_{i=1}^{m^{\prime}}$ be the cells with ${\mathcal{L}}\cap
B_{z_{i}}\neq\emptyset$. Let ${\mathcal{L}}_{i}:={\mathcal{L}}\cap B_{z_{i}}$,
$\ell_{i}:=|{\mathcal{L}}_{i}|$ and
$L:=|{\mathcal{L}}|=\sum_{i=1}^{m^{\prime}}\ell_{i}$.

We will distinguish two cases for the arrangement of the vertices among the
cells: either the number of cells is linear in the number of vertices, or
there is a positive fraction of all cells that all contain ‘many’ vertices. To
make this more precise, we prove the next combinatorial claim.

######  Claim 4.5 (Pigeon-hole principle for cells).

Let $\delta\in(0,1)$, $\nu\geq 1$, and $\ell_{1},\dots,\ell_{m^{\prime}}\geq
1$ integers such that $\sum_{i\leq m^{\prime}}\ell_{i}=L$. If
$m^{\prime}<L(1-\delta)/\nu$ then

$\exists\ {\mathcal{I}}\subseteq[m^{\prime}]:\quad\forall
i\in{\mathcal{I}}:\ell_{i}\geq\nu,\qquad\text{ and
}\qquad\sum_{i\in{\mathcal{I}}}\ell_{i}\geq\delta L.$ (4.5)

###### Proof.

Assume for contradiction that $\delta,\nu,\ell_{1},\dots,\ell_{m^{\prime}}$
are such that $m^{\prime}<L(1-\delta)/\nu$ holds but (4.5) does not hold. Let
${\mathcal{J}}:=\\{j:\ell_{j}<\nu\\}\subseteq[m^{\prime}]$ and let
${\mathcal{J}}^{c}:=[m^{\prime}]\backslash{\mathcal{J}}$. Then $\forall
i\in{\mathcal{J}}^{c}:\ell_{i}\geq\nu$ and hence, we assumed the opposite of
(4.5), it holds that $\sum_{j\in{\mathcal{J}}^{c}}\ell_{j}<\delta L$. Since
the total sum is $L$, this implies that
$\sum_{j\in{\mathcal{J}}}\ell_{j}\geq(1-\delta)L$. Moreover, since
$\ell_{j}<\nu$ for $j\in{\mathcal{J}}$, it must hold that
$|{\mathcal{J}}|\geq(1-\delta)L/\nu$, which then gives a contradiction with
the assumption in that $m^{\prime}<L(1-\delta)/\nu$. ∎

We define the first possibility for the set
${\mathcal{K}}_{n}({\mathcal{L}})$, which is inspired by Claim 4.5 with
$\nu={\mathrm{e}}d^{d/2}2^{3d}$ and $\delta=1/2$.

######  Definition 4.6 (Proper cover).

We say that ${\mathcal{L}}$ admits a _proper cover_ if
$m^{\prime}\geq|{\mathcal{L}}|/(2{\mathrm{e}}d^{d/2}2^{3d})$ in Definition
4.4, and we define the cover of ${\mathcal{L}}$ as

${\mathcal{K}}_{n}^{(\mathrm{prop.})}({\mathcal{L}}):=\bigcup_{i\in[m^{\prime}]}B_{z_{i}},\quad\mbox{
satisfying
}\quad\mathrm{Vol}({\mathcal{K}}_{n}^{\scriptscriptstyle(\mathrm{prop.})})\geq\frac{1}{d^{d/2}{\mathrm{e}}2^{4d+1}}|{\mathcal{L}}|.$

By (4.4), $\nu={\mathrm{e}}d^{d/2}2^{3d}$, and $\delta=1/2$, hence, we obtain
the desired volume bound on the right-hand side above, establishing (4.2) for
sets admitting a proper cover. Moreover, consider now
$(x_{v},w_{v})\in(B_{z_{i}}\cap{\mathcal{L}})\times[1,\infty)$ and
$u:=(x_{u},w_{u})\in B_{z_{i}}\times[\underline{w},\infty)$ with
$B_{z_{i}}\subseteq{\mathcal{K}}_{n}^{\scriptscriptstyle(\mathrm{prop.})}$.
Then $\|x_{u}-x_{v}\|\leq 2\sqrt{d}$ by (4.4). Since we assumed
$\underline{w}\geq 2^{d}d^{d/2}/\beta$ above (4.1), using (2.3) and (1.10),

$\mathrm{p}(u,v)\geq
p\min\\{1,(\beta\kappa_{1,\sigma}(\underline{w},1)/(2\sqrt{d})^{d})^{\alpha}\\}=p\min\\{1,(\beta\underline{w}/(2\sqrt{d})^{d})^{\alpha}\\}\geq
p.$ (4.6)

This shows (4.3) for sets admitting a proper cover. The argument for
$\alpha=\infty$ is similar.

The remainder of this section focuses on sets ${\mathcal{L}}$ that do not
admit a proper cover, i.e., the number of cells that contain vertices of
${\mathcal{L}}$ is too small. We define an “expanded” cover, obtained after
applying a suitable volume-increasing procedure to
$\cup_{i\in[m^{\prime}]}B_{z_{i}}$ that will be explained at the end of the
section.

###  4.1. Cover expansion

In this section we assume that ${\mathcal{L}}$ does not admit a proper cover.
By Claim 4.5, and re-indexing cells in Definition 4.4, without loss of
generality we may assume that ${\mathcal{I}}=[m]\subseteq[m^{\prime}]$
satisfies (4.5) with $\nu={\mathrm{e}}d^{d/2}2^{3d}$ and $\delta=1/2$. We use
$\Lambda(x,s)$ in (2.1) here for the box of volume $s$ centered at
$x\in{\mathbb{R}}^{d}$.

######  Definition 4.7 (Cover expansion).

Let ${\mathcal{L}}$ be a set of locations of vertices that does not admit a
proper cover in the sense of Definitions 4.4 and 4.6. Let
$[m]:=\\{j:\ell_{j}\geq{\mathrm{e}}d^{d/2}2^{3d}\\}\subseteq[m^{\prime}]$
satisfying (4.5) with $\nu={\mathrm{e}}d^{d/2}2^{3d}$ and $\delta=1/2$. The
_cover expansion_ is defined as a subset of labels
${\mathcal{J}}^{{\scriptscriptstyle(\star)}}\subseteq[m]$ and corresponding
boxes
$(B_{j}^{\scriptscriptstyle(\star)})_{j\in{\mathcal{J}}^{{\scriptscriptstyle(\star)}}}\subset{\mathbb{R}}^{d}$,
centered at $(z_{j})_{j\in{\mathcal{J}}^{{\scriptscriptstyle(\star)}}}$,
together with an allocation ${\buildrel\star\over{\mapsto}}$ of the cells
$B_{z_{i}}:i\leq m$ to these boxes, with

$\mathrm{Cells}_{j}^{\scriptscriptstyle(\star)}:=\bigcup_{i\leq
m}\big{\\{}i:B_{z_{i}}\ {\buildrel\star\over{\mapsto}}\
B_{j}^{\scriptscriptstyle(\star)}\big{\\}},$ (4.7)

satisfying the following properties:

  * (disj.)

the boxes
$(B_{j}^{\scriptscriptstyle(\star)})_{j\in{\mathcal{J}}^{{\scriptscriptstyle(\star)}}}$
are pairwise disjoint sets in ${\mathbb{R}}^{d}$;

  * (vol.)

for all $j\in{\mathcal{J}}^{{\scriptscriptstyle(\star)}}$; we have

$B_{j}^{\scriptscriptstyle(\star)}=\Lambda\Big{(}z_{j},\frac{1}{{\mathrm{e}}d^{d/2}2^{3d}}\sum_{i\in\mathrm{Cells}_{j}^{\scriptscriptstyle(\star)}}\ell_{i}\Big{)};\quad\mathrm{Vol}(B_{j}^{\scriptscriptstyle(\star)})=\frac{1}{{\mathrm{e}}d^{d/2}2^{3d}}\sum_{i\in\mathrm{Cells}_{j}^{\scriptscriptstyle(\star)}}\ell_{i};$
(4.8)

  * (near)

for each $i\in[m]$ ; $i\in\mathrm{Cells}_{j}^{\scriptscriptstyle(\star)}$

$\|z_{i}-z_{j}\|^{d}\leq
d^{d/2}\mathrm{Vol}(B_{j}^{\scriptscriptstyle(\star)}).$ (4.9)

We define the _expanded cover_ of ${\mathcal{L}}$ as

${\mathcal{K}}_{n}^{\scriptscriptstyle(\mathrm{exp})}({\mathcal{L}}):=\Lambda_{n}\cap\Big{(}\bigcup_{j\in{\mathcal{J}}^{{\scriptscriptstyle(\star)}}}B_{j}^{\scriptscriptstyle(\star)}\Big{)}$
(4.10)

and call $B_{j}^{\scriptscriptstyle(\star)}$ the expanded boxes.

A few comments about Definition 4.7: (disj) and (vol) together ensure that the
total volume of the expanded cover is proportional to $|{\mathcal{L}}|$.
Further, (vol) ensures that $\mathrm{Vol}(B_{j}^{\scriptscriptstyle(\star)})$
is proportional to the number of vertices that are in cells allocated to
$B_{j}^{\scriptscriptstyle(\star)}$. Finally, (near) ensures that the center
$z_{i}$ of each cell $B_{z_{i}}$ is relatively close to the center of the box
to which it is allocated. Observe that when the final box
$B_{j}^{\scriptscriptstyle({\star})}$ is large, (4.9) allows for large
distances between allocated initial cells and the center of
$B_{j}^{\scriptscriptstyle({\star})}$.

######  Proposition 4.8 (Every set has either a proper cover or a cover
expansion).

Assume ${\mathcal{L}}$ does not admit a proper cover defined in Definition
4.6. Then there exists a cover expansion for ${\mathcal{L}}$ in the sense of
Definition 4.6 and 4.7. Further, the total volume of the expanded cover is
linear in $|{\mathcal{L}}|$, i.e.,

$\mathrm{Vol}({\mathcal{K}}_{n}^{\scriptscriptstyle(\mathrm{exp})}({\mathcal{L}}))\geq\frac{1}{2^{4d+1}{\mathrm{e}}d^{d/2}}|{\mathcal{L}}|.$
(4.11)

We defer the proof of existence of the desired cover expansion to the end of
the section. Assuming that a cover expansion exists, we show now the linearity
of its volume along with some other observations. Afterwards, we show how
Proposition 4.2 follows from Proposition 4.8.

######  Observation 4.9 (Cover-expansion properties).

Consider the cover expansion of a set ${\mathcal{L}}$ that does not admit a
proper cover according to Definition 4.6.

  * (i)

Every expanded box has volume at least $1$, i.e., for all
$j\in{\mathcal{J}}^{{\scriptscriptstyle(\star)}}$,
$\mathrm{Vol}(B_{j}^{\scriptscriptstyle(\star)})\geq 1$.

  * (ii)

For any cell with $B_{z_{i}}\ {\buildrel\star\over{\mapsto}}\
B_{j}^{\scriptscriptstyle(\star)}$,

$\sup\big{\\{}\|x_{u}-x_{v}\|:x_{u}\in{\mathcal{L}}_{i},x_{v}\in
B_{j}^{\scriptscriptstyle(\star)}\big{\\}}\leq
4\sqrt{d}\mathrm{Vol}(B_{j}^{\scriptscriptstyle(\star)})^{1/d}.$

  * (iii)

For every box $B_{j}^{\scriptscriptstyle(\star)}$, there exists a box
$B_{j}^{\prime}$ centered at $z_{j}$ such that

$\mathrm{Vol}(B_{j}^{\prime})=d^{d/2}2^{3d}\mathrm{Vol}(B_{j}^{\scriptscriptstyle(\star)}),\qquad\text{
and }\qquad|{\mathcal{L}}\cap
B_{j}^{\prime}|\geq{\mathrm{e}}\mathrm{Vol}(B_{j}^{\prime}).$ (4.12)

  * (iv)

If ${\mathcal{L}}$ is $s$-expandable, then for all
$j\in{\mathcal{J}}^{{\scriptscriptstyle(\star)}}$

$\mathrm{Vol}(B_{j}^{\scriptscriptstyle(\star)})\leq d^{-d/2}2^{-3d}s.$ (4.13)

  * (v)

The total volume of a cover expansion is linear in $|{\mathcal{L}}|$, i.e.,
(4.11) holds.

###### Proof.

Part (i) is a consequence of Definition 4.7: every cell with label at most $m$
has $\ell_{i}\geq{\mathrm{e}}d^{d/2}3^{d}$, so by (vol), i.e., (4.8),
Observation (i) follows.

For part (ii) we apply the triangle inequality: since
$x_{u}\in{\mathcal{L}}_{i}$, it holds that $x_{u}\in B_{z_{i}}$, and so by
(4.4), $\|x_{u}-z_{i}\|\leq 2\sqrt{d}$; and by (4.9)
$\|z_{i}-z_{j}\|\leq\sqrt{d}\mathrm{Vol}(B_{j}^{\scriptscriptstyle(\star)})^{1/d}$;
hence $\|x_{u}-z_{j}\|\leq
2\sqrt{d}+\sqrt{d}\mathrm{Vol}(B_{j}^{\scriptscriptstyle(\star)})^{1/d}.$
Also, for any $x_{v}\in B_{j}^{\scriptscriptstyle(\star)}$ it holds that
$\|z_{j}-x_{v}\|\leq(\sqrt{d}/2)\mathrm{Vol}(B_{j}^{\scriptscriptstyle(\star)})^{1/d}$
by (4.8). Combining these bounds and using
$\mathrm{Vol}(B_{j}^{\scriptscriptstyle(\star)})^{1/d}\geq 1$ yields

$\|x_{u}-x_{v}\|\leq
2\sqrt{d}+(3\sqrt{d}/2)\mathrm{Vol}(B_{j}^{\scriptscriptstyle(\star)})^{1/d}\leq(7\sqrt{d}/2)\mathrm{Vol}(B_{j}^{\scriptscriptstyle(\star)})^{1/d}\leq
4\sqrt{d}\mathrm{Vol}(B_{j}^{\scriptscriptstyle(\star)})^{1/d},$

and part (ii) is proven. For part (iii), note that part (ii) applied to
$u\in{\mathcal{L}}_{i}\subset B_{z_{i}}$ and $z_{j}$, yields that

$\sup_{i\in\mathrm{Cells}_{j}^{\scriptscriptstyle(\star)}}\big{\\{}\|x_{u}-z_{j}\|:x_{u}\in{\mathcal{L}}_{i}\big{\\}}\leq
4\sqrt{d}\mathrm{Vol}(B_{j}^{\scriptscriptstyle(\star)})^{1/d}.$

Consequently, the box $B_{j}^{\prime}$ centered at $z_{j}$ of volume
$\mathrm{Vol}(B_{j}^{\prime})=d^{d/2}2^{3d}\mathrm{Vol}(B_{j}^{\scriptscriptstyle(\star)})$
contains all $u\in{\mathcal{L}}_{i}$ with
$i\in\mathrm{Cells}_{j}^{\scriptscriptstyle(\star)}$. Hence, using (4.8), we
obtain

$|{\mathcal{L}}\cap
B_{j}^{\prime}|\,\geq\,\sum_{i\in\mathrm{Cells}_{j}^{\scriptscriptstyle(\star)}}\ell_{i}\,=\,{\mathrm{e}}d^{d/2}2^{3d}\mathrm{Vol}(B_{j}^{\scriptscriptstyle(\star)})\,=\,{\mathrm{e}}\mathrm{Vol}(B_{j}^{\prime}),$
(4.14)

and part (iii) follows. For part (iv), by combining (4.14) with Definition 4.1
we see that ${\mathcal{L}}$ can only be $s$-expandable if
$\mathrm{Vol}(B^{\prime}_{j})\leq s$. Rearrangement of the first part of
(4.12) yields (4.13).

Finally, for part (v), by an argument similar to (4.4),
$\mathrm{Vol}(B_{j}^{{\scriptscriptstyle(\star)}}\cap\Lambda_{n})\geq
2^{-d}\mathrm{Vol}(B_{j}^{{\scriptscriptstyle(\star)}})$ for all
$j\in{\mathcal{J}}^{{\scriptscriptstyle(\star)}}$. Since all boxes of the
cover expansion are disjoint, and each cell is allocated once, (4.8) and
(4.10) imply that

$\displaystyle\mathrm{Vol}({\mathcal{K}}_{n}^{\scriptscriptstyle(\mathrm{exp})}({\mathcal{L}}))$
$\displaystyle=\sum_{j\in{\mathcal{J}}^{{\scriptscriptstyle(\star)}}}\mathrm{Vol}(B_{j}^{\scriptscriptstyle(\star)}\cap\Lambda_{n})\geq
2^{-d}\sum_{j\leq{\mathcal{J}}^{{\scriptscriptstyle(\star)}}}\mathrm{Vol}(B_{j}^{\scriptscriptstyle(\star)})$
$\displaystyle=\frac{1}{{\mathrm{e}}2^{4d}d^{d/2}}\sum_{j\in{\mathcal{J}}^{{\scriptscriptstyle(\star)}}}\sum_{i\in\mathrm{Cells}_{j}^{\scriptscriptstyle(\star)}}\ell_{i}=\frac{1}{{\mathrm{e}}d^{d/2}2^{4d}}\sum_{i\leq
m}\ell_{i}\geq\frac{1}{{\mathrm{e}}d^{d/2}2^{4d+1}}L,$

where the last bound follows by the assumption in Definition 4.7 that
$\ell_{i}\geq{\mathrm{e}}d^{d/2}2^{3d}$ for $i\leq m$, and the initial
assumption that (4.5) in Claim 4.5 holds for $[m]$ with $\delta=1/2$. ∎

###### Proof of Proposition 4.2 assuming Proposition 4.8.

For sets ${\mathcal{L}}$ that admit a proper cover, we recall the reasoning
below Definition 4.6 (in particular (4.6)) which implies both bounds (4.2) and
(4.3) in Proposition 4.2. Let ${\mathcal{L}}$ be an $s$-expandable set that
does not admit a proper cover. Let
${\mathcal{K}}_{n}^{\scriptscriptstyle(\mathrm{exp})}$ be an expanded cover
given by the boxes
$(B_{j}^{\scriptscriptstyle(\star)})_{j\in{\mathcal{J}}^{{\scriptscriptstyle(\star)}}},{\mathcal{J}}^{{\scriptscriptstyle(\star)}}\subseteq[m]$
and an allocation ${\buildrel\star\over{\mapsto}}$ of the initial cells
$(B_{z_{i}})_{i\in[m]}$ to these boxes. The existence of this cover expansion
is guaranteed by Proposition 4.8. The volume bound (4.2) follows from (4.11)
in Proposition 4.8. Hence, it only remains to verify (4.3).

Let
$u=(x_{u},w_{u})\in{\mathcal{K}}_{n}^{\scriptscriptstyle(\mathrm{exp})}\times[\underline{w},\infty)$.
By (disj), and (4.10), there exists
$j\in{\mathcal{J}}^{\scriptscriptstyle(\star)}$ such that $x_{u}\in
B_{j}^{\scriptscriptstyle(\star)}$. Recall from (4.7) that
$\mathrm{Cells}_{j}^{{\scriptscriptstyle(\star)}}$ are the cells allocated to
$B_{j}^{\scriptscriptstyle(\star)}$, and from Definition 4.4 that
${\mathcal{L}}_{i}={\mathcal{L}}\cap B_{z_{i}}$. Let now
${\mathcal{L}}_{j}^{{\scriptscriptstyle(\star)}}:=\cup_{i\in\mathrm{Cells}_{j}^{{\scriptscriptstyle(\star)}}}{\mathcal{L}}_{i}$.
Recall the formula of the connection probability from (2.3).

_Case (1): $\alpha<\infty$_. By Observation 4.9(ii) for any
$v=(x_{v},w_{v})\in{\mathcal{L}}_{j}^{{\scriptscriptstyle(\star)}}$, and any
$x_{u}\in B_{j}^{\scriptscriptstyle(\star)}$, using the lower bounds for the
marks $w_{v}\geq 1,w_{u}\geq\underline{w}$, and that
$\kappa(w_{u},w_{v})=(w_{u}\vee w_{v})(w_{u}\wedge w_{v})^{\sigma}$ for some
$\sigma\geq 0$, we obtain using (2.3) that

$\mathrm{p}\big{(}u,v\big{)}=p\min\Big{\\{}1,\beta^{\alpha}\frac{\kappa(w_{u},w_{v})^{\alpha}}{\|x_{v}-x_{u}\|^{d\alpha}}\Big{\\}}\geq
p\min\Big{\\{}1,\frac{\beta^{\alpha}\underline{w}^{\alpha}}{(4\sqrt{d})^{\alpha
d}\mathrm{Vol}(B_{j}^{\scriptscriptstyle(\star)})^{\alpha}}\Big{\\}}=:r.$

By (4.8),
$|{\mathcal{L}}_{j}^{{\scriptscriptstyle(\star)}}|=\sum_{i\in\mathrm{Cells}_{j}^{{\scriptscriptstyle(\star)}}}\ell_{i}={\mathrm{e}}d^{d/2}2^{3d}\mathrm{Vol}(B_{j}^{\scriptscriptstyle(\star)})$.
Hence, we have

$\displaystyle\mathbb{P}\big{(}\nexists(x_{v},w_{v})\in{\mathcal{L}}_{j}^{{\scriptscriptstyle(\star)}}$
$\displaystyle:\,(x_{u},w_{u})\leftrightarrow(x_{v},w_{v})\big{)}$
$\displaystyle\leq(1-r)^{{\mathrm{e}}d^{d/2}2^{3d}\mathrm{Vol}(B_{j}^{\scriptscriptstyle(\star)})}$
$\displaystyle\leq\exp\big{(}-p{\mathrm{e}}d^{d/2}2^{3d}\min\big{\\{}\mathrm{Vol}(B_{j}^{\scriptscriptstyle(\star)}),\beta^{\alpha}\underline{w}^{\alpha}(4\sqrt{d})^{-\alpha
d}\mathrm{Vol}(B_{j}^{\scriptscriptstyle(\star)})^{1-\alpha}\big{\\}}\big{)}.$

Since $\alpha\geq 1$, and ${\mathcal{L}}$ is $s$-expandable, we can use the
upper bound in (4.13) on $\mathrm{Vol}(B_{j}^{\scriptscriptstyle(\star)})$ to
bound the second term in the minimum on the right-hand side of the last row,
and we use $\mathrm{Vol}(B_{j}^{\scriptscriptstyle(\star)})\geq 1$ by
Observation 4.9(i) to bound the first term. We obtain

$\displaystyle\mathbb{P}\big{(}\nexists(x_{v},w_{v})\in{\mathcal{L}}_{j}^{{\scriptscriptstyle(\star)}}$
$\displaystyle:(x_{u},w_{u})\leftrightarrow(x_{v},w_{v})\big{)}$
$\displaystyle\leq\exp\big{(}-p{\mathrm{e}}\min\big{\\{}d^{d/2}2^{3d},d^{d/2}2^{3d}\beta^{\alpha}\underline{w}^{\alpha}(4\sqrt{d})^{-\alpha
d}s^{1-\alpha}(d^{-d/2}2^{-3d})^{1-\alpha}\big{\\}}\big{)}$
$\displaystyle=\exp(-p{\mathrm{e}}\min\\{d^{d/2}3^{d},(2^{d}\beta)^{\alpha}\underline{w}^{\alpha}s^{1-\alpha}\\})\leq\exp(-{\mathrm{e}}p)\leq
p/2,$

where we used in the last row that $d^{d/2}3^{d}>1$ and also that the bound on
$\underline{w}$ in (4.1) ensures that the second term inside the minimum is at
least 1, and that $\exp(-{\mathrm{e}}p)\leq p/2$ for $p\in[0,1]$. This
concludes the proposition for $\alpha<\infty$.

_Case (2): $\alpha=\infty$_. Using the same bounds as for $\alpha<\infty$ on
the distance, mark and volume of boxes, but now (2.3) for $\alpha=\infty$, for
any $u=(x_{u},w_{u})\in
B_{j}^{\scriptscriptstyle(\star)}\times[\underline{w},\infty)$ and any
$v=(x_{v},w_{v})\in{\mathcal{L}}_{j}^{{\scriptscriptstyle(\star)}}$ that

$\displaystyle\mathrm{p}\big{(}(x_{u},w_{u}),(x_{v},w_{v})\big{)}$
$\displaystyle\geq
p\mathbbm{1}\\{\beta\underline{w}>(4\sqrt{d})^{d}\mathrm{Vol}(B_{j}^{(\star)})\\}\geq
p\mathbbm{1}\\{\beta\underline{w}>(4\sqrt{d})^{d}d^{-d/2}2^{-3d}s\\}$
$\displaystyle=p\mathbbm{1}\\{\beta\underline{w}>2^{-d}s\\}=p\geq p/2,$

where in the one-but-last step we used (4.1), finishing the proof of
$\alpha=\infty$. ∎

We observe that the case $\alpha=\infty$ does not use of the size of
${\mathcal{L}}_{j}^{{\scriptscriptstyle(\star)}}$, and only requires a single
vertex in it, which is intuitive considering the threshold nature of
$\mathrm{p}$ in (2.3). It remains to prove Proposition 4.8, which is the
content of the following subsection.

###  4.2. The algorithm producing the cover expansion

Now we give the algorithm producing the expanded cover of any discrete set
${\mathcal{L}}$ without a proper cover, thence, proving the desired
proposition.

#### Setup for the algorithm.

Recall the notation from Definitions 4.4 and 4.7. Throughout, we will assume
that ${\mathcal{L}}$ does not admit a proper cover in Definition 4.6 and that
$(B_{z_{i}}:i\in[m])$ are the cells satisfying (4.5). Contrary to Definition
4.7, which allocates the initial cells $B_{z_{i}}$ _to boxes_
$B_{j}^{{\scriptscriptstyle(\star)}}$, the algorithm allocates the labels $i$,
$i\leq m$ of the initial cells $B_{z_{i}}$ _towards each other_ in discrete
rounds $r\in{\mathbb{N}}$. We write $i\ {\buildrel r\over{\mapsto}}\ j$ to
indicate that label $i$ is allocated to label $j$ in the allocation of round
$r$. We also write

${\buildrel r\over{\mapsto}}:=\\{(i,j):i\ {\buildrel r\over{\mapsto}}\
j\\}_{i\leq m};\quad\mathrm{Cells}_{j}^{\scriptscriptstyle(r)}:=\bigcup_{i\leq
m}\big{\\{}i:i\ {\buildrel r\over{\mapsto}}\
j\big{\\}};\quad{\mathcal{J}}^{\scriptscriptstyle(r)}:=\\{j:\mathrm{Cells}_{j}^{\scriptscriptstyle(r)}\neq\emptyset\\}.$

In each round $r\geq 0$, the boxes
$\\{B_{j}^{{}^{{\scriptscriptstyle(r)}}}\\}_{j\in{\mathcal{J}}^{\scriptscriptstyle(r)}}$,
and the centers of these boxes are completely determined by ${\buildrel
r\over{\mapsto}}$ by the formula

$B_{j}^{\scriptscriptstyle(r)}:=\Lambda\bigg{(}z_{j},\frac{1}{{\mathrm{e}}d^{d/2}2^{3d}}\sum_{i\in\mathrm{Cells}_{j}^{\scriptscriptstyle(r)}}\ell_{i}\bigg{)}\quad\emph{for}\quad
j\in{\mathcal{J}}^{{\scriptscriptstyle(r)}};$ (4.15)

where $\Lambda(x,s)$ is a box of volume $s$ centered at $x\in{\mathbb{R}}^{d}$
(see (2.1)). Since label $j$ corresponds to center $z_{j}$ across different
rounds, by slightly abusing notation we also write $B_{z_{i}}\ {\buildrel
r\over{\mapsto}}\ B_{j}^{\scriptscriptstyle(r)}$ if and only if $i\ {\buildrel
r\over{\mapsto}}\ j$. We say that ${\buildrel r\over{\mapsto}}$ satisfies one
(or more) conditions in Definition 4.7 if
$(B_{j}^{{\scriptscriptstyle(r)}})_{j\in{\mathcal{J}}^{{\scriptscriptstyle(r)}}}$
with allocation ${\buildrel r\over{\mapsto}}$ satisfies the condition(s).

The algorithm starts with the identity as initial allocation ${\buildrel
0\over{\mapsto}}$ that induces possibly overlapping boxes
$B_{1}^{\scriptscriptstyle(0)},\dots,B_{m}^{\scriptscriptstyle(0)}$; we will
show that ${\buildrel 0\over{\mapsto}}$ already satisfies (near) and (vol.) of
Definition 4.7. In each stage the algorithm attempts to remove an overlap – a
non-empty intersection – between a pair of boxes by re-allocating a few cell
labels, while maintaining properties (near) and (vol.); we achieve (disj) in
the last round $r^{\star}$. The last round $r^{\star}<\infty$ corresponds to
the final output, by setting
${\mathcal{J}}^{{\scriptscriptstyle(\star)}}:={\mathcal{J}}^{{\scriptscriptstyle(r^{\star})}};B_{j}^{\scriptscriptstyle(\star)}:=B_{j}^{\scriptscriptstyle(r^{\star})}$
and defining $B_{z_{i}}\ {\buildrel\star\over{\mapsto}}\
B_{j}^{\scriptscriptstyle(\star)}$ if and only if $i\ {\buildrel
r^{\star}\over{\mapsto}}\ j$.

#### The cover-expansion algorithm.

  1. (input)

$(B_{z_{i}})_{i\in[m]}$ and ${\mathcal{L}}_{i}={\mathcal{L}}\cap B_{z_{i}}$
satisfying (4.5) with $\nu={\mathrm{e}}d^{d/2}2^{3d}$ and $\delta=1/2$.

  2. (init.)

Set $r:=0$, and allocate $j\ {\buildrel 0\over{\mapsto}}\ j$ for all $j\leq
m$.

  3. (while)

If
$(B_{j}^{{\scriptscriptstyle(r)}})_{j\in{\mathcal{J}}^{{\scriptscriptstyle(r)}}}$
in (4.15) are all pairwise disjoint, set $r^{\star}:=r$; and return
${\mathcal{J}}^{{\scriptscriptstyle(\star)}}:={\mathcal{J}}^{{\scriptscriptstyle(r^{\star})}};B_{j}^{\scriptscriptstyle(\star)}:=B_{j}^{\scriptscriptstyle(r^{\star})}$
and ${\buildrel\star\over{\mapsto}}:={\buildrel r^{\star}\over{\mapsto}}$.

Otherwise, let $j_{1}(r)\in{\mathcal{J}}^{\scriptscriptstyle(r)}$ be the label
corresponding to the largest box $B_{j_{1}(r)}^{{\scriptscriptstyle(r)}}$ with
an overlap with some other box in round $r$, and let $j_{2}(r)$ be the label
of the largest box that overlaps with
$B_{{j_{1}(r)}}^{{\scriptscriptstyle(r)}}$ (using an arbitrary tie-breaking
rule). Define

$\hskip
20.0pt\mathcal{I}_{1}^{{\scriptscriptstyle(r)}}:=\mathrm{Cells}_{j_{2}(r)}^{(r)}\cap\big{\\{}i:\|z_{i}-z_{j_{1}(r)}\|\leq\sqrt{d}\mathrm{Vol}(B_{j_{1}(r)}^{\scriptscriptstyle(r)})^{1/d}\big{\\}}_{i\leq
m};\qquad\mathcal{I}_{2}^{{\scriptscriptstyle(r)}}:=\mathrm{Cells}_{j_{2}(r)}^{(r)}\setminus\mathcal{I}_{1}^{{\scriptscriptstyle(r)}}.$
(4.16)

Then we define ${\buildrel r+1\over{\mapsto}}$ by only re-allocating labels in
$\mathrm{Cells}_{j_{2}(r)}^{(r)}$ as follows:

     * (i)

for $i\in\mathcal{I}_{1}^{{\scriptscriptstyle(r)}}$ we allocate $i\ {\buildrel
r+1\over{\mapsto}}\ j_{1}(r)$, i.e., the labels of cells that are sufficiently
close to the center of $B_{j_{1}(r)}^{{\scriptscriptstyle(r)}}$ in order to
satisfy (4.9) are re-allocated to $j_{1}(r)$;

     * (ii)

for $i\in\mathcal{I}_{2}^{{\scriptscriptstyle(r)}}$ we allocate $i\ {\buildrel
r+1\over{\mapsto}}\ i$, i.e., the labels of cells in
$\mathrm{Cells}_{j_{2}(r)}^{(r)}$ that are potentially too far away from the
center of $B_{j_{1}(r)}^{\scriptscriptstyle(r+1)}$ are re-allocated back to
themselves;

     * (iii)

for $i\in[m]\setminus(\mathrm{Cells}_{j_{2}}^{{\scriptscriptstyle(r)}})$, we
set $i\ {\buildrel r+1\over{\mapsto}}\ k$ if and only if $i\ {\buildrel
r\over{\mapsto}}\ k$ (that is, ${\buildrel r+1\over{\mapsto}}$ agrees with
${\buildrel r\over{\mapsto}}$ outside labels in
$\mathrm{Cells}_{j_{2}(r)}^{{\scriptscriptstyle(r)}}$).

Increase $r$ by one and repeat (while).

We make the immediate observation:

######  Observation 4.10.

In each iteration of (while), $\mathcal{I}_{1}^{{\scriptscriptstyle(r)}}$ in
(4.16) is always non-empty. Moreover,

$\mathrm{Vol}\big{(}B_{{j_{1}(r)}}^{\scriptscriptstyle(r+1)}\big{)}-\mathrm{Vol}\big{(}B_{{j_{1}(r)}}^{\scriptscriptstyle(r)}\big{)}\geq
1.$ (4.17)

###### Proof.

It can be shown inductively that $j\ {\buildrel r\over{\mapsto}}\ j$ holds for
all $j\in{\mathcal{J}}^{\scriptscriptstyle(r)}$. Since the boxes
$B_{j_{1}(r)}^{\scriptscriptstyle(r)}$ and
$B_{j_{2}(r)}^{\scriptscriptstyle(r)}$ overlap, the distance of their centers
$\|z_{j_{2}(r)}-z_{j_{1}(r)}\|$ is at most the diameter of
$B_{j_{1}(r)}^{\scriptscriptstyle(r)}$, which is
$\sqrt{d}\mathrm{Vol}(B_{{j_{1}(r)}}^{\scriptscriptstyle(r)})^{1/d}$. Hence,
$j_{2}(r)\in{\mathcal{I}}_{1}^{(r)}$. Since each cell contains
$\ell_{i}\geq{\mathrm{e}}d^{d/2}2^{3d}$ many vertices by the assumption in
(input), we obtain by (4.15)

$\mathrm{Vol}\big{(}B_{{j_{1}(r)}}^{\scriptscriptstyle(r+1)}\big{)}-\mathrm{Vol}\big{(}B_{{j_{1}(r)}}^{\scriptscriptstyle(r)}\big{)}\geq\frac{\ell_{j_{2}(r)}}{{\mathrm{e}}d^{d/2}2^{3d}}\geq
1.\qed$

###### Proof of Proposition 4.8.

Once having shown that a cover expansion of ${\mathcal{L}}$ exists, the bound
on its volume (4.11) holds by Observation 4.9(v). So it remains to show that
the algorithm produces in finitely many rounds an output satisfying all
conditions of a cover expansion in Definition 4.7.

_The algorithm stops in finitely many rounds._ We argue using a monotonicity
argument. We say that a vector $\bm{a}=(a_{1},\dots,a_{m})\in{\mathbb{R}}^{m}$
is non-increasing if $a_{i}\geq a_{i+1}$ for all $i\leq m-1$. We use the
lexicographic ordering for non-increasing vectors
$\bm{a},\bm{b}\in{\mathbb{R}}^{m}$: let $\bm{a}>_{L}\bm{b}$ if there exists a
coordinate $j\leq m$ such that $a_{\ell}=b_{\ell}$ for all $\ell<j$ and
$a_{\ell}>b_{\ell}$ for $\ell=j$.

For all $r\in{\mathbb{N}}$,
${\mathcal{J}}^{{\scriptscriptstyle(r)}}\subseteq[m]$, and hence,
$m^{{\scriptscriptstyle(r)}}:=|{\mathcal{J}}^{{\scriptscriptstyle(r)}}|\leq
m$. Let $\bm{a}^{{\scriptscriptstyle(r)}}\in{\mathbb{R}}^{m}$ be the non-
increasing vector of the re-ordered
$(\mathrm{Vol}(B_{j}^{{\scriptscriptstyle(r)}}))_{j\in{\mathcal{J}}^{{\scriptscriptstyle(r)}}}$
appended with $(m-m^{{\scriptscriptstyle(r)}})$-many zeroes. By Observation
4.10, the entry corresponding to
$\mathrm{Vol}\big{(}B_{{j_{1}(r)}}^{\scriptscriptstyle(r)}\big{)}$ in
$\bm{a}^{{\scriptscriptstyle(r)}}$ increases in
$\bm{a}^{{\scriptscriptstyle(r)}}$. Moreover, the entry corresponding to
$\mathrm{Vol}\big{(}B_{{j_{2}(r)}}^{\scriptscriptstyle(r)}\big{)}$ “crumbles”
into smaller volumes (corresponding to boxes with label in
${\mathcal{I}}_{2}^{{\scriptscriptstyle(r)}})$ that appear in
$\bm{a}^{{\scriptscriptstyle(r)}}$. Since by definition, $j_{1}(r)$
corresponds to the largest box among
$(B_{j}^{{\scriptscriptstyle(r)}})_{j\in{\mathcal{J}}^{{\scriptscriptstyle(r)}}}$
that has an overlap with some other box, so also
$\mathrm{Vol}(B_{j_{2}(r)}^{{\scriptscriptstyle(r)}})\leq\mathrm{Vol}(B_{j_{1}(r)}^{{\scriptscriptstyle(r)}})$,
and the allocation of labels except those in
$\mathrm{Cells}_{j_{2}(r)}^{{\scriptscriptstyle(r)}}$ remains unchanged, these
together imply that
$\bm{a}^{\scriptscriptstyle(r+1)}>_{L}\bm{a}^{\scriptscriptstyle(r)}$.
Finally, for any $r$ and any $j\in{\mathcal{J}}^{{\scriptscriptstyle(r)}}$,
$\mathrm{Vol}(B_{j}^{{\scriptscriptstyle(r)}})\leq|{\mathcal{L}}|/({\mathrm{e}}d^{d/2}2^{3d})=:b$
by (4.8), implying that for all $r$,
$(b,\dots,b)>_{L}\bm{a}^{{\scriptscriptstyle(r)}}$. So,
$(\bm{a}^{\scriptscriptstyle(r)})_{r\geq 0}$ is an increasing bounded sequence
with respect to $>_{L}$, with an increase of at least $1$ per step by (4.17).
Hence, $(\bm{a}^{{\scriptscriptstyle(r)}})_{r\geq 0}$ converges and attains
its limit after finitely many rounds, i.e., $r^{\star}<\infty$.

_The output corresponds to a cover expansion._ We now prove that the output
${\mathcal{J}}^{{\scriptscriptstyle(\star)}},\ {\buildrel\star\over{\mapsto}}$
and the corresponding boxes in (4.15) satisfy the conditions of Definition
4.7. By the stopping condition in step (while) of the algorithm,
$(B_{j}^{{\scriptscriptstyle(\star)}})_{j\in{\mathcal{J}}^{{\scriptscriptstyle(\star)}}}$
satisfy (disj.), and by their definition in (4.15), also (vol.). We need to
still verify (near). We show this by induction: initially, for
$(B_{j}^{{\scriptscriptstyle(0)}})_{j\in{\mathcal{J}}^{{\scriptscriptstyle(0)}}},{\buildrel
0\over{\mapsto}}$, (near) holds, since in (init.) all labels are allocated to
themselves, so $\mathrm{Cells}_{j}^{{\scriptscriptstyle(0)}}=\\{j\\}$, and
thus the left-hand side in (4.9) is $0$. Assume then $r>0$. We prove that
(near) holds for ${\buildrel r+1\over{\mapsto}}$, assuming that it holds for
${\buildrel r\over{\mapsto}}$. Recall from (while) that $j_{1}(r)$ is the
label of the largest box that has an overlap; $j_{2}(r)$ is the label of the
largest box overlapping with $B_{j_{1}(r)}^{{\scriptscriptstyle(r)}}$; by
(4.16), $\mathcal{I}_{1}^{{\scriptscriptstyle(r)}}$ is the set of labels in
$\mathrm{Cells}_{j_{2}(r)}^{{\scriptscriptstyle(r)}}$ re-allocated to
$j_{1}(r)$, and
$\mathcal{I}_{2}^{{\scriptscriptstyle(r)}}=\mathrm{Cells}_{j_{2}(r)}^{{\scriptscriptstyle(r)}}\setminus\mathcal{I}_{1}^{{\scriptscriptstyle(r)}}$
is the set labels allocated in round $r$ to $j_{2}(r)$, and in round $r+1$ to
themselves. We distinguish between four cases for the proof of the inductive
step:

  * •

Assume
$i\notin(\mathrm{Cells}_{j_{1}(r)}^{\scriptscriptstyle\mathrm{(r)}}\cup\mathrm{Cells}_{j_{2}(r)}^{\scriptscriptstyle\mathrm{(r)}})$
and let $k$ be such that $i\ {\buildrel r+1\over{\mapsto}}k$. By (while) part
(iii),
$\mathrm{Cells}_{k}^{\scriptscriptstyle(r+1)}=\mathrm{Cells}_{k}^{\scriptscriptstyle(r)}$,
so by the induction hypothesis, (4.9) holds for ${\buildrel
r+1\over{\mapsto}}$.

  * •

Assume $i\in\mathrm{Cells}_{j_{1}(r)}^{\scriptscriptstyle(r)}$. Since
$B_{j_{1}(r)}^{\scriptscriptstyle(r)}\subsetneq
B_{j_{1}(r)}^{\scriptscriptstyle(r+1)}$ by (4.15) and (4.17), considering
$\|z_{i}-z_{j_{1}(r)}\|$ and the left-hand side in (4.9) stay the same, while
the right-hand side increases, so the inequality required for (near) still
holds.

  * •

Assume
$i\in\mathcal{I}_{1}^{{\scriptscriptstyle(r)}}\subseteq\mathrm{Cells}_{j_{2}(r)}^{\scriptscriptstyle(r)}$.
The definition of $\mathcal{I}_{1}^{{\scriptscriptstyle(r)}}$ in (4.16) forces
that $\|z_{i}-z_{j_{1}(r)}\|$ satisfies (4.9).

  * •

Assume
$i\in\mathcal{I}_{2}^{{\scriptscriptstyle(r)}}=\mathrm{Cells}_{j_{2}}^{\scriptscriptstyle(r)}\setminus\mathcal{I}_{1}^{{\scriptscriptstyle(r)}}$:
(4.9) holds for the same reason as for the base case, i.e., since $i\
{\buildrel r+1\over{\mapsto}}\ i$, $\|z_{i}-z_{i}\|=0$ trivially satisfies
(4.9).

Having all possible cases covered, this finishes the proof of the induction.
Since $r^{\star}<\infty$, this finishes the proof of Proposition 4.8. ∎

###  4.3. Poisson point processes are expandable

We end this section by showing that a Poisson point process is typically
$s$-expandable for $s$ sufficiently large. Recall
$\Lambda_{n}=[-n^{1/d}/2,n^{1/d}/2]^{d}$.

######  Lemma 4.11 (PPPs are expandable).

Let $\Gamma$ be a Poisson point process on ${\mathbb{R}}^{d}$ equipped with an
absolutely continuous intensity measure $\mu$ such that
$\mu(\mathrm{d}x)\leq\mathrm{Leb}(\mathrm{d}x)$. Then there exists a constant
$C_{\ref{lem:expandable-ppp}}>0$ such that for any $s>0$,

$\mathbb{P}\big{(}\Gamma\cap\Lambda_{n}\text{ is not
}s\text{-expandable}\big{)}\leq C_{\ref{lem:expandable-ppp}}n\exp(-s).$

###### Proof.

Using stochastic domination of point processes, without loss of generality we
can assume that $\Gamma$ has intensity measure $\mathrm{Leb}(\mathrm{d}x)$.
Let us define
$\mathrm{R}(s):=\\{s+\ell/({\mathrm{e}}d^{d/2}2^{3d}):\ell\in\mathbb{N}\\}$,
the range of volumes of boxes that we need to consider in Definition 4.1. By a
union bound over the at most $n$ possible centers of the boxes in
$\Lambda_{n}$, and by translation invariance of $\mathrm{Leb}$, it holds that

$\displaystyle\mathbb{P}\big{(}\Gamma\cap\Lambda_{n}\text{ is not
}s\text{-expandable}\big{)}$ $\displaystyle=\mathbb{P}\big{(}\exists
x\in{\mathbb{Z}}^{d}\cap\Lambda_{n},\exists
s^{\prime}\in\mathrm{R}(s):|\Lambda_{s^{\prime}}(x)\cap\Gamma|\geq{\mathrm{e}}s^{\prime}\big{)}$
(4.18) $\displaystyle\leq
n\sum_{s^{\prime}\in\mathrm{R}(s)}\mathbb{P}\big{(}|\Lambda_{s^{\prime}}\cap\Gamma|\geq{\mathrm{e}}s^{\prime}\big{)}.$

Since the intensity of $\Gamma$ is equal to one, by Lemma C.1, each summand is
at most $\exp(-s^{\prime})$ on the right-hand side. Hence, using that
$\sum_{\ell=a}^{\infty}f(\ell)\leq\int_{a-1}^{\infty}f(x)\mathrm{d}x$ for a
monotone non-increasing function, we obtain for the summation in (4.18)

$\displaystyle\mathbb{P}$ $\displaystyle\big{(}\Gamma\cap\Lambda_{n}\text{ is
not }s\text{-expandable}\big{)}\leq
n\exp(-s)\sum_{\ell=0}^{\infty}\exp\big{(}-\ell/({\mathrm{e}}d^{d/2}2^{3d})\big{)}$
$\displaystyle\leq
n\exp(-s)\int_{-1}^{\infty}\exp\big{(}-x/({\mathrm{e}}d^{d/2}2^{3d})\big{)}\mathrm{d}x=n\exp(-s){\mathrm{e}}d^{d/2}2^{3d}\exp\big{(}1/({\mathrm{e}}d^{d/2}2^{3d})\big{)}.$

The proof of the lemma follows by setting $C_{\ref{lem:expandable-
ppp}}={\mathrm{e}}d^{d/2}2^{3d}\exp\big{(}1/({\mathrm{e}}d^{d/2}2^{3d})\big{)}$.
∎

##  5\. Upper bound: second-largest component

The main goal of this section is to prove the following proposition for
general values of $n$ and $k$, which readily implies Theorem 2.4(ii), i.e.,
(2.10). Recall $\zeta_{\mathrm{hh}}=1-\gamma_{\mathrm{hh}}(\tau-1)$ from
(1.12). We restrict ourselves to $\sigma\in(\tau-2,\tau-1]$, since
$\sigma\leq\tau-2$ implies that $\zeta_{\mathrm{hh}}\leq 0$. We recall from
Section 3.3 that the superscript $\star$ below indicates that the result does
not generalize to i-KSRGs on ${\mathbb{Z}}^{d}$.

######  Proposition⋆ 5.1.

Consider a supercritical i-KSRG model in Definition 2.1, and parameters
$\alpha>1,\tau>2$ and $d\in{\mathbb{N}}$. Assume further that also
$\sigma\in(\tau-2,\tau-1]$. There exists a constant $c_{\ref{prop:2nd-upper-
bound-hh}}>0$ such that whenever $n>k^{1+\zeta_{\mathrm{hh}}/\alpha}$ it holds
that

$\mathbb{P}\big{(}|{\mathcal{C}}^{\scriptscriptstyle(2)}_{n}|\geq
k\big{)}\leq(n/c_{\ref{prop:2nd-upper-bound-hh}})\exp\big{(}-c_{\ref{prop:2nd-
upper-bound-hh}}k^{\zeta_{\mathrm{hh}}}\big{)}.$ (5.1)

We follow the steps of the methodology from Section 3.1.1. The bulk of the
work is to establish Steps 1 and 3, since we already developed the cover
expansion of Step 4 in Section 4. We first introduce some notation. We aim to
partition the box $\Lambda_{n}$ into disjoint subboxes of (roughly) volume
$k$. Define

$n^{\prime}:=k\lfloor(n/k)^{1/d}\rfloor^{d}.$ (5.2)

The box $\Lambda_{n^{\prime}}\subseteq\Lambda_{n}$ is the largest box inside
$\Lambda_{n}$ that can be partitioned into $n^{\prime}/k$ disjoint subboxes of
volume exactly $k$ (boundaries are allocated uniquely similar to Definition
4.3). Let the boxes of this partitioning of $\Lambda_{n^{\prime}}$ be
${\mathcal{Q}}_{1},\dots,{\mathcal{Q}}_{n^{\prime}/k}$, labeled so that
${\mathcal{Q}}_{i}$ shares a boundary (that is, a $(d-1)$-dimensional face)
with ${\mathcal{Q}}_{i+1}$ for all $i<n^{\prime}/k$. Define for each
$u=(x_{u},w_{u})\in\Xi_{n}\subset\Lambda_{n}$

${\mathcal{Q}}(u):=\operatorname*{arg\,min}_{{\mathcal{Q}}_{i}}\|x_{u}-{\mathcal{Q}}_{i}\|,$
(5.3)

with the convention that $\|x_{u}-{\mathcal{Q}}_{i}\|=0$ if
$x_{u}\in{\mathcal{Q}}_{i}$, and take the box with the smallest index if the
minimum is non-unique. Similarly to (4.4), we observe that for any point
$u\in\Xi_{n}\subset\Lambda_{n}$

$\sup_{y\in{\mathcal{Q}}(u)}\|x_{u}-y\|\leq 2\sqrt{d}k^{1/d}.$ (5.4)

### Step 1. Construction of the backbone

Recall the definition of ${\mathcal{G}}_{n}[a,b)$ from (2.4) in Definition
2.1. We first show that, for some $w_{\mathrm{hh}}=w_{\mathrm{hh}}(k)$, the
graph
${\mathcal{G}}_{n,1}:={\mathcal{G}}_{n}[w_{\mathrm{hh}},2w_{\mathrm{hh}})$
contains a so-called backbone, a connected component
${\mathcal{C}}_{\mathrm{bb}}$ that contains at least
$s_{k}=\Theta(k^{\zeta_{\mathrm{hh}}})$ vertices in every subbox. Using
$\alpha$ and $\beta$ from Definition 2.1, define the constant $C_{1}$ to be
the solution of the equation

$\displaystyle(p/16)\beta^{\alpha}C_{1}^{1-(\sigma+1)\alpha/(\tau-1)}(2\sqrt{d})^{-\alpha
d}$ $\displaystyle=\log(2),$ $\displaystyle\mbox{if }\alpha$
$\displaystyle<\infty,$ (5.5) $\displaystyle\beta
C_{1}^{-(1+\sigma)/(\tau-1)}d^{-d/2}2^{-d-2\sigma}$ $\displaystyle=1,$
$\displaystyle\mbox{if }\alpha$ $\displaystyle=\infty.$ (5.6)

We set, with $\gamma_{\mathrm{hh}}$ from (1.11),

$w_{\mathrm{hh}}:=w_{\mathrm{hh}}(k):=C_{1}^{-1/(\tau-1)}k^{\gamma_{\mathrm{hh}}},\qquad
s_{k}:=(C_{1}/16)k^{1-\gamma_{\mathrm{hh}}(\tau-1)}=kw_{\mathrm{hh}}^{-(\tau-1)}/16.$
(5.7)

To avoid cumbersome notation, we assume that $s_{k}\in\mathbb{N}$. Recall the
notation $\Xi_{\mathcal{Q}}[a,b)$ from (2.12). Let

${\mathcal{A}}_{\mathrm{bb}}:={\mathcal{A}}_{\mathrm{bb}}(n,k):=\left\\{\begin{aligned}
&{\mathcal{G}}_{n,1}\text{ contains a connected component
}{\mathcal{C}}_{\mathrm{bb}}(n,k)\text{ such that }\\\ &\text{ for all
}i\leq(n^{\prime}/k):|\Xi_{{\mathcal{Q}}_{i}}[w_{\mathrm{hh}},2w_{\mathrm{hh}})\cap{\mathcal{C}}_{\mathrm{bb}}|\geq
s_{k}\end{aligned}\right\\}.$ (5.8)

On ${\mathcal{A}}_{\mathrm{bb}}$, let
${\mathcal{C}}_{\mathrm{bb}}:={\mathcal{C}}_{\mathrm{bb}}(n,k)$, the backbone,
be the largest component in
${\mathcal{G}}_{n}[w_{\mathrm{hh}},2w_{\mathrm{hh}})$ that satisfies the event
${\mathcal{A}}_{\mathrm{bb}}$. In the following lemma we obtain a lower bound
on the probability that there exists a backbone. Observe that
$s_{k}=\Theta(k^{\zeta_{\mathrm{hh}}})$ in (5.7), so the decay on the right-
hand side in (5.9) below is of the same order as the desired decay in
Proposition 5.1.

######  Lemma 5.2 (Backbone construction).

Consider a supercritical i-KSRG model as in Definition 2.1, and parameters
$\alpha>1$, $\tau\in(2,2+\sigma)$, $\sigma\geq 0$, $d\in{\mathbb{N}}$. There
exist constants $c_{\ref{lemma:upper-hh-bb}}=c_{\ref{lemma:upper-hh-
bb}}(p,\beta,d,\alpha,\tau,\sigma)>0$ and $k_{1}\in{\mathbb{N}}$ such that for
$k\geq k_{1}$ and all $n$ satisfying $n\geq k^{1+\zeta_{\mathrm{hh}}/\alpha}$
we have

$\mathbb{P}\big{(}\neg{\mathcal{A}}_{\mathrm{bb}}(n,k)\big{)}\leq
3(n/k)\exp\big{(}-c_{\ref{lemma:upper-hh-bb}}s_{k}\big{)}.$ (5.9)

###### Proof.

Towards proving (5.9), we reveal $\Xi_{n}[w_{\mathrm{hh}},2w_{\mathrm{hh}})$,
i.e., _only_ the vertex set of ${\mathcal{G}}_{n,1}$, and define

${\mathcal{A}}_{\mathrm{poi}}:=\\{\forall i\leq
n^{\prime}/k:|\Xi_{{\mathcal{Q}}_{i}}[w_{\mathrm{hh}},2w_{\mathrm{hh}})|\geq
4s_{k}\\}.$ (5.10)

On ${\mathcal{A}}_{\mathrm{poi}}$, every box contains enough vertices in
${\mathcal{G}}_{n,1}$. Reveal now the edges of ${\mathcal{G}}_{n,1}$ _only
within each of the boxes_ $({\mathcal{Q}}_{i})_{i\leq n^{\prime}/k}$: let
${\mathcal{H}}_{i,1}$ be the induced subgraph of ${\mathcal{G}}_{n,1}$ on
$\Xi_{{\mathcal{Q}}_{i}}[w_{\mathrm{hh}},2w_{\mathrm{hh}})$, and define

$J:=\min\left\\{i:{\mathcal{H}}_{i,1}\mbox{\ contains a connected component\
}{\mathcal{C}}\mbox{\ with\ }|{\mathcal{C}}|\geq s_{k}\right\\}.$ (5.11)

We write $J=\infty$ if no such box-index exists. Then

$\mathbb{P}(\neg{\mathcal{A}}_{\mathrm{bb}})\leq\mathbb{P}(\neg{\mathcal{A}}_{\mathrm{poi}})+\mathbb{P}(J=\infty\mid{\mathcal{A}}_{\mathrm{poi}})+\sum_{i=1}^{n^{\prime}/k}\mathbb{P}(J=i\mid{\mathcal{A}}_{\mathrm{poi}})\mathbb{P}(\neg{\mathcal{A}}_{\mathrm{bb}}\mid\\{J=i\\}\cap{\mathcal{A}}_{\mathrm{poi}}).$
(5.12)

We first bound $\mathbb{P}(\neg{\mathcal{A}}_{\mathrm{poi}})$ from above. The
distribution of $|\Xi_{{\mathcal{Q}}_{i}}[w_{\mathrm{hh}},2w_{\mathrm{hh}})|$
is Poisson with mean
$kw_{\mathrm{hh}}^{-(\tau-1)}(1-2^{-(\tau-1)})=16(1-2^{-(\tau-1)})s_{k}\geq
8s_{k}$ by (2.2), (5.7) and since $\tau\geq 2$. Lemma C.1 yields

$\mathbb{P}\big{(}|\Xi_{{\mathcal{Q}}_{i}}[w_{\mathrm{hh}},2w_{\mathrm{hh}})|\leq
4s_{k}\big{)}\leq\mathbb{P}\big{(}{\mathrm{Poi}}(8s_{k})<4s_{k}\big{)}\leq\exp\big{(}-4s_{k}(1-\log(2))\big{)}.$

Since $1-\log(2)\geq 1/4$, by a union bound over the at most $n^{\prime}/k\leq
n/k$ subboxes we get

$\mathbb{P}(\neg{\mathcal{A}}_{\mathrm{poi}})\leq(n/k)\exp(-s_{k}).$ (5.13)

We will now show an upper bound on the summands in (5.12) that holds uniformly
in $i$. For this, we iteratively ‘construct’ a backbone. The subboxes
${\mathcal{Q}}_{1},\dots,{\mathcal{Q}}_{n^{\prime}/k}$ are ordered so that
${\mathcal{Q}}_{i}$ and ${\mathcal{Q}}_{i+1}$ share a boundary for all $i$. On
$\\{J=i\\}$, we know that ${\mathcal{H}}_{i,1}$ inside ${\mathcal{Q}}_{i}$
contains a connected component ${\mathcal{C}}$ with at least $s_{k}$ many
vertices. We now reveal edges between ${\mathcal{Q}}_{i}$ and
${\mathcal{Q}}_{i+1}$, and bound the probability that there are at least
$s_{k}$ many vertices in ${\mathcal{Q}}_{i+1}$ that are connected by an edge
to ${\mathcal{C}}$: denote this set of vertices by
$\widetilde{\mathcal{V}}_{i+1}$. Next, we apply the same bound to show that at
least $s_{k}$ many vertices in ${\mathcal{Q}}_{i+2}$ connect by an edge to
$\widetilde{\mathcal{V}}_{i+1}$, and so on. For $\ell<i$, we proceed
similarly. Although $\\{J=i\\}$ implies that the _induced_ graph
${\mathcal{H}}_{\ell,1}\in{\mathcal{Q}}_{\ell}$ does not contain a large
enough connected component, we can, thanks to conditioning on
${\mathcal{A}}_{\mathrm{poi}}$, still ensure that at least $s_{k}$ many
vertices in ${\mathcal{Q}}_{i-1}$ connect directly by an edge to the connected
component ${\mathcal{C}}$ in ${\mathcal{Q}}_{i}$, _irrespective of the vertex
positions in ${\mathcal{Q}}_{i-1}$_. Again, denote these vertices by
$\widetilde{\mathcal{V}}_{i-1}$. We repeat this procedure for
$\ell\in\\{i-2,\dots,1\\}$. Hence, for $\ell\geq i$, we need to analyze the
probability that a vertex in ${\mathcal{Q}}_{\ell+1}$ connects to a vertex in
$\widetilde{\mathcal{V}}_{\ell}$, conditionally on
$|\widetilde{\mathcal{V}}_{\ell}|\geq s_{k}$. Since by assumption
$\tau<2+\sigma$, by definition of $\gamma_{\mathrm{hh}}$ in (1.11) for all
$\tau<2+\sigma$ and $\alpha\leq\infty$, it holds that

$1-(1+\sigma)\gamma_{\mathrm{hh}}\geq 0,\quad\mbox{and}\quad 2+\sigma-\tau>0.$
(5.14)

Let $c_{d}$ be the volume of the unit $d$-dimensional ball. Then let $k_{1}$
be the smallest integer so that, depending on the value of $\alpha$, the
following bounds hold (with $C_{1}=C_{1}(\alpha)$ from (5.5)-(5.6),
respectively):

$\displaystyle(1-p)^{C_{1}k_{1}^{\zeta_{\mathrm{hh}}}/16}$ $\displaystyle\leq
1/2,\qquad\mbox{and }\qquad(C_{1}/4)k_{1}^{\zeta_{\mathrm{hh}}}$
$\displaystyle\leq\exp\big{(}p\beta
c_{d}2^{-d}\big{(}C_{1}^{-1/(\tau-1)}k_{1}\big{)}^{(2+\sigma-\tau)\gamma_{\mathrm{hh}}}/8\big{)}.$
(5.15)

The Euclidean distance between vertices in neighboring boxes is at most
$2\sqrt{d}k^{1/d}$ (twice the diameter of a single box), and all considered
vertices have mark at least $w_{\mathrm{hh}}$. When $\alpha=\infty$, we use
that $\gamma_{\mathrm{hh}}=1/(1+\sigma)$ (see (1.11)), and so
$w_{\mathrm{hh}}^{1+\sigma}/k=\Theta(1)$ by (5.7). We obtain using (5.6),
$\mathrm{p}$ in (2.3), that for any
$u=(x_{u},w_{u})\in\Xi_{{\mathcal{Q}}_{\ell+1}}[w_{\mathrm{hh}},2w_{\mathrm{hh}})$,

$\displaystyle\mathbb{P}\big{(}(x_{u},w_{u})\leftrightarrow\widetilde{\mathcal{V}}_{\ell}\mid|\widetilde{\mathcal{V}}_{\ell}|\geq
s_{k}\big{)}$ $\displaystyle\geq 1-\Big{(}1-p\mathbbm{1}\Big{\\{}\frac{\beta
w_{\mathrm{hh}}^{1+\sigma}}{(2\sqrt{d})^{d}k}\geq
1\Big{\\}}\Big{)}^{s_{k}}=1-(1-p)^{s_{k}}\geq 1/2,$ (5.16)

for all $k\geq k_{1}$ by the first criterion in (5.15). When $\alpha<\infty$,
using $\mathrm{p}$ in (2.3) for $u\in{\mathcal{Q}}_{\ell+1}$ with $w_{u}\geq
w_{\mathrm{hh}}$, either the minimum is at $1$ below in (5.17) (in which case
the right-hand side of (5.16) remains valid) or, the minimum in $\mathrm{p}$
is attained at the second term below in (5.17): then we substitute $s_{k}$
from (5.7),

$\displaystyle\mathbb{P}\big{(}(x_{u},w_{u})\leftrightarrow\widetilde{\mathcal{V}}_{\ell}\mid|\widetilde{\mathcal{V}}_{\ell}|\geq
s_{k}\big{)}$ $\displaystyle\geq
1-\big{(}1-p\min\big{\\{}1,\beta^{\alpha}(2\sqrt{d})^{-\alpha
d}w_{\mathrm{hh}}^{(1+\sigma)\alpha}k^{-\alpha}\big{\\}}\big{)}^{s_{k}}$
(5.17) $\displaystyle=1-\big{(}1-p\beta^{\alpha}(2\sqrt{d})^{-\alpha
d}w_{\mathrm{hh}}^{(1+\sigma)\alpha}k^{-\alpha}\big{)}^{kw_{\mathrm{hh}}^{-(\tau-1)}/16}$
$\displaystyle\geq 1-\exp\big{(}-(p/16)\beta^{\alpha}(2\sqrt{d})^{-\alpha
d}w_{\mathrm{hh}}^{(1+\sigma)\alpha-(\tau-1)}k^{1-\alpha}\big{)}.$

By choice of $w_{\mathrm{hh}}$, and $\gamma_{\mathrm{hh}}$ and $C_{1}$ and as
defined in (5.7), (5.5), and (1.11), respectively, factors containing $k$
cancel, and after simplification we arrive at

$\displaystyle\mathbb{P}\big{(}u\leftrightarrow\widetilde{\mathcal{V}}_{\ell}$
$\displaystyle\mid|\widetilde{\mathcal{V}}_{\ell}|\geq s_{k}\big{)}\geq
1-\exp\big{(}-(p/16)\beta^{\alpha}(2\sqrt{d})^{-\alpha
d}C_{1}^{1-(1+\sigma)\alpha/(\tau-1)}\big{)}=1/2.$ (5.18)

Combining (5.18) with (5.16), we obtain a lower bound of $1/2$ for all
$\alpha>1$ for any
$u\in\Xi_{{\mathcal{Q}}_{\ell+1}}[w_{\mathrm{hh}},2w_{\mathrm{hh}})$. On
${\mathcal{A}}_{\mathrm{poi}}$ (see (5.10)) there are at least $4s_{k}$
vertices in $\Xi_{{\mathcal{Q}}_{\ell+1}}[w_{\mathrm{hh}},2w_{\mathrm{hh}})$.
Each of these vertices connects conditionally independently by an edge to
vertices in $\widetilde{\mathcal{V}}_{\ell}$ with probability at least $1/2$,
so for all $\ell\geq i$

$\displaystyle\mathbb{P}\big{(}|\widetilde{\mathcal{V}}_{\ell+1}|\geq
s_{k}\mid|\widetilde{\mathcal{V}}_{\ell}|\geq
4s_{k},{\mathcal{A}}_{\mathrm{poi}}\big{)}\geq\mathbb{P}\big{(}\,{\mathrm{Bin}}(4s_{k},1/2\,)\geq
s_{k}\big{)}\geq 1-\exp(-s_{k}/4),$

where the last bound follows by Chernoff’s bound, see e.g. [40, Theorem 2.1].
When $J=i$ and $\ell<i$, we can analogously bound the probability that
$|\widetilde{\mathcal{V}}_{\ell}|\geq s_{k}$, conditionally on
$|\widetilde{\mathcal{V}}_{\ell+1}|\geq s_{k}$. By a union bound over the at
most $n^{\prime}/k$ subboxes (with indices both smaller as well as larger than
$i$), we obtain

$\mathbb{P}\big{(}\neg{\mathcal{A}}_{\mathrm{bb}}\mid\\{J=i\\}\cap{\mathcal{A}}_{\mathrm{poi}}\big{)}\leq(n^{\prime}/k)\exp(-s_{k}/4)\leq(n/k)\exp(-s_{k}/4).$

The bound holds for all $i\leq n^{\prime}/k$. Using this in the summation on
the right-hand side of (5.12), and using (5.13) to bound
$\mathbb{P}(\neg{\mathcal{A}}_{\mathrm{poi}})$, (5.12) turns into

$\displaystyle\mathbb{P}\big{(}\neg{\mathcal{A}}_{\mathrm{bb}}\big{)}$
$\displaystyle\leq(n/k)\exp(-s_{k})+\mathbb{P}(J=\infty\mid{\mathcal{A}}_{\mathrm{poi}})+(n/k)\exp(-s_{k}/4)\mathbb{P}(J\neq\infty\mid{\mathcal{A}}_{\mathrm{poi}})$
(5.19) $\displaystyle\leq
2(n/k)\exp(-s_{k}/4)+\mathbb{P}(J=\infty\mid{\mathcal{A}}_{\mathrm{poi}}).$

It remains to bound $\mathbb{P}(J=\infty\mid{\mathcal{A}}_{\mathrm{poi}})$,
with $J$ from (5.11). For this we show that the graph ${\mathcal{H}}_{i,1}$
induced on $\Xi_{{\mathcal{Q}}_{i}}[w_{\mathrm{hh}},2w_{\mathrm{hh}})$
stochastically dominates a soft random geometric graph above its connectivity
threshold. Indeed, consider $(x_{u},w_{u})$ and $(x_{v},w_{v})$ in
$\Xi_{{\mathcal{Q}}_{i}}[w_{\mathrm{hh}},2w_{\mathrm{hh}})$. Then using (2.3),
for $\alpha=\infty$,

$\mathrm{p}\big{(}(x_{u},w_{u}),(x_{v},w_{v}))\geq
p\min\big{\\{}1,\beta^{\alpha}w_{\mathrm{hh}}^{(1+\sigma)\alpha}\|x_{u}-x_{v}\|^{-d\alpha}\big{\\}}\geq
p,$

whenever
$\|x_{u}-x_{v}\|\leq\beta^{1/d}w_{\mathrm{hh}}^{(1+\sigma)/d}=:r_{\mathrm{hh}}$.
The calculation for $\alpha=\infty$ is analogous yielding the same radius
$r_{\mathrm{hh}}$ and same lower bound $p$. Hence,
${\mathcal{H}}_{i,1}\succcurlyeq\mathrm{RG_{i}}$ where in $\mathrm{RG}_{i}$ is
a soft random geometric graph: conditioned on ${\mathcal{A}}_{\mathrm{poi}}$,
there are say $N_{i}\geq 4s_{k}$ many vertices in
$\Xi_{{\mathcal{Q}}_{i}}[w_{\mathrm{hh}},2w_{\mathrm{hh}})$, and two vertices
are connected by an edge with probability $p$ whenever they are within
distance $r_{\mathrm{hh}}=\beta^{1/d}w_{\mathrm{hh}}^{(1+\sigma)/d}$ of each
other. Writing $B_{r}$ for the Euclidean ball of radius $r$ around the origin
and for some dimension dependent constant $c_{d}$, the expected degree of a
vertex at _any_ location in $\mathrm{RG}_{i}$ is thus, conditional on $N_{i}$:

$\mathbb{E}[\deg_{\mathrm{RG}_{i}}(v)\mid N_{i}]\geq
pN_{i}\frac{\mathrm{Vol}(B_{r_{\mathrm{hh}}})/2^{d}}{k}=N_{i}\cdot pc_{d}\beta
2^{-d}\cdot w_{\mathrm{hh}}^{1+\sigma}/k.$ (5.20)

We apply [61, Equation (2.6) below Theorem 2.1] to $\mathrm{RG_{i}}$, and
combine it with ${\mathcal{H}}_{i,1}\succcurlyeq\mathrm{RG}_{i}$ to obtain

$\mathbb{P}({\mathcal{H}}_{i,1}\mbox{ not connected}\mid
N_{i})\leq\mathbb{P}(\mathrm{RG_{i}}\mbox{ not connected}\mid N_{i})\leq
N_{i}\exp\big{(}-\mathbb{E}[\deg_{\mathrm{RG}_{i}}(v)\mid N_{i}]\,\big{)}.$

On the event ${\mathcal{A}}_{\mathrm{poi}},N_{i}\geq 4s_{k}$ holds for all
$i$. Hence, by (5.20), uniformly for all $i\leq n^{\prime}/k$,

$\displaystyle\mathbb{P}({\mathcal{H}}_{i,1}\mbox{ not
connected}\mid{\mathcal{A}}_{\mathrm{poi}})$ $\displaystyle\leq\sup_{N_{i}\geq
4s_{k}}N_{i}\exp\big{(}-\mathbb{E}[\deg_{\mathrm{RG}_{i}}(v)\mid
N_{i}]\,\big{)}$ $\displaystyle\leq 4s_{k}\exp\big{(}-4s_{k}\cdot pc_{d}\beta
2^{-d}\cdot w_{\mathrm{hh}}^{1+\sigma}/k\big{)}$
$\displaystyle\leq(C_{1}/4)k^{\zeta_{\mathrm{hh}}}\exp\big{(}-pc_{d}\beta
w_{\mathrm{hh}}^{2+\sigma-\tau}/4\big{)},$

where we used $s_{k}$ from (5.7) to obtain the last row. Using the second
criterion in (5.15), for all $k\geq k_{1}$,

$\mathbb{P}({\mathcal{H}}_{i,1}\mbox{ not
connected}\mid{\mathcal{A}}_{\mathrm{poi}})\leq\exp(-pc_{d}\beta
2^{-d}w_{\mathrm{hh}}^{2+\sigma-\tau}/8)=:p_{1}.$

By (5.14), the exponent of $w_{\mathrm{hh}}$ is positive. Since the induced
subgraphs $({\mathcal{H}}_{i,1})_{i\leq n^{\prime}/k}$ are independent (being
contained in disjoint boxes ${\mathcal{Q}}_{i}$), and the number of boxes is
$n^{\prime}/k=\lfloor(n/k)^{1/d}\rfloor^{d}\geq n/(2k)$, using the definition
of $w_{\mathrm{hh}}$ from (5.7), we get

$\displaystyle\mathbb{P}(J=\infty\mid{\mathcal{A}}_{\mathrm{poi}})$
$\displaystyle\leq\mathbb{P}(\forall i\leq
n^{\prime}/k:{\mathcal{H}}_{i,1}\mbox{ not
connected}\mid{\mathcal{A}}_{\mathrm{poi}})\leq p_{1}^{n/(2k)}$
$\displaystyle\leq\exp\big{(}-pc_{d}\beta
2^{-d-4}(n/k)w_{\mathrm{hh}}^{2+\sigma-\tau}\big{)}\big{)}$
$\displaystyle\leq\exp\big{(}-(pc_{d}\beta
2^{-d-4})C_{1}^{-(2+\sigma-\tau)(\tau-1)}(n/k)k^{\gamma_{\mathrm{hh}}(2+\sigma-\tau)}\big{)}.$

Using (1.11) and (1.12), it is elementary to check that
$\gamma_{\mathrm{hh}}(2+\sigma-\tau)=\zeta_{\mathrm{hh}}(1-1/\alpha)$. Hence,
whenever $n/k>k^{\zeta_{\mathrm{hh}}/\alpha}$, the exponent of $k$ on the
right-hand side is (at least) $\zeta_{\mathrm{hh}}$. Since we assumed $n\geq
k^{1+\zeta_{\mathrm{hh}}/\alpha}$, this is indeed the case. Furthermore, since
$s_{k}=(C_{1}/16)k^{\zeta_{\mathrm{hh}}}$ by (5.7), with $c_{2}:=(pc_{d}\beta
2^{-d})C_{1}^{-(2+\sigma-\tau)(\tau-1)-1}$, using $C_{1}$ from (5.5)), we
obtain that
$\mathbb{P}(J=\infty\mid{\mathcal{A}}_{\mathrm{poi}})\leq\exp(-c_{2}s_{k}).$
Combined with (5.19), this yields the statement of the lemma in (5.9) with
$c_{\ref{lemma:upper-hh-bb}}:=\min\\{c_{2},1/4\\}$. ∎

We will end Step 1 with a claim that shows (3.2), using notation for the
construction of the graph ${\mathcal{G}}_{n}$ that facilitates later steps
that we introduce first. We recall the definition of i-KSRG from Definition
2.1. Given the vertex set $\Xi$, it is standard practice to use independent
uniform random variables to facilitate couplings with the edge-set. This
definition here is more general and allows for other helping random variables
as well, leading to different distributions on graphs. This will be useful
later.

######  Definition 5.3 (Graph encoding).

Let $\xi\subset{\mathbb{R}}^{d}\times[1,\infty)$ be a discrete set and assume
that
$\Psi_{\xi}=\big{\\{}\varphi_{u,v}:\varphi_{u,v}\in[0,1],\\{u,v\\}\in\binom{\xi}{2}\big{\\}}$
is a collection of random variables given $\xi$. For a given connectivity
function $\mathrm{p}:({\mathbb{R}}^{d}\times[1,\infty))^{2}\to[0,1]$, we call
${\mathcal{G}}^{\prime}=({\mathcal{V}}^{\prime},{\mathcal{E}}^{\prime})$ the
(sub)graph _encoded by_ $(\xi,\Psi_{\xi},\mathrm{p})$ if
${\mathcal{V}}^{\prime}=\xi$ and for all $\\{u,v\\}\in\binom{\xi}{2}$, with
$u=(x_{u},w_{u}),v=(x_{v},w_{v})$,

$\big{\\{}\\{u,v\\}\in{\mathcal{E}}^{\prime}\big{\\}}\Longleftrightarrow\big{\\{}\varphi_{u,v}\leq\mathrm{p}\big{(}(x_{u},w_{u}),(x_{v},w_{v})\big{)}\big{\\}}.$
(5.21)

Given $\Xi$ in (2.2), and $\mathrm{p}$ from (2.3), let $\Psi_{\Xi}$ be a
collection of independent $\mathrm{Unif}[0,1]$ random variables given $\Xi$.
${\mathcal{G}}_{\infty}$ in Definition 2.1 is then the graph _encoded by_
$(\Xi,\Psi_{\Xi},\mathrm{p})$. Writing
$\Psi_{n}[a,b):=\big{\\{}\varphi_{u,v}\in\Psi_{\Xi}:\\{u,v\\}\in\binom{\Xi_{n}[a,b)}{2}\\}$
and $\Psi_{n}:=\Psi_{n}[1,\infty)$, ${\mathcal{G}}_{n}$ in (2.4) is then the
graph encoded by $(\Xi_{n},\Psi_{n},\mathrm{p})$.

An immediate corollary is the following:

######  Corollary 5.4.

Assume $\widetilde{\mathcal{G}},\widehat{\mathcal{G}}$ are two random graphs,
encoded respectively by $(\widetilde{\Xi},\widetilde{\Psi},\mathrm{p})$, and
$(\widehat{\Xi},\widehat{\Psi},\mathrm{p})$ for respective point processes
$\widetilde{\Xi},\widehat{\Xi}$ on ${\mathbb{R}}^{d}\times[1,\infty)$ using
the _same_ connectivity function $\mathrm{p}$. If
$(\widetilde{\Xi},\widetilde{\Psi})$ and $(\widehat{\Xi},\widehat{\Psi})$ have
the same law then the encoded graphs $\widetilde{\mathcal{G}}$ and
$\widehat{\mathcal{G}}$ also have the same law.

The collection of (conditionally) independent _uniform_ variables
$\Psi_{n}=\\{\varphi_{u,v}:\\{u,v\\}\in\binom{\Xi_{n}}{2}\\}$ and the
connectivity function $\mathrm{p}$ determine the presence of edges in
${\mathcal{G}}_{n}$. By (5.21), if for some $r>0$ it holds that
$\varphi_{u,v}\leq r\leq\mathrm{p}(u,v)$, then $\\{u\leftrightarrow v\\}$.
Writing ${\mathcal{Q}}(u)$ for the box containing or closest to $u\in\Xi_{n}$
(see (5.3)), let $v_{u}(1),v_{u}(2),\dots,v_{u}(s_{k}),\dots$ denote the
vertices in ${\mathcal{Q}}(u)\cap{\mathcal{C}}_{\mathrm{bb}}$, in decreasing
order with respect to their marks. Let

${\mathcal{S}}(u):=\big{\\{}v_{u}(1),\dots,v_{u}(s_{k})\big{\\}}.$ (5.22)

######  Claim 5.5 (Connections to the backbone).

Consider an i-KSRG satisfying the conditions of Proposition 5.1. Fix $n$ and
$k$ and assume ${\mathcal{G}}_{n,1}$ satisfies the event
${\mathcal{A}}_{\mathrm{bb}}(n,k)$. Let
$\Psi_{n}=\\{\varphi_{u,v}:\\{u,v\\}\in\binom{\Xi_{n}}{2}\\}$ be a collection
of iid $\mathrm{Unif}[0,1]$ random variables and $r_{k}:=1-2^{-1/s_{k}}$.
Then, for all $u\in\Xi_{n}[2w_{\mathrm{hh}}(k),\infty)$ and
$v\in{\mathcal{S}}(u)$, $\mathrm{p}(u,v)\geq r_{k}$ and

$\mathbb{P}\big{(}\forall
v\in{\mathcal{S}}(u):\varphi_{u,v}>r_{k}\mid{\mathcal{G}}_{n,1},{\mathcal{A}}_{\mathrm{bb}}\big{)}=\mathbb{P}\big{(}\exists
v\in{\mathcal{S}}(u):\varphi_{u,v}\leq
r_{k}\mid{\mathcal{G}}_{n,1},{\mathcal{A}}_{\mathrm{bb}}\big{)}=1/2.$ (5.23)

###### Proof.

On the event ${\mathcal{A}}_{\mathrm{bb}}$,
${\mathcal{C}}_{\mathrm{bb}}\subseteq{\mathcal{G}}_{n,1}$ satisfies (5.8) and
in particular ${\mathcal{S}}(u)$ in (5.22) is well-defined and has size
$s_{k}$. Since $\\{\varphi_{u,v}\\}$ is a collection of iid
$\mathrm{Unif}[0,1]$ random variables, (cf. Definition 5.3), one _must_ set
$r_{k}:=1-2^{-1/s_{k}}$ for (5.23) to hold. Hence, it only remains to show
$\mathrm{p}(u,v)\geq r_{k}$ in the statement.

With ${\mathcal{Q}}(u)$ and ${\mathcal{S}}(u)$ from (5.3) and (5.22),
respectively, by (5.4), every $u\in\Xi_{n}[2w_{\mathrm{hh}},\infty)$ is at
distance at most $2\sqrt{d}k$ from any vertex in $v\in{\mathcal{S}}(u)$. Since
$w_{u}\geq 2w_{\mathrm{hh}}\geq w_{\mathrm{hh}}$, and
$|{\mathcal{S}}(u)|=s_{k}$, the computations (5.16) – (5.18) word-by-word
carry through with $\widetilde{\mathcal{V}}_{\ell}$ replaced by
${\mathcal{S}}(u)$, obtaining

$\mathbb{P}(u\leftrightarrow{\mathcal{S}}(u)\mid{\mathcal{G}}_{n,1},\Xi_{n},{\mathcal{A}}_{\mathrm{bb}})=1-\prod_{v\in{\mathcal{S}}(u)}(1-\mathrm{p}(u,v))\geq
1-(1-z_{k})^{s_{k}}\geq 1/2,$

with $z_{k}$ either equaling $p$ in the right-hand side of (5.16) or the
appropriate expression in the right-hand side of (5.17), that bound
_individually_ each $\mathrm{p}(u,v)$ from below. Following now the
calculations towards (5.18) ensures that in both cases $z_{k}\geq
1-2^{-1/s_{k}}$. The assumptions on $k\geq k_{1}$ in (5.15) are also needed
for this (for instance that $p\geq r_{k}$). ∎

### Step 2. Revealing low-mark vertices

Having established that ${\mathcal{G}}_{n,1}$ contains a backbone with
sufficiently high probability, we define
${\mathcal{G}}_{n,2}:={\mathcal{G}}_{n}[1,2w_{\mathrm{hh}})\supseteq{\mathcal{G}}_{n,1}$.

### Step 3. Presampling the vertices connecting to the backbone

We make Step 3 of Section 3.1.1 precise now. Step 3 ensures that during Step 4
below no _small-to-large_ merging occurs when revealing the connector vertices
of $\Xi_{n}[2w_{\mathrm{hh}},\infty)$. That is, components of size smaller
than $k$ do not merge into a larger component via edges to a vertex
$v\in\Xi_{n}[2w_{\mathrm{hh}},\infty)$ that is not connected to the backbone
${\mathcal{C}}_{\mathrm{bb}}$ (${\mathcal{C}}_{\mathrm{bb}}$ will be contained
in the giant component of ${\mathcal{G}}_{n}$). So, we partially pre-sample
some randomness that encodes the presence of some edges.

For a pair $n,k$, we now present the alternative graph-encoding
$\widehat{\mathcal{G}}_{n}$ of KSRGs (cf. Definitions 2.1 and 5.3) and verify
that $\widehat{\mathcal{G}}_{n}$ and ${\mathcal{G}}_{n}$ in Definition 2.1
have the same law. The difference between the encoding in Definition 5.3 and
the construction of $\widehat{\mathcal{G}}_{n}$ is that in the latter the
edge-variables $\varphi_{u,v}$ are no longer independent
${\mathrm{Unif}}[0,1]$ random variables, but are sampled from a suitable
(conditional) joint distribution, whenever
$u\in\Xi_{n}[2w_{\mathrm{hh}}(k),\infty)$ and $v\in{\mathcal{S}}(u)$ from
(5.22). Recall $r_{k}=1-2^{-1/s_{k}}$ from Claim 5.5, with
$w_{\mathrm{hh}}(k):=w_{\mathrm{hh}}$ and $s_{k}$ defined in (5.7).

######  Definition 5.6 (Alternative graph construction).

Fix $n$ and $k$. Let
${\mathcal{G}}_{n,2}={\mathcal{G}}_{n}[1,2w_{\mathrm{hh}}(k))$ from Definition
2.1 be the graph encoded by
$\big{(}\Xi_{n}[1,2w_{\mathrm{hh}}),\Psi_{n}[1,2w_{\mathrm{hh}}),\mathrm{p}\big{)}$.
Let
$\widehat{\Xi}_{n}^{\scriptscriptstyle(\mathrm{unsure})}[2w_{\mathrm{hh}},\infty)$
and
$\widehat{\Xi}_{n}^{\scriptscriptstyle(\mathrm{sure})}[2w_{\mathrm{hh}},\infty)$
be two _independent_ Poisson point processes on
$\Lambda_{n}\times[2w_{\mathrm{hh}},\infty)$ with intensity
$(1/2)\mathrm{Leb}\otimes F_{W}(\mathrm{d}w)$, with $F_{W}$ as in (2.2), and
let

$\widehat{\Xi}_{n}[2w_{\mathrm{hh}},\infty):=\widehat{\Xi}_{n}^{\scriptscriptstyle(\mathrm{unsure})}[2w_{\mathrm{hh}},\infty)\cup\widehat{\Xi}_{n}^{\scriptscriptstyle(\mathrm{sure})}[2w_{\mathrm{hh}},\infty).$
(5.24)

Let
$\Sigma_{n}:=\\{U_{u,v}:u\in\widehat{\Xi}_{n}[2w_{\mathrm{hh}},\infty),v\in\Xi_{n}[1,2w_{\mathrm{hh}})\cup\widehat{\Xi}_{n}[2w_{\mathrm{hh}},\infty)\\}$
be a collection of iid $\mathrm{Unif}[0,1]$ random variables (conditionally on
these PPPs).

(i) If
${\mathcal{G}}_{n,1}={\mathcal{G}}_{n}[w_{\mathrm{hh}},2w_{\mathrm{hh}})\subseteq{\mathcal{G}}_{n,2}$
does not satisfy the event ${\mathcal{A}}_{\mathrm{bb}}$ in (5.8), then set
$\widehat{\Psi}_{n}:=\Psi_{n}[1,2w_{\mathrm{hh}})\cup\Sigma_{n}$ in Definition
5.3 to construct $\widehat{\mathcal{G}}_{n}\supseteq{\mathcal{G}}_{n,2}$ on
$\Xi_{n}[1,2w_{\mathrm{hh}})\cup\widehat{\Xi}_{n}[2w_{\mathrm{hh}},\infty)$,
i.e.,

$\widehat{\mathcal{G}}_{n}:=(\Xi_{n}[1,2w_{\mathrm{hh}})\cup\widehat{\Xi}_{n}[2w_{\mathrm{hh}},\infty),\Psi_{n}[1,2w_{\mathrm{hh}})\cup\Sigma_{n},\mathrm{p}).$

(ii) If ${\mathcal{G}}_{n,1}\subseteq{\mathcal{G}}_{n,2}$ satisfies the event
${\mathcal{A}}_{\mathrm{bb}}$, then we construct
$\widehat{\mathcal{G}}_{n}\supseteq{\mathcal{G}}_{n,2}$ _conditionally on_
${\mathcal{G}}_{n,2}$ as follows. For each
$u\in\widehat{\Xi}_{n}[2w_{\mathrm{hh}},\infty)$ in (5.24), the set of
vertices ${\mathcal{S}}(u)\subseteq\Xi_{n}[1,2w_{\mathrm{hh}})$ is a
deterministic function of ${\mathcal{G}}_{n,1}\subseteq{\mathcal{G}}_{n,2}$,
given by (5.22). Let

$\displaystyle\widehat{\Psi}_{n}^{{\scriptscriptstyle(\mathrm{iid},\mathrm{unsure})}}$
$\displaystyle:=\big{\\{}U_{u,v}:u\in\widehat{\Xi}_{n}^{{\scriptscriptstyle\mathrm{(unsure)}}}[2w_{\mathrm{hh}},\infty),v\in\widehat{\Xi}_{n}^{{\scriptscriptstyle\mathrm{(unsure)}}}[2w_{\mathrm{hh}},\infty)\cup\Xi_{n}[1,2w_{\mathrm{hh}})\setminus{\mathcal{S}}(u)\big{\\}},$
(5.25)
$\displaystyle\widehat{\Psi}_{n}^{{\scriptscriptstyle(\mathrm{iid},\mathrm{sure})}}$
$\displaystyle:=\big{\\{}U_{u,v}:u\in\widehat{\Xi}_{n}^{{\scriptscriptstyle\mathrm{(sure)}}}[2w_{\mathrm{hh}},\infty),v\in\widehat{\Xi}_{n}^{{\scriptscriptstyle\mathrm{(sure)}}}[2w_{\mathrm{hh}},\infty)\cup\Xi_{n}[1,2w_{\mathrm{hh}})\setminus{\mathcal{S}}(u)\big{\\}},$
$\displaystyle\widehat{\Psi}_{n}^{{\scriptscriptstyle(\mathrm{iid},\mathrm{both})}}$
$\displaystyle:=\big{\\{}U_{u,v}:u\in\widehat{\Xi}_{n}^{{\scriptscriptstyle\mathrm{(sure)}}}[2w_{\mathrm{hh}},\infty),v\in\widehat{\Xi}_{n}^{{\scriptscriptstyle\mathrm{(unsure)}}}[2w_{\mathrm{hh}},\infty)\big{\\}}$

be disjoint subsets of $\Sigma_{n}$, and write
$\widehat{\Psi}_{n}^{{\scriptscriptstyle(\mathrm{iid})}}:=\widehat{\Psi}_{n}^{{\scriptscriptstyle(\mathrm{iid},\mathrm{unsure})}}\cup\widehat{\Psi}_{n}^{{\scriptscriptstyle(\mathrm{iid},\mathrm{sure})}}\cup\widehat{\Psi}_{n}^{{\scriptscriptstyle(\mathrm{iid},\mathrm{both})}}$
for the union. Conditionally on
$\widehat{\Xi}_{n}^{\scriptscriptstyle(\mathrm{unsure})}[2w_{\mathrm{hh}},\infty),\widehat{\Xi}_{n}^{\scriptscriptstyle(\mathrm{sure})}[2w_{\mathrm{hh}},\infty)$