# Giant component in the configuration model under geometric constraints

Ivan Kryven111 Mathematical Institute, Utrecht University, P.O. Box 80010,
3508 TA Utrecht, The Netherlands, E-mail<EMAIL_ADDRESS> and
Rik Versendaal11footnotemark: 1

###### Abstract

We study the emergence of a giant component in the configuration model subject
to additional constraints on the edges. We partition a $d$-dimensional torus
into a cubic lattice with a diverging number of compartments containing
vertices and allow only local edges inside and between neighbouring
compartments. We show that, when the number of vertices per compartment grows
quickly enough, a giant component emerges under similar conditions as for the
standard configuration model. Conversely, when the compartment sizes are
fixed, our model might not feature a giant component even if the standard
configuration model does have one. Locally, our model resembles the
configuration model, while globally, it has properties more akin to a
$d$-dimensional lattice. Nonetheless the model remains analytically tractable
using multitype branching processes with infinite number of types and opens
new potential ways to study percolation in graphs with geometric properties.

Keywords: Configuration model, giant component, multitype branching process,
concentration inequalities, geometric networks

MSC2020 Classes: 05C80, 60J80

###### Contents

  1. 1 Introduction
  2. 2 Compartment model on a $d$-dimensional torus
    1. 2.1 Main theorem
  3. 3 Branching processes
    1. 3.1 Galton-Watson tree
    2. 3.2 Multitype branching processes
  4. 4 Proof of Theorem 2.2
    1. 4.1 Exploration process
    2. 4.2 From local to global
    3. 4.3 The size of the giant component
    4. 4.4 Proof of Theorem 2.2
  5. 5 Difference with standard configuration model
  6. A Appendix: Concentration inequalities

##  1 Introduction

Since the classical random graph model was first introduced by Erdős and
Rényi, many alternative models were studied by adding constraints to this
random graph. In the configuration model one can impose an arbitrary degree
sequence. Such a choice may affect the global connectivity of the random
graph, inducing a so-called phase transition [MR98, JL09, BR15]. That is, the
model may or may not feature a giant connected component that involves a
positive fraction of vertices depending on the chosen degree sequence. In
random geometric graphs, the vertices have coordinates defined by a point
process and are connected based on their proximity. These graphs also feature
a similar phase transition [Pen03], which seems to be a property of the
embedding metric space. At the same time, the embedding space also induces a
certain degree distribution, which one cannot control independently. In
general, even though both models feature phase transition-like behaviour,
there are only a few results allowing to study random geometric graphs that
have a given degree distribution. One approach was suggested in the small
world graphs [WS98, BR01], where a regular circular lattice or a continuous
circle is randomly rewired by adding shortcuts to obtain an object that
retains some of the original geometric properties while having a controlled
degree distribution. Random graph models in which both the degree distribution
and geometrical features can be controlled are relevant when modelling real
networks having some spatial content.

Our aim is to provide a simple geometric generalisation of the configuration
model by additionally forbidding some pairs of vertices to be connected, hence
inducing a notion of a metric. We study the following model: We consider
$k\in\mathbb{N}$ compartments arranged into a $d$-dimensional cubic lattice on
a torus and distribute the vertices equally over these compartments. Every
compartment has $2d$ neighbouring compartments. We then only allow an edge to
connect pairs of vertices belonging to the same or neighbouring compartments.
This makes it more difficult for a giant component to emerge, as connections
can only be made locally on the $d$-torus. Our model is furthermore motivated
by studying networks with geometric constraints. Since we are only allowed to
connect vertices from neighbouring compartments, such construction may be
viewed as a random geometric graph on ${\bf Z}_{k}^{d}$ that has a given
degree distribution. When ${\bf Z}_{k}^{d}$ is embedded in the $d$-torus, the
larger $k$ is, the closer the connected vertices are together. However useful
${\bf Z}_{k}^{d}$ model is for applications, we also hope that the techniques
used in this study will in future inspire investigation of the classical
random geometric graphs, for example in $\mathbb{R}^{d}$.

Our technique relies on the idea that the exploration of components in the
random graph can be linked to a branching process. However, in comparison to
the standard setting, this connection is only valid for a small number of
exploration steps, and consequently, this only allows us to prove that
locally-large components emerge. Since the number of compartments tends to
infinity, these components become ‘more and more local’. A delicate step in
this reasoning is to show that a growing number of local components will be
simultaneously present with high probability, so that one giant ‘super’
component can be formed from infinitely many local components connecting
together. To do this, we introduce a countably infinite number of types into
the exploration process to track how each explored component spreads through
the different compartments. This allows us to connect the exploration process
to a multitype branching process, where the type of a vertex represents the
compartment it belongs to. This connection allows us to prove that locally-
large components spread through a sufficient number of compartments, occupying
a positive fraction of the vertices in each of them, and that these components
are connected to each other with high probability – resulting in a giant
component. To this end, we need to analyse the probability that a local
connected component emerges much more carefully in comparison to the standard
setting and to obtain precise quantitative bounds for these probabilities.

We believe that our multitype exploration technique can be reapplied to many
different settings beyond the ${\bf Z}_{k}^{d}$ arrangement of compartments.
For example, one may use heterogeneous compartments to impose clustered
structure in a network or long range dependencies between vertex degrees.

This article is structured as follows. In Section 2 we introduce the model we
are studying and state our main theorem. As with the standard configuration
model, the proof of our main theorem relies on building a connection with an
exploration process, which in our case is a multitype branching process. We
introduce this process in Section 3, where we also derive some relevant
properties. With all preparations done, Section 4 is dedicated to proving our
main theorem, which is done in a number of propositions. Finally, in Section 5
we provide an example that shows that the geometric constraints give rise to
different behaviour compared to the configuration model without geometric
constraints.

##  2 Compartment model on a $d$-dimensional torus

Figure 1: Fragment of the configuration model with compartments arranged into
a square lattice.

The model we are studying is illustrated in Figure 1 for $d=2$. In general,
let $d\geq 1$ be an integer. For every $n\in\mathbb{N}$, we consider
$k(n)^{d}$ compartments $\\{C_{i}^{n}\\}_{i\in[k(n)]^{d}}$, where
$[k(n)]:=\\{1,\ldots,k(n)\\}$. We assume each compartment contains $m(n)$
vertices and we define $V_{n}=\bigcup_{i\in[k(n)]^{d}}C_{i}$ as the set of
vertices. Our aim is to study graphs on $V_{n}$ satisfying two types of
constraints:

  1. 1.

_Constraint on allowed connections:_ Vertices $x,y\in V_{n}$ can only be
connected if $x\in C_{i},y\in C_{j}$ with $|i-j|_{1}\leq 1$. Here, we identify
$k(n)$ with 0, allowing for instance also edges between compartments
$C_{(i,k(n))}$ and $C_{(i,1)}$ with $i\in[k(n)-1]^{d}$. This results in the
$d$-dimensional torus structure.

  2. 2.

_Degree constraint_ : The vertices have prescribed degrees, given by a
sequence $d_{n}=\\{d(1),\ldots,d(k(n)m(n))\\}$ of non-negative integers. We
will refer to $d_{n}$ as the _degree sequence_.

In principle, the random graph $G_{n}=(V_{n},E_{n})$ satisfying the above-
mentioned constraints can be constructed algorithmically as follows: The
degree of a vertex $x\in V_{n}$ is represented by $d_{n}(x)$ half-edges. At
each iteration we choose uniformly a pair of half-edges which are allowed to
be connected together. We repeat this until no matches can be made. We refer
to this model as the _compartment model on $d$-torus_.

First of all, note that $G_{n}$ is in general a multi-graph since we do not
exclude self-loops or multi-edges. Furthermore, it might happen that we do not
satisfy the full degree sequence, even if we assume the sum of the degrees is
even. However, when the construction terminates, at most one half-edge per
compartment will be unmatched. This will be no problem, since we will be
assuming that $m(n)$, the amount of vertices per compartment, tends to
infinity.

The compartment model on the $d$-torus is closely related to a random
geometric graph on the torus. Indeed, the number of compartments $k(n)$ is
related to the distance between vertices that can be connected. However, in
the compartment model, the neighbourhoods of the vertices are homogenized, in
the sense that each vertex in a compartment has the same neighbours it can be
connected to.

###  2.1 Main theorem

Our main result is concerned with providing sufficient conditions under which
the random graphs $G_{n}$ asymptotically contain a giant component with high
probability. Moreover, we will also determine its size. In this section we
collect all of our assumptions.

First of all, we assume that $V_{n}$ asymptotically contains $n$ vertices.
Noting that $|V_{n}|=k(n)^{d}m(n)$ we therefore assume that

$\lim_{n\to\infty}\frac{k(n)^{d}m(n)}{n}=1.$

Second, we will assume that $\lim_{n\to\infty}k(n)=\infty$. On the one hand,
this reflects the idea that vertices are only allowed to be connected when
they are very close together. On the other hand, this assures that our model
is clearly distinguished from the standard configuration model. Indeed, if we
only have finitely many compartments, then it should be possible to deduce
from the standard configuration model that a giant component emerges locally.
It then remains to show that (finitely many) of those connect together with
high probability.

In Section 5 we will see that if the number of vertices per compartment
becomes fixed, then a giant component does not necessarily emerge, even if the
degree sequence satisfies the conditions of our main theorem. Therefore, we
will assume that $m(n)$, the number of vertices per compartment, tends to
infinity. In particular, we will assume that

$\lim_{n\to\infty}\frac{n}{m(n)^{k}}=0$

for some $k\in\mathbb{N}$, which can be equivalently stated as there exist
$C,\alpha>0$ such that

$m(n)\geq Cn^{\alpha}.$

Apart from assumptions on the graph structure, we also need assumptions on the
degree sequences $d_{n}$. These are the same for the standard configuration
model, see e.g. [BR15, Hof17, Dur07]. In what follows, we denote by
$n_{j}(d_{n},C_{i}^{n})$ the amount of vertices of degree $j$ in compartment
$C_{i}^{n}$. Furthermore, we define $\mu_{n}(d_{n},C_{i}^{n})$ by

$\mu_{n}(d_{n},C_{i}^{n}):=\frac{1}{2}\sum_{x\in
C_{i}^{n}}d(x)=\frac{1}{2}\sum_{j=1}^{\infty}jn_{j}(d_{n},C_{i}^{n}).$

Using this notation, we make the following assumption on the convergence of
the degree sequence $d_{n}$.

######  Assumption 2.1 (Convergent degree sequence).

The degree sequence $d_{n}$ converges to a distribution $D$ in the following
sense:

  1. 1.

For every $\varepsilon>0$ there exists an $N$ such that for all $n\geq N$ and
all $i\in[k(n)]^{d}$ we have

$\left|\frac{n_{j}(d_{n},C_{i}^{n})}{m(n)}-\mathbb{P}(D=j)\right|<\varepsilon$

for all $j$.

  2. 2.

For every $\varepsilon>0$ there exists an $N$ such that for all $n\geq N$ and
all $i\in[k(n)]^{d}$ we have

$\left|\frac{\mu_{n}(d_{n},C_{i}^{n})}{m(n)}-\frac{\mathbb{E}(D)}{2}\right|<\varepsilon.$

We are now ready to state the main theorem.

######  Theorem 2.2.

Consider the compartment model on the $d$-torus with $k(n)^{d}$ compartments
with $m(n)$ vertices each, so that
$\lim_{n\to\infty}\frac{m(n)k(n)^{d}}{n}=1$. Assume that
$\lim_{n\to\infty}k(n)=\infty$ and that there exists $k\in\mathbb{N}$ such
that

$\lim_{n\to\infty}\frac{n}{m(n)^{k}}=0.$

Furthermore, for every $n$ let $d_{n}$ be a degree sequence on $m(n)k(n)^{d}$
vertices satisfying Assumption 2.1 with distribution $D$. Assume $E(D(D-2))>0$
and that there exists a $t>0$ such that $\mathbb{E}(e^{tD})<\infty$. If we
denote by $L_{1}(G_{n})$ the largest component in $G_{n}$, then there exists a
$\rho\in[0,1)$ such that

$\lim_{n\to\infty}\frac{L_{1}(G_{n})}{n}=1-\rho$

in probability. Furthermore, with high probability, there is no other cluster
of size more than $\beta\log m(n)$ for some $\beta>0$.

######  Remark 2.3.

The constant $\rho$ in Theorem 2.2 can be determined from the distribution
$D$. More precisely, we define the distribution $D^{*}$ by
$\mathbb{P}(D^{*}=i)=\frac{i\mathbb{P}(D=i)}{\mathbb{E}(D)}$, the so called
_size-biased degree distribution_. We can then interpret $\rho$ as the
extinction probability of the Galton-Watson tree where the root has offspring
distribution $D$, and all other individuals have offspring distribution
$Z_{D}=D^{*}-1$. The condition $E(D(D-2))>0$ implies that
$\mathbb{E}(Z_{D})>1$. In particular, this implies that the Galton-Watson tree
survives with positive probability, implying that $\rho<1$.

##  3 Branching processes

Studying components in random graphs is closely related to studying branching
processes. This occurs when we explore components of a graph from a given
vertex. Then, the next generation of the branching process resembles the
neighbours in the graph of the current generation. Such exploration may
traverse from one compartment to the other. Therefore, we will make use of a
multitype branching process to keep track of the compartment we are in. In
this section we will shortly introduce these processes, and collect some
necessary results. For a more thorough treatment, see e.g. [AN72, AL06].

###  3.1 Galton-Watson tree

The prototypical example of a branching process is the Galton-Watson tree,
which models the evolution of a population in which every individual of a
generation gets a random number of children. Furthermore, it is assumed that
the number of children of different individuals are independent, and follow
the same distribution.

More precisely, let $D$ be a probability distribution on the nonnegative
integers and denote by $Z_{n}$ the number of individuals in generation $n$.
For every $n$, let $X_{1}^{n},\ldots,X_{Z_{n}}^{n}$ be independent random
variables with distribution $D$. Then

$Z_{n+1}=\sum_{i=1}^{Z_{n}}X_{i}^{n}.$

An important question regarding such processes is whether they become extinct
or grow on indefinitely. We define the _extinction probability_ by

$\rho(D)=\lim_{n\to\infty}\mathbb{P}(Z_{n}=0).$

If $\mathbb{E}(D)<1$ then the process becomes almost surely extinct, i.e.
$\rho(D)=1$. If $\mathbb{E}(D)>1$ then the process has a positive probability
to grow on indefinitely. Moreover, this probability can be computed from the
generating function of the distribution $D$. In particular, the extinction
probability is the largest solution in $[0,1]$ of the equation

$x=\sum_{i=0}^{\infty}\mathbb{P}(D=i)x^{i}.$

###  3.2 Multitype branching processes

For our purposes, it is not sufficient to understand how large components
grow. We also need information on how components spread through different
compartments. In order to study this, we consider a branching process with
types, where type $i\in I^{d}\subset\mathbb{Z}^{d}$ of a vertex represents its
compartment. We denote generation $n$ of the branching process by a matrix
$Z_{n}$ of size $|I|^{d}$, where $Z_{n}(i)$ is the number of individuals of
type $i$ in generation $n$. We denote by $|Z_{n}|$ the size of generation $n$,
i.e.,

$|Z_{n}|=\sum_{i\in I^{d}}Z_{n}(i).$

For every type $i\in I^{d}$ we have an offspring distribution $D_{i}$, which
is now a distribution on matrices representing the types of the offspring. For
every $n$ and every $i\in I$, let $X_{1}^{n,i},\dots,X_{Z_{n}(i)}^{n,i}$ be
independent random variables with distribution $D_{i}$. We then have that

$Z_{n+1}=\sum_{i\in I}\sum_{j=1}^{Z_{n}(i)}X_{j}^{n,i}.$

When $I$ is finite, one looks at the matrix $M$ of expected offspring to study
the extinction of such processes. If we, for instance, assume that $M^{k}$ has
only positive entries for some sufficiently large $k$, then the largest
eigenvalue $\rho_{max}$ of $M$ determines whether extinction occurs almost
surely or whether there is some positive probability that the tree grows
indefinitely, see e.g. [Har63, Dur07]. When $I$ is countably infinite, the
conditions for extinction are more subtle, and we refer to [Moy64, HLN13]
among others.

####  3.2.1 Assigning types independently

We are specifically interested in the case where each offspring of a vertex is
independently assigned a type according to some distribution. In this case,
the offspring distribution is a multinomial distribution. Our claim is that
the distribution of individuals over the types in generation $n$ of such a
multitype branching process can be found by running a number of $n$-step
independent random walks equal to the size of the $n$-th generation.

More precisely, let $I^{d}\subset\mathbb{Z}^{d}$ be the state space. Let $N$
be a random variable taking values in the nonnegative integers, denoting the
number of children an individual will have. Furthermore, for $i\in I^{d}$, let
$p^{i}=(p_{j}^{i})_{j\in I^{d}}$ be a probability distribution on $I^{d}$. Let
$D_{i}$ denote a multinomial distribution with $N$ trials and probability
vector $p^{i}$, which we will take as offspring distribution of a type $i$
individual. Finally, we denote by $(Z_{n})_{n}$ the associated multitype
branching process.

Let us now define the inhomogeneous random walk $(S_{n})_{n}$ with which we
want to compare the branching process $(Z_{n})_{n}$. Since the walk is
inhomogeneous, we will construct it recursively. Let $S_{0}$ be distributed
according to a uniformly random individual of $Z_{0}$. Now, if $S_{n}$ is
given, we define $S_{n+1}$ as the random variable with distribution
$p^{S_{n}}$. The following proposition relates this random walk to the
branching process with multinomial offspring distribution.

######  Proposition 3.1.

Let $(Z_{n})_{n}$ be a multitype branching process with multinomial offspring
distribution. Let $(S_{n})_{n}$ be the associated random walk defined above,
and let $S^{1},S^{2},\ldots,S^{|Z_{n}|}$ be independent copies of $S_{n}$. For
$i\in I^{d}$, let $E_{i}$ be the matrix such that $E_{i}(j)=\delta_{ij}$. Then
$Z_{n}$ is in distribution equal to

$\mathcal{S}_{n}=\sum_{i=1}^{|Z_{n}|}E_{S^{i}}.$

###### Proof.

We will prove this using induction on $n$. First of all, note that
$\mathcal{S}_{0}$ is equal in distribution to $Z_{0}$, since $S_{0}$ is
distributed according to a uniformly random individual of $Z_{0}$.

Now suppose that $\mathcal{S}_{n}$ has the same distribution as $Z_{n}$.
Observe that by definition, the random variables $Z_{n}(i)$ for $i\in I^{d}$
are independent. Therefore, if $X_{1},\ldots,X_{|Z_{n+1}|}$ are independent
samples taken uniformly from the population $Z_{n+1}$, then

$Z_{n+1}=\sum_{j=1}^{|Z_{n+1}|}E_{X_{j}}$

in distribution. Now note that the distribution of $X_{j}$ is equal to
$p^{Y_{n}}$ where $Y_{n}$ is a uniform sample from the population $Z_{n}$.
Since $Z_{n}$ is equal in distribution to $\mathcal{S}_{n}$, this means that
$X_{j}$ has distribution $p^{S_{n}}$. As a consequence, we find that $X_{j}$
is equal in distribution to $S_{n+1}$. Putting everything together, we
conclude that $Z_{n+1}=\mathcal{S}_{n+1}$ in distribution. ∎

The above identification of the multitype branching process as a sum of random
walks is useful in deriving properties of the distribution of its $n$-th
generation. In particular, we consider the specific case where $I=\mathbb{Z}$
and

$p^{i}=\frac{1}{2d+1}\sum_{|j-i|_{1}\leq 1}E_{j}.$

One can show that in generation $n$, all types that are at most at distance
$\sqrt{n}$ from the starting type $Z_{0}=E_{0}$ are present with a significant
fraction. Before we can turn this in a rigorous statement, we first need the
following result on the associated random walk.

######  Lemma 3.2.

Let $X_{1},X_{2},\ldots$ be a sequence of i.i.d. random variables with
$\mathbb{P}(X_{i}=\pm e_{j})=\mathbb{P}(X_{i}=0)=\frac{1}{2d+1}$ for all
$j=1,\ldots,d$, where $\\{e_{1},\ldots,e_{d}\\}$ denotes the standard basis of
$\mathbb{R}^{d}$. Define $S_{n}=\sum_{i=1}^{n}X_{i}$. Then there exists a
$\delta>0$ such that for $n$ large enough we have

$\mathbb{P}(S_{n^{2}}=v)\geq\delta\mathbb{P}(S_{n^{2}}=0).$

for all $v\in\mathbb{Z}^{d}$ with $|v|_{1}=n$. Moreover, for $n$ large enough
we have

$\mathbb{P}(S_{n}=v)\geq\delta\mathbb{P}(S_{n}=0).$

for all $v\in\mathbb{Z}^{d}$ with $|v|_{1}\leq\sqrt{n}$.

###### Proof.

By the Kolmogorov-Rogozin inequality ([Ess66, Theorem 3], see also [Kol58,
Rog61]) there exists a constant $C>0$ such that

$\mathbb{P}(S_{n^{2}}=0)\leq Cn^{-d}.$

We are done once we show that for $v\in\mathbb{Z}^{d}$ with $|v|_{1}=n$ we
have

$\mathbb{P}(S_{n^{2}}=v)\geq cn^{-d}$

for some $c>0$ (independent of $v$). To this end, note that
$\mathbb{E}(X_{1})=0$ with covariance matrix $\Sigma$ given by

$\Sigma_{ij}=\begin{cases}\frac{2d}{(2d+1)^{2}}&i=j\\\
-\frac{1}{(2d+1)^{2}}&i\neq j\\\ \end{cases}.$

Therefore, by the central limit theorem we find that

$\frac{1}{n}S_{n^{2}}\Rightarrow\mathcal{N}\left(0,\Sigma\right).$

Now define for $0\leq r<s$ the annulus $A_{1}(r,s)\subset\mathbb{R}^{d}$ by

$A_{1}(r,s)=\\{x\in\mathbb{R}^{d}|r\leq|x|_{1}\leq s\\}.$

We then find that asymptotically we have

$\mathbb{P}(n\leq|S_{n^{2}}|_{1}\leq(1+\varepsilon)n)\geq(2\pi)^{-\frac{d}{2}}(\det\Sigma)^{-\frac{1}{2}}\int_{A_{1}(1,1+\varepsilon)}\exp\left(-\frac{1}{2}\langle
x,\Sigma^{-1}x\rangle\right)\,\mathrm{d}x.$

To compute this further, we use the spectrum of $\Sigma$. It turns out that
this is given by $\lambda_{1}=\frac{d+1}{(2d+1)^{2}}$ with multiplicity 1 and
$\lambda_{2}=\frac{1}{2d+1}$ with multiplicity $d-1$. This implies that

$\det\Sigma=\frac{(d+1)}{(2d+1)^{(}d+1)}.$

Furthermore, we have that

$|\langle
x,\Sigma^{-1}x\rangle|\leq||\Sigma^{-1}||_{2}||x||_{2}^{2}=\lambda_{\max}(\Sigma^{-1})||x||_{2}^{2}=\frac{(2d+1)^{2}}{d+1}||x||_{2}^{2}\leq\frac{(2d+1)^{2}}{d+1}||x||_{1}^{2}.$

Therefore, on $A(1,1+\varepsilon)$, we have

$|\langle
x,\Sigma^{-1}x\rangle|\leq\frac{(2d+1)^{2}}{d+1}(1+\varepsilon)^{2}=C(d)(1+\varepsilon)^{2}.$

Collecting everything, we find that

$\mathbb{P}(n\leq|S_{n^{2}}|_{1}\leq(1+\varepsilon)n)\geq(2\pi)^{-\frac{d}{2}}(d+1)^{-\frac{1}{2}}(2d+1)^{\frac{1}{2}(d+1)}\mathrm{Vol}(A_{1}(1,1+\varepsilon))e^{-\frac{1}{2}C(d)(1+\varepsilon)^{2}}.$

Now note that

$\mathrm{Vol}(1,1+\varepsilon)\sim\varepsilon^{d}.$

We thus have constants $C_{1}(d),C_{2}(d)>0$ such that

$\mathbb{P}(n\leq|S_{n^{2}}|_{1}\leq(1+\varepsilon)n)\geq
C_{1}(d)\varepsilon^{d}e^{-C_{2}(d)(1+\varepsilon)^{2}}$

Furthermore, we have

$|\\{v\in\mathbb{Z}^{d}|n\leq|v|_{1}\leq(1+\varepsilon)n\\}|\sim(\varepsilon
n)^{d}.$

Now, making use of the fact that $\mathbb{P}(S_{n^{2}}=v)$ is decreasing in
$|v|_{1}$ and $\mathbb{P}(S_{n^{2}}=v)=\mathbb{P}(S_{n^{2}}=w)$ whenever
$|v|_{1}=|w|_{1}$, we find from the above that

$\mathbb{P}(S_{n^{2}}=v)\geq C_{1}(d)\frac{1}{(\varepsilon
n)^{d}}\varepsilon^{d}e^{-C_{2}(d)(1+\varepsilon)^{2}}=C_{1}(d)n^{-d}e^{-C_{2}(d)(1+\varepsilon)^{2}}$

whenever $|v|_{1}=n$. This shows we can take

$c=C_{1}(d)e^{-C_{2}(d)(1+\varepsilon)^{2}},$

which proves the first statement.

The second statement now follows from the observation that
$\mathbb{P}(S_{n}=v)$ is decreasing when $|v|_{1}$ is increasing. ∎

Using concentration inequalities, we now show that if we start with a type 0
individual, then in generation $n$ all types $i$ at distance at most
$\sqrt{n}$ from the origin form a positive fraction of the total size of
generation $n$. We have the following proposition.

######  Proposition 3.3.

Let $Z_{n}$ be a multitype branching process with types $I=\mathbb{Z}^{d}$.
Assume the offspring distribution is multinomial with parameters $N$ and
$p=(p^{i})$, where $p^{i}=\frac{1}{2d+1}\sum_{|j-i|_{1}\leq 1}E_{j}$. Suppose
$M_{n}$ is such that $\mathbb{P}(|Z_{n}|\geq M_{n})>0$. Then there exists a
$\delta>0$ such that for every integer $0\leq r\leq\sqrt{n}$ and for $n$ large
enough we have

$\mathbb{P}\left(Z_{n}(k)\geq\delta\frac{M_{n}}{n^{\frac{d}{2}}}\mbox{ for
}|k|_{1}\leq r\middle||Z_{n}|\geq M_{n}\right)\geq
1-2(2r+1)^{d}\exp\left(-\frac{\delta^{2}M_{n}}{8n^{d}}\right).$ (3.1)

###### Proof.

Let $X_{1},X_{2},\ldots,X_{|Z_{n}|}$ be independent copies of the random walk
$S_{n}$ in Lemma 3.2. By Proposition 3.1 we have that $Z_{n}$ is equal in
distribution to

$\mathcal{S}_{n}=\sum_{i=1}^{|Z_{n}|}E_{X_{i}}.$

Now define

$\overline{\mathcal{S}}_{n}=\sum_{i=1}^{M_{n}}E_{X_{i}}.$

Note that $\mathcal{S}_{n}$ is larger in distribution than
$\overline{\mathcal{S}}_{n}$. As a consequence, we find that

$\displaystyle\mathbb{P}\left(Z_{n}(k)\geq\delta\frac{M_{n}}{\sqrt{n}}\mbox{
for }|k|_{1}\leq r\middle||Z_{n}|\geq M_{n}\right)$
$\displaystyle=\mathbb{P}\left(\mathcal{S}_{n}(k)\geq\delta\frac{M_{n}}{\sqrt{n}}\mbox{
for }|k|_{1}\leq r\middle||Z_{n}|\geq M_{n}\right)$
$\displaystyle\geq\mathbb{P}\left(\overline{\mathcal{S}}_{n}(k)\geq\delta\frac{M_{n}}{\sqrt{n}}\mbox{
for }|k|_{1}\leq r\right).$

Now define the function $F:\mathbb{R}^{M_{n}}\to\mathbb{R}^{\mathbb{Z}^{d}}$
given by

$F(x_{1},\ldots,x_{M_{n}})=\sum_{i=1}^{M_{n}}E_{x_{i}}$

Writing $I_{r}=[-r,r]\cap\mathbb{Z}$, we define from this the function
$\tilde{F}_{r}:\mathbb{R}^{M_{n}}\to\mathbb{R}^{I_{r}^{d}}$ given by

$\tilde{F}_{r}(x_{1},\ldots,x_{M_{n}})=\sum_{|l|_{1}\leq
r}F_{l}(x_{1},\ldots,x_{M_{n}})E_{l}.$

Here, $F_{l}$ denotes the $l$-th coordinate of $F$.

If we change a variable $x_{i}$, then at most one entry in the image of
$\tilde{F}_{r}$ is increased by 1 while at most one other is decreased by 1.
Therefore, we can apply Theorem A.2 with $c_{i}=1$ for all $i\in I_{r}^{d}$.
Since $|I_{r}^{d}|=(2r+1)^{d}$, this gives us that

$\mathbb{P}\left(||\overline{\mathcal{S}}_{n}-\mathbb{E}(\overline{\mathcal{S}}_{n})||_{L^{\infty}(I_{r}^{d})}\geq\varepsilon\right)\leq
2(2r+1)^{d}\exp\left(-\frac{\varepsilon^{2}}{2M_{n}}\right)$

for every $\varepsilon>0$.

Now we can compute
$\mathbb{E}(\overline{\mathcal{S}}_{n}(k))=M_{n}\mathbb{P}(S_{n}=k)$.
Therefore, by Lemma 3.2 there exists a $\delta>0$ such that

$\mathbb{E}(\overline{\mathcal{S}}_{n}(k))\geq\delta
M_{n}\mathbb{P}(S_{n}=0).$

for $n$ large enough and $|k|_{1}\leq\sqrt{n}$. By then central limit theorem
and the fact that $\mathbb{P}(S_{n}=k)$ is largest when $k=0$, we find that

$\mathbb{P}(S_{n}=0)\geq cn^{-\frac{d}{2}}$

for some $c>0$. Therefore, by shrinking $\delta$ sufficiently, we find that

$\mathbb{E}(\overline{\mathcal{S}}_{n}(k))\geq\delta\frac{M_{n}}{n^{\frac{d}{2}}}.$

Now

$\displaystyle\mathbb{P}\left(\overline{\mathcal{S}}_{n}(k)\geq\frac{\delta}{2}\frac{M_{n}}{n^{\frac{d}{2}}}\mbox{
for }|k|_{1}\leq r\right)$
$\displaystyle\geq\mathbb{P}\left(\left|\overline{\mathcal{S}}_{n}(k)-\mathbb{E}(\overline{\mathcal{S}}_{n}(k))\right|\leq\frac{\delta}{2}\frac{M_{n}}{n^{\frac{d}{2}}}\mbox{
for }|k|_{1}\leq r\right)$
$\displaystyle\geq\mathbb{P}\left(||\overline{\mathcal{S}}_{n}-\mathbb{E}(\overline{\mathcal{S}}_{n})||_{L^{\infty}(I_{r}^{d})}\leq\frac{\delta}{2}\frac{M_{n}}{n^{\frac{d}{2}}}\right)$
$\displaystyle=1-\mathbb{P}\left(||\overline{\mathcal{S}}_{n}-\mathbb{E}(\overline{\mathcal{S}}_{n})||_{L^{\infty}(I_{r}^{d})}>\frac{\delta}{2}\frac{M_{n}}{n^{\frac{d}{2}}}\right)$
$\displaystyle\geq 1-2(2r+1)\exp\left(-\frac{\delta^{2}M_{n}}{8n^{d}}\right)$

which concludes the proof. ∎

##  4 Proof of Theorem 2.2

In this section we prove Theorem 2.2. The proof relies on a similar idea as
the proof in [Dur07] for the standard configuration model. To study the
components of the random graph $G_{n}$ from the compartment model, we use an
exploration process. However, a major complication that arises in our case is
that we can only use this to find large components locally, because the
compartment structure restricts the neighbours of vertices we are exploring.
Since the total number of compartments $k(n)$ diverges, these large components
become ‘more and more local’.

The main idea is now to show that many (i.e. tending to infinity) such
locally-large components together form one giant component. However, this
means that we have to prove that a diverging number of such local components
exist simultaneously with high probability. Therefore, we need to obtain
precise quantitative bounds on the probability that the exploration process
finds a sufficiently large (local) component.

To study this exploration process, we connect it to a branching process. In
particular, we also need to track how the explored component spreads through
the different compartments. For this, our idea is to introduce types, where
each type represents a component. We then connect the exploration process
through the compartments to a multitype branching process. A similar argument
was recently used in [Siv14] to study site-percolation on the $d$-dimensional
Hamming torus. There, the types represent the $d$ directions in which
exploration can take place. We use the types in a completely different way,
with the multitype branching process tracking ’higher-order’ structure of the
graph, that is its compartmental structure. This representation allows us to
show that all locally-large components connect together with high probability
to form one large component that spreads through all compartments of the
$d$-dimensional torus. Finally, the proof is concluded by showing that this
large component is actually a giant component by determining its size.

###  4.1 Exploration process

In order to study the growth of components in the graph $G_{n}=(V_{n},E_{n})$
of the compartment model, we will explore them iteratively. To do this, we
start at a vertex $v\in V_{n}$ and reveal its neighbours. After that, we
consider each of these newly revealed vertices and reveal their neighbours,
and so on. In particular, in the exploration, we keep track of the compartment
to which each vertex belongs. Let us now define this process rigorously.

Recall that the graph $G_{n}=(V_{n},E_{n})$ consists of $k(n)^{d}$
compartments $\\{C_{i}^{n}\\}_{i\in[k(n)]^{d}}$, each containing $m(n)$
vertices. Let now $v\in C_{j}^{n}$ be some vertex in the graph $G_{n}$. The
_exploration process_ started at $v$ is a sequence of tuples
$(R_{l},A_{l},U_{l})$ of hypermatrices of dimension $k(n)^{d}$ constructed
recursively. Here $R_{l}(i)$ denotes the set of explored vertices in
compartment $C_{i}^{n}$, $A_{l}(i)$ the set of active vertices in compartment
$C_{i}^{n}$, i.e., those that we have already revealed, but not yet explored,
and $U_{l}(i)$ are the other, yet unseen vertices in compartment $C_{i}^{n}$.
We initialize the process by setting $R_{0}(i)=\emptyset$ for all $i$,
$A_{0}(j)=\\{v\\}$ and $A_{0}(i)=\emptyset$ for all $i\neq j$ and
$U_{0}(j)=C_{j}^{n}-\\{v\\}$ and $U_{0}(i)=C_{i}^{n}$ for $i\neq j$. Now, at
every iteration, we define $A_{l+1}$ to be all neighbours of vertices in
$A_{l}$ which are in $U_{l}$. We then set $R_{l+1}=R_{l}\cup A_{l}$ and
$U_{l+1}=U_{l}\setminus A_{l+1}$, where the set operations have to be
interpreted element-wise.

A somewhat related exploration process was used in [Siv14]. However, there the
types are assigned while the exploration is running, while in our case, the
types are known beforehand. Furthermore, in [Siv14], one vertex is explored at
a time, while we consider an entire generation at once.

Using this exploration process, we want to analyse how large the component we
explore grows. In order to do this, we need to find a lower bound on the size
of the active set $A_{l}$. To this end, we introduce the following notation:

$|A_{l}|=(|A_{l}(i)|)_{i\in[k(n)]^{d}}$

and

$||A_{l}||=\sum_{i\in[k(n)]^{d}}|A_{l}(i)|.$

In the upcoming proposition we prove that we can use a multitype branching
process as pointwise stochastic lower bound for $|A_{l}|$. For real-valued
random variables $X$ and $Y$ we say that $X$ is a lower bound for $Y$ if for
all $a\in\mathbb{R}$ we have $\mathbb{P}(X\geq a)\leq\mathbb{P}(Y\geq a)$.
Furthermore, we call a sequence $r=(r_{k})_{k\geq 0}$ a _distribution_ if
$\sum_{k=0}^{\infty}r_{k}=1$ and $r_{k}\geq 0$ for all $k$. For every such
sequence, we let $W_{r}:(0,1)\to\mathbb{N}$ be a non-decreasing function
satisfying

$|\\{\omega|W_{r}(\omega)=k\\}|=r_{k}.$

It follows that if we remove mass $\eta$ from the distribution $r$ and
normalize, then this will be stochastically larger than
$W_{r}^{\eta}=(W_{r}(\omega)|\omega<1-\eta)$. Indeed, the latter removes mass
$\eta$, starting from the largest values of $W_{r}$. Using all this, we can
state and prove the following proposition.

######  Proposition 4.1.

Let the assumptions of Theorem 2.2 be satisfied. Let $i\in[k(n)]^{d}$ and let
$v\in C_{i}^{n}$ and denote by $(R_{l},A_{l},U_{l})$ the exploration process
started at $v$. Let $\eta\in(0,1)$ and assume that at most $\eta m(n)$
vertices of each compartment have already been exposed. Then for every
$\delta>0$ there exist a multitype branching process $(S_{l})_{l}$, such that
until $\delta m(n)$ vertices in at least one compartment have been exposed, we
have that $|A_{l}|$ is stochastically bounded from below by $S_{l}$.

Moreover, the offspring distribution of $(S_{l})_{l}$ can be chosen to be
multinomial with parameters $N$ and $p=(p^{i})$ where
$p^{i}=\frac{1}{2d+1}\sum_{|j-i|_{1}\leq 1}E_{j}$. Furthermore, for $\delta$
small enough, $N$ can be chosen such that $\mathbb{E}(N)>1$.

###### Proof.

We argue the existence by constructing a suitable multitype branching process.
To this end, we first argue what happens when exploring a single vertex $w\in
C_{j}^{n}$. Assume that at most $\eta m(n)$ vertices have been exposed in
every compartment. Let $D^{*}$ be the size-biased degree distribution (see
Remark 2.3) and set $Z_{D}=D^{*}-1$. We define the distribution $q=(q_{k})$ by
$q_{k}=\mathbb{P}(Z_{D}=k)$. Since at most a fraction $\eta$ of the vertices
has been exposed, together with the fact that $d_{n}$ converges to $D$ as in
Assumption 2.1, it follows that for $n$ large enough the amount of new
neighbours found while exploring $w$ is bounded from below by $W_{q}^{2\eta}$.

By symmetry, these $W_{q}^{2\eta}$ new vertices are equally likely to be in
any of the neighbouring compartments of $w$, i.e., in the compartments
$C_{i}^{n}$ with $|i-j|_{1}\leq 1$. Therefore, we consider the random
variables

$\bar{W}_{q,j}^{2\eta}\sim\mathrm{Mult}\left(W_{q}^{2\eta},\frac{1}{2d+1}\sum_{|i-j|_{1}\leq
1}E_{i}\right),$

which is a multinomial distribution. Here, $E_{i}(x)=\delta_{ix}$ for
$x\in[k(n)]^{d}$.

Finally, we need to take into account that the new vertices may already have
been exposed before. Because of the degree constraints, we remove these
vertices from the active set. Note that $\bar{W}_{q,j}^{2\eta}(i)$ takes
values in the set $\\{0,1,\ldots,L\\}$, where $L=W_{q}(1-2\eta)$. Therefore,
if at most $\delta m(n)$ vertices have been exposed from any compartment
$C_{i}^{n}$, then there are at most $L\delta m(n)$ possible half-edges
connected to active vertices in $C_{i}^{n}$. On the other hand, there are at
least $\mu_{n}(d_{n},C_{i}^{n})-L\delta m(n)$ half-edges left which are not
connected to an active vertex. Therefore, the probability of choosing an
active neighbour in that compartment is at most

$\frac{L\delta m(n)}{\mu_{n}(d_{n},C_{i}^{n})-L\delta m(n)}.$

From Assumption 2.1 it follows that $\frac{\mu_{n}(d_{n},C_{i}^{n})}{m(n)}$
converges to $\frac{1}{2}\mathbb{E}(D)$ uniformly over the compartments.
Therefore, given $\varepsilon>0$, for $n$ large enough the above is smaller
than

$\gamma_{\delta}:=\frac{L\delta}{\frac{1}{2}\mathbb{E}(D)-\varepsilon-L\delta}$

provided $\delta>0$ is small enough.

Collecting everything, we see that the number of new vertices found while
exploring $w\in C_{j}^{n}$ is bounded from below by

$X_{j}\sim\bar{W}_{q,j}^{2\eta}-2\sum_{|i-j|_{1}\leq
1}\mathrm{Bin}(|\bar{W}_{q,j}^{2\eta}(i)|,\gamma_{\delta})E_{i}.$

From this we can conclude that $X_{j}$ follows a multinomial distribution with
parameters $N$ and $p^{j}=\frac{1}{2d+1}\sum_{|i-j|_{1}\leq 1}E_{i}$. In
particular, for $N$ we have

$N\sim W_{q}^{2\eta}-2\mathrm{Bin}(W_{q}^{2\eta},\gamma_{\delta}).$

From this it follows that

$\mathbb{E}(N)=\mathbb{E}(W_{q}^{2\eta})(1-2\gamma_{\delta}).$

Now note that $\lim_{\eta\to
0}\mathbb{E}(W_{q}^{2\eta})=\mathbb{E}(W_{q})=\mathbb{E}(Z_{D})$. Since by
assumption $\mathbb{E}(Z_{D})>1$ (see Remark 2.3), we find that for $\eta$
small enough we have $\mathbb{E}(W_{q}^{2\eta})>1$. Furthermore, note that
$\gamma_{\delta}$ tends to 0 as $\delta$ tends to 0. Combining the above, we
find that we can choose $\delta$ and $\eta$ small enough so that
$\mathbb{E}(N)>1$. ∎

Our next aim is to prove that if $||A_{l}||$ grows to size $\beta\log m(n)$,
then it actually grows to size $m(n)^{\frac{2}{3}}$ with high probability. For
this, we will use the lower bound we found in Proposition 4.1. Before we can
show this, we first need a lemma.

######  Lemma 4.2.

Let $X$ be a random variable such that $X\geq-1$, $\mathbb{P}(X=-1)>0$ and
$\mathbb{E}(X)>0$. Define $S_{n}$ by

$S_{n}=S_{0}+\sum_{i=1}^{n}Y_{i},$

where $Y_{i}=\sum_{j=1}^{S_{i-1}}X_{j}$ with $X_{1},\ldots X_{S_{i-1}}$ i.i.d.
with distribution $X$. Suppose $S_{0}=x>0$ and define

$T(x):=\inf\\{n||S_{n}|=0\\}.$

Then there exists a $\lambda>0$ such that

$\mathbb{P}(T(x)<\infty)\leq e^{-\lambda x}.$

###### Proof.

It suffices to prove the statement for $X$ bounded from above, since this only
increases $T(x)$. Let $M(t)=\mathbb{E}(e^{tX})$ be the moment generating
function of $X$. Since $X$ is bounded from below, we have that $M(t)$ is
defined for all $t\leq 0$. Note that $M(0)=1$, $M^{\prime}(0)=\mathbb{E}(X)>0$
and

$\lim_{t\to-\infty}M(t)\geq\lim_{t\to-\infty}\mathbb{P}(X=-1)e^{-t}=\infty.$

From this, together with the continuity of $M(t)$, it follows that there
exists a $\lambda>0$ such that $M(-\lambda)=1$. This implies that
$Z_{n}=e^{-\lambda S_{n}}$ is a martingale.

From the optional stopping theorem, we find that

$\mathbb{E}\left(Z_{T(x)}\right)=\lim_{n\to\infty}\mathbb{E}\left(Z_{n\wedge
T(x)}\right)=\mathbb{E}(Z_{0})=e^{-\lambda x}.$

On the other hand,

$\mathbb{E}\left(Z_{T(x)}\right)\geq\mathbb{P}(T<\infty),$

and hence we find that $\mathbb{P}(T(x)<\infty)\leq e^{-\lambda x}$. ∎

Using this lemma, we can show that if the active set of the exploration
process grows to size $\beta\log m(n)$, then the probability that the
exploration process does not explore a large cluster is small. More precisely,
we have the following proposition.

######  Proposition 4.3.

Let the assumptions in Proposition 4.1 be satisfied. Suppose
$\sum_{i=0}^{l}||A_{i}||\geq\beta\log m(n)$ for some $l$. Define

$T:=\inf\\{n|||A_{n}||=0\\}.$

Then for $\beta$ large enough we have

$\mathbb{P}(T<\infty)\leq 2m(n)^{-k}.$

###### Proof.

Let $S_{n}$ be the lower bound for $|A_{n}|$ from Proposition 4.1. Then

$|S_{n}|=\sum_{i\in[k(n)]^{d}}S_{n}(i)$

is a lower bound for $||A_{n}||$, and in particular,

$\Sigma_{l}=\sum_{i=0}^{l}|S_{i}|$

is a lower bound for $\sum_{i=0}^{l}||A_{i}||$.

Now assume that $\Sigma_{l}\geq\beta\log m(n)$ and define

$\tilde{T}=\inf\\{n||S_{n}|=0\\}.$

Then $\mathbb{P}(T<\infty)\leq\mathbb{P}(\tilde{T}<\infty)$.

Note that we can write

$|S_{l+1}|=\sum_{i=1}^{|S_{l}|}\tilde{X}_{i},$

where $\tilde{X}_{1},\ldots,\tilde{X}_{|S_{l}|}$ are independent and
distributed like $N$ as in Proposition 4.1. By telescoping, this implies that

$|S_{l+1}|=\sum_{j=1}^{\Sigma_{l}}X_{j},$

where $X_{1},\ldots,X_{\Sigma_{l}}$ are independent and equal in distribution
to $N-1$.

Let $\lambda$ be as in Lemma 4.2 for the random variable $X_{1}$. From
Chernoff’s bound it follows that

$\displaystyle\mathbb{P}\left(\sum_{j=1}^{\sigma}X_{j}\leq\frac{k}{\lambda}\log
m(n)\right)$ $\displaystyle\leq e^{\theta\frac{k}{\lambda}\log
m(n)}\mathbb{E}(e^{-\theta X_{1}})^{\sigma}$
$\displaystyle=\exp\left(\theta\frac{k}{\lambda}\log m(n)+\sigma\log
M(-\theta)\right)$

for all $\theta>0$, where $M(t)=\mathbb{E}(e^{tX_{1}})$. Since
$M(0)=1,M(-\lambda)=1$ and $M^{\prime}(0)=\mathbb{E}(X_{1})>0$, there exists a
$\lambda^{\prime}\in(0,\lambda)$ such that $M(-\lambda^{\prime})<1$. In
particular, this implies that $\log M(-\lambda^{\prime})<0$. From this it
follows that for $\sigma\geq\beta\log m(n)$ we have

$\mathbb{P}\left(\sum_{j=1}^{\sigma}X_{j}\leq\frac{k}{\lambda}\log
m(n)\right)\leq\exp\left(\left(\lambda^{\prime}\frac{k}{\lambda}+\beta\log
M(-\lambda^{\prime})\right)\log m(n)\right).$

Using that $\log M(-\lambda^{\prime})<0$, we can take $\beta$ large enough
such that

$\lambda^{\prime}\frac{k}{\lambda}+\beta\log M(-\lambda^{\prime})\leq-k$

so that

$\mathbb{P}\left(\sum_{j=1}^{\sigma}X_{j}\leq\frac{k}{\lambda}\log
m(n)\right)\leq m(n)^{-k}.$

From this we conclude that if $\Sigma_{l}\geq\beta\log m(n)$ for large enough
$\beta$, we have that

$\mathbb{P}\left(|S_{l+1}|<\frac{k}{\lambda}\log m(n)\right)\leq m(n)^{-k}.$

From this, we obtain that

$\displaystyle\mathbb{P}(\tilde{T}<\infty)$
$\displaystyle\leq\mathbb{P}\left(\left|S_{l+1}\right|\leq\frac{k}{\lambda}\log
m(n)\right)+\mathbb{P}\left(\tilde{T}<\infty\middle|\left|S_{l+1}\right|\geq\frac{k}{\lambda}\log
m(n)\right)$ $\displaystyle\leq 2m(n)^{-k}.$

Here, we applied Lemma 4.2 to bound the second term. Since
$\mathbb{P}(T<\infty)\leq\mathbb{P}(\tilde{T}<\infty)$, this proves the claim.
∎

We conclude this part by proving that if we repeatedly start the exploration
process at a vertex in $C_{i}^{n}$ for some fixed $i\in[k(n)]^{d}$, then with
high probability we find a component of size at least $m(n)^{\frac{2}{3}}$
before $\delta m(n)$ vertices have been exposed. This follows from the fact
that with high probability, each failed attempt uses at most $\beta\log m(n)$
vertices. Carefully estimating this probability is necessary to deal with the
diverging number of locally-large components that we find. This provides a
major contrast with [Dur07], where showing that the result holds with high
probability suffices.

######  Proposition 4.4.

The probability that the exploration process started (repeatedly) at a vertex
in $C_{i}^{n}$ finds a component of size at least $m(n)^{\frac{2}{3}}$ before
a total of $\delta m(n)$ vertices have been exposed is at least

$\left(1-2m(n)^{-k}\right)^{\frac{\delta m(n)}{\beta\log
m(n)}}\left(1-(1-p)^{\frac{\delta m(n)}{\beta\log m(n)}}\right).$

Here, $p>0$ is the probability that the branching process $(S_{n})_{n}$ in
Proposition 4.1 survives indefinitely.

###### Proof.

Let $G$ denote the number of tries it takes before $S_{n}$ grows to size
$m(n)^{\frac{2}{3}}$. Then $G$ is geometrically distributed with parameter
$\tilde{p}\geq p>0$. Let $R_{1},R_{2},\ldots$ be a sequence of i.i.d. random
variables representing the number of vertices exposed in a failed attempt. We
need to prove that

$\mathbb{P}\left(\sum_{i=1}^{G}R_{i}\leq\delta
m(n)\right)\geq\left(1-2m(n)^{-k}\right)^{\frac{\delta m(n)}{\beta\log
m(n)}}\left(1-(1-p)^{\frac{\delta m(n)}{\beta\log m(n)}}\right).$

Now

$\mathbb{P}\left(\sum_{i=1}^{G}R_{i}\leq\delta
m(n)\right)=\sum_{g=1}^{\infty}\mathbb{P}\left(\sum_{i=1}^{g}R_{i}\leq\delta
m(n)\right)\mathbb{P}(G=g).$

For $g\leq\frac{\delta m(n)}{\beta\log m(n)}$ we have

$\mathbb{P}\left(\sum_{i=1}^{g}R_{i}\leq\delta
m(n)\right)\geq(1-2m(n)^{-k})^{g}\geq\left(1-2m(n)^{-k}\right)^{\frac{\delta
m(n)}{\beta\log m(n)}},$

where the first inequality follows from Proposition 4.3. Using this, we find
that

$\displaystyle\mathbb{P}\left(\sum_{i=1}^{G}R_{i}\leq\delta m(n)\right)$
$\displaystyle\geq\left(1-2m(n)^{-k}\right)^{\frac{\delta m(n)}{\beta\log
m(n)}}\mathbb{P}\left(G\leq\frac{\delta m(n)}{\beta\log m(n)}\right)$
$\displaystyle=\left(1-2m(n)^{-k}\right)^{\frac{\delta m(n)}{\beta\log
m(n)}}\left(1-(1-\tilde{p})^{\frac{\delta m(n)}{\beta\log m(n)}}\right).$

The desired bound now follow because $\tilde{p}\geq p$. ∎

###  4.2 From local to global

In Proposition 4.4 we have seen that if we start exploring from a vertex in
$C_{i}^{n}$, with high probability we find a component of size at least
$m(n)^{\frac{2}{3}}$ at some point. In this section, we will first show that
such a component spreads equally through all compartments near $C_{i}^{n}$.
Since we could have started equally well from any other compartment, the idea
is to show that with high probability, many of such locally-large components
exist which together cover all compartments. It then remains to prove that
these components are all connected with high probability, forming a large
component which spreads through every compartment.

####  4.2.1 Spreading through compartments

To see how the explored component spreads through neighbouring compartments,
we use the multitype branching process found in Proposition 4.1. We will first
show that, provided the branching process grows to a certain size, it actually
does so exponentially fast with high probability. The following proposition is
closely related to the large deviation results in [Ath94] (see also [AN72]).
However, we need more precise information on the growth of the involved
constants.

######  Proposition 4.5.

Let $T=(T_{l})_{l}$ be a Galton-Watson tree with bounded offspring
distribution $N$ satisfying $\mathbb{E}(N)>1$ and $T_{0}=1$. Suppose there
exists an $l$ such that $T_{l}\geq M_{n}$. Define

$p(n)=\inf\\{p|T_{p}\geq M_{n}\\}<\infty.$

Then for every $0<\tau<1$ and every $L>1$ we have

$\mathbb{P}\left(p(n)\leq LM_{n}^{\tau}\right)\geq 1-2e^{-2(L-1)M_{n}^{\tau}}$

for $n$ sufficiently large.

###### Proof.

Because there exists and $l$ such that $T_{l}\geq M_{n}$, we know that every
generation contains at least one vertex which survives until the tree grows to
size $M_{n}$. We call such a vertex immortal. Every immortal vertex has at
least one child that is also immortal. Moreover, since $E(N)>1$, the
probability of having only one immortal child is less than 1. Denote by
$\overline{N}$ the offspring distribution $N$ conditioned to be at least 1.
Then $\mathbb{E}(\overline{N})>1$ and $\overline{N}$ is bounded since $N$ is
bounded.

Denote by $(Z_{l})$ the Galton-Watson tree with offspring distribution
$\overline{N}$. Since $\overline{N}\geq 1$, $Z_{l}$ is non-decreasing in $l$
and therefore we have

$p(n)\leq LM_{n}^{\tau}\quad\iff\quad Z_{LM_{n}^{\tau}}\geq M_{n}.$

This implies that

$\mathbb{P}\left(p(n)\leq
LM_{n}^{\tau}\right)=\mathbb{P}\left(Z_{LM_{n}^{\tau}}\geq M_{n}\right).$

Since $\overline{N}\geq 1$, we have that $Z_{n}\geq n$. This implies that

$\mathbb{P}(Z_{(\tilde{L}+1)n^{\tau}}\leq
n)\leq\mathbb{P}(Z_{\tilde{L}n^{\tau}}\leq n|Z_{0}=n^{\tau}).$

Now consider

$\mathbb{P}(Z_{l+1}\leq(1+c)Z_{l}|Z_{l}=x)$

for some $c>0$. We have

$Z_{l+1}\geq Z_{l}+\sum_{i=1}^{x}B_{i},$

where the $B_{i}$ are independent Bernoulli random variables with parameter
$p=\mathbb{P}(\overline{N})>1>0$. Taking $c<p$, we find that

$\mathbb{P}(Z_{l+1}\leq(1+c)Z_{l}|Z_{l}=x)\leq\mathbb{P}\left(\frac{1}{x}\sum_{i=1}^{x}B_{i}\leq
c\right).$

Using Hoeffding’s inequality, we find

$\displaystyle\mathbb{P}\left(\frac{1}{x}\sum_{i=1}^{x}B_{i}\leq c\right)$
$\displaystyle\leq\mathbb{P}\left(\left|\sum_{i=1}^{x}B_{i}-xp\right|>(p-c)x\right)$
$\displaystyle\leq 2\exp\left(-2x(p-c)^{2}\right).$

In particular, taking $x=n^{\tau}$, we find that

$\mathbb{P}(Z_{l+1}\leq(1+c)Z_{l}|Z_{l}=n^{\tau})\leq
2\exp\left(-2n^{\tau}(p-c)^{2}\right)=:q_{n}.$

Now note that for $\alpha_{n}=\frac{1-\tau}{\log(1+c)}\log n$ we have
$(1+c)^{\alpha_{n}}n^{\tau}=n$. Let us denote by $\tilde{B}_{i}$ independent
Bernoulli random variables with parameter $p_{n}=1-q_{n}$. Then

$\mathbb{P}(Z_{\tilde{L}n^{\tau}}\leq
n|Z_{0}=n^{\tau})\leq\mathbb{P}\left(\sum_{i=1}^{\tilde{L}n^{\tau}}\tilde{B}_{i}\leq\alpha_{n}\right).$

In a similar fashion as above, we find that

$\mathbb{P}\left(\sum_{i=1}^{\tilde{L}n^{\tau}}\tilde{B}_{i}\leq\alpha_{n}\right)\leq
2\exp\left(-2\tilde{L}n^{\tau}(\tilde{L}n^{\tau}p_{n}-\alpha_{n})^{2}\right)$

Since $\alpha_{n}\sim\log n$, we find that

$2\exp\left(-2\tilde{L}n^{\tau}(\tilde{L}n^{\tau}p_{n}-\alpha_{n})^{2}\right)\leq
2\exp\left(-2\tilde{L}n^{\tau}\right)$

for $n$ sufficiently large. The result now follows by combining all estimates
above, inserting $M_{n}$ and noticing that $\tilde{L}=L-1$. ∎

We are now ready to estimate the sizes of the locally-large components we find
while exploring the spread through the compartments. This result is the main
reason why we have to resort to multitype branching processes.

######  Proposition 4.6.

Let the assumptions of Proposition 4.1 be satisfied and denote by $C$ a
component explored by the exploration process started at a vertex $v\in
C_{i}^{n}$ for some $i\in[k(n)]^{d}$. Assume the active set of the exploration
process reaches size $m(n)^{\frac{2}{3}}$. Then for every $\varepsilon>0$ and
$0<\tau<\frac{2}{3}$ we have

$\mathbb{P}\left(|C\cap C_{i}^{n}|\geq\varepsilon
m(n)^{\frac{2}{3}-\tau}\right)\geq\left(1-2\exp\left(-\frac{1}{8}\varepsilon^{2}m(n)^{\frac{2}{3}-2\tau}\right)\right)\left(1-2e^{-2m(n)^{\frac{2}{d}\tau}}\right)$

for sufficiently large $n$.

###### Proof.

Let $(S_{n})_{n}$ be the multitype branching process from Proposition 4.1.
Assume there exists an $l$ such that $|S_{l}|\geq m(n)^{\frac{2}{3}}$. Set

$p(n):=\inf\left\\{p\middle||S_{p}|\geq m(n)^{\frac{2}{3}}\right\\}<\infty.$

Then $|C\cap C_{i}^{n}|\geq S_{p(n)}(i)$. Therefore, it suffices to find a
lower bound for

$\mathbb{P}\left(S_{p(n)}(i)\geq\varepsilon m(n)^{\frac{2}{3}-\tau}\right).$

Note that $p(n)$ is a random variable. We have

$\mathbb{P}\left(S_{p(n)}(i)\geq\varepsilon
m(n)^{\frac{2}{3}-\tau}\right)=\sum_{p}\mathbb{P}\left(S_{p}(i)\geq\varepsilon
m(n)^{\frac{2}{3}-\tau}\right)\mathbb{P}(p(n)=p).$

By Proposition 4.5 we have (taking $L=2$)

$\mathbb{P}(p(n)\leq 2m(n)^{\frac{2}{d}\tau})\geq
1-2e^{-2m(n)^{\frac{2}{d}\tau}}.$

Now, for $p\leq 2m(n)^{\frac{2}{d}\tau}$ we have

$\displaystyle\mathbb{P}\left(S_{p}(i)\geq\varepsilon
m(n)^{\frac{2}{3}-\tau}\right)$
$\displaystyle\geq\mathbb{P}\left(S_{p}(i)\geq\varepsilon
2^{\frac{d}{2}}\frac{m(n)^{\frac{2}{3}}}{p^{\frac{d}{2}}}\right)$
$\displaystyle\geq
1-2\exp\left(-\frac{\varepsilon^{2}2^{d}m(n)^{\frac{2}{3}}}{8p^{d}}\right)$
$\displaystyle\geq
1-2\exp\left(-\frac{1}{8}\varepsilon^{2}m(n)^{\frac{2}{3}-2\tau}\right).$

Here, the third line follows from Proposition 3.3 (with $r=0$).

If we now collect everything, we find that

$\displaystyle\mathbb{P}\left(S_{p(n)}(i)\geq\varepsilon
m(n)^{\frac{2}{3}-\tau}\right)$
$\displaystyle\geq\left(1-2\exp\left(-\frac{1}{8}\varepsilon^{2}m(n)^{\frac{2}{3}-2\tau}\right)\right)\mathbb{P}(p(n)\leq
2m(n)^{\frac{2}{d}\tau})$
$\displaystyle\geq\left(1-2\exp\left(-\frac{1}{8}\varepsilon^{2}m(n)^{\frac{2}{3}-2\tau}\right)\right)\left(1-2e^{-2m(n)^{\frac{2}{d}\tau}}\right).$

This concludes the proof. ∎

####  4.2.2 Connecting local components

Proposition 4.4 and 4.6 together give a lower bound on the probability that
there exists a component of at least size $m(n)^{\frac{2}{3}}$ of which at
least $\varepsilon m(n)^{\frac{2}{3}-\tau}$ vertices are in a given
compartment $C_{i}^{n}$.

For $i\in[k(n)]^{d}$, denote by $I_{i}$ the indicator random variable of the
event that there exists a component as in Section 4.2.1, where the exploration
is started in compartment $C_{i}^{n}$. It follows from Proposition 4.4 and 4.6
that $\mathbb{P}(I_{i}=1)=a_{n}b_{n}$, where

$a_{n}=\left(1-2m(n)^{-k}\right)^{\frac{\delta m(n)}{\beta\log
m(n)}}\left(1-(1-p)^{\frac{\delta m(n)}{\beta\log m(n)}}\right)$

and

$b_{n}=\left(1-2\exp\left(-\frac{1}{8}\varepsilon^{2}m(n)^{\frac{2}{3}-2\tau}\right)\right)\left(1-2e^{-2m(n)^{\frac{2}{d}\tau}}\right).$

However, the random variables $I_{i}$ are not independent. Nonetheless, we
have

$\displaystyle\mathbb{P}(I_{i}=1\mbox{ for all }i=\in[k(n)]^{d})$
$\displaystyle=1-\mathbb{P}(I_{i}=0\mbox{ for some }i\in[k(n)]^{d})$
$\displaystyle\geq 1-\sum_{i\in[k(n)]^{d}}\mathbb{P}(I_{i}=0)$
$\displaystyle=1-k(n)^{d}\mathbb{P}(I_{1}=0)$
$\displaystyle=1-k(n)^{d}(1-a_{n}b_{n}).$

Next, we want to show that sufficiently large components from neighbouring
compartments are actually connected with high probability. For this, we need
the following lemma.

######  Lemma 4.7.

Let $i,j\in[k(n)]^{d}$ be such that $|i-j|_{1}\leq 1$. Let $A\subset
C_{i}^{n}$ and $B\subset C_{j}^{n}$. Assume that the vertices in $A$ and $B$
have degree at least 1. Then there exists a $C>0$ (depending on $d$) such that
for $n$ large enough the probability that there is no edge between $A$ and $B$
in $G_{n}$ is at most

$\exp\left(-\frac{C|A||B|}{m(n)}\right).$

###### Proof.

Since all vertices have degree at least 1, the total degree in $A$ and $B$ is
at least $|A|$ respectively $|B|$. On the other hand, because of the
convergence of the degree sequence of $G_{n}$, we know that for $n$ large
enough the total degree in each compartment is at most $2\mathbb{E}(D)m(n)$.
This implies that a half-edge at a vertex can be connected to at most
$(4d+2)\mathbb{E}(D)m(n)$ half-edges. With these observations, the result
follows from a similar reasoning as in [BR15, Lemma 20]. ∎

From Lemma 4.7 it follows that the probability that two neighbouring
components are connected is more than

$c_{n}:=1-\exp\left(-C\varepsilon^{2}m(n)^{\frac{1}{3}-2\tau}\right).$

Collecting everything, we find that there exists a component $C$ with $|C\cap
C_{i}^{n}|\geq\varepsilon m(n)^{\frac{2}{3}-\tau}$ for all $i\in[k(n)]^{d}$
with probability at least

$(1-k(n)^{d}(1-a_{n}b_{n}))(1-dk(n)c_{n}).$

Here, the $d$ in the second factor comes from the observation that every
compartment has $2d$ neighbouring compartment. Since every neighbour relation
is counted twice when summing over all compartment, we have to divide by two.

From the above discussion, we obtain the following.

######  Proposition 4.8.

For every $\tau\in(0,\frac{1}{6})$ we have that with high probability there
exists a component $C$ in $G_{n}$ such that for all $i\in[k(n)]^{d}$ we have

$|C\cap C_{i}^{n}|\geq\varepsilon m(n)^{\frac{2}{3}-\tau}.$

###### Proof.

Following the reasoning above, it remains to show that

$\lim_{n\to\infty}(1-k(n)^{d}(1-a_{n}b_{n}))(1-dk(n)c_{n})=1.$

In order to do this, we observe that is suffices to prove that

$\lim_{n\to\infty}a_{n}^{k(n)^{d}}=\lim_{n\to\infty}b_{n}^{k(n)^{d}}=\lim_{n\to\infty}(1-c_{n})^{dk(n)}=1$
(4.1)

Indeed, suppose $0<x_{n}<1$ and assume $\lim_{n\to\infty}x_{n}^{f(n)}=1$. Then
we have $\lim_{n\to\infty}f(n)\log(x_{n})=0$. But $\log(x_{n})\leq x_{n}-1\leq
0$, and hence, by the squeeze theorem we find that
$\lim_{n\to\infty}f(n)(x_{n}-1)=0$ from which it follows that
$\lim_{n\to\infty}1-f(n)(1-x_{n})=1$.

Let us prove that (4.1) holds. We will only show this for $a_{n}$, the result
for $b_{n}$ and $c_{n}$ being proven similarly (the conditions on $\tau$ being
needed there to have the desired decay).

Since by assumption $\lim_{n\to\infty}\frac{k(n)^{d}m(n)}{n}=1$, we have for
$n$ large that $k(n)^{d}\approx\frac{n}{m(n)}$. Therefore, we have
asymptotically

$a_{n}^{k(n)^{d}}\approx\left(1-2m(n)^{-k}\right)^{\frac{\delta n}{\beta\log
m(n)}}\left(1-(1-p)^{\frac{\delta m(n)}{\beta\log
m(n)}}\right)^{\frac{n}{m(n)}}.$

For the first factor, taking logarithms, we have

$\frac{\delta n}{\beta\log
m(n)}\log\left(1-2m(n)^{-k}\right)\approx-\frac{\delta n}{\beta m(n)^{k}\log
m(n)}$

where we used that $\log(1-x)\approx-x$. Since by assumption $k$ is such that
$\lim_{n\to\infty}nm(n)^{-k}=0$, the above converges to 0 and therefore

$\lim_{n\to\infty}\left(1-2m(n)^{-k}\right)^{\frac{\delta n}{\beta\log
m(n)}}=1.$

In a similar way, the second factor converges to 1 if

$\lim_{n\to\infty}\frac{n}{m(n)}(1-p)^{\frac{\delta m(n)}{\beta\log m(n)}}=0.$

This again follows from the assumptions that $\lim_{n\to\infty}nm(n)^{-k}=0$,
since the second factor decays exponentially in $m(n)$. This concludes the
proof. ∎

###  4.3 The size of the giant component

So far, we have shown that with high probability there exists a large
component spreading through all compartments. It remains to show that there is
only one such component, and that its size is asymptotically $(1-\rho)n$,
where $\rho$ is the extinction probability of the Galton-Watson tree as
explained in Remark 2.3.

From Proposition 4.3 we obtain the following identification of the largest
component in the compartment model $G_{n}$. Note that this also proves the
final statement of Theorem 2.2.

######  Proposition 4.9.

Let the assumptions of Theorem 2.2 be satisfied. Then with high probability
the largest component in $G_{n}$ is equal to

$\\{x||C_{x}|\geq\beta\log m(n)\\},$

where $C_{x}$ denotes the component of $G_{n}$ containing $x$.

###### Proof.

By Proposition 4.8 we know that $C\subset\\{x||C_{x}|\geq\beta\log m(n)\\}$
with high probability. The claim now follows once we show that

$\mathbb{P}\left(\\{x||C_{x}|\geq\beta\log m(n)\\}\subset C\right)$

goes to 1. For this, it suffices to prove that

$\mathbb{P}(|C_{x}|\geq\beta\log m(n)\mbox{ and }x\notin C\mbox{ for some }x)$

goes to 0. Note that there are at most $\frac{n}{\beta\log m(n)}$ components
of size larger than $\beta\log m(n)$. Therefore, the above probability is
bounded above by

$\frac{n}{\beta\log m(n)}\mathbb{P}\left(|\tilde{C}|\geq\beta\log m(n)\mbox{
and }\tilde{C}\cap C=\emptyset\right).$

By conditioning we have

$\displaystyle\mathbb{P}\left(|\tilde{C}|\geq\beta\log m(n)\mbox{ and
}\tilde{C}\cap C=\emptyset\right)$
$\displaystyle\leq\mathbb{P}\left(|\tilde{C}|<m(n)^{\frac{2}{3}}\middle||\tilde{C}|\geq\beta\log
m(n)\right)+\mathbb{P}\left(\tilde{C}\cap C=\emptyset\middle||\tilde{C}|\geq
m(n)^{\frac{2}{3}}\right).$

From Proposition 4.3 it follows that

$\mathbb{P}\left(|\tilde{C}|<m(n)^{\frac{2}{3}}\middle||\tilde{C}|\geq\beta\log
m(n)\right)\leq m(n)^{-k}.$

Furthermore, an argument similar to the proof of Lemma 4.7 gives us that

$\mathbb{P}\left(\tilde{C}\cap C=\emptyset\middle||\tilde{C}|\geq
m(n)^{\frac{2}{3}}\right)\leq\exp\left(-Cm(n)^{\frac{1}{3}-\tau}\right).$

Here we used that the component $C$ contains at least $\varepsilon
m(n)^{\frac{2}{3}-\tau}$ vertices from each compartment.

Since by assumption $\lim_{n\to\infty}nm(n)^{-k}=0$, it follows that

$\lim_{n\to\infty}\frac{n}{\beta\log
m(n)}\left(m(n)^{-k}+\exp\left(-Cm(n)^{\frac{1}{3}-\tau}\right)\right)=0$

as long as we take $\tau<\frac{1}{3}$. This completes the proof. ∎

From Proposition 4.9 it follows that we are done once we show that

$\frac{1}{n}\left|\\{x||C_{x}|\geq\beta\log m(n)\\}\right|\to 1-\rho$

in probability, where $\rho$ is as in Remark 2.3. For this, we first prove the
following result.

######  Proposition 4.10.

Let the assumptions of Theorem 2.2 be satisfied. Let $\rho$ be as in Remark
2.3 and let $C$ be a component of $G_{n}$. Then

$\lim_{n\to\infty}\mathbb{P}(|C|\leq\beta\log m(n))=\rho.$ (4.2)

###### Proof.

Define $Z_{t}$ by

$Z_{t}=Z_{0}+\sum_{i=1}^{t}X_{i}$

where $Z_{0}$ has distribution $D$ and $X_{1},\ldots,X_{t}$ are i.i.d. with
distribution $Z_{D}$ as in Remark 2.3. Furthermore, define
$S_{t}=\sum_{i=0}^{t}Z_{i}$. Suppose we explore the component $C$ using the
exploration process $(R_{t},A_{t},U_{t})$, where we do not track to which
compartment the vertices belong. Since during the exploration we might have
collisions, we find that $|A_{t}|\leq Z_{t}$ and $|R_{t}|\leq S_{t}$. Define

$\tau:=\inf\\{t|A_{t}=\emptyset\\}$

and

$T:=\inf\\{t|Z_{t}=0\\}.$

Since $|A_{t}|\leq Z_{t}$ we have $\tau\leq T$. Furthermore, note that
$\mathbb{P}(|C|\leq\beta\log m(n))=\mathbb{P}(|R_{\tau}|\leq\beta\log m(n))$.
Because $|R_{t}|\leq S_{t}$, it follows that

$\mathbb{P}(|R_{\tau}|\leq\beta\log m(n))\geq\mathbb{P}(S_{T}\leq\beta\log
m(n)).$

It holds that

$\lim_{n\to\infty}\mathbb{P}(S_{T}\leq\beta\log
m(n))=\mathbb{P}(T<\infty)=\rho.$

Indeed, since $S_{t}$ increases by at least 1 in every step, we have

$\mathbb{P}(S_{T}\leq\beta\log m(n))\leq\mathbb{P}(T\leq\beta\log
m(n))\to\rho.$

On the other hand, note that

$\displaystyle\mathbb{P}(S_{T}\leq\beta\log m(n))$
$\displaystyle\geq\mathbb{P}(S_{T}\leq\beta\log m(n)|T\leq\tilde{\beta}\log
m(n))\mathbb{P}(T\leq\tilde{\beta}\log m(n))$
$\displaystyle=(1-o(1))\mathbb{P}(T\leq\tilde{\beta}\log m(n))$
$\displaystyle\to\rho$

provided $\tilde{\beta}$ is small enough. This can for example be proven using
Chernoff’s bound.

We conclude that

$\liminf_{n\to\infty}\mathbb{P}(|R_{\tau}|\leq\beta\log m(n))\geq\rho.$ (4.3)

For the reverse inequality, we write

$\displaystyle\mathbb{P}(S_{T}>\beta\log m(n))$
$\displaystyle=\mathbb{P}(S_{T}>\beta\log m(n),S_{t}=|R_{t}|\mbox{ for all
}t\leq\beta\log m(n))$ $\displaystyle\qquad+\mathbb{P}(S_{T}>\beta\log
m(n),S_{t}>|R_{t}|\mbox{ for some }t\leq\beta\log m(n)).$

Note that

$\mathbb{P}(S_{T}>\beta\log m(n),S_{t}=|R_{t}|\mbox{ for all }t\leq\beta\log
m(n))\leq\mathbb{P}(|R_{\tau}|>\beta\log m(n)).$

We will show that the second term vanishes. For this, observe that it suffices
to prove that the probability of a collision before $\beta\log m(n)$ vertices
are exposed vanishes. For this, observe that if we explore half-edge
$t\leq\beta\log m(n)$, then there are at most $\beta\log m(n)$ vertices it can
attach to to form a collision. Since the degree sequence converges, there
exists a constant $C>0$ such that with high probability there are at most
$C\log m(n)$ half-edges that lead to a collision. For the same reason, there
are at least $cm(n)$ half-edges to choose from in total. Therefore, the
probability of causing a collision when exploring half-edge $t$ is at most
$\tilde{C}\frac{\log m(n)}{m(n)}$. It follows that the probability of a
collision in the first $\beta\log m(n)$ exploration steps is of order
$\frac{(\log m(n))^{2}}{m(n)}$, which tends to 0.

Collecting everything, we find that

$\mathbb{P}(S_{T}>\beta\log m(n))\leq\mathbb{P}(|R_{\tau}|>\beta\log
m(n))+o(1),$

from which it follows that

$\mathbb{P}(|R_{\tau}|\leq\beta\log m(n))\leq\mathbb{P}(S_{T}\leq\beta\log
m(n))+o(1).$

From this we conclude that

$\limsup_{n\to\infty}\mathbb{P}(|R_{\tau}|\leq\beta\log
m(n))\leq\lim_{n\to\infty}\mathbb{P}(S_{T}\leq\beta\log m(n))=\rho.$

Together with the inequality in (4.3) this completes the proof. ∎

###  4.4 Proof of Theorem 2.2

With all preparations done, we are finally ready to prove Theorem 2.2.

###### Proof of Theorem 2.2.

From Proposition 4.9 it follows that we are done once we show that

$\lim_{n\to\infty}\frac{1}{n}|\\{x||C_{x}|\geq\beta\log m(n)\\}|=1-\rho$

in probability.

To this end, define for $x\in V_{n}$ the random variables $Y_{x}^{n}$, where
$Y_{x}^{n}=1$ if $|C_{x}|\leq\beta\log m(n)$ and 0 otherwise. Then

$|\\{x||C_{x}|\leq\beta\log m(n)\\}|=\sum_{x=1}^{k(n)^{d}m(n)}Y_{x}.$

Note that by (4.2) we have

$\lim_{n\to\infty}\mathbb{E}(Y_{x}^{n})=\lim_{n\to\infty}\mathbb{P}(|C_{x}|\leq\beta\log
m(n))=\rho.$

Therefore, we find that

$\lim_{n\to\infty}\mathbb{P}\left(\left|\frac{1}{n}|\\{x||C_{x}|\geq\beta\log
m(n)\\}|-\rho\right|>\varepsilon\right)\\\
=\lim_{n\to\infty}\mathbb{P}\left(\left|\sum_{x=1}^{k(n)^{d}m(n)}Y_{x}-k(n)^{d}m(n)\rho\right|\geq
n\varepsilon\right).$ (4.4)

By Chebyshev’s inequality, we have

$\mathbb{P}\left(\left|\sum_{x=1}^{k(n)^{d}m(n)}Y_{x}-k(n)^{d}m(n)\rho\right|\geq
n\varepsilon\right)\leq\frac{\mathrm{Var}\left(\sum_{x=1}^{k(n)^{d}m(n)}Y_{x}\right)}{\varepsilon^{2}n^{2}}.$

Note that

$\mathrm{Var}\left(\sum_{x=1}^{k(n)^{d}m(n)}Y_{x}\right)\\\ \leq
k(n)^{d}m(n)+\sum_{x\neq y}\mathrm{Cov}(Y_{x},Y_{y})\leq
k(n)^{d}m(n)+k(n)^{2d}m(n)^{2}\mathrm{Cov}(Y_{1},Y_{2}).$ (4.5)

We can compute

$\mathrm{Cov}(Y_{1},Y_{2})=\mathbb{P}(Y_{1}=1,Y_{2}=1)-\mathbb{P}(Y_{1}=1)\mathbb{P}(Y_{2}=1).$

To estimate this, we consider two independent exploration processes starting
at vertex 1 and 2 where we couple them once they meet. Following a reasoning
similar to [Dur07, Lemma 2.3.4], we find that

$\mathrm{Cov}(Y_{1},Y_{2})\leq\frac{C(\beta\log m(n))^{2}}{m(n)}$

for some $C>0$.

Altogether, we obtain

$\mathrm{Var}\left(\sum_{x=1}^{k(n)m(n)}Y_{x}\right)\leq Ck(n)^{2d}m(n)(\log
m(n))^{2}$

for some (possibly different) constant $C>0$. Plugging this into the equation
above and using that $\lim_{n\to\infty}\frac{k(n)^{d}m(n)}{n}=1$ and
$\lim_{n\to\infty}m(n)=\infty$, we find that

$\lim_{n\to\infty}\mathbb{P}\left(\left|\sum_{x=1}^{k(n)^{d}m(n)}Y_{x}-k(n)^{d}m(n)\rho\right|\geq
n\varepsilon\right)=0.$

Putting everything together, we obtain

$\frac{1}{n}|\\{x||C_{x}|\leq\beta\log m(n)\\}|\to\rho$

in probability, which implies that

$\frac{1}{n}|\\{x||C_{x}|\geq\beta\log m(n)\\}|\to 1-\rho$

in probability as desired. ∎

##  5 Difference with standard configuration model

We conclude by considering an example to see the difference between the
compartment model on torus and the standard configuration model. This example
also shows that some condition on the number of vertices $m(n)$ per
compartment is necessary when we want to keep the conditions on the degree
sequence in line with the standard configuration model.

For our example, let $D$ be random variable taking values in the non-negative
integers. Assume that $\mathbb{P}(D\leq 1)=p>0$ and $\mathbb{E}(D(D-2))>0$.
Let $d_{n}$ be a degree sequence on $n$ vertices converging to $D$ in the
sense of Assumption 2.1 (without the compartments). Let $G(d_{n})$ be the
random graph obtain from the standard configuration model on $n$ vertices with
degree sequence $d_{n}$. Then (see e.g. [BR15])

$\lim_{n\to\infty}\frac{L_{1}(G(d_{n}))}{n}=1-\rho$

in probability, where $\rho$ is the extinction probability of the Galton-
Watson tree associated to $D$ as in Remark 2.3. In particular, because
$\mathbb{E}(D(D-2))>0$ it holds that $\rho<1$. We thus see that with high
probability the graph $G(d_{n})$ contains a giant component.

We will now prove that under the same conditions, the compartment model on the
torus does not contain a giant component with high probability if we assume
the compartment contain a fixed number of vertices. This is caused only by the
assumption that $\mathbb{P}(D\leq 1)>0$. The result below considers the circle
($d=1$). Afterwards, we will remark how this may be extended to higher
dimensions.

######  Proposition 5.1.

Let $D$ be a random variable taking values in the non-negative integers such
that $\mathbb{P}(D\leq 1)=p>0$. Let $d_{n}$ be a degree sequence sampled
independently and uniformly from $D$. Let $G_{n}$ be the compartment model on
the circle (i.e. $d=1$) with degree sequence $d_{n}$ and assume that
$m(n)=\lambda\geq 1$ for all $n$. Then

$\lim_{n\to\infty}\frac{L_{1}(G_{n})}{n}=0$

in probability.

###### Proof.

Observe that if all vertices in a compartment have degree 0 or 1, then no
component can cross this compartment. As a consequence, the size of components
is bounded by the maximum distance between such compartments multiplied by
$\lambda$.

Note that with probability $p^{\lambda}$ a compartment contains only degree 0
or 1 vertices. Since for different compartments these events are independent,
the distance between such compartments is geometrically distributed with
parameter $p^{\lambda}$. Moreover, since $\lambda\geq 1$, we have at most $n$
such intervals.

Let $X_{1},\ldots,X_{n}$ be independent random variables with a geometric
distribution with parameter $p^{\lambda}$. By the above, it follows that the
size of the largest component is bounded by $\max_{i=1}^{n}X_{i}$.

Now let $\varepsilon>0$. Then

$\mathbb{P}\left(\max_{i=1}^{n}X_{i}\leq\varepsilon
n\right)=\prod_{i=1}^{n}\mathbb{P}(X_{i}\leq\varepsilon
n)=\left(1-(1-p^{\lambda})^{\varepsilon n}\right)^{n}$

Now,

$\lim_{n\to\infty}\left(1-(1-p^{\lambda})^{\varepsilon n}\right)^{n}=1.$

To see this, note that

$\log\left(\left(1-(1-p^{\lambda})^{\varepsilon
n}\right)^{n}\right)=n\log\left(1-(1-p^{\lambda})^{\varepsilon
n}\right)\approx n(1-p^{\lambda})^{\varepsilon n},$

which goes to 0 since $0<(1-p^{\lambda})^{\varepsilon}<1$.

Using the above, we find that

$\lim_{n\to\infty}\mathbb{P}\left(\max_{i=1}^{n}X_{i}\leq\varepsilon
n\right)=1$

Collecting everything, it follows that

$\displaystyle\lim_{n\to\infty}\mathbb{P}\left(\frac{L_{1}(G_{n})}{n}>\varepsilon\right)$
$\displaystyle\leq\lim_{n\to\infty}\mathbb{P}\left(\max_{i=1}^{n}X_{i}>n\varepsilon\lambda^{-1}\right)$
$\displaystyle=1-\lim_{n\to\infty}\mathbb{P}\left(\max_{i=1}^{n}X_{i}\leq
n\varepsilon\lambda^{-1}\right)$ $\displaystyle=0.$

We conclude that

$\lim_{n\to\infty}\frac{L_{1}(G_{n})}{n}=0$

in probability. ∎

The result of Proposition 5.1 remains true in higher dimensions, at least
under the additional assumption that $p^{\lambda}$ (i.e., the probability of a
compartment with only vertices of degree at most 1) is sufficiently large. The
reasoning makes use of the phase transition in site-percolation on the lattice
$(\mathbb{Z}/k(n)\mathbb{Z})^{d}$. Indeed, the vertices in
$(\mathbb{Z}/k(n)\mathbb{Z})^{d}$ represent compartments. Since components in
the compartment model cannot cross compartments with only degree 1 vertices,
they are restricted to compartments that form components in
$(\mathbb{Z}/k(n)\mathbb{Z})^{d}$ after removing sites with probability
$p^{\lambda}$. If this is sufficiently large, then only components of size
$\log(k(n))$ remain with high probability. In that case, the components in the
compartment model have at most size $m(n)\log(k(n))$, which is $o(n)$. Hence,
if $p^{\lambda}$ is large enough, the associated compartment model on the
torus does not have a giant component.

######  Remark 5.2.

The result in Proposition 5.1 can actually be extended to slightly larger
compartment sizes (as long as $d=1$). Indeed, the same reasoning also works
when $m(n)=\lambda\log n$ as long as $\lambda<-\frac{1}{\log p}$. This proves
that at least for some degree distributions $D$ (and for $d=1$) it is actually
necessary for $m(n)$ to tend to infinity in order to see a giant component.
This also underpins the idea that there is an interplay between the
assumptions on the degree sequence and compartment for the emergence of a
giant component.

Remark 5.2 suggest that there is a phase transition in the behaviour of the
giant component in the compartment model on a circle depending on the size of
the compartments. In particular, we have the following conjecture.

######  Conjecture 5.3.

Let $D$ be a random variable taking values in the non-negative integers such
that $\mathbb{P}(D\leq 1)=p>0$. Let $d_{n}$ be a degree sequence sampled
independently and uniformly from $D$. Let $G_{n}$ be the compartment model on
the circle (i.e. $d=1$) with degree sequence $d_{n}$ and assume that
$m(n)=\lambda\log n$ for all $n$. Then there exists a critical value
$\lambda^{*}$ at which a phase transition occurs in the existence of a giant
component in graph $G_{n}$.

It should be noted that Conjecture 5.3 will likely not hold for general degree
distributions, and relies on the assumption that $\mathbb{P}(D\leq 1)>0$. As
mentioned in Remark 5.2, we expect that there is intricate interplay between
assumptions on the degree sequence and compartment size in order to see a
giant component. Therefore, any potential critical size of $m(n)$ is likely to
rely on properties of the degree distribution $D$.

######  Remark 5.4 (Percolation).

As a consequence of the results in this section, we find that percolation for
the compartment model on the circle with fixed size compartments looks very
unusual. Indeed, if we independently keep edges with probability $p<1$, then
the probability that a vertex in the resulting graph has degree at most 1 is
greater than 0. The argument above then shows that this graph does not have a
giant component. Therefore, the percolation threshold is $p^{*}=1$.

##  Appendix A Appendix: Concentration inequalities

In this appendix we obtain the vector-valued extension of the classical result
on concentration inequalities by McDiarmid. This is a special case of the
results in [Kat+21]. Since we do not need such generality, we state
McDiarmid’s theorem ([McD+89]) for completeness and derive the vector-valued
extension from this.

######  Theorem A.1.

Let $f:\mathbb{R}^{n}\to\mathbb{R}$ be a function and $X_{1},\ldots,X_{n}$
independent real-valued random variables. Let $c_{1},\ldots,c_{n}$ be
constants such that

$\sup_{x_{1},\ldots,x_{i},x_{i}^{\prime},\ldots,x_{n}}f(x_{1},\ldots,x_{i},\ldots,x_{n})-f(x_{1},\ldots,x_{i}^{\prime},\ldots,x_{n})\leq
c_{i}.$

Then for every $\varepsilon>0$ we have

$\mathbb{P}(|f(X_{1},\ldots,X_{n})-\mathbb{E}(f(X_{1},\ldots,X_{n}))|\geq\varepsilon)\leq
2\exp\left(-\frac{\varepsilon^{2}}{2\sum_{i=1}^{n}c_{i}^{2}}\right).$

We will prove a similar estimate when $F$ is vector-valued. For
$x\in\mathbb{R}^{d}$ we denote by $||x||_{\infty}$ the sup-norm of $x$, i.e.,

$||x||_{\infty}=\max_{i=1,\ldots,n}|x_{i}|.$

We obtain the following extension of McDiarmid’s theorem.

######  Theorem A.2.

Let $F:\mathbb{R}^{n}\to\mathbb{R}^{d}$ be a function and $X_{1},\ldots,X_{n}$
independent, real-valued random variables. Let $c_{1},\ldots,c_{n}$ be
constants such that

$\sup_{x_{1},\ldots,x_{i},x_{i}^{\prime},\ldots,x_{n}}||F(x_{1},\ldots,x_{i},\ldots,x_{n})-F(x_{1},\ldots,x_{i}^{\prime},\ldots,x_{n})||_{\infty}\leq
c_{i}.$

Then for every $\varepsilon>0$ we have

$\mathbb{P}(||F(X_{1},\ldots,X_{n})-\mathbb{E}(F(X_{1},\ldots,X_{n}))||_{\infty}\geq\varepsilon)\leq
2d\exp\left(-\frac{\varepsilon^{2}}{2\sum_{i=1}^{n}c_{i}^{2}}\right).$

###### Proof.

For every $j=1,\ldots,d$ we can apply Theorem A.1 to
$F_{j}:\mathbb{R}^{n}\to\mathbb{R}$, the $j$-th component of $F$. This gives
us that

$\mathbb{P}(|F_{j}(X_{1},\ldots,X_{n})-\mathbb{E}(F_{j}(X_{1},\ldots,X_{n}))|\geq\varepsilon)\leq
2\exp\left(-\frac{\varepsilon^{2}}{2\sum_{i=1}^{n}c_{i}^{2}}\right).$

We can now estimate

$\displaystyle\mathbb{P}(||F(X_{1},\ldots,X_{n})-\mathbb{E}(F(X_{1},\ldots,X_{n}))||_{\infty}\geq\varepsilon)$
$\displaystyle=\mathbb{P}\left(|F_{j}(X_{1},\ldots,X_{n})-\mathbb{E}(F_{j}(X_{1},\ldots,X_{n}))|\geq\varepsilon\mbox{
for some }j=1,\ldots,d\right)$
$\displaystyle\leq\sum_{j=1}^{d}\mathbb{P}(|F_{j}(X_{1},\ldots,X_{n})-\mathbb{E}(F_{j}(X_{1},\ldots,X_{n}))|\geq\varepsilon)$
$\displaystyle\leq
2d\exp\left(-\frac{\varepsilon^{2}}{2\sum_{i=1}^{n}c_{i}^{2}}\right),$

which completes the proof. ∎

Acknowledgement This research was sponsored by the Army Research Office and
was accomplished under Cooperative Agreement Number W911NF-20-2-0187.

## References

  * [AL06] Krishna B. Athreya and Soumendra N. Lahiri  “Measure theory and probability theory”, Springer Texts in Statistics  Springer, New York, 2006
  * [AN72] Krishna B. Athreya and Peter E. Ney  “Branching processes”, Die Grundlehren der mathematischen Wissenschaften, Band 196  Springer-Verlag, New York-Heidelberg, 1972
  * [Ath94] K. B. Athreya  “Large deviation rates for branching processes. I. Single type case”  In _Ann. Appl. Probab._ 4.3, 1994, pp. 779–790
  * [BR01] Andrew D Barbour and Gesine Reinert  “Small worlds”  In _Random Structures & Algorithms_ 19.1 Wiley Online Library, 2001, pp. 54–74
  * [BR15] Béla Bollobás and Oliver Riordan  “An old approach to the giant component problem”  In _J. Combin. Theory Ser. B_ 113, 2015, pp. 236–260  DOI: 10.1016/j.jctb.2015.03.002
  * [Dur07] Rick Durrett  “Random graph dynamics” 20, Cambridge Series in Statistical and Probabilistic Mathematics  Cambridge University Press, Cambridge, 2007
  * [Ess66] C. G. Esseen  “On the Kolmogorov-Rogozin inequality for the concentration function”  In _Z. Wahrscheinlichkeitstheorie und Verw. Gebiete_ 5, 1966, pp. 210–216
  * [Har63] Theodore E. Harris  “The theory of branching processes”, Die Grundlehren der mathematischen Wissenschaften, Band 119  Springer-Verlag, Berlin; Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963, pp. xiv+230
  * [HLN13] S. Hautphenne, G. Latouche and G. Nguyen  “Extinction probabilities of branching processes with countably infinitely many types”  In _Adv. in Appl. Probab._ 45.4, 2013, pp. 1068–1082
  * [Hof17] Remco Hofstad  “Random graphs and complex networks. Vol. 1”, Cambridge Series in Statistical and Probabilistic Mathematics, [43]  Cambridge University Press, Cambridge, 2017, pp. xvi+321  DOI: 10.1017/9781316779422
  * [JL09] Svante Janson and Malwina J. Luczak  “A new approach to the giant component problem”  In _Random Structures Algorithms_ 34.2, 2009, pp. 197–216
  * [Kat+21] Dimitrios Katselis, Xiaotian Xie, Carolyn L. Beck and R. Srikant  “On concentration inequalities for vector-valued Lipschitz functions”  In _Statist. Probab. Lett._ 173, 2021, pp. Paper No. 109071, 6  DOI: 10.1016/j.spl.2021.109071
  * [Kol58] André Kolmogorov  “Sur les propriétés des fonctions de concentrations de M. P. Lévy”  In _Annales de l’institut Henri Poincaré_ 16.1 INSTITUT HENRI POINCARÉ ET GAUTHIER-VILLARS, 1958, pp. 27–34
  * [McD+89] Colin McDiarmid  “On the method of bounded differences”  In _Surveys in combinatorics_ 141.1 Norwich, 1989, pp. 148–188
  * [Moy64] J. E. Moyal  “Multiplicative population proceses”  In _J. Appl. Probability_ 1, 1964, pp. 267–283
  * [MR98] Michael Molloy and Bruce Reed  “The size of the giant component of a random graph with a given degree sequence”  In _Combin. Probab. Comput._ 7.3, 1998, pp. 295–305
  * [Pen03] Mathew Penrose  “Random geometric graphs” 5, Oxford Studies in Probability  Oxford University Press, Oxford, 2003, pp. xiv+330  DOI: 10.1093/acprof:oso/9780198506263.001.0001
  * [Rog61] B. A. Rogozin  “An Estimate for Concentration Functions”  In _Theory of Probability & Its Applications_ 6.1, 1961, pp. 94–97
  * [Siv14] David Sivakoff  “Site percolation on the $d$-dimensional Hamming torus”  In _Combin. Probab. Comput._ 23.2, 2014, pp. 290–315  DOI: 10.1017/S096354831300059X
  * [WS98] Duncan J Watts and Steven H Strogatz  “Collective dynamics of ‘small-world’networks”  In _nature_ 393.6684 Nature Publishing Group, 1998, pp. 440–442