# Bootstrap percolation on the high-dimensional Hamming graph

Mihyun Kang, Michael Missethan, Dominik Schmid  Institute of Discrete
Mathematics, Graz University of Technology, Steyrergasse 30, 8010 Graz,
Austria<EMAIL_ADDRESS>
###### Abstract.

In the random $r$-neighbour bootstrap percolation process on a graph $G$, a
set of initially infected vertices is chosen at random by retaining each
vertex of $G$ independently with probability $p\in(0,1)$, and ‘healthy’
vertices get infected in subsequent rounds if they have at least $r$ infected
neighbours. A graph $G$ _percolates_ if every vertex becomes eventually
infected. A central problem in this process is to determine the critical
probability $p_{c}(G,r)$, at which the probability that $G$ percolates passes
through one half. In this paper, we study random $2$-neighbour bootstrap
percolation on the $n$-dimensional Hamming graph $\square_{i=1}^{n}K_{k}$,
which is the graph obtained by taking the Cartesian product of $n$ copies of
the complete graph $K_{k}$ on $k$ vertices. We extend a result of Balogh and
Bollobás [Bootstrap percolation on the hypercube, Probab. Theory Related
Fields. 134 (2006), no. 4, 624–648. MR2214907] about the asymptotic value of
the critical probability $p_{c}(Q^{n},2)$ for random $2$-neighbour bootstrap
percolation on the $n$-dimensional hypercube $Q^{n}=\square_{i=1}^{n}K_{2}$ to
the $n$-dimensional Hamming graph $\square_{i=1}^{n}K_{k}$, determining the
asymptotic value of $p_{c}\left(\square_{i=1}^{n}K_{k},2\right)$, up to
multiplicative constants (when $n\rightarrow\infty$), for arbitrary
$k\in\mathbb{N}$ satisfying $2\leq k\leq 2^{\sqrt{n}}$.

##  1\. Introduction and results

###  1.1. Motivation

Bootstrap percolation was introduced in 1979 by Chalupa, Leath, and Reich [19]
in the context of magnetic systems. Since then it has found many applications
ranging from studying the spread of information through social networks [31]
to modelling collective behaviour [22]. For a survey of applications in
physical science we refer the readers to [1].

Consider the $r$-neighbour bootstrap percolation process described as follows.
Given a graph $G$, a set $A_{0}\subseteq V(G)$ of _initially infected_
vertices and the so-called _infection parameter_ $r\in\mathbb{N}$, a _healthy_
vertex gets infected if it has at least $r$ infected neighbours. Once a vertex
has been infected, it remains in this state forever. The process ends if
either all vertices have been infected or all healthy vertices have less than
$r$ infected neighbours. The set of infected vertices can be thought of
growing in rounds: In each round $j\in\mathbb{N}$, we move all healthy
vertices to the set $A_{j}$ that have at least $r$ neighbours in $A_{j-1}$,
i.e., we let

$\displaystyle A_{j}:=A_{j-1}\cup\left\\{v\in V(G)\mid\left|N(v)\cap
A_{j-1}\right|\geq r\right\\}.$ (1.1)

Note that the percolation process stops (or stabilises) as soon as
$A_{j}=A_{j-1}$ for some $j\in\mathbb{N}$. We set

$\displaystyle\left[{A}\right]\coloneqq\bigcup_{j\in\mathbb{N}\cup\\{0\\}}A_{j}.$

If $\left[{A}\right]=V(G)$, we say $A$ _spans_ $G$; or equivalently $G$
_percolates_ ; or equivalently $A$ is a percolating set.

Choosing the set of initially infected vertices deterministically leads to
interesting extremal questions, e.g., finding a smallest percolating set [11,
12, 21, 32, 34] or determining the longest time a graph can take to percolate
[13, 26, 33]. Yet, the probably most-studied case is when the set of initially
infected vertices is chosen randomly in such a way that each vertex is
initially infected with probability $p\in(0,1)$ independently of the other
vertices. A typical question in this context is above which _critical
probability_ $p_{c}$ a graph $G$ is likely to percolate. More formally, in so-
called _random_ $r$-neighbour bootstrap percolation on a graph $G$, the set of
initially infected vertices is a $p$-_random_ subset $\boldsymbol{A}_{p}$ of
$V(G)$, which is obtained by retaining each vertex in $V(G)$ independently
with probability $p$. We define the _critical probability_ as

$\displaystyle
p_{c}(G,r)\coloneqq\inf\left\\{p\in(0,1)\mid\mathbb{P}\left[\boldsymbol{A}_{p}\text{
spans }G\right]\geq 1/2\right\\}.$

We aim to determine the asymptotic value of the critical probability or to
bound the width of the ‘critical window’ where the probability that $G$
percolates changes from tending to zero to tending to one as $n$ tends to
infinity. One of the first results on random $r$-neighbour bootstrap
percolation was obtained by Schonmann [36], who showed that
$p_{c}\left(\mathbb{Z}^{d},r\right)=0$ if $r\leq d$ and
$p_{c}\left(\mathbb{Z}^{d},r\right)=1$ otherwise. Aizenmann and Lebowitz[2]
determined $p_{c}\left([n]^{d},2\right)$ up to a constant factor. In
subsequent papers, the percolation threshold on $[n]^{d}$ was extended to
different sets of parameters $r,d$ and improved to a sharp threshold [6, 7, 8,
18, 17, 28]. Random $r$-neighbour bootstrap percolation was also studied for
other base graphs, e.g., the infinite lattice [24, 27, 28, 36], the binomial
random graph $G(n,p)$[4, 29, 30, 35], or various types of trees [10, 14, 15,
16, 25, 37].

In this paper, we consider _random_ $2$-neighbour bootstrap percolation on the
high-dimensional Hamming graph. For each $n,k\in\mathbb{N}$ with $k\geq 2$ let
$\square_{i=1}^{n}K_{k}$ denote the $n$-dimensional Hamming graph which is
obtained by taking the $n$-fold Cartesian product of the complete graph
$K_{k}$ – the formal definition of the Cartesian product of graphs can be
found in Definition 2.1. Note that the special case $k=2$ yields the well-
studied $n$-dimensional hypercube
$Q^{n}=\\{0,1\\}^{n}=\mathbb{Z}_{2}^{n}=[2]^{n}$, in other words,
$Q^{n}=\square_{i=1}^{n}K_{2}$. When the dimension $n$ is _constant_ and the
size $k$ of the base graph $K_{k}$ tends to infinity, random $r$-neighbour
bootstrap percolation on $\square_{i=1}^{n}K_{k}$ is well studied, e.g., by
Gravner, Hoffman, Pfeiffer, and Sivakoff [23]and by Slivken [38]. However, the
case when $n$ tends to infinity and $k\geq 2$ is arbitrary is relatively
unknown except for the special case $k=2$. Regarding random $2$-neighbour
bootstrap percolation on $Q^{n}=\square_{i=1}^{n}K_{2}$, Balogh and
Bollobás[5] determined the asymptotic value of the critical probability up to
multiplicative constants:

$\displaystyle
p_{c}\left(Q^{n},2\right)=\Theta\left(n^{-2}2^{-2\sqrt{n}}\right).$ (1.2)

In this paper we generalise the result (1.2) of Balogh and Bollobás[5] to the
$n$-dimensional Hamming graph $\square_{i=1}^{n}K_{k}$ when $n$ tends to
infinity 111Throughout the paper, all asymptotics are considered as
$n\to\infty$ and we say an event $\mathcal{E}$ holds whp (with high
probability) if the probability of $\mathcal{E}$ tends to one as
$n\to\infty$.. Our results allow the size $k$ of the base graphs $K_{k}$ to be
an arbitrarily large constant and we even allow $k=k(n)$ to be a function in
$n$ that grows at most exponentially in $\sqrt{n}$.

###  1.2. Main results and key proof techniques

For $n,k\in\mathbb{N}$ with $k\geq 2$, consider _random_ $2$-neighbour
bootstrap percolation on the $n$-dimensional Hamming graph
$\square_{i=1}^{n}K_{k}$, where the set of initially infected vertices is a
$p$-random subset $\boldsymbol{A}_{p}$ of
$V\left(\square_{i=1}^{n}K_{k}\right)$, meaning
$\mathbb{P}\left[v\in\boldsymbol{A}_{p}\right]=p\in(0,1)$ independently for
each vertex $v\in V\left(\square_{i=1}^{n}K_{k}\right)$. Set
$A_{0}:=\boldsymbol{A}_{p}$ and for each $j\in\mathbb{N}$ let

$\displaystyle A_{j}\coloneqq A_{j-1}\cup\left\\{v\in
V\left(\square_{i=1}^{n}K_{k}\right)\mid\left|N(v)\cap A_{j-1}\right|\geq
2\right\\}\quad\text{ and
}\quad\left[{\boldsymbol{A}_{p}}\right]:=\bigcup_{j\in\mathbb{N}\cup\left\\{0\right\\}}A_{j}.$

Our main result is that for any $2\leq k\leq 2^{\sqrt{n}}$ the critical
probability satisfies

$p_{c}\left(\square_{i=1}^{n}K_{k},2\right)=\Theta\left(n^{-2}k^{-2\sqrt{n}+1}\right),$

which recovers (1.2) of Balogh and Bollobás [5] by taking $k=2$. More
precisely, we determine for which $p$ does $\square_{i=1}^{n}K_{k}$ percolate,
i.e., $\left[{\boldsymbol{A}_{p}}\right]=V\left(\square_{i=1}^{n}K_{k}\right)$
and for which $p$ it does not, i.e.,
$V\left(\square_{i=1}^{n}K_{k}\right)\setminus\left[{\boldsymbol{A}_{p}}\right]\neq\emptyset.$

######  Theorem 1.1.

Let $n,k\in\mathbb{N}$ satisfy $2\leq k\leq 2^{\sqrt{n}}$. Consider random
$2$-neighbour bootstrap percolation on the $n$-dimensional Hamming graph
$G=\square_{i=1}^{n}K_{k}$ in which the set of initially infected vertices is
a $p$-random subset $\boldsymbol{A}_{p}$ of $V(G)$. Set
$p_{*}:=n^{-2}k^{-2\sqrt{n}+1}$ and $p^{*}:=200n^{-2}k^{-2\sqrt{n}+1}$. Then
the following hold.

  1. (a)

If $p\leq p_{*}$, then whp $G$ does not percolate.

  2. (b)

If $p\geq p^{*}$, then whp $G$ percolates.

Note that Theorem 1.1 implies

$\displaystyle n^{-2}k^{-2\sqrt{n}+1}\leq
p_{c}\left(\square_{i=1}^{n}K_{k},2\right)\leq 200n^{-2}k^{-2\sqrt{n}+1}$

and determines a threshold for the property that $G$ percolates, up to
multiplicative constant factors. Regarding the case $k=2$, improving upon
(1.2) Balogh, Bollobás and Morris[7] determined a sharp threshold (and more):

$\displaystyle\frac{16\lambda}{n^{2}}\left(1+\frac{\log
n}{\sqrt{n}}\right)2^{-2\sqrt{n}}\leq
p_{c}(Q^{n},2)\leq\frac{16\lambda}{n^{2}}\left(1+\frac{5\log^{2}n}{\sqrt{n}}\right)2^{-2\sqrt{n}},$
(1.3)

where $\lambda\approx 1.166$. Although the constants in 1.1 could be improved
(especially for $p^{*}$), different techniques are needed to improve our
result to a sharp threshold. Furthermore, note that the restriction $k\leq
2^{\sqrt{n}}$ on the size of the base graphs $K_{k}$ is due to technical
reasons in the proof of Section LABEL:*thm:main:threshold (a) and we did not
try to optimise this restriction, although the result might still hold for $k$
growing arbitrarily fast in $n$.

The advantages of our proof techniques lie in their universality and
applicability to more general classes of high-dimensional product graphs. Two
key concepts in the standard analysis of bootstrap percolation on high-
dimensional graphs are internally spanned projections and a critical
dimension. Given a Cartesian product graph $G$, a projection of $G$ is a
subgraph of $G$ that is isomorphic to a lower-dimensional Cartesian product
graph; and a projection is internally spanned if its induced subgraph
percolates. One of the key properties of the Hamming graph is that two
projections within distance two together span another projection containing
both of them. This enables us to use ‘hierarchies’ to obtain good upper bounds
on the probability that a projection is internally spanned and to show that
the probability of $G$ percolating is bounded from above by the probability of
the appearance of an internally spanned projection of a certain _critical
dimension_. To prove Section LABEL:*thm:main:threshold (a) it then suffices to
show that for $p\leq p_{*}$ there exists no internally spanned projection of
this _critical dimension_. We note that in earlier work [5, 7] as well as in
our work the property that two projections within distance two always span a
larger projection was crucial.

To prove Section LABEL:*thm:main:threshold (b) we consider a specific type of
percolating set, called a sequentially spanning set (see Definition 2.9 for
formal definition). The importance of sequentially spanning sets is two-fold:
They are minimum percolating sets; and the majority of all minimum percolating
sets comes from sequentially spanning sets. We use the second moment method to
show the existence of a sufficiently large sequentially spanning set. In
comparison to the earlier work of Balogh and Bollobás [5] and Balogh, Bollobás
and Morris[7], we incorporate the ordering of the vertices in a sequentially
spanning set and consider a sequentially spanning sequence instead (see
Definition 4.1 for formal definition), which has certain advantages: On the
one hand, the correlation between two sequentially spanning sequences can be
computed quite explicitly, allowing for much more generous applications of the
second moment method; and on the other hand, while sequentially spanning sets
are used in literature in order to derive lower bounds on the probability that
a projection is internally spanned, the use of sequentially spanning sequences
allows us to avoid this step. The concept of sequentially spanning sequences
transfers quite naturally to other types of Cartesian product graphs, and so
we believe that our techniques will be useful for deriving similar bounds on
more general classes of product graphs.

###  1.3. Outline of the paper

In Section 2 we introduce notations and concepts needed for bootstrap
percolation on the Hamming graph. Section 3 is dedicated to the proof of
Section LABEL:*thm:main:threshold (a), and more technical proofs of auxiliary
results of Section 3 are deferred to Section 5. Similarly, we prove Section
LABEL:*thm:main:threshold (b) in Section 4 and other technical results in
Section 6. We discuss open problems and future research directions in Section
7.

##  2\. Preliminaries

In this section we first introduce necessary notations and useful known
results. We then provide some intuition on the deterministic $2$-neighbour
bootstrap percolation process on the Hamming graph and characterise
percolating or non-percolating sets. In Section 2.3, we take a closer look at
the percolation process and set up the scene for what is known as the
_hierarchy_ technique, which was introduced by Holroyd [28] and since then has
become a fundamental tool to derive lower bounds on bootstrap percolation
thresholds.

###  2.1. Notation and terminology

We define $\mathbb{N}_{0}\coloneqq\mathbb{N}\cup\left\\{0\right\\}$. Given a
set $X$ and $\ell\in\mathbb{N}$, we denote by $\binom{X}{\ell}$ the set of all
$\ell$-element subsets of $X$ and define $[\ell]:=\\{1,2,\ldots,\ell\\}$.

Given a graph $G$, the _distance_ between two different vertices in $G$,
denoted by $\operatorname{dist}\left(x,y\right)$, is defined as the length of
a shortest path between them. The distance between two sets of vertices
$A,A^{\prime}\subseteq V(G)$ is defined as the minimum distance between all
pairs of vertices from the two sets:

$\displaystyle\operatorname{dist}\left(A,A^{\prime}\right)=\operatorname{dist}\left(A^{\prime},A\right)\coloneqq\min_{u\in
A}\min_{v\in A^{\prime}}\operatorname{dist}\left(u,v\right).$

Now we define the Cartesian product of graphs and introduce important
concepts.

######  Definition 2.1.

Given graphs
$G^{(1)}=\left(V^{(1)},E^{(1)}\right),\ldots,G^{(n)}=\left(V^{(n)},E^{(n)}\right)$,
we define the Cartesian product of $G^{(1)},\ldots,G^{(n)}$, denoted by
$G=G^{(1)}\square\cdots\square G^{(n)}$ or $G=\square_{i=1}^{n}G^{(i)}$, as
the graph $G=(V,E)$ with vertex and edge set

$\displaystyle V$ $\displaystyle=V(G)=V^{(1)}\times\cdots\times
V^{(n)}:=\left\\{v=(v_{1},\ldots,v_{n})\mid\forall i\in[n]:v_{i}\in
V^{(i)}\right\\}$ $\displaystyle E$
$\displaystyle=E(G):=\left\\{\\{v,w\\}\in\binom{V}{2}\mid\exists
j\in[n]:\Big{(}\left\\{v_{j},w_{j}\right\\}\in
E^{(j)}\Big{)}\wedge\Big{(}\forall
i\in[n]\setminus\\{j\\}:v_{i}=w_{i}\Big{)}\right\\}.$

Throughout the paper we will call $G=\square_{i=1}^{n}G^{(i)}$ the product
graph instead of the Cartesian product graph, unless specified otherwise, and
the graphs $G^{(1)},\ldots,G^{(n)}$ the _base graphs_ of $G$. A base graph is
called _trivial_ , if it consists of a single vertex.

######  Definition 2.2.

Given a product graph $G=\square_{i=1}^{n}G^{(i)}$ we call a subgraph
$H\subseteq G$ a projection of $G$ if $H$ can be written as
$H=\square_{i=1}^{n}H^{(i)}$ where for each $i\in[n]$ we have either
$H^{(i)}=G^{(i)}$ or $H^{(i)}=\left\\{v_{i}\right\\}$ for some vertex
$v_{i}\in V^{(i)}$. The dimension of $H$ is defined as the number of non-
trivial base graphs $H^{(i)}$ in $H$.

In order to keep track of the dimension of a projection, we will often write
$H_{\ell}$ for a projection of dimension $\ell\in\mathbb{N}_{0}$. With slight
abuse of notation, we will sometimes view a projection not as a subgraph of
$G$, but just as a subset of $V(G)$. Similarly, when we say a subset
$U\subseteq V(G)$ is a projection, we mean that the subgraph of $G$ induced by
$U$ is a projection.

Next we introduce some necessary notations for the bootstrap percolation
process.

######  Definition 2.3.

Given a graph $G=(V,E)$ and a set $A\subseteq V$, we define the closure of
$A$, denoted by $\left[{A}\right]$, as the set of eventually infected vertices
in the $2$-neighbour bootstrap percolation process with $A$ being the set of
initially infected vertices. More formally, we define

$\displaystyle\left[{A}\right]\coloneqq\bigcup_{j\in\mathbb{N}_{0}}A_{j},$

where $A_{0}:=A$ and $A_{j}:=A_{j-1}\cup\left\\{v\in V\mid\left|N(v)\cap
A_{j-1}\right|\geq 2\right\\}$ for $j\in\mathbb{N}$. We say

  1. (1)

$A$ is closed, if $\left[{A}\right]=A$;

  2. (2)

a closed set $U\subseteq V$ is called internally spanned by $A$, if
$U=\left[{A\cap U}\right]$.

The collection of all closed subsets of $V$ that are internally spanned by $A$
is denoted by

$\displaystyle\mathcal{H}_{A}\coloneqq\left\\{U\subseteq V\mid U=\left[{A\cap
U}\right]\right\\}.$

Furthermore we say

  1. (3)

two (not-necessarily disjoint) closed sets $U,W\subseteq V$ are disjointly
internally spanned by $A$, if there exist two disjoint subsets
$A_{U},A_{W}\subseteq A$ that internally span $U$ and $W$, respectively, i.e.,
$U=\left[{A_{U}\cap U}\right]$ and $W=\left[{A_{W}\cap W}\right]$.

In this case, we write

$\displaystyle\\{U,W\\}\subseteq_{d}\mathcal{H}_{A}.$

Analogously for arbitrary numbers of sets $U_{1},\ldots,U_{\ell}\subseteq V$
we say they are disjointly internally spanned by $A$, if there exist disjoint
subsets $A_{U_{1}},\ldots,A_{U_{\ell}}\subseteq A$ that internally span
$U_{1},\ldots,U_{\ell}$, respectively.

A powerful tool in our analysis is the van den Berg-Kesten Lemma. Essentially
in the context of bootstrap percolation it implies the following.

######  Lemma 2.4 ([39, Theorem 1.6.(iii)]).

Given a graph $G=(V,E)$ and $p\in(0,1)$ let $\boldsymbol{A}_{p}$ be a
$p$-random subset of $V$, i.e.,
$\mathbb{P}\left[v\in\boldsymbol{A}_{p}\right]=p$ for each $v\in V$
independently. For any $U,W\subseteq V$, we have

$\displaystyle\mathbb{P}\left[\\{U,W\\}\subseteq_{d}\mathcal{H}_{\boldsymbol{A}_{p}}\right]\leq\mathbb{P}\left[U\in\mathcal{H}_{\boldsymbol{A}_{p}}\right]\cdot\mathbb{P}\left[W\in\mathcal{H}_{\boldsymbol{A}_{p}}\right].$

We will use the following version of the second moment method, due to Alon and
Spencer [3].

######  Lemma 2.5 ([3], Corollary 4.3.4).

Let $X=\sum_{i=1}^{n}X_{i}$ be a sum of indicator random variables for the
events $(\mathcal{E}_{i})_{i=1}^{n}$. For indices $i,j\in[n]$ write $i\sim j$,
if the events $\mathcal{E}_{i}$ and $\mathcal{E}_{j}$ are dependent. If

$\displaystyle\mathbb{E}\left[X\right]\rightarrow\infty\quad\text{ and
}\quad\sum_{i\sim
j}\mathbb{P}\left[\mathcal{E}_{i}\cap\mathcal{E}_{j}\right]=o\left(\mathbb{E}\left[X\right]^{2}\right)\quad\text{
as }n\rightarrow\infty,$

then $\mathbb{P}\left[X\geq 1\right]\rightarrow 1$ as $n\rightarrow\infty$.

###  2.2. Deterministic bootstrap percolation on the Hamming graph

In this section we collect properties of closed sets in the Hamming graph and
how they interact with each other. Note that the results presented in this
section are already known and can be found e.g., in [38], but for the sake of
completeness we include their proofs in Appendix A. Throughout this section
and the next section we consider the $n$-dimensional Hamming graph

$G=(V,E)=\square_{i=1}^{n}K_{k},$

where $n,k\in\mathbb{N}$ satisfying $k\geq 2$. We start with a simple but
important observation about projections.

######  Lemma 2.6.

Any projection of $G$ is closed.

Next we state the most important result in this section, which tells us how
projections within small distance interact in the $2$-neighbour bootstrap
percolation process.

######  Lemma 2.7.

Let $H^{\prime},H^{\prime\prime}$ be two projections of $G$ satisfying
$\operatorname{dist}\left(H^{\prime},H^{\prime\prime}\right)\leq 2$. Then,
there exists a projection $H$ of $G$ satisfying
$\operatorname{dim}\left(H\right)\leq\operatorname{dim}\left(H^{\prime}\right)+\operatorname{dim}\left(H^{\prime\prime}\right)+\operatorname{dist}\left(H^{\prime},H^{\prime\prime}\right)$
and

$\displaystyle\left[{H^{\prime}\cup H^{\prime\prime}}\right]=H.$

2.7 tells us that two projections within distance two span another larger
projection that contains both of them.

######  Remark 2.8.

Note that if two projections $H^{\prime}$ and $H^{\prime\prime}$ lie at
distance at least three, they have no common neighbours and thus do not
interact under $2$-neighbour bootstrap percolation, i.e.,

$\displaystyle\left[{H^{\prime}\cup H^{\prime\prime}}\right]=H^{\prime}\cup
H^{\prime\prime}.$

By 2.7 we know that we can generate larger and larger projections by adding
vertices that lie at distance two of the previous projection. The set of
vertices used in this construction is very useful in the $2$-neighbour
bootstrap percolation process and we define it more precisely in the
following.

######  Definition 2.9.

A set $U\subseteq V$ is called sequentially spanning, if there is an ordering
$(v_{0},\ldots,v_{|U|-1})$ of its vertices such that

$\displaystyle\operatorname{dist}\left(\left[{\\{v_{0},\ldots,v_{i-1}\\}}\right],v{{}_{i}}\right)=2\quad\text{
for all }i\in[|U|-1].$ (2.1)

In words, Property (2.1) guarantees that each vertex in the ordering lies
exactly at distance two from the projection spanned by the previous vertices.
We will see in 3.2 that a majority of all percolating sets in $G$ are
sequentially spanning. The next lemma tells us that sequentially spanning sets
always span large projections.

Figure 1. A sequentially spanning set of size two (discs in red) in
$\square_{i=1}^{4}K_{2}$ and all possible extensions to a sequentially
spanning set of size three (squares in black).

######  Lemma 2.10.

Assume that $U\subseteq V$ is a sequentially spanning set. Then there exists a
projection $H$ of $G$ such that

$\displaystyle\operatorname{dim}\left(H\right)=2(|U|-1)\quad\quad\text{ and
}\quad\quad\left[{U}\right]=H.$

Next we discuss an alternative way of looking at the bootstrap percolation
process, using projections.

###  2.3. A different view on the bootstrap percolation process

Given a set $A\subseteq V$, consider the collection $\mathcal{H}_{A}$ of all
subsets that are internally spanned by $A$, as in Definition 2.3. For each
$H\in\mathcal{H}_{A}$ (so $H=\left[{A\cap H}\right]$) we can think of the set
$A\cap H$ as a set
$S_{0}=\left\\{\left\\{a_{0}\right\\},\ldots,\left\\{a_{s}\right\\}\right\\}$
of $0$-dimensional projections. As each of these projections consists of a
single _infected_ vertex, it is clear that they are _disjointly internally
spanned_. By 2.8, projections at distance at least three do not interact at
all, so it follows from $\left[{S_{0}}\right]=H$ that at least two of those
projections, w.l.o.g. $a_{0}$ and $a_{1}$, are within distance two of each
other. By 2.7, $a_{0}\cup a_{1}$ spans a projection that is by construction
disjointly internally spanned from all other projections $a_{2},\ldots,a_{s}$.
Thus, we obtain a set $S_{1}=\left\\{\left[{a_{0}\cup
a_{1}}\right],\left\\{a_{2}\right\\},\ldots,\left\\{a_{s}\right\\}\right\\}$
consisting of $|S_{1}|=|S_{0}|-1$ disjointly internally spanned projections.
Note that the set $S_{1}$ is not uniquely determined, as it depends on the
choice of projections within distance two. Continuing this process we
sequentially obtain sets $S_{i}$ of disjointly internally spanned projections
until at the final step $S_{s}=\\{H\\}$. More formally, we obtain the
following.

######  Lemma 2.11.

Let $H\in\mathcal{H}_{A}$ and set $s\coloneqq\left|A\cap H\right|-1$. Then,
there exist families $S_{0},\ldots,S_{s}$ of subsets of $V$ such that the
following hold.

  1. (1)

$S_{0}=\left\\{\\{v\\}\mid v\in A\cap H\right\\}$;

  2. (2)

for all $0\leq i\leq s-1,$ there exist $H^{\prime},H^{\prime\prime}\in
S_{i}\text{ such that }S_{i+1}=S_{i}\cup\left\\{\left[{H^{\prime}\cup
H^{\prime\prime}}\right]\right\\}\setminus\\{H^{\prime},H^{\prime\prime}\\}$;

  3. (3)

for all $0\leq i\leq s$, the elements of $S_{i}$ are disjointly internally
spanned projections of $G$;

  4. (4)

$S_{s}=\\{H\\}$.

Now given $H\in\mathcal{H}_{A}$ and any integer $1\leq
t\leq\operatorname{dim}\left(H\right)$ we consider the first time a projection
of dimension at least $t$ appears in this process. Looking at the two
projections that were joined in this step, 2.11 immediately implies the
following key result.

######  Lemma 2.12.

Let $H\in\mathcal{H}_{A}$. Then for every $1\leq
t\leq\operatorname{dim}\left(H\right)$, there exist indices
$(\ell,i,j,d)\in\mathbb{N}_{0}^{4}$ with $\ell\geq t,\ j\leq i<t$ and
$d\in\\{0,1,2\\}$ and projections $H_{i},H_{j},H_{\ell}$ of respective
dimensions $i,j,\ell$ such that

  1. (1)

$\operatorname{dist}\left(H_{i},H_{j}\right)=d$;

  2. (2)

$\left[{H_{i}\cup H_{j}}\right]=H_{\ell}$;

  3. (3)

$\left\\{H_{i},H_{j}\right\\}\subseteq_{d}\mathcal{H}_{A}$.

We call the quadruple $(H_{\ell},H_{i},H_{j},d)$ a witnessing quadruple for
$H$ at threshold $t$.

##  3\. The lower threshold: Proof of 1.1 (a)

In the rest of the paper we assume that $n\in\mathbb{N}$ is sufficiently large
and let $G=(V,E)=\square_{i=1}^{n}K_{k}$ be the $n$-dimensional Hamming graph
with $2\leq k\leq 2^{\sqrt{n}}$ and let $\boldsymbol{A}_{p}$ be a $p$-random
subset of $V$, as in 1.1. Let

$\displaystyle\mathcal{H}=\mathcal{H}_{\boldsymbol{A}_{p}}\coloneqq\left\\{U\subseteq
V\mid U=\left[{\boldsymbol{A}_{p}\cap U}\right]\right\\}$

be the collection of all subsets of $V$ that are internally spanned by
$\boldsymbol{A}_{p}$. Recall that we write $H_{\ell}$ for a projection of
dimension $\ell\in\mathbb{N}_{0}$ in order to keep track of its dimension.

This section is devoted to the proof of Section LABEL:*thm:main:threshold (a),
along which we will introduce some auxiliary results, but we defer their
proofs to Section 5. So we assume

$\displaystyle p\leq p_{*}\coloneqq n^{-2}k^{-2\sqrt{n}+1}$

and will show

$\displaystyle\mathbb{P}\left[G\text{
percolates}\right]=\mathbb{P}\left[\left[{\boldsymbol{A}_{p}}\right]=V\right]=o\left(1\right).$

We first note that in many bootstrap percolation processes the bottleneck for
percolation is given by the appearance of a small substructure of the
underlying graph, called a _critical droplet_. In our case, this critical
droplet is an internally spanned projection of a specific dimension
$t_{*}\in[n]$, where $t_{*}$ is chosen such that the expected number of
internally spanned projections is minimal: We call $t_{*}$ the critical
dimension.

Assume that $G$ percolates, i.e., $\left[{\boldsymbol{A}_{p}}\right]=V$. As
described in Lemma 2.11, we can view the set of initially infected vertices as
a collection of 0-dimensional projections that sequentially pairwise span
larger projections until in the final step two projections together span $G$.
In particular, for every threshold dimension $t\in[n]$ we can look at the
first time a projection $H$ of dimension at least $t$ appears in this process
and consider the projections that together span $H$. More precisely, it
follows from 2.12 that there has to exist a _witnessing quadruple_ for $G$ at
this threshold and thus we have

$\displaystyle\mathbb{P}\left[G\text{ percolates}\right]$
$\displaystyle\leq\mathbb{P}\left[\text{there exists a witnessing quadruple{}
for $G$ at threshold $t$}\right].$ (3.1)

In order for a quadruple $(H_{\ell},H_{i},H_{j},d)$ to be a witnessing
quadruple, it has to satisfy Properties (1),(2) and (3) of 2.12 and the
indices $(\ell,i,j,d)\in\mathbb{N}_{0}^{4}$ should fulfill the dimension
constraints $\ell\geq t,\ j\leq i<t$ and $d\in\\{0,1,2\\}$. However, note that
all requirements except Property (3) of 2.12 are deterministic statements that
do not depend on the set of initially infected vertices.

We call all quadruples $(H_{\ell},H_{i},H_{j},d)$ that satisfy the dimension
constraints as well as Properties (1) and (2) of 2.12 candidate quadruples and
denote by $\mathcal{C}(G,t)$ the set of all candidate quadruples. Thus, a
candidate quadruple is a witnessing quadruple if and only if it satisfies
Property (3) of 2.12. On the other hand, by the van den Berg-Kesten Lemma 2.4,
it holds that

$\displaystyle\mathbb{P}\left[\left\\{H_{i},H_{j}\right\\}\subseteq_{d}\mathcal{H}\right]\leq\mathbb{P}\left[H_{i}\in\mathcal{H}\right]\cdot\mathbb{P}\left[H_{j}\in\mathcal{H}\right].$

Hence, for any candidate quadruple
$(H_{\ell},H_{i},H_{j},d)\in\mathcal{C}(G,t)$ we have

$\displaystyle\mathbb{P}\left[(H_{\ell},H_{i},H_{j},d)\text{ is a witnessing
quadruple{}}\right]\leq\mathbb{P}\left[H_{i}\in\mathcal{H}\right]\cdot\mathbb{P}\left[H_{j}\in\mathcal{H}\right].$
(3.2)

Putting (3.1) and (3.2) together and taking a union bound over all candidate
quadruples we obtain the following bound for all $t\in[n]$:

$\displaystyle\mathbb{P}\left[G\text{ percolates}\right]$
$\displaystyle\leq\mathbb{P}\left[\text{there exists a witnessing quadruple{}
for $G$ at threshold $t$}\right]$
$\displaystyle\leq\sum_{(H_{\ell},H_{i},H_{j},d)\in\mathcal{C}(G,t)}\mathbb{P}\left[H_{i}\in\mathcal{H}\right]\cdot\mathbb{P}\left[H_{j}\in\mathcal{H}\right].$
(3.3)

Due to the symmetry of $G$, we have that for any projection $H$ of $G$, the
probability $\mathbb{P}\left[H\in\mathcal{H}\right]$ solely depends on
$\operatorname{dim}\left(H\right)$ (and does not depend on its structure).
Thus, for each $\ell\in[n]\cup\left\\{0\right\\}$ and each projection
$H_{\ell}$ of dimension $\ell$, we define

$\displaystyle\varphi({\ell})\coloneqq\mathbb{P}\left[H_{\ell}\in\mathcal{H}\right].$
(3.4)

Given indices $(\ell,i,j,d)\in\mathbb{N}_{0}^{4}$ let us denote by

$\displaystyle
U_{G,t}\left(\ell,i,j,d\right)\coloneqq\left|\left\\{\left(H_{\ell^{\prime}},H_{i^{\prime}},H_{j^{\prime}},d^{\prime}\right)\in\mathcal{C}(G,t)\mid\left(\ell^{\prime}=\ell\right)\land\left(i^{\prime}=i\right)\land\left(j^{\prime}=j\right)\land\left(d^{\prime}=d\right)\right\\}\right|$
(3.5)

the number of candidate quadruples in $G$ at threshold $t$ with fixed indices
$(\ell,i,j,d)$. Let us determine for which sets of indices this function is
actually non-zero. From 2.11 it follows that $\ell\geq t$, $j\leq i<t$ and
$d\in\\{0,1,2\\}$. Also, because the projections $H_{i}$ and $H_{j}$ have to
lie at distance $d$ it is not possible that $i=\ell-1$ and $d=2$, yielding the
condition $i+d<\ell$. Furthermore, by 2.7, in order for the projections
$H_{i}$ and $H_{j}$ to span the projection $H_{\ell}$ it also has to hold that
$i+j+d\geq\ell$. Finally, note that because $H_{\ell}$ is a projection of $G$,
we have
$\ell=\operatorname{dim}\left(H_{\ell}\right)\leq\operatorname{dim}\left(G\right)$.
These constraints lead to the set of all admissible indices, denoted by

$\displaystyle
I_{G,t}:=\left\\{(\ell,i,j,d)\in\mathbb{N}_{0}^{4}\mid\left(t\leq\ell\leq\min\left\\{i+j+d,\operatorname{dim}\left(G\right)\right\\}\right)\land(j\leq
i<t)\land(i+d<\ell)\land(d\in\\{0,1,2\\})\right\\}.$

Analogously, we define $\mathcal{C}(H,t)$, $U_{H,t}(\cdot)$ and $I_{H,t}$ for
a projection $H$ of $G$ and a threshold
$t\in\left[\operatorname{dim}\left(H\right)\right]$.

In terms of the functions $\varphi({\cdot})$ and $U_{H,t}(\cdot)$ defined in
(3.4) and (3.5), the percolation probability bound (3.3) can be written as
follows.

######  Lemma 3.1.

For every $t\in[n]$ we have

$\displaystyle\mathbb{P}\left[G\text{
percolates}\right]\leq\sum_{(\ell,i,j,d)\in
I_{G,t}}U_{G,t}\left(\ell,i,j,d\right)\varphi({i})\varphi({j}).$ (3.6)

The value of $U_{G,t}(\cdot)$ will be calculated quite explicitly in 5.1.
Thus, a key step in deriving an upper bound on the percolation probability is
to obtain good bounds on the probability of a projection being internally
spanned and choosing the optimal threshold value $t$. As we will see in
Section 5, the critical dimension in which the right hand side of (3.6) yields
the best bounds is

$t_{*}:=\left\lfloor 2\sqrt{n}\right\rfloor-2.$

In order to bound the right hand side of (3.6) from above, we need the
following upper bound on the function $\varphi({\cdot})$ defined in (3.4).

######  Lemma 3.2.

For all $m\in[t_{*}]\cup\\{0\\}$ we have

$\displaystyle\varphi({m})\leq\Phi(m)$ (3.7)

where the function $\Phi:\mathbb{N}_{0}\to\mathbb{R}$ is defined as

$\displaystyle\Phi(m)\coloneqq c_{m}p^{\frac{m}{2}+1}m!\
2^{-\frac{m}{2}}(k-1)^{m}k^{\frac{m^{2}+2m}{4}}$ (3.8)

with

$c_{m}\coloneqq\mathbb{1}_{\left\\{m=0\right\\}}+\mathbb{1}_{\left\\{1\leq
m\leq
14\right\\}}\frac{1}{2}\left(\frac{9\sqrt{2}}{10}\right)^{m}+\mathbb{1}_{\left\\{m\geq
15\right\\}}c_{m-1}\left(1+k^{-\frac{m-11}{2}}\right)\left(1+\frac{4}{n}\right).$

Before we proceed with the proof of Section LABEL:*thm:main:threshold (a) let
us give some intuition on the function $\Phi$. The value $\Phi(0)=p$ is
exactly the probability of a $0$-dimensional projection (i.e., a single
vertex) being internally spanned by a $p$-random subset $\boldsymbol{A}_{p}$.
For even $m\in[t_{*}]$, the value $\Phi(m)$ is equal to the expected number of
sequentially spanning sets in a projection of dimension $m$, up to a
multiplicative factor $c_{m}$ and up to permutations of vertices. Thus, 3.2
states that a majority of percolating sets is given by sequentially spanning
sets. For odd $m\in[t_{*}]$, the value $\Phi(m)$ overestimates the actual
probability $\varphi({m})$ by quite a large margin, but spares us from a
tedious case distinction. Lastly, note that for all $m\in[t_{*}]\cup\\{0\\}$
the functions $c_{m}$ are bounded from above by a universal constant (see
5.7).

The key to showing 3.2 lies in the following observation: Any projection $H$
of $G$ is isomorphic to a Hamming graph of dimension
$\operatorname{dim}\left(H\right)$, and thus the event
$\\{H\in\mathcal{H}\\}=\\{H\in\mathcal{H}_{\boldsymbol{A}_{p}}\\}$ happens
with the same probability as the event that the Hamming graph
$G^{\prime}:=\square_{i=1}^{\operatorname{dim}\left(H\right)}K_{k}$
percolates. Hence, we can apply 3.1 to obtain that for all $m\in[n]$ and for
all $t\in[m]$

$\displaystyle\varphi({m})\leq\sum_{(\ell,i,j,d)\in
I_{H_{m},t}}U_{H_{m},m}\left(\ell,i,j,d\right)\varphi({i})\varphi({j}).$

It turns out that we obtain the best bounds by considering the threshold value
$t=m$, i.e., by looking at the final step in the percolation process, where
two projections of respective dimensions smaller than $m$ together span
$H_{m}$. Let us assume by induction that the conclusion of 3.2, i.e.,
$\varphi({j})\leq\Phi(j)$, holds for all $j\in[m-1]$ for some
$m\in[t_{*}]\cup\\{0\\}$. Because any $(\ell,i,j,d)\in I_{H_{m},m}$ satisfies
$j\leq i<m$, we obtain

$\displaystyle\varphi({m})\leq\sum_{(\ell,i,j,d)\in
I_{H_{m},m}}U_{H_{m},m}\left(\ell,i,j,d\right)\Phi(i)\Phi(j).$ (3.9)

3.2 then follows from (3.9) by a careful comparison of ratios of consecutive
terms.

Returning to the proof of Section LABEL:*thm:main:threshold (a), using 3.1
with $t=t_{*}:=\left\lfloor 2\sqrt{n}\right\rfloor-2$ and 3.2 we have

$\displaystyle\mathbb{P}\left[G\text{ percolates}\right]$
$\displaystyle{\leq}\sum_{(\ell,i,j,d)\in
I_{G,t_{*}}}U_{G,t_{*}}\left(\ell,i,j,d\right)\varphi({i})\varphi({j})$
$\displaystyle{\leq}\sum_{(\ell,i,j,d)\in
I_{G,t_{*}}}U_{G,t_{*}}\left(\ell,i,j,d\right)\Phi(i)\Phi(j).$ (3.10)

Due to technical reasons, we will consider the partition of the set
$I_{G,t_{*}}$ into two sets, depending on the size of $\ell$,

$\displaystyle I_{G,t_{*}}^{(1)}\coloneqq\left\\{(\ell,i,j,d)\in
I_{G,t_{*}}\mid\ell\leq 3\sqrt{n}\right\\}\ \text{ and }\
I_{G,t_{*}}^{(2)}\coloneqq\left\\{(\ell,i,j,d)\in
I_{G,t_{*}}\mid\ell>3\sqrt{n}\right\\},$ (3.11)

so that

$\displaystyle I_{G,t_{*}}=I_{G,t_{*}}^{(1)}\cup I_{G,t_{*}}^{(2)}.$ (3.12)

Furthermore, to ease notation on the right hand side of (3) we introduce the
function

$\displaystyle f\left(\ell,i,j,d\right)\coloneqq
U_{G,t_{*}}\left(\ell,i,j,d\right)\Phi(i)\Phi(j).$ (3.13)

Using (3.12) and (3.13) we rewrite (3) as

$\displaystyle\mathbb{P}\left[G\text{
percolates}\right]\leq\sum_{(\ell,i,j,d)\in
I_{G,t_{*}}^{(1)}}f\left(\ell,i,j,d\right)+\sum_{(\ell,i,j,d)\in
I_{G,t_{*}}^{(2)}}f\left(\ell,i,j,d\right).$ (3.14)

We deal with the first and second sums in (3.14) separately. We claim that the
second sum over all indices in $I_{G,t_{*}}^{(2)}$ converges to zero (see 3.3)
and the first sum over all indices in $I_{G,t_{*}}^{(1)}$ is bounded from
above by a single term $f\left(t_{*},t_{*}-2,0,2\right)$, up to a
multiplicative factor (see 3.4).

######  Claim 3.3.

$\displaystyle\sum_{(\ell,i,j,d)\in
I_{G,t_{*}{}}^{(2)}}f\left(\ell,i,j,d\right)$ $\displaystyle=o(1).$

In order to deal with the sum over all indices in $I_{G,t_{*}{}}^{(1)}$, we
first note that $f\left(\ell,i,j,d\right)$ essentially bounds the expected
number of projections of respective dimensions $i$ and $j$ that lie at
distance $d$ and together span a projection of dimension $\ell\geq t_{*}$ in
$G$. We then note that a major role in $2$-neighbour bootstrap percolation on
the hypercube is played by sequentially spanning sets (see Definition 2.9),
and thus we expect that the dominating term of the left hand side of 3.3 would
also stem from sequentially spanning sets and so in the last step of the
percolation process a projection of dimension $t_{*}-2$ would be joined with a
single vertex at distance two: It corresponds to
$f\left(t_{*},t_{*}-2,0,2\right)$. The next lemma shows that the sum is indeed
dominated by this term, up to a small multiplicative factor.

######  Lemma 3.4.

$\displaystyle\sum_{(\ell,i,j,d)\in
I_{G,t_{*}{}}^{(1)}}f\left(\ell,i,j,d\right)\leq
5k^{\frac{1}{2}}f\left(t_{*},t_{*}-2,0,2\right).$

Using simple calculations we can relate the value of
$f\left(t_{*},t_{*}-2,0,2\right)$ with $\Phi(t_{*})$.

######  Claim 3.5.

$\displaystyle
f\left(t_{*},t_{*}-2,0,2\right)\leq\binom{n}{t_{*}}k^{n-t_{*}}\Phi(t_{*}).$

Now, combining 3.4 and 3.5 we obtain

$\displaystyle\sum_{(\ell,i,j,d)\in
I_{G,t_{*}{}}^{(1)}}f\left(\ell,i,j,d\right)\overset{Lem.\leavevmode\nobreak\
\ref{lem:triplesumdomination_part2}}{\leq}5k^{\frac{1}{2}}f\left(t_{*},t_{*}-2,0,2\right)\overset{C.\leavevmode\nobreak\
\ref{claim:ffuncSmaller_Upboundcubeintspan}}{\leq}5\binom{n}{t_{*}}k^{n-t_{*}+\frac{1}{2}}\Phi(t_{*}).$
(3.15)

Thus, (3.14), 3.3 and (3.15) yield

$\displaystyle\mathbb{P}\left[G\text{ percolates}\right]$
$\displaystyle{\leq}\sum_{(\ell,i,j,d)\in
I_{G,t_{*}}^{(1)}}f\left(\ell,i,j,d\right)+\sum_{(\ell,i,j,d)\in
I_{G,t_{*}}^{(2)}}f\left(\ell,i,j,d\right)$
$\displaystyle{\leq}5\binom{n}{t_{*}}k^{n-t_{*}+\frac{1}{2}}\Phi(t_{*})+o\left(1\right).$

Summing up, we obtain an upper bound on the percolation probability in terms
of the value of the function $\Phi(\cdot)$ at the critical dimension $t_{*}$.

######  Lemma 3.6.

$\displaystyle\mathbb{P}\left[G\text{ percolates}\right]\leq
5\binom{n}{t_{*}}k^{n-t_{*}+\frac{1}{2}}\Phi(t_{*})+o\left(1\right).$

We observe that the right hand side of the inequality in 3.6 is an upper bound
on the number of internally spanned projections of dimension $t_{*}$ in $G$,
up to a factor of order $\Theta\left(\sqrt{k}\right)$. Indeed, there are
exactly $\binom{n}{t_{*}}k^{n-t_{*}}$ ways of choosing a projection of
dimension $t_{*}$ in $G$ and for each such projection $H$, the probability
that $H$ is internally spanned is bounded from above by $\Phi(t_{*})$. Thus,
3.6 shows that the bottleneck for percolation in the Hamming graph lies in
finding an internally spanned projection of dimension $t_{*}$. On the other
hand, we will see in 4.4 that as soon as an internally spanned projection of
dimension $t_{*}$ appears in $G$, the whole graph percolates whp. To complete
the proof of Section LABEL:*thm:main:threshold (a), we show that for $p\leq
p_{*}$ the expected number of internally spanned projections of dimension
$t_{*}$ (even with an additional factor $\sqrt{k}$ ) tends to zero.

######  Lemma 3.7.

$\displaystyle\binom{n}{t_{*}}k^{n-t_{*}+\frac{1}{2}}\Phi(t_{*})=o(1).$

Now we are ready to prove Section LABEL:*thm:main:threshold (a).

###### Proof of Section LABEL:*thm:main:threshold (a).

From Lemmas 3.6 and 3.7 we have

$\displaystyle\mathbb{P}\left[G\text{ percolates}\right]=o\left(1\right),$

as desired. ∎

##  4\. The upper threshold: Proof of 1.1 (b)

In this section we will prove 1.1 (b). Along the proof we will derive several
auxiliary results, whose proofs are deferred to Section 6. We assume

$\displaystyle p\geq p^{*}=200n^{-2}k^{-2\sqrt{n}+1}$

and will show

$\displaystyle\mathbb{P}\left[G\text{
percolates}\right]=\mathbb{P}\left[[\boldsymbol{A}_{p}]=V\right]=1+o\left(1\right).$

In order to show that whp $G$ percolates it suffices to find a single
percolating set in $G$ that is initially infected, contrary to the lower
threshold, where we had to consider all possible percolating sets. It turns
out the correct type of sets to consider are _sequentially spanning sets_ (see
Definition 2.9). One intuitive reason why these sets are essential to the
percolation process is that they form minimum percolating sets and are thus
more likely to be initially infected than larger percolating sets. To keep
track of the order on the vertices of a sequentially spanning set (as given by
Definition 2.9), we will consider sequences instead of sets.

######  Definition 4.1.

Let $\ell\in\mathbb{N}$.

  1. (1)

A sequence $\overline{v}_{\ell}=(v_{0},\ldots,v_{\ell})$ of vertices in $V$ is
called sequentially spanning, if $(v_{0},\ldots,v_{\ell})$ satisfies Property
(2.1). The _length_ of $\ \overline{v}_{\ell}=(v_{0},\ldots,v_{\ell})$ is
defined as $\ell$.

  2. (2)

A sequentially spanning sequence $\overline{v}_{\ell}=(v_{0},\ldots,v_{\ell})$
is called infected, if
$\\{\overline{v}_{\ell}\\}\coloneqq\\{v_{0},\ldots,v_{\ell}\\}\subseteq\boldsymbol{A}_{p}$.

  3. (3)

For two sequentially spanning sequences
$\overline{v}_{\ell},\overline{w}_{\ell}$ we define
$\overline{v}_{\ell}\cap\overline{w}_{\ell}\coloneqq\\{\overline{v}_{\ell}\\}\cap\\{\overline{w}_{\ell}\\}$.

Note that the length of $\overline{v}_{\ell}=(v_{0},\ldots,v_{\ell})$ is
defined in such a way that a sequentially spanning sequence of length $\ell$
spans a projection of dimension $2\ell$ (see 2.10).

Our aim is to find a sufficiently large _infected_ sequentially spanning
sequence in $G$. To that end, let us denote by

$S_{\ell}=S_{\ell}(G)\coloneqq\left\\{\overline{v}_{\ell}=(v_{0},\ldots,v_{\ell})\mid\overline{v}_{\ell}\text{
is sequentially spanning{}}\right\\}$

the set of all sequentially spanning sequences of length $\ell$ in $G$ and by
$X_{\ell}$ the number of all _infected_ sequentially spanning sequences of
length $\ell$. Then, for all $\ell\in\mathbb{N}_{0}$ we obtain

$\displaystyle X_{\ell}=\sum_{\overline{v}_{\ell}\in
S_{\ell}}\mathbb{1}_{\left\\{\\{\overline{v}_{\ell}\\}\subseteq\boldsymbol{A}_{p}\right\\}}.$

A first step towards our goal is to count the number of sequentially spanning
sequences. Because a sequentially spanning sequence of length zero consists of
a single vertex, it clearly holds that

$|S_{0}|=\left|V\right|=k^{n}.$

In the next lemma we explicitly compute the number of sequentially spanning
sequences of given length by successively extending such sequences.

######  Lemma 4.2.

For $1\leq\ell\leq\left\lfloor\frac{n}{2}\right\rfloor$, let
$\overline{v}_{\ell-1}=(v_{0},\ldots,v_{\ell-1})\in S_{\ell-1}$ be a
sequentially spanning sequence of length $\ell-1$. Denote by

$\displaystyle C_{\ell}\coloneqq\left|\left\\{w\in
V\mid(v_{0},\ldots,v_{\ell-1},w)\in S_{\ell}\right\\}\right|$

the number of vertices in $V$ that extend $\overline{v}_{\ell-1}$ to a
sequentially spanning sequence of length $\ell$. Then, for
$1\leq\ell\leq\left\lfloor\frac{n}{2}\right\rfloor$,

$\displaystyle C_{\ell}=\binom{n-2\ell+2}{2}(k-1)^{2}k^{2\ell-2}$

and for $0\leq\ell\leq\left\lfloor\frac{n}{2}\right\rfloor$,

$\displaystyle|S_{\ell}|=k^{n}\prod_{j=1}^{\ell}C_{j}=\frac{n!}{(n-2\ell)!}(k-1)^{2\ell}2^{-\ell}k^{n+\ell^{2}-\ell}.$
(4.1)

Observe that by the definitions of $S_{\ell}$ and $C_{\ell}$, we obtain that
for $1\leq\ell\leq\left\lfloor\frac{n}{2}\right\rfloor$,

$\displaystyle|S_{\ell}|=|S_{\ell-1}|\cdot C_{\ell}.$ (4.2)

Using 4.2 we already have a good grip on the expected number of sequentially
spanning sequences of given length, because for any sequence
$\overline{v}_{\ell}\in S_{\ell}$ it holds that
$\mathbb{P}\left[\mathbb{1}_{\left\\{\\{\overline{v}_{\ell}\\}\subseteq\boldsymbol{A}_{p}\right\\}}\right]=p^{\ell+1}$
and thus

$\displaystyle\mathbb{E}\left[X_{\ell}\right]=p^{\ell+1}|S_{\ell}|.$ (4.3)

Next we aim to apply the second moment method to show that whp there exists an
infected sequentially spanning sequence of length
$\left\lfloor\frac{n}{2}\right\rfloor$. Note that we cannot hope to find a
sequentially spanning sequence of length $\ell$ which is strictly larger than
$\left\lfloor\frac{n}{2}\right\rfloor$, because by 2.10 such a sequence would
span a projection of dimension $2\ell>n=\operatorname{dim}\left(G\right)$ – a
contradiction. Thus we set

$\displaystyle\ell^{*}\coloneqq\left\lfloor\frac{n}{2}\right\rfloor;$
$\displaystyle\Delta\coloneqq\sum_{\left\\{\\{\overline{v}_{\ell^{*}},\overline{w}_{\ell^{*}}\\}\subseteq
S_{\ell^{*}}\mid\overline{v}_{\ell^{*}}\cap\overline{w}_{\ell^{*}}\neq\emptyset\right\\}}\mathbb{P}\left[\mathbb{1}_{\left\\{\left(\\{\overline{v}_{\ell^{*}}\\}\subseteq\boldsymbol{A}_{p}\right)\land\left(\\{\overline{w}_{\ell^{*}}\\}\subseteq\boldsymbol{A}_{p}\right)\right\\}}\right]$

and note that by 2.5 it suffices to show

$\displaystyle\mathbb{E}\left[X_{\ell^{*}}\right]\xrightarrow{}\infty;$ (4.4)
$\displaystyle\frac{\Delta}{\mathbb{E}\left[X_{\ell^{*}}\right]^{2}}\xrightarrow{}0.$
(4.5)

Like in most applications of the second moment method, the harder part is to
prove (4.5), which requires us to compute the correlation between different
infected sequentially spanning sequences. For
$\\{\overline{v}_{\ell},\overline{w}_{\ell}\\}\subseteq S_{\ell}$ it holds
that

$\displaystyle\mathbb{P}\left[\mathbb{1}_{\left\\{\left(\\{\overline{v}_{\ell}\\}\subseteq\boldsymbol{A}_{p}\right)\land\left(\\{\overline{w}_{\ell}\\}\subseteq\boldsymbol{A}_{p}\right)\right\\}}\right]=p^{2(\ell+1)-\left|\overline{v}_{\ell}\cap\overline{w}_{\ell}\right|}.$
(4.6)

Thus, the proof boils down to bounding the number of pairs of sequentially
spanning sequences that share a certain amount of vertices. For each
$\ell\in[\ell^{*}]\cup\left\\{0\right\\}$ and each $i\in[\ell+1]$ we denote by

$\displaystyle
Y_{\ell}(i)\coloneqq\left\\{\\{\overline{v}_{\ell},\overline{w}_{\ell}\\}\subseteq
S_{\ell}\mid\left|\overline{v}_{\ell}\cap\overline{w}_{\ell}\right|=i\right\\}$
(4.7)

the number of pairs of sequentially spanning sequences of length $\ell$ that
intersect exactly in $i$ vertices. To give some intuition on what we expect
the size of $Y_{\ell}(i)$ to be, consider the following way of constructing
intersecting sequentially spanning sequences: Start both sequences with the
same initial sequence of length $i-1$ (with the same $i$ vertices) and then
use arbitrary vertices to extend them. Clearly, there are $|S_{i-1}|$ ways for
choosing an initial sequence of length $i-1$. Furthermore, by (4.2), we have
$C_{j}=\frac{|S_{j}|}{|S_{j-1}|}$ and thus there are
$\prod_{j=i+1}^{\ell}C_{j}^{2}=\left(\frac{|S_{\ell}|}{|S_{i-1}|}\right)^{2}$
ways to extend two sequences of length $i-1$ to two sequences of length
$\ell$. Note that it is possible that the resulting sequences overlap in even
more than $i$ vertices, which happens if one of the extensions also appeared
previously in the other sequence, however this only reduces the number of
possible extensions by an insignificant amount. Thus, we expect that
$|Y_{\ell}(i)|\geq\frac{|S_{\ell}|^{2}}{|S_{i-1}|}$ and it turns out that this
naive bound is almost tight, as shown in the following lemma.

######  Lemma 4.3.

For $\ell\in[\ell^{*}]\cup\\{0\\}$ and $i\in[\ell+1]$ we have

$\displaystyle\left|Y_{\ell}(i)\right|\leq\Theta\left(1\right)8^{i}(\ell+1)^{3}\frac{|S_{\ell}|^{2}}{|S_{i-1}|}.$
(4.8)

Combining (4.6) and (4.7) we have

$\displaystyle\Delta\overset{\eqref{eq:secondmoment:prob},\eqref{eq:def:seqoverlap}}{=}\sum_{i=1}^{\ell^{*}+1}\left|Y_{\ell^{*}}(i)\right|p^{2\ell^{*}+2-i}\leq(\ell^{*}+1)\max_{i\in[\ell^{*}+1]}\left(\left|Y_{\ell^{*}}(i)\right|p^{2\ell^{*}+2-i}\right).$
(4.9)

Using (4.9) and 4.3 (by taking $\ell=\ell^{*}$) we obtain

$\displaystyle\Delta$
$\displaystyle{\leq}\Theta(1)(\ell^{*}+1)^{4}\max_{i\in[\ell^{*}+1]}\left(8^{i}\frac{|S_{\ell^{*}}|^{2}}{|S_{i-1}|}p^{2\ell^{*}+2-i}\right)$
$\displaystyle\leq\Theta(n^{4})\max_{i\in[\ell^{*}+1]}\left(8^{i}\frac{|S_{\ell^{*}}|^{2}}{|S_{i-1}|}p^{2\ell^{*}+2-i}\right),$
(4.10)

where the last inequality is due to $\ell^{*}=\Theta(n)$. From (4.10) and
(4.3) (with $\ell=\ell^{*}$ and $\ell=i-1$, obtaining
$\mathbb{E}\left[X_{\ell^{*}}\right]=p^{\ell^{*}+1}|S_{\ell^{*}}|$ and
$\mathbb{E}\left[X_{i-1}\right]=p^{i}|S_{i-1}|$, respectively) it follows

$\displaystyle\Delta$
$\displaystyle{\leq}\Theta(n^{4})\max_{i\in[\ell^{*}+1]}\left(8^{i}\frac{|S_{\ell^{*}}|^{2}p^{2\ell^{*}+2}}{|S_{i-1}|p^{i}}\right)$
$\displaystyle{\leq}\Theta(n^{4})\max_{i\in[\ell^{*}+1]}\left(8^{i}\frac{\mathbb{E}\left[X_{\ell^{*}}\right]^{2}}{\mathbb{E}\left[X_{i-1}\right]}\right)=\frac{\Theta(n^{4})\mathbb{E}\left[X_{\ell^{*}}\right]^{2}}{\min_{i\in[\ell^{*}+1]}\left(8^{-i}\mathbb{E}\left[X_{i-1}\right]\right)},$

which implies

$\displaystyle\frac{\Delta}{\mathbb{E}\left[X_{\ell^{*}}\right]^{2}}\leq\frac{\Theta(n^{4})}{\min_{i\in[\ell^{*}+1]}\left(8^{-i}\mathbb{E}\left[X_{i-1}\right]\right)}.$
(4.11)

Thus, in order to prove (4.5), i.e.,
$\frac{\Delta}{\mathbb{E}\left[X_{\ell^{*}}\right]^{2}}\to 0$, it suffices to
verify that $\mathbb{E}\left[X_{i}\right]$ grows faster than $8^{i+1}n^{4}$
for all $i\in[\ell^{*}]\cup\\{0\\}$.

######  Lemma 4.4.

For every $i\in[\ell^{*}]\cup\\{0\\}$,

$\displaystyle\frac{\mathbb{E}\left[X_{i}\right]}{8^{i+1}\Theta(n^{4})}=\omega(1).$
(4.12)

As we will see in the proof of 4.4, the function
$x\mapsto\frac{\mathbb{E}\left[X_{x}\right]}{8^{x+1}\Theta(n^{4})}$ attains
its minimum over the reals when

$\displaystyle x=\sqrt{n}-1.$

However, in 4.4 the index $i\in[\ell^{*}]\cup\\{0\\}$ is an integer, and thus
the actual minimiser (or ‘bottleneck’), i.e., the index
$i\in[\ell^{*}]\cup\\{0\\}$ at which
$\frac{\mathbb{E}\left[X_{i}\right]}{8^{i+1}\Theta(n^{4})}$ is smallest,
happens either for $i=\left\lfloor\sqrt{n}\right\rfloor-1$ or for
$i=\left\lceil\sqrt{n}\right\rceil-1$. Because in both cases the error terms
are insignificant, we only focus on the former. We observe that each
sequentially spanning sequence of length
$i_{*}:=\left\lfloor\sqrt{n}\right\rfloor-1$ spans a projection of dimension
$2i_{*}$. Thus, the critical droplet for percolation is indeed an internally
spanned projection of critical dimension

$t_{*}:=2i_{*}=\left\lfloor 2\sqrt{n}\right\rfloor-2.$

(See 3.6 for the ‘negative’ statement, meaning that for $p\leq p_{*}$ whp
there does not exist an internally spanned projection of dimension $t_{*}$).

As discussed before, by the second moment method (see 2.5), in order to show
that whp $X_{\ell^{*}}\geq 1$ it suffices to verify (4.4), i.e.,
$\mathbb{E}\left[X_{\ell^{*}}\right]\xrightarrow{}\infty$, and (4.5), i.e.,
$\frac{\Delta}{\mathbb{E}\left[X_{\ell^{*}}\right]^{2}}\to 0$: We observe that
the former follows directly from 4.4 (with $i=\ell^{*}$) and the latter from
(4.11) and 4.4 (with $i=\ell^{*}$).

######  Corollary 4.5.

Whp $X_{\ell^{*}}\geq 1$.

Note that by 4.5, whp $G$ contains an infected sequentially spanning sequence
of length $\ell^{*}$ and by 2.10, this sequence spans a projection $H$ in $G$
of dimension $2\ell^{*}$: In other words, whp $G$ contains an internally
spanned projection $H$ of dimension $2\ell^{*}$. Recalling
$\ell^{*}:=\left\lfloor\frac{n}{2}\right\rfloor$ we obtain the following.

######  Corollary 4.6.

Whp there exists an internally spanned projection $H$ of dimension
$2\left\lfloor\frac{n}{2}\right\rfloor$ in $G$.

In order to prove Section LABEL:*thm:main:threshold (b) we need one last
auxiliary result when $n$ is odd.

######  Lemma 4.7.

Let $n=2m+1$ for $m\in\mathbb{N}_{0}$. Then whp the following holds: For every
projection $H$ of dimension $2m$ there exists at least one infected vertex in
$G$ that is not contained in $H$.

###### Proof of Section LABEL:*thm:main:threshold (b).

By 4.6, whp there exists an internally spanned projection $H$ of dimension
$2\left\lfloor\frac{n}{2}\right\rfloor$ in $G$.

If $n$ is even, then
$\operatorname{dim}\left(H\right)=2\left\lfloor\frac{n}{2}\right\rfloor=n$ and
thus $H=G$, showing that whp $G$ percolates.

If $n$ is odd, say $n=2m+1$ for $m\in\mathbb{N}_{0}$, then
$\operatorname{dim}\left(H\right)=2\left\lfloor\frac{n}{2}\right\rfloor=2m$.
But, it follows from 4.7 that whp there exists an infected vertex $v$ that is
not contained in $H$. Clearly, $\\{v\\}\cup H$ can have no trivial coordinates
and in addition it has to hold that $\operatorname{dist}\left(v,H\right)=1$.
Thus, by 2.7 we have $\left[{\\{v\\}\cup H}\right]=G,$ and thus whp $G$
percolates. ∎

##  5\. Proofs of auxiliary results for the lower threshold

In this section we will prove auxiliary results that were necessary to show
the lower threshold of Section LABEL:*thm:main:threshold (a). Recall that for
a projection $H$ of $G$, threshold dimension $t\in[n]$ and indices
$(\ell,i,j,d)\in\mathbb{N}_{0}^{4}$ we denote by

$\displaystyle
U_{H,t}\left(\ell,i,j,d\right)\coloneqq\left|\left\\{\left(H_{\ell^{\prime}},H_{i^{\prime}},H_{j^{\prime}},d^{\prime}\right)\in\mathcal{C}(H,t)\mid\left(\ell^{\prime}=\ell\right)\land\left(i^{\prime}=i\right)\land\left(j^{\prime}=j\right)\land\left(d^{\prime}=d\right)\right\\}\right|$

the number of candidate quadruples with fixed indices $(\ell,i,j,d)$. In
addition we denote by

$\displaystyle
I_{H,t}\coloneqq\left\\{(\ell,i,j,d)\in\mathbb{N}_{0}^{4}\mid\left(t\leq\ell\leq\min\left\\{i+j+d,\operatorname{dim}\left(H\right)\right\\}\right)\land(j\leq
i<t)\land(i+d<\ell)\land(d\in\\{0,1,2\\})\right\\}$

the set of all _admissible indices_ and by

$\hat{I}_{H,t}\coloneqq\left\\{(\ell,i,d)\subseteq\mathbb{N}_{0}^{3}\mid\exists
j\colon(\ell,i,j,d)\in I_{H,t}\right\\}$

the set of _admissible triples_.

We begin with explicitly computing the function
$U_{H,t}\left(\ell,i,j,d\right)$.

######  Lemma 5.1.

For $m\in[n]$, let $H$ be a projection of dimension $m$. Then for $t\in[m]$
and $(\ell,i,j,d)\in\mathbb{N}_{0}^{4}$,

$\displaystyle
U_{H,t}\left(\ell,i,j,d\right)=\binom{m}{\ell}\binom{\ell}{i}\binom{\ell-i}{d}\binom{i}{i+j+d-\ell}k^{m+\ell-
i-
j-d}(k-1)^{d}\left(\frac{1}{2}\right)^{\mathbb{1}_{\left\\{i=j\right\\}}}\mathbb{1}_{\left\\{(\ell,i,j,d)\in
I_{H,t}\right\\}}.$ (5.1)

###### Proof.

Note first that by 2.12, the relations $H_{\ell}\subseteq H_{m}$ and
$H_{i}\cup H_{j}\subseteq H_{\ell}$ have to hold. We start by choosing a
projection $H_{\ell}$ in $H_{m}$. There are $\binom{m}{\ell}$ ways to choose
the coordinates in which $H_{\ell}$ will consist of a complete $K_{k}$. In all
other coordinates we can choose any of $k$ vertices, resulting in
$\binom{m}{\ell}k^{m-\ell}$ choices for $H_{\ell}$. Similarly, there are
$\binom{\ell}{i}k^{\ell-i}$ ways to fix a projection $H_{i}$ in $H_{\ell}$.
Next, we aim to fix the $d$ coordinates in which $H_{i}$ and $H_{j}$ differ.
Clearly, $H_{i}$ has to consist of single vertices in these coordinates,
implying that there are $\binom{\ell-i}{d}$ possibilities for choosing those
coordinates and further $(k-1)^{d}$ possibilities for specifying the value of
$H_{j}$ in those coordinates. To recap shortly, we already have specified
$H_{\ell}$ and $H_{i}$ as well as the $d$ coordinates of $H_{j}$ in which it
differs from $H_{i}$.

Continuing with fixing $H_{j}$, let us next assign the $j$ coordinates in
which $H_{j}$ consists of complete graphs. There are $\ell-i-d$ remaining
coordinates, in which $H_{i}$ consists of a single vertex. In each of those
$H_{j}$ has to be a complete $K_{k}$, as otherwise the two projections would
either lie at distance at least three, or not span $H_{\ell}$. Thus, there
only remain $j-(\ell-i-d)=i+j+d-\ell$ coordinates in which $H_{j}$ is complete
and these coordinates can be chosen from any coordinate in which $H_{i}$ is
also complete, resulting in further $\binom{i}{i+j+d-\ell}$ choices. Finally,
it remains to specify the value of $H_{j}$ in the remaining $\ell-j-d$
coordinates in which $H_{j}$ consists of a single vertex, leading to $k^{\ell-
j-d}$ further possibilities. After simplifying the expression, we are left
with a total of
$\binom{m}{\ell}\binom{\ell}{i}\binom{\ell-i}{d}\binom{i}{i+j+d-\ell}k^{m+\ell-
i-j-d}(k-1)^{d}$ possibilities. Lastly, note that in the case $i=j$ a factor
of $2$ is lost due to symmetry and we have to require $(\ell,i,j,d)\in
I_{H_{m},t}$ in order to make sure that the indices $(\ell,i,j,d)$ fulfill the
dimensional constraints posed in 2.12. ∎

Our next aim is to prove 3.2. Similarly as in (3.13), for every projection
$H$, threshold dimension $t\in[n]$ and indices
$(\ell,i,j,d)\in\mathbb{N}_{0}^{4}$ we define

$\displaystyle f_{H,t}\left(\ell,i,j,d\right)\coloneqq
U_{H,t}\left(\ell,i,j,d\right)\Phi(i)\Phi(j),$ (5.2)

and set $t_{*}\coloneqq\left\lfloor 2\sqrt{n}\right\rfloor-2$ as before.
Observe that the functions $c_{\ell}$ in 3.2 are chosen in such a way that for
all $\ell\in[t_{*}]$ we have

$\displaystyle\frac{c_{\ell}}{c_{\ell-1}}\leq\frac{9\sqrt{2}}{10}\leq\frac{9\sqrt{k}}{10},$
(5.3)

which can be verified by simple calculations. To show 3.2 we need the
following auxiliary result.

######  Lemma 5.2.

Let $15\leq m\leq t_{*}$ and let $H$ be a projection of dimension $m$. Then,

$\displaystyle\sum_{(\ell,i,j,d)\in
I_{H,m}}f_{H,m}\left(\ell,i,j,d\right)\leq\left(1+k^{-\frac{m-11}{2}}\right)\left(1+\frac{4}{n}\right)f_{H,m}\left(m,m-2,0,2\right).$

Observe that 5.2 is quite similar to 3.4 and we will prove 5.2 using slightly
more general results than necessary in order for them to be also applicable to
3.4. Let us start by comparing consecutive terms of $\Phi(\cdot)$.

######  Lemma 5.3.

For $j\in[n]\cup\\{0\\}$,

$\displaystyle\frac{\Phi(j+1)}{\Phi(j)}\leq\frac{j+1}{n}k^{\frac{j+5-2\sqrt{n}}{2}}.$

###### Proof.

By the definition (3.8) of $\Phi(\cdot)$ it holds that

$\displaystyle\frac{\Phi(j+1)}{\Phi(j)}=\frac{c_{j+1}p^{\frac{j+1}{2}+1}(j+1)!2^{\frac{-j-1}{2}}(k-1)^{j+1}k^{\frac{(j+1)^{2}+2(j+1)}{4}}}{c_{j}p^{\frac{j}{2}+1}j!2^{\frac{-j}{2}}(k-1)^{j}k^{\frac{j^{2}+2j}{4}}}=\frac{c_{j+1}\sqrt{p}(j+1)k^{\frac{2j+3}{4}}(k-1)}{c_{j}\sqrt{2}}.$
(5.4)

Furthermore, using (5.3) and $p\leq n^{-2}k^{-2\sqrt{n}+1}$ we get

$\displaystyle\frac{c_{j+1}\sqrt{p}(j+1)k^{\frac{2j+3}{4}}(k-1)}{c_{j}\sqrt{2}}\leq\sqrt{p}(j+1)k^{\frac{2j+3}{4}}(k-1)\leq\sqrt{p}(j+1)k^{\frac{j+4}{2}}\leq\frac{j+1}{n}k^{\frac{j+5-2\sqrt{n}}{2}},$

yielding together with (5.4) that

$\displaystyle\frac{\Phi(j+1)}{\Phi(j)}\leq\frac{j+1}{n}k^{\frac{j+5-2\sqrt{n}}{2}},$

as claimed. ∎

In order to prove 5.2, we will now consider the effect it has on
$f_{H,t}\left(\ell,i,j,d\right)$ to change each of the respective indices
$i,j$ and $d$. We will first deal with different values of $j$, then, in 5.5,
consider different values of $i$ and lastly compare different values of $d$ in
5.6 .

######  Lemma 5.4.

For $m\in[n]$, let $H$ be a projection of dimension $m$. Let $15\leq
t\leq\min\left\\{m,t_{*}\right\\}$ and $(\ell,i,d)\in\hat{I}_{H,t}$ such that
$15\leq\ell\leq 3\sqrt{n}$. Then,

$\displaystyle\sum_{j=0}^{i}f_{H,t}\left(\ell,i,j,d\right)\leq
f_{H,t}\left(\ell,i,\ell-i-d,d\right)\left(1+k^{-\frac{\sqrt{n}}{6}}\right).$
(5.5)

###### Proof.

Observe first that $j$ is the only index of $f_{H,t}\left(\ell,i,j,d\right)$
that is not fixed on the left and right hand sides of the inequality in (5.4).
To ease notation, let us define

$\displaystyle F\left(j\right)\coloneqq
f_{H,t}\left(\ell,i,j,d\right)\overset{\eqref{def:ffunc2}}{=}U_{H,t}\left(\ell,i,j,d\right)\Phi(i)\Phi(j)$
(5.6)

and

$j^{*}\coloneqq\ell-i-d.$

By 5.1, for all $j<j^{*}$ or $j\geq t_{*}$ it holds that
$U_{H_{m},t}\left(\ell,i,j,d\right)=0$. For $j^{*}\leq j\leq j+1\leq t_{*}$ we
have

$\displaystyle\frac{U_{H,t}\left(\ell,i,j+1,d\right)}{U_{H,t}\left(\ell,i,j,d\right)}=\frac{\binom{i}{i+j+1+d-\ell}\left(\frac{1}{2}\right)^{\mathbb{1}_{\left\\{i=j+1\right\\}}}}{\binom{i}{i+j+d-\ell}k\left(\frac{1}{2}\right)^{\mathbb{1}_{\left\\{i=j\right\\}}}}\leq\frac{\ell-
j-d}{k(i+j+d+1-\ell)},$

implying together with 5.3 that for all $j\geq j^{*}$

$\displaystyle\frac{F\left(j+1\right)}{F\left(j\right)}$
$\displaystyle{=}\frac{\Phi(i)\Phi(j+1)U_{H,t}\left(\ell,i,j+1,d\right)}{\Phi(i)\Phi(j)U_{H,t}\left(\ell,i,j,d\right)}\leq
k^{\frac{j+3-2\sqrt{n}}{2}}\frac{(j+1)(\ell-d-j)}{n(j+1+i+d-\ell)}$ (5.7)
$\displaystyle\leq 6k^{\frac{j+3-2\sqrt{n}}{2}},$ (5.8)

where the last inequality uses $j+1\leq t_{*}:=\left\lfloor
2\sqrt{n}\right\rfloor-2\leq 2\sqrt{n}$ and $\ell\leq 3\sqrt{n}$.

Next we aim to show that $\frac{F\left(j+1\right)}{F\left(j\right)}\leq 1$.
Indeed, if $j\leq\frac{5\sqrt{n}}{3}$ we obtain from (5.8) that

$\displaystyle\frac{F\left(j+1\right)}{F\left(j\right)}\leq
6k^{\frac{j+3-2\sqrt{n}}{2}}\leq 6k^{-\frac{\sqrt{n}}{7}}\leq 1.$ (5.9)

If $j>\frac{5\sqrt{n}}{3}$, because $j+1\leq t_{*}-1\leq 2\sqrt{n}-3$ and
$j+1+i+d-\ell\geq\frac{10\sqrt{n}}{3}-3\sqrt{n}\geq\frac{\sqrt{n}}{3}$, we
obtain from (5.7)

$\displaystyle\frac{F\left(j+1\right)}{F\left(j\right)}\leq
k^{\frac{j+3-2\sqrt{n}}{2}}\frac{(j+1)(\ell-
d-j)}{n(j+1+i+d-\ell)}\leq\frac{\left(2\sqrt{n}\right)\left(4\sqrt{n}\right)}{n\frac{\sqrt{n}}{3}}\leq\frac{24}{\sqrt{n}}\leq
1.$ (5.10)

It thus follows from (5.9) and (5.10) that

$\frac{F\left(j+1\right)}{F\left(j\right)}\leq 1\quad\text{for all}\quad j\geq
j^{*}$

and hence

$\displaystyle\sum_{j=0}^{i}F\left(j\right)\leq
F\left(j^{*}\right)+iF\left(j^{*}+1\right).$ (5.11)

Furthermore, as $j^{*}\leq i$, it follows from $\ell=i+j^{*}+d$ that
$j^{*}\leq\frac{\ell}{2}\leq\frac{3\sqrt{n}}{2}$, implying together with (5.8)

$\displaystyle\frac{F\left(j^{*}+1\right)}{F\left(j^{*}\right)}\leq
6k^{\frac{j^{*}+3-2\sqrt{n}}{2}}\leq 6k^{\frac{3-\frac{1}{2}\sqrt{n}}{2}}\leq
k^{-\frac{\sqrt{n}}{5}},$

and thus together with (5.11) we have

$\displaystyle\sum_{j=0}^{i}F\left(j\right)\leq
F\left(j^{*}\right)\left(1+ik^{-\frac{\sqrt{n}}{5}}\right)\leq
F\left(j^{*}\right)\left(1+k^{-\frac{\sqrt{n}}{6}}\right),$

as claimed. ∎

We continue by considering different values of $i$. Here we need to make a
case distinction depending on whether $\ell>t_{*}$ or not.

######  Lemma 5.5.

(a) For $t_{*}<\ell\leq 3\sqrt{n}$ and $d\in\\{0,1,2\\}$ it holds that

$\displaystyle\sum_{i=0}^{t_{*}-1}f_{G,t_{*}}\left(\ell,i,\ell-
i-d,d\right)\leq\left(1+k^{-\frac{\sqrt{n}}{6}}\right)f_{G,t_{*}}\left(\ell,t_{*}-1,\ell-(t_{*}-1)-d,d\right).$
(5.12)

(b) For $15\leq m\leq t_{*}$ let $H$ be a projection of dimension $m$. Then
for $d\in\\{0,1,2\\}$ we have

$\displaystyle\sum_{i=0}^{m-1}f_{H,m}\left(m,i,m-i-d,d\right)\leq\left(1+k^{-\frac{m-11}{2}}\right)f_{H,m}\left(m,m-1-\mathbb{1}_{\left\\{d=2\right\\}},1-d+\mathbb{1}_{\left\\{d=2\right\\}},d\right).$
(5.13)

###### Proof.

We first derive some properties that are relevant for both (a) and (b). Assume
$H$ is a projection of $G$ and let $t\in[n]$ (in fact, we will take $t=t_{*}$
for part (a) and $t=m$ for part (b)). To ease notation, for
$(\ell,i,d)\in\hat{I}_{H,t}$ we set $j^{*}:=\ell-i-d$ and define

$\displaystyle\hat{F}_{H,t}\left(i\right)\coloneqq
f_{H,t}\left(\ell,i,j^{*},d\right)\overset{\eqref{def:ffunc2}}{=}U_{H,t}\left(\ell,i,j^{*},d\right)\Phi(i)\Phi(j^{*}).$
(5.14)

We aim to bound the ratio
$\frac{\hat{F}_{H,t}\left(i-1\right)}{\hat{F}_{H,t}\left(i\right)}$ from
above, so let us assume for now that we are on the domain where
$\hat{F}_{H,t}\left(\cdot\right)$ is non-zero. First observe that by (5.4) and
(5.3) it holds that

$\displaystyle\frac{\Phi(i-1)\Phi(j^{*}+1)}{\Phi(i)\Phi(j^{*})}\overset{\eqref{eq:ratio:P(j):equality}}{=}k^{-\frac{i-j^{*}-1}{2}}\frac{c_{i-1}c_{j^{*}+1}}{c_{i}c_{j^{*}}}\frac{(j^{*}+1)}{i}\overset{\eqref{eq:cubeintspanconst_bounds}}{\leq}k^{-\frac{i-j^{*}-2}{2}}\frac{9(j^{*}+1)}{10i}.$
(5.15)

Furthermore, it follows from 5.1 that

$\displaystyle\frac{U_{H,m}\left(\ell,i-1,j^{*}+1,d\right)}{U_{H,m}\left(\ell,i,j^{*},d\right)}=\frac{\binom{\ell}{i-1}\binom{\ell-i+1}{d}}{\binom{\ell}{i}\binom{\ell-i}{d}}\frac{\left(\frac{1}{2}\right)^{\mathbb{1}_{\left\\{i-1=j^{*}+1\right\\}}}}{\left(\frac{1}{2}\right)^{\mathbb{1}_{\left\\{i=j^{*}\right\\}}}}\leq\frac{i(\ell-i+1)}{(\ell-i+1)(\ell-
i-d+1)}=\frac{i}{j^{*}+1}.$ (5.16)

From the definition (5.14) of $\hat{F}_{H,t}\left(\cdot\right)$ as well as
from (5.15) and (5.16) we have

$\displaystyle\frac{\hat{F}_{H,t}\left(i-1\right)}{\hat{F}_{H,t}\left(i\right)}$
$\displaystyle{=}\frac{\Phi(i-1)\Phi(j^{*}+1)U_{H,m}\left(\ell,i-1,j^{*}+1,d\right)}{\Phi(i)\Phi(j^{*})U_{H,m}\left(\ell,i,j^{*},d\right)}$
$\displaystyle{\leq}k^{-\frac{i-j^{*}-2}{2}}\frac{9(j^{*}+1)}{10i}\frac{i}{j^{*}+1}$
$\displaystyle=k^{-\frac{i-j^{*}-2}{2}}\frac{9}{10}$ (5.17)
$\displaystyle<k^{-\frac{i-j^{*}-2}{2}}.$ (5.18)

From (5.17) we obtain

$\displaystyle\frac{\hat{F}_{H,t}\left(i-1\right)}{\hat{F}_{H,t}\left(i\right)}$
$\displaystyle\leq\frac{9}{10},$ (5.19)

because $i-1\geq j^{*}+1$ on the domain where $\hat{F}_{H,t}\left(i-1\right)$
is non-zero. Thus the function $i\mapsto\hat{F}_{H,t}\left(i\right)$ is
increasing in $i$ and it remains to determine the largest value of $i$ at
which $\hat{F}_{H,t}\left(i\right)$ is non-zero. We proceed now with a case
distinction, starting with the proof of (5.12).

To prove part (a) take $H=G$ and $t=t_{*}$. In this case, the largest value
$i$ may take is at $i=t_{*}-1$ at which $j^{*}:=\ell-i-d=\ell-t_{*}-d+1$.
Checking all conditions from the definition of the set $I_{G,t_{*}}$ of
admissible indices it indeed holds that $(\ell,t_{*}-1,j^{*},d)\in
I_{G,t_{*}}$ and thus it follows from (5.19) that

$\displaystyle\sum_{i=0}^{t_{*}-1}\hat{F}_{G,t_{*}}\left(i\right)\overset{\eqref{eq:ffunc:diagonalbound2}}{\leq}\hat{F}_{G,t_{*}}\left(t_{*}-1\right)+\hat{F}_{G,t_{*}}\left(t_{*}-2\right)\sum_{i=0}^{t_{*}-2}\left(\frac{9}{10}\right)^{i}\leq\hat{F}_{G,t_{*}}\left(t_{*}-1\right)+10\hat{F}_{G,t_{*}}\left(t_{*}-2\right),$
(5.20)

where the last inequality follows from a standard bound on geometric series.
Furthermore, it follows from (5.18) (by taking $H=G$, $t=t_{*}$, $i=t_{*}-1$
and $j^{*}:=\ell-i-d$) that

$\displaystyle\frac{\hat{F}_{G,t_{*}}\left(t_{*}-2\right)}{\hat{F}_{G,t_{*}}\left(t_{*}-1\right)}\overset{\eqref{eq:ffunc:diagonalbound}}{\leq}k^{-\frac{(t_{*}-1)-(\ell-
t_{*}+1-d)-2}{2}}\leq k^{-\frac{\sqrt{n}}{4}},$ (5.21)

where the last inequality is because $(t_{*}-1)-(\ell-t_{*}+1-d)-2\geq
2t_{*}-\ell-4\geq\frac{\sqrt{n}}{2}$. Combining (5.20) and (5.21) implies

$\displaystyle\sum_{i=0}^{t_{*}-1}\hat{F}_{G,t_{*}}\left(i\right)\overset{\eqref{eq:sumdom:i:eq3}}{\leq}\hat{F}_{G,t_{*}}\left(t_{*}-1\right)\left(1+\frac{10\hat{F}_{G,t_{*}}\left(t_{*}-2\right)}{\hat{F}_{G,t_{*}}\left(t_{*}-1\right)}\right)$
$\displaystyle{\leq}\hat{F}_{G,t_{*}}\left(t_{*}-1\right)\left(1+10k^{-\frac{\sqrt{n}}{4}}\right)$
$\displaystyle\leq\hat{F}_{G,t_{*}}\left(t_{*}-1\right)\left(1+k^{-\frac{\sqrt{n}}{6}}\right),$

and thus obtaining (5.12).

To prove part (b) let $H$ be a projection of dimension $m$ and assume $15\leq
m\leq t_{*}$. Consider the function $\hat{F}_{H,m}\left(i\right)$ as defined
in (5.14) by taking $\ell=m$. Recalling that $i$ now may take values from $0$
to $m-1$, it follows from the definition of the set $I_{G,t_{*}}$ of
admissible indices that $\hat{F}_{H,m}\left(i\right)$ is only zero in the case
$i=m-1$ and $d=2$. Thus, $\hat{F}_{H,m}\left(i\right)$ takes its largest value
at $i=m-1$ if $d\in\left\\{0,1\right\\}$, and at $i=m-2$ if $d=2$. Hence, it
follows (analogously to (5.20)) from (5.19) that

$\displaystyle\sum_{i=0}^{m-1}\hat{F}_{H,m}\left(i\right)$
$\displaystyle{\leq}\hat{F}_{H,m}\left(m-1-\mathbb{1}_{\left\\{d=2\right\\}}\right)+\hat{F}_{H,m}\left(m-2-\mathbb{1}_{\left\\{d=2\right\\}}\right)\sum_{i=0}^{m-2}\left(\frac{9}{10}\right)^{i}$
$\displaystyle\leq\hat{F}_{H,m}\left(m-1-\mathbb{1}_{\left\\{d=2\right\\}}\right)+10\hat{F}_{H,m}\left(m-2-\mathbb{1}_{\left\\{d=2\right\\}}\right).$
(5.22)

Furthermore, if $d\in\left\\{0,1\right\\}$, we obtain from (5.18) (by taking
$t=m$, $i=m-1$ and $j^{*}:=\ell-i-d=m-i-d=1-d$) that

$\displaystyle\frac{\hat{F}_{H,m}\left(m-2\right)}{\hat{F}_{H,m}\left(m-1\right)}\overset{\eqref{eq:ffunc:diagonalbound}}{\leq}k^{-\frac{m-1-(1-d)-2}{2}}\leq
k^{-\frac{m-4}{2}},$ (5.23)

and, if $d=2$, it also follows from (5.18) (by taking $t=m$, $i=m-2$ and
$j^{*}:=\ell-i-d=m-i-2=0$) that

$\displaystyle\frac{\hat{F}_{H,m}\left(m-3\right)}{\hat{F}_{H,m}\left(m-2\right)}\overset{\eqref{eq:ffunc:diagonalbound}}{\leq}k^{-\frac{m-4}{2}}.$
(5.24)

Combining (5), (5.23) and (5.24) implies

$\displaystyle\sum_{i=0}^{m-1}\hat{F}_{H,m}\left(i\right)$
$\displaystyle{\leq}\hat{F}_{H,m}\left(m-1-\mathbb{1}_{\left\\{d=2\right\\}}\right)\left(1+\frac{10\hat{F}_{H,m}\left(m-2-\mathbb{1}_{\left\\{d=2\right\\}}\right)}{\hat{F}_{H,m}\left(m-1-\mathbb{1}_{\left\\{d=2\right\\}}\right)}\right)$
$\displaystyle{\leq}\hat{F}_{H,m}\left(m-1-\mathbb{1}_{\left\\{d=2\right\\}}\right)\left(1+10k^{-\frac{m-4}{2}}\right)$
$\displaystyle\leq\hat{F}_{H,m}\left(m-1-\mathbb{1}_{\left\\{d=2\right\\}}\right)\left(1+k^{-\frac{m-11}{2}}\right),$

where we used the fact that $10\leq 2^{\frac{7}{2}}\leq k^{\frac{7}{2}}$,
completing the proof. ∎

Next, we consider all the possible values of $d\in\\{0,1,2\\}$.

######  Lemma 5.6.

(a) For $t_{*}<\ell\leq 3\sqrt{n}$ it holds that

$\displaystyle\sum_{d=0}^{2}f_{G,t_{*}}\left(\ell,t_{*}-1,\ell-(t_{*}-1)-d,d\right)\leq\left(1+k^{-\frac{\sqrt{n}}{6}}\right)f_{G,t_{*}}\left(\ell,t_{*}-1,\ell-
t_{*}-1,2\right).$ (5.25)

(b) For $15\leq m\leq t_{*}$ let $H$ be a projection of dimension $m$. Then we
have

$\displaystyle\sum_{d=0}^{2}f_{H,m}\left(m,m-1-\mathbb{1}_{\left\\{d=2\right\\}},1-d+\mathbb{1}_{\left\\{d=2\right\\}},d\right)\leq\left(1+\frac{3}{n}\right)f_{H,m}\left(m,m-2,0,2\right).$
(5.26)

###### Proof.

Let us start with (5.25). Note first that the function $d\mapsto
U_{G,t_{*}}\left(\ell,t_{*}-1,\ell-(t_{*}-1)-d,d\right)$ is clearly increasing
in $d$. Using 5.3 it thus follows that for $d\in\\{0,1\\}$,

$\displaystyle\frac{f_{G,t_{*}}\left(\ell,t_{*}-1,\ell-(t_{*}-1)-d,d\right)}{f_{G,t_{*}}\left(\ell,t_{*}-1,\ell-(t_{*}-1)-d-1,d+1\right)}\leq\frac{\Phi(\ell-
t_{*}-d+1)}{\Phi(\ell-t_{*}-d)}\leq\frac{\ell-t_{*}-d+1}{n}k^{\frac{\ell-
t_{*}-d+5-2\sqrt{n}}{2}}\leq\frac{1}{2}k^{-\frac{\sqrt{n}}{6}},$

where the last inequality uses $\ell-t_{*}-d+1\leq\sqrt{n}+4$, immediately
implying (5.25).

Moving on to the case $15\leq m\leq t_{*}$, an analogous argument shows that

$\displaystyle\frac{f_{H,m}\left(m,m-1,1,0\right)}{f_{H,m}\left(m,m-1,0,1\right)}\leq\frac{1}{2}.$
(5.27)

For the ratio
$\frac{f_{H,m}\left(m,m-1,0,1\right)}{f_{H,m}\left(m,m-2,0,2\right)}$ we need
to be a bit more precise. A direct computation shows that

$\displaystyle\frac{U_{H,m}\left(m,m-1,0,1\right)}{U_{H,m}\left(m,m-2,0,2\right)}=\frac{2}{(k-1)(m-1)}$
(5.28)

and, being a bit more careful in the estimates in 5.3, it can be shown that

$\displaystyle\frac{\Phi(m-1)}{\Phi(m-2)}\leq\frac{(k-1)(m-1)}{n}k^{\frac{m+2-2\sqrt{n}}{2}}.$
(5.29)

Putting these together, we obtain

$\displaystyle\frac{f_{H,m}\left(m,m-1,0,1\right)}{f_{H,m}\left(m,m-2,0,2\right)}$
$\displaystyle{=}\frac{U_{H,m}\left(m,m-1,0,1\right)}{U_{H,m}\left(m,m-2,0,2\right)}\frac{\Phi(m-1)}{\Phi(m-2)}$
$\displaystyle{\leq}\frac{2}{(k-1)(m-1)}\frac{\Phi(m-1)}{\Phi(m-2)}$
$\displaystyle{\leq}\frac{2}{(k-1)(m-1)}\frac{(k-1)(m-1)}{n}k^{\frac{m+2-2\sqrt{n}}{2}}\leq\frac{2}{n},$
(5.30)

where the last inequality uses $m\leq t_{*}:=\left\lfloor
2\sqrt{n}\right\rfloor-2\leq 2\sqrt{n}-2$. Combining (5.27) and (5) now yields

$\displaystyle\sum_{d=0}^{2}f_{H,m}\left(m,m-1-\mathbb{1}_{\left\\{d=2\right\\}},1-d+\mathbb{1}_{\left\\{d=2\right\\}},d\right)$
$\displaystyle{\leq}\frac{3}{2}f_{H,m}\left(m,m-1,0,1\right)+f_{H,m}\left(m,m-2,0,2\right)$
$\displaystyle{\leq}\left(1+\frac{3}{n}\right)f_{H,m}\left(m,m-2,0,2\right),$

completing the proof. ∎

Now we have all the tools to show 5.2.

###### Proof of 5.2.

Let $15\leq m\leq t_{*}$ and let $H$ be a projection of dimension $m$. Observe
first that by definition of $I_{H,m}$, any indices $(\ell,i,j,d)\in I_{H,m}$
have to satisfy $\ell=m,\ d\in\left\\{0,1,2\right\\}$ and $0\leq j\leq
i\leq\ell-1$. It thus follows from 5.4 that

$\displaystyle\sum_{(\ell,i,j,d)\in I_{H,m}}f_{H,m}\left(\ell,i,j,d\right)$
$\displaystyle=\sum_{d=0}^{2}\sum_{i=0}^{m-1}\sum_{j=0}^{i}f_{H,m}\left(m,i,j,d\right)$
$\displaystyle{\leq}\left(1+k^{-\frac{\sqrt{n}}{6}}\right)\sum_{d=0}^{2}\sum_{i=0}^{m-1}f_{H,m}\left(m,i,m-i-d,d\right).$
(5.31)

Furthermore, by Lemmas 5.5 (b) and 5.6 (b) we obtain

$\displaystyle\sum_{d=0}^{2}\sum_{i=0}^{m-1}f_{H,m}\left(m,i,m-i-d,d\right)$
$\displaystyle{\leq}\left(1+k^{-\frac{m-11}{2}}\right)\sum_{d=0}^{2}f_{H,m}\left(m,m-1-\mathbb{1}_{\left\\{d=2\right\\}},1-d+\mathbb{1}_{\left\\{d=2\right\\}},d\right)$
$\displaystyle{\leq}\left(1+k^{-\frac{m-11}{2}}\right)\left(1+\frac{3}{n}\right)f_{H,m}\left(m,m-2,0,2\right).$
(5.32)

Combining (5) and (5.32) yields

$\displaystyle\sum_{(\ell,i,j,d)\in I_{H,m}}f_{H,m}\left(\ell,i,j,d\right)$
$\displaystyle\leq\left(1+k^{-\frac{\sqrt{n}}{6}}\right)\left(1+k^{-\frac{m-11}{2}}\right)\left(1+\frac{3}{n}\right)f_{H,m}\left(m,m-2,0,2\right)$
$\displaystyle\leq\left(1+k^{-\frac{m-11}{2}}\right)\left(1+\frac{4}{n}\right)f_{H,m}\left(m,m-2,0,2\right),$

where the last inequality is because
$\left(1+k^{-\frac{\sqrt{n}}{6}}\right)\left(1+\frac{3}{n}\right)\leq\left(1+\frac{4}{n}\right)$
holds for large enough $n$. ∎

5.2 now enables us to prove 3.2.

###### Proof of 3.2.

We will show the statement by induction on $m$. The case $0\leq m\leq 14$ can
easily be proved by a tedious enumeration and will be omitted. Below we assume
$15\leq m\leq t_{*}$. Let $H$ be a projection of dimension $m$ and assume that
$\varphi({m^{\prime}})\leq\Phi(m^{\prime})$ for all $m^{\prime}<m$. By 3.1 and
using the induction hypothesis we obtain analogously as in (3.9) that

$\displaystyle\varphi({m})$ $\displaystyle\leq\sum_{(\ell,i,j,d)\in
I_{H,m}}U_{H_{m},m}\left(\ell,i,j,d\right)\varphi({i})\varphi({j})\leq\sum_{(\ell,i,j,d)\in
I_{H,m}}U_{H,m}\left(\ell,i,j,d\right)\Phi(i)\Phi(j)$
$\displaystyle=\sum_{(\ell,i,j,d)\in I_{H,m}}f_{H,m}\left(\ell,i,j,d\right).$

Furthermore, 5.2 implies

$\displaystyle\sum_{(\ell,i,j,d)\in
I_{H,m}}f_{H,m}\left(\ell,i,j,d\right)\leq\left(1+k^{-\frac{m-11}{2}}\right)\left(1+\frac{4}{n}\right)f_{H,m}\left(m,m-2,0,2\right),$

yielding

$\displaystyle\varphi({m})\leq\left(1+k^{-\frac{m-11}{2}}\right)\left(1+\frac{4}{n}\right)f_{H,m}\left(m,m-2,0,2\right).$
(5.33)

By the definition of $\Phi(\cdot)$ and by 5.1 it holds that

$\displaystyle f_{H,m}\left(m,m-2,0,2\right)$
$\displaystyle=\Phi(m-2)\Phi(0)U_{H,m}\left(m,m-2,0,2\right)$
$\displaystyle=c_{m-2}p^{\frac{m-2}{2}+1}(m-2)!\
2^{-\frac{m-2}{2}}(k-1)^{m-2}k^{\frac{(m-2)^{2}+2(m-2)}{4}}p\binom{m}{2}(k-1)^{2}k^{m}$
$\displaystyle=c_{m-2}p^{\frac{m}{2}+1}m!\
2^{-\frac{m}{2}}(k-1)^{m}k^{\frac{m^{2}+2m}{4}}$
$\displaystyle=\frac{c_{m-2}}{c_{m}}\Phi(m).$ (5.34)

Using
$\left(1+k^{-\frac{m-11}{2}}\right)\left(1+\frac{4}{n}\right)=\frac{c_{m}}{c_{m-1}}\leq\frac{c_{m}}{c_{m-2}}$,
it follows together with (5.34) that

$\displaystyle\left(1+k^{-\frac{m-11}{2}}\right)\left(1+\frac{4}{n}\right)f_{H,m}\left(m,m-2,0,2\right)\leq\frac{c_{m}}{c_{m-2}}\frac{c_{m-2}}{c_{m}}\Phi(m)\leq\Phi(m).$
(5.35)

Combining (5.33) and (5.35) we obtain

$\displaystyle\varphi({m})\overset{\eqref{eq:proof:upboundcubeintspan:eq2}}{\leq}\left(1+k^{-\frac{m-11}{2}}\right)\left(1+\frac{4}{n}\right)f_{H,m}\left(m,m-2,0,2\right)\overset{\eqref{eq:proof:upboundcubeintspan:eq3}}{\leq}\Phi(m),$

completing the induction and thus the proof. ∎

Next, we show that the functions $c_{m}$ are bounded from above by a universal
constant.

######  Lemma 5.7.

For all $m\in[t_{*}]$ we have

$\displaystyle c_{m}=\Theta\left(1\right).$

###### Proof.

It is easy to see that the function $m\mapsto c_{m}$ is increasing in $m$.
Thus, it suffices to bound $c_{t_{*}}$ from above and we obtain

$\displaystyle c_{t_{*}}$
$\displaystyle=\frac{1}{2}\left(\frac{9\sqrt{2}}{10}\right)^{14}\prod_{m=15}^{t_{*}}\left(1+k^{-\frac{m-11}{2}}\right)\left(1+\frac{4}{n}\right)$
$\displaystyle\leq\Theta(1)\left(1+\frac{4}{n}\right)^{t_{*}}\prod_{m=15}^{t_{*}}\exp\left(k^{-\frac{m-11}{2}}\right)$
$\displaystyle\leq\Theta(1)\exp\left(\frac{4t_{*}}{n}\right)\exp\left(\sum_{m=0}^{\infty}k^{-\frac{m}{2}}\right)=\Theta(1),$

where the last equality follows because $t_{*}:=\left\lfloor
2\sqrt{n}\right\rfloor-2\leq n$. ∎

We continue by proving 3.3.

###### Proof of 3.3.

We aim to bound the function $f_{G,t_{*}}\left(\ell,i,j,d\right)$ for all
indices $(\ell,i,j,d)\in I_{G,t_{*}}^{(2)}$. Using crude bounds we get

$\displaystyle U_{G,t_{*}}\left(\ell,i,j,d\right)$
$\displaystyle\leq\binom{n}{\ell}\binom{\ell}{i}\binom{\ell-i}{d}\binom{i}{j+i+d-\ell}k^{n+\ell-
i-j-d}(k-1)^{d}$ $\displaystyle\leq
n^{\ell}\ell^{i+d}i^{j+i+d-\ell}k^{n+\ell}$ $\displaystyle\leq
n^{3\ell}k^{n+\ell}.$ (5.36)

On the other hand, by the definition (3.8) of $\Phi(\cdot)$ and using $j!\leq
i!\leq n^{\ell}$ and 5.7 we obtain

$\displaystyle\Phi(i)\Phi(j)$
$\displaystyle{=}c_{i}c_{j}p^{\frac{i+j}{2}+2}(i!)(j!)2^{-\frac{i+j}{2}}(k-1)^{2(i+j)}k^{\frac{1}{4}\left(i^{2}+j^{2}+2i+2j\right)}$
$\displaystyle\leq\Theta\left(1\right)p^{\frac{i+j}{2}+2}n^{2\ell}k^{\frac{1}{4}\left(i^{2}+j^{2}+10i+10j\right)}.$

Furthermore, using $p\leq p_{*}\leq k^{-2\sqrt{n}+1}$ it follows that

$\displaystyle\Phi(i)\Phi(j)\leq\Theta\left(1\right)n^{2\ell}k^{\frac{1}{4}\left(i^{2}+j^{2}-(i+j)(4\sqrt{n}-12)+16\sqrt{n}-8\right)}.$
(5.37)

In order to obtain a universal upper bound of (5.37) for all indices $(i,j)$
under consideration, we focus on the exponent of (5.37) and consider the
function

$h:\mathbb{R}^{2}\to\mathbb{R},(x,y)\mapsto
x^{2}+y^{2}-(x+y)(4\sqrt{n}-12)+16\sqrt{n}-8.$

Note that the function $h(x,y)$ defines a circular paraboloid whose center is
shifted to $(2\sqrt{n}-6,2\sqrt{n}-6)$. Recalling $(\ell,i,j,d)\in
I_{G,t_{*}}^{(2)}$, where

$\displaystyle
I_{G,t_{*}}^{(2)}\coloneqq\left\\{(\ell,i,j,d)\in\mathbb{N}_{0}^{4}\mid\left(3\sqrt{n}<\ell\leq\min\left\\{i+j+d,\operatorname{dim}\left(G\right)\right\\}\right)\land(j\leq
i<t_{*})\land(i+d<\ell)\land(d\in\\{0,1,2\\})\right\\},$

we note that the function $h(x,y)$ should however be considered only for
$(i,j)\in\tilde{I}$, where

$\tilde{I}:=\left\\{(i,j)\in\mathbb{N}_{0}^{2}\mid(j\leq
i<t_{*})\wedge(i+j\geq\ell-d\geq 3\sqrt{n}-1)\text{ for
}d\in\\{0,1,2\\}\right\\}.$

Hence, the (shifted circular paraboloid) function $h:\tilde{I}\to\mathbb{R}$
takes its maximum when $i$ is maximal and $j$ is minimal possible on the
domain $\tilde{I}$, in other words, the maximiser of the function $h$
restricted on the domain $\tilde{I}$ is given by $i=t_{*}-1=\left\lfloor
2\sqrt{n}\right\rfloor-3$ and $j=\left\lceil
3\sqrt{n}\right\rceil-1-i=\left\lceil 3\sqrt{n}\right\rceil-\left\lfloor
2\sqrt{n}\right\rfloor+2$. Relaxing the domain $\tilde{I}$ of $h$ to the
reals, it follows that at the function $h:\tilde{I}\to\mathbb{R}$ is upper
bounded by $h(2\sqrt{n}-3,\sqrt{n}+2)=-7n+48\sqrt{n}-7\leq-6n$, implying
together with (5.37) that

$\displaystyle\Phi(i)\Phi(j)\leq\Theta\left(1\right)n^{2\ell}k^{-\frac{3n}{2}}.$
(5.38)

Combining (5) and (5.38) and plugging into the definition (5.2) of
$f_{G,t_{*}}$, we obtain that for large enough $n$ and for all
$(\ell,i,j,d)\in I_{G,t_{*}}^{(2)}$,

$\displaystyle f_{G,t_{*}}\left(\ell,i,j,d\right)$
$\displaystyle{=}\Phi(i)\Phi(j)U_{G,t_{*}}\left(\ell,i,j,d\right)$
$\displaystyle{\leq}\Theta\left(1\right)n^{5\ell}k^{-\frac{n}{2}+\ell}\leq
n^{20\sqrt{n}}k^{-\frac{n}{3}}=o(n^{-3}),$ (5.39)

where the penultimate inequality uses that $\ell\leq i+j+d\leq 2t_{*}\leq
4\sqrt{n}$. Hence, by the definition of $I_{G,t_{*}}^{(2)}$ and (5) it holds
that

$\displaystyle\sum_{(\ell,i,j,d)\in
I_{G,t_{*}}^{(2)}}f_{G,t_{*}}\left(\ell,i,j,d\right)$
$\displaystyle=\sum_{\ell=3\sqrt{n}+1}^{4\sqrt{n}}\sum_{d=0}^{2}\sum_{i=0}^{t_{*}-1}\sum_{j=0}^{i}f_{G,t_{*}}\left(\ell,i,j,d\right)$
$\displaystyle\leq 3n^{3}\max_{(\ell,i,j,d)\in
I_{G,t_{*}}^{(2)}}f_{G,t_{*}}\left(\ell,i,j,d\right)\overset{\eqref{eq:prf_of_expec_to_zero_largeterms:4}}{=}o(1).$

∎

Moving on, we now aim to show 3.4. As mentioned before, the proof of 3.4 goes
along similar lines as the proof of 5.2, however in addition to dealing with
different values of $i,j$ and $d$, we now also have to consider different
values of $\ell$.

######  Lemma 5.8.

It holds that

$\displaystyle\sum_{\ell=t_{*}+1}^{3\sqrt{n}}f_{G,t_{*}}\left(\ell,t_{*}-1,\ell-
t_{*}-1,2\right)\leq
2k^{\frac{1}{2}}f_{G,t_{*}}\left(t_{*},t_{*}-2,0,2\right).$ (5.40)

###### Proof.

To ease notation, let us define for $t_{*}+1\leq\ell\leq 3\sqrt{n}$

$\displaystyle\bar{F}\left(\ell\right)\coloneqq
f_{G,t_{*}}\left(\ell,t_{*}-1,\ell-t_{*}-1,2\right)$

and consider the ratio

$\displaystyle\frac{\bar{F}\left(\ell+1\right)}{\bar{F}\left(\ell\right)}=\frac{\Phi(\ell-
t_{*})}{\Phi(\ell-t_{*}-1)}\frac{U_{G,t_{*}}\left(\ell+1,t_{*}-1,\ell-
t_{*},2\right)}{U_{G,t_{*}}\left(\ell,t_{*}-1,\ell-t_{*}-1,2\right)}.$

Using 5.3 and $\ell-t_{*}\leq\sqrt{n}+2$ we obtain

$\displaystyle\frac{\Phi(\ell-t_{*})}{\Phi(\ell-t_{*}-1)}\leq\frac{(\ell-
t_{*})}{n}k^{\frac{1}{2}\left(\ell-t_{*}+4-2\sqrt{n}\right)}\leq
k^{-\frac{\sqrt{n}}{3}}.$ (5.41)

Furthermore, we get

$\displaystyle\frac{U_{G,t_{*}}\left(\ell+1,t_{*}-1,\ell-
t_{*},2\right)}{U_{G,t_{*}}\left(\ell,t_{*}-1,\ell-
t_{*}-1,2\right)}=\frac{\binom{n}{\ell+1}\binom{\ell+1}{t_{*}-1}\binom{\ell-
t_{*}+2}{2}}{\binom{n}{\ell}\binom{\ell}{t_{*}-1}\binom{\ell-
t_{*}+1}{2}}=\frac{n-\ell}{\ell-t_{*}}\leq n,$

implying together with (5.41)

$\displaystyle\frac{\bar{F}\left(\ell+1\right)}{\bar{F}\left(\ell\right)}\leq
nk^{-\frac{\sqrt{n}}{3}}\leq\frac{1}{2}.$

It thus follows that

$\displaystyle\sum_{\ell=t_{*}+1}^{3\sqrt{n}}\bar{F}\left(\ell\right)\leq
2\bar{F}\left(t_{*}+1\right).$ (5.42)

On the other hand, using Lemmas 5.1 and 5.3 we obtain

$\displaystyle\frac{\bar{F}\left(t_{*}+1\right)}{f_{G,t_{*}}\left(t_{*},t_{*}-2,0,2\right)}$
$\displaystyle=\frac{\Phi(t_{*}-1)}{\Phi(t_{*}-2)}\frac{U_{G,t_{*}}\left(t_{*}+1,t_{*}-1,0,2\right)}{U_{G,t_{*}}\left(t_{*},t_{*}-2,0,2\right)}$
$\displaystyle\leq\frac{t_{*}-1}{n}k^{\frac{1}{2}\left(t_{*}+3-2\sqrt{n}\right)}\frac{\binom{n}{t_{*}+1}\binom{t_{*}+1}{2}}{\binom{n}{t_{*}}\binom{t_{*}}{2}}\leq\frac{(n-t_{*})k^{\frac{1}{2}}}{n}\leq
k^{\frac{1}{2}},$

where the penultimate inequality uses $t_{*}:=\left\lfloor
2\sqrt{n}\right\rfloor-2\leq 2\sqrt{n}-2$.

Combining with (5.42) we thus obtain

$\displaystyle\sum_{\ell=t_{*}+1}^{3\sqrt{n}}\bar{F}\left(\ell\right)\leq
2\bar{F}\left(t_{*}+1\right)\leq
2k^{\frac{1}{2}}f_{G,t_{*}}\left(t_{*},t_{*}-2,0,2\right),$

completing the proof. ∎

5.8 provides us with the final ingredient to prove 3.4.

###### Proof of 3.4.

Let us partition $I_{G,t_{*}}^{(1)}$ into
$I_{G,t_{*}}^{(1)}=I_{G,t_{*}}^{(a)}\cup I_{G,t_{*}}^{(b)}$, where

$\displaystyle I_{G,t_{*}}^{(a)}\coloneqq\left\\{(\ell,i,j,d)\in
I_{G,t_{*}}^{(1)}\mid\ell=t_{*}\right\\}\ \text{ and }\
I_{G,t_{*}}^{(b)}\coloneqq\left\\{(\ell,i,j,d)\in
I_{G,t_{*}}^{(1)}\mid\ell\geq t_{*}+1\right\\}.$

Starting with the sum over indices in $I_{G,t_{*}}^{(b)}$, we observe that

$\displaystyle\sum_{(\ell,i,j,d)\in
I_{G,t_{*}}^{(b)}}f_{G,t_{*}}\left(\ell,i,j,d\right)=\sum_{\ell=t_{*}+1}^{3\sqrt{n}}\sum_{d=0}^{2}\sum_{i=0}^{t_{*}-1}\sum_{j=0}^{i}f_{G,t_{*}}\left(\ell,i,j,d\right).$
(5.43)

Using 5.4 and 5.5 (a) we obtain

$\displaystyle\sum_{\ell=t_{*}+1}^{3\sqrt{n}}\sum_{d=0}^{2}\sum_{i=0}^{t_{*}-1}\sum_{j=0}^{i}f_{G,t_{*}}\left(\ell,i,j,d\right)$
$\displaystyle{\leq}\left(1+k^{-\frac{\sqrt{n}}{6}}\right)\sum_{\ell=t_{*}+1}^{3\sqrt{n}}\sum_{d=0}^{2}\sum_{i=0}^{\ell-1}f_{G,t_{*}}\left(\ell,i,\ell-
i-d,d\right)$
$\displaystyle{\leq}\left(1+k^{-\frac{\sqrt{n}}{6}}\right)^{2}\sum_{\ell=t_{*}+1}^{3\sqrt{n}}\sum_{d=0}^{2}f_{G,t_{*}}\left(\ell,t_{*}-1,\ell-(t_{*}-1)-d,d\right),$

and furthermore, by 5.6 (a) and 5.8

$\displaystyle\left(1+k^{-\frac{\sqrt{n}}{6}}\right)^{2}\sum_{\ell=t_{*}+1}^{3\sqrt{n}}\sum_{d=0}^{2}f_{G,t_{*}}\left(\ell,t_{*}-1,\ell-(t_{*}-1)-d,d\right)$
$\displaystyle{\leq}\left(1+k^{-\frac{\sqrt{n}}{6}}\right)^{3}\sum_{\ell=t_{*}+1}^{3\sqrt{n}}f_{G,t_{*}}\left(\ell,t_{*}-1,\ell-
t_{*}-1,2\right)$
$\displaystyle{\leq}\left(1+k^{-\frac{\sqrt{n}}{6}}\right)^{3}2k^{\frac{1}{2}}f_{G,t_{*}}\left(t_{*},t_{*}-2,0,2\right)$
$\displaystyle\leq 3k^{\frac{1}{2}}f_{G,t_{*}}\left(t_{*},t_{*}-2,0,2\right),$

which yields together with (5.43)

$\displaystyle\sum_{(\ell,i,j,d)\in
I_{G,t_{*}}^{(b)}}f_{G,t_{*}}\left(\ell,i,j,d\right)\leq
3k^{\frac{1}{2}}f_{G,t_{*}}\left(t_{*},t_{*}-2,0,2\right).$ (5.44)

To bound the sum over indices in $I_{G,t_{*}}^{(a)}$, observe first that by
5.1 it holds that for any indices $(\ell,i,j,d)\in I_{G,t_{*}}^{(a)}$ and any
projection $H$ of dimension $t_{*}$,

$\displaystyle
U_{G,t_{*}}\left(\ell,i,j,d\right)=\binom{n}{t_{*}}k^{n-t_{*}}U_{H,t_{*}}\left(\ell,i,j,d\right),$

implying

$\displaystyle
f_{G,t_{*}}\left(\ell,i,j,d\right)=\binom{n}{t_{*}}k^{n-t_{*}}f_{H,t_{*}}\left(\ell,i,j,d\right).$
(5.45)

Furthermore, it follows by 5.2 that

$\displaystyle\sum_{(\ell,i,j,d)\in
I_{G,t_{*}}^{(a)}}f_{H_{t_{*}},t_{*}}\left(\ell,i,j,d\right)$
$\displaystyle\leq\left(1+k^{-\frac{t_{*}-11}{2}}\right)\left(1+\frac{4}{n}\right)f_{H_{t_{*}},t_{*}}\left(t_{*},t_{*}-2,0,2\right)$
$\displaystyle\leq 2f_{H_{t_{*}},t_{*}}\left(t_{*},t_{*}-2,0,2\right),$ (5.46)

yielding together with (5.45) that for large enough $n$

$\displaystyle\sum_{(\ell,i,j,d)\in
I_{G,t_{*}}^{(a)}}f_{G,t_{*}}\left(\ell,i,j,d\right)$
$\displaystyle{=}\binom{n}{t_{*}}k^{n-t_{*}}\sum_{(\ell,i,j,d)\in
I_{G,t_{*}}^{(a)}}f_{H_{t_{*}},t_{*}}\left(\ell,i,j,d\right)$
$\displaystyle{\leq}2\binom{n}{t_{*}}k^{n-t_{*}}f_{H_{t_{*}},t_{*}}\left(t_{*},t_{*}-2,0,2\right)$
$\displaystyle{=}2f_{G,t_{*}}\left(t_{*},t_{*}-2,0,2\right).$ (5.47)

Finally, using $I_{G,t_{*}}^{(1)}=I_{G,t_{*}}^{(a)}\cup I_{G,t_{*}}^{(b)}$ and
combining (5.47) and (5.44) we have

$\displaystyle\sum_{(\ell,i,j,d)\in
I_{G,t_{*}}^{(1)}}f_{G,t_{*}}\left(\ell,i,j,d\right)$
$\displaystyle=\sum_{(\ell,i,j,d)\in
I_{G,t_{*}}^{(a)}}f_{G,t_{*}}\left(\ell,i,j,d\right)+\sum_{(\ell,i,j,d)\in
I_{G,t_{*}}^{(b)}}f_{G,t_{*}}\left(\ell,i,j,d\right)$ $\displaystyle\leq
5k^{\frac{1}{2}}f_{G,t_{*}}\left(t_{*},t_{*}-2,0,2\right),$

as desired. ∎

We continue by showing 3.5.

###### Proof of 3.5.

As a special case of (5.45) it holds that

$\displaystyle
f_{G,t_{*}}\left(t_{*},t_{*}-2,0,2\right)=\binom{n}{t_{*}}k^{n-t_{*}}f_{H_{t_{*}},t_{*}}\left(t_{*},t_{*}-2,0,2\right).$

In addition, as a special case of (5.34) we have
$f_{H,t_{*}}\left(t_{*},t_{*}-2,0,2\right)\leq\frac{c_{t_{*}-2}}{c_{t_{*}}}\Phi(t_{*})$
and thus

$\displaystyle
f_{H_{t_{*}},t_{*}}\left(t_{*},t_{*}-2,0,2\right)\leq\frac{c_{t_{*}-2}}{c_{t_{*}}}\Phi(t_{*})\leq\Phi(t_{*}),$

where the last inequality follows as the functions $c_{m}$ are clearly
increasing in $m$. This implies

$\displaystyle
f_{G,t_{*}}\left(t_{*},t_{*}-2,0,2\right)\leq\binom{n}{t_{*}}k^{n-t_{*}}\Phi(t_{*}),$

as claimed. ∎

We complete the proof of Section LABEL:*thm:main:threshold (a) by showing that
indeed the expected number of internally spanned projections of dimension
$t_{*}$ turns to $0$ as $n$ tends to infinity.

###### Proof of 3.7.

Recalling the definition (3.8) of the function $\Phi(\cdot)$ and using 5.7 we
obtain

$\displaystyle\binom{n}{t_{*}}n^{k-t_{*}+\frac{1}{2}}\Phi(t_{*})$
$\displaystyle{=}c_{t_{*}}\binom{n}{t_{*}}(t_{*}!)k^{n-t_{*}+\frac{1}{2}}p^{\frac{t_{*}}{2}+1}2^{-\frac{t_{*}}{2}-1}(k-1)^{t_{*}}k^{\frac{t_{*}^{2}+2t_{*}}{4}}$
$\displaystyle\leq
c_{t_{*}}n^{t_{*}}\left(\frac{1}{2n^{2}}\right)^{\frac{t_{*}}{2}+1}k^{n+\frac{1}{4}\left(t_{*}^{2}+2t_{*}+2\right)-(2\sqrt{n}-1)(\frac{t_{*}}{2}+1)}\quad(\text{because
}p\leq p_{*}=n^{-2}k^{-2\sqrt{n}+1})$
$\displaystyle{\leq}\Theta(1)\left(\frac{1}{2}\right)^{\frac{t_{*}}{2}+1}k^{n+\frac{1}{4}\left(t_{*}^{2}+2t_{*}+2\right)-(2\sqrt{n}-1)(\frac{t_{*}}{2}+1)}.$
(5.48)

Now observe that the function $g:\mathbb{R}\to\mathbb{R},x\mapsto
n+\frac{1}{4}\left(x^{2}+2x+2\right)-(2\sqrt{n}-1)(\frac{x}{2}+1)$ defines a
convex parabola whose center is shifted to $2\sqrt{n}-2$ and thus it takes its
minimum at $x=2\sqrt{n}-2$ and is decreasing up to this value. In particular,
as $t_{*}\coloneqq\left\lfloor 2\sqrt{n}\right\rfloor-2\geq 2\sqrt{n}-3$ it
holds that $g(t_{*})\leq g(2\sqrt{n}-3)=\frac{3}{4}$. Thus, we obtain together
with (5.48) that

$\displaystyle\binom{n}{t_{*}}n^{k-t_{*}+\frac{1}{2}}\Phi(t_{*})\leq\Theta\left(1\right)\left(\frac{1}{2}\right)^{\sqrt{n}-\frac{1}{2}}k^{\frac{3}{4}}=o(1),$

where the last equality uses that $k\leq 2^{\sqrt{n}}$. ∎

##  6\. Proofs of auxiliary results for the upper threshold

In this section we prove auxiliary results from Section 4. Recall
$\ell^{*}\coloneqq\left\lfloor\frac{n}{2}\right\rfloor$. For each
$1\leq\ell\leq\ell^{*}$ we set

$\displaystyle\tilde{C_{\ell}}\coloneqq\binom{n-2\ell+2}{2}(k-1)^{2}k^{2\ell-2}.$

Recall that $S_{\ell}$ denotes the set of all sequentially spanning sequences
of length $\ell$ in $G=(V,E)$ and we start by computing $|S_{\ell}|$.

###### Proof of 4.2.

Let $1\leq\ell\leq\ell^{*}$ and let
$\overline{v}_{\ell-1}=(v_{0},\ldots,v_{\ell-1})\in S_{\ell-1}$ be a
sequentially spanning sequence of length $\ell-1$. Looking at Property (2.1)
it follows immediately that

$\displaystyle C_{\ell}:$ $\displaystyle=\left|\left\\{w\in
V\mid\overline{v}_{\ell}=(v_{0},\ldots,v_{\ell-1},w)\in
S_{\ell}\right\\}\right|$ $\displaystyle=\left|\left\\{w\in
V\mid\operatorname{dist}\left(\left[{\left\\{\overline{v}_{\ell-1}\right\\}}\right],w\right)=2\right\\}\right|.$

By 2.10, $\left[{\left\\{\overline{v}_{\ell-1}\right\\}}\right]$ spans a
projection $H$ of dimension $2\ell-2$. Thus, it suffices to count the number
of vertices that lie at distance two from $H$. To that end, note that any
vertex $v$ satisfying $\operatorname{dist}\left(v,H_{2\ell-2}\right)=2$ has to
differ from $H$ in exactly two coordinates. As there are $2\ell-2$
coordinates, in which $H$ consists of a complete graph $K_{k}$, there are
$\binom{n-2\ell+2}{2}$ possibilities for choosing the coordinates in which $v$
differs from $H$ and $(k-1)^{2}$ possibilities for specifying a value of $v$
in those coordinates. In all coordinates, in which $H$ consists of a complete
graph, $v$ can take an arbitrary value $\in[k]$, leading to $k^{2\ell-2}$
additional choices. All remaining coordinates of $v$ have to coincide with
$H$, implying

$\displaystyle
C_{\ell}=\binom{n-2\ell+2}{2}(k-1)^{2}k^{2\ell-2}=:\tilde{C_{\ell}},$ (6.1)

as claimed.

To show (4.1) and thus to explicitly compute $|S_{\ell}|$, recall that
$|S_{0}|=k^{n}$ and note that by the definitions of $S_{\ell}$ and $C_{\ell}$
we have

$\displaystyle|S_{\ell}|=|S_{\ell-1}|\cdot C_{\ell}\quad\quad\text{for all
}\quad 1\leq\ell\leq\ell^{*}.$ (6.2)

Thus, (6.1) and (6.2) imply

$\displaystyle|S_{\ell}|$
$\displaystyle=k^{n}\prod_{j=1}^{\ell}C_{j}=k^{n}\prod_{j=1}^{\ell}\binom{n-2j+2}{2}(k-1)^{2}k^{2j-2}=k^{n}\prod_{j=1}^{\ell}C_{j}=\frac{n!}{(n-2\ell)!}(k-1)^{2\ell}2^{-\ell}k^{n+\ell^{2}-\ell},$

completing the proof.

∎

We continue with the proof of 4.3 on the upper bound on the number of pairs of
sequentially spanning sequences of length $\ell$ that intersect exactly in $i$
vertices, which was denoted by

$Y_{\ell}(i)\coloneqq\left\\{\\{\overline{v}_{\ell},\overline{w}_{\ell}\\}\subseteq
S_{\ell}\mid\left|\overline{v}_{\ell}\cap\overline{w}_{\ell}\right|=i\right\\}.$

In general, our proof strategy is to start with pairs of very short sequences
and then sequentially extend them to length $\ell$. To that end, we first take
a look at pairs of sequences that do not intersect until their last index.
Note that the resulting sequences can then either intersect in one or two
vertices, depending on whether only one of the respective final vertices is
contained in the other sequence, or both of them are. In particular, for
$m\in[n]\cup\\{0\\}$ and $j\in[2]$ let us denote by

$\displaystyle
Y_{m}^{(j)}\coloneqq\left\\{\left\\{\overline{v}_{m}=(v_{0},\ldots,v_{m}),\overline{w}_{m}=(w_{0},\ldots,w_{m})\right\\}\in
Y_{m}(j)\mid\\{v_{0},\ldots,v_{m-1}\\}\cap\\{w_{0},\ldots,w_{m-1}\\}=\emptyset\right\\},$
(6.3)

the set of pairs of sequentially spanning sequences of length $m$ with
intersection of size $j$ such that the cut-off sequences (i.e., the sequences
without the last vertex) of length $m-1$ have empty intersection. In the next
lemma we bound the sizes of these sets from above.

######  Lemma 6.1.

Let $m\in[n]\cup\left\\{0\right\\}$ and let $Y_{m}^{(1)}$ and $Y_{m}^{(2)}$ be
defined as in (6.3). Then,

  1. (a)

$|Y_{m}^{(1)}|\leq\frac{2(m+1)}{k^{n}}|S_{m}|^{2}$;

  2. (b)

$|Y_{m}^{(2)}|\leq\mathbb{1}_{\left\\{m\geq
1\right\\}}\frac{m(m+1)}{C_{m}k^{n}}|S_{m}|^{2}$.

###### Proof.

We start by showing (a). Due to symmetry we can assume w.lo.g. that all pairs
of sequences
$\\{\overline{v}_{m}=(v_{0},\ldots,v_{m}),\overline{w}_{m}=(w_{0},\ldots,w_{m})\\}\in
Y_{m}^{(1)}$ satisfy $w_{m}\in\left\\{\overline{v}_{m}\right\\}$ and
$v_{m}\notin\left\\{\overline{w}_{m}\right\\}$. For an arbitrary vertex $x\in
V$ let us denote by

$\displaystyle S_{m}(x)\coloneqq\left\\{\overline{w}_{m}=(w_{0},\ldots
w_{m})\in S_{m}\mid w_{m}=x\right\\},$

the set of sequentially spanning sequences of length $m$ that end with vertex
$x$. Now observe that we can obtain every pair of sequences in $Y_{m}^{(1)}$
by first choosing a sequence $\overline{v}_{m}\in S_{m}$, then fixing a vertex
$x\in\left\\{\overline{v}_{m}\right\\}$ and finally choosing a sequence
$\overline{w}_{m}\in S_{m}(x)$ that ends with vertex $x$. In particular, we
obtain

$\displaystyle|Y_{m}^{(1)}|\leq 2\sum_{\overline{v}_{m}\in
S_{m}}\sum_{x\in\left\\{\overline{v}_{m}\right\\}}|S_{m}(x)|.$ (6.4)

To bound $|S_{m}(x)|$ from above, note that

$\displaystyle\bigcup_{x\in G}S_{m}(x)=S_{m}.$

Indeed, because any sequence $\overline{v}_{m}\in S_{m}(x)$ is a sequentially
spanning sequence of length $m$, it clearly holds that $\bigcup_{x\in
G}S_{m}(x)\subseteq S_{m}$. For the other inclusion, observe that for any
sequence $\overline{v}_{m}=(v_{0},\ldots,v_{m})\in S_{m}$ it holds that
$\overline{v}_{m}\in S_{m}(v_{m})$. Now note that for different values of $x$,
the sets $S_{m}(x)$ are disjoint and furthermore, due to symmetry, the value
$|S_{m}(x)|$ does not depend on $x$ , implying together that for all $x\in V$,

$\displaystyle k^{n}\left|S_{m}(x)\right|=\sum_{x\in V}|S_{m}(x)|=|S_{m}|,$

and in particular,

$\displaystyle\left|S_{m}(x)\right|=\frac{\left|S_{m}\right|}{k^{n}}.$ (6.5)

Plugging it into (6.4) we obtain

$\displaystyle|Y_{m}^{(1)}|\overset{\eqref{eq:lem:bound:seqoverlaplastindex},\eqref{eq:univeraleq}}{\leq}2\sum_{\overline{v}_{m}\in
S_{m}}\sum_{x\in\left\\{\overline{v}_{m}\right\\}}\frac{|S_{m}|}{k^{n}}=2|S_{m}|\cdot|\left\\{\overline{v}_{m}\right\\}|\cdot\frac{|S_{m}|}{k^{n}}=\frac{2(m+1)}{k^{n}}|S_{m}|^{2},$

completing the proof of (a).

To show (b), note that we can count $Y_{m}^{(2)}$ similarly as $Y_{m}^{(1)}$:
We fix first a sequence $\overline{v}_{m-1}$ and then a vertex $x$ of
$\overline{v}_{m-1}$ with which $\overline{w}_{m}$ should end. Next we fix a
sequence $\overline{w}_{m}\in S_{m}(x)$ and finally choose a vertex $y$ from
all the vertices in $\overline{w}_{m}$ to extend $\overline{v}_{m-1}$.
Independently of all these choice we have
$\left|\left\\{\overline{w}_{m}\right\\}\right|=m+1$. Thus, from (6.5) and
(6.2) with $\ell=m$, i.e., $|S_{m-1}|=|S_{m}|/C_{m}$ we obtain

$\displaystyle|Y_{m}^{(2)}|$ $\displaystyle\leq\sum_{\overline{v}_{m-1}\in
S_{m-1}}\sum_{x\in\left\\{\overline{v}_{m-1}\right\\}}\sum_{\overline{w}_{m}\in
S_{m}(x)}\left|\left\\{\overline{w}_{m}\right\\}\right|$
$\displaystyle=|S_{m-1}|\cdot|\left\\{\overline{v}_{m-1}\right\\}|\cdot|S_{m}(x)|\cdot(m+1)$
$\displaystyle{=}|S_{m-1}|\cdot m(m+1)\cdot\frac{|S_{m}|}{k^{n}}$
$\displaystyle{=}\frac{m(m+1)}{C_{m}k^{n}}|S_{m}|^{2},$

as required. ∎

6.1 essentially tells us how many ways there are to start intersecting pairs
of sequences. We continue by counting the number of ways we can extend such
pairs of sequences to sequences of length $\ell$. For $m\in[n]$ and
$i\in[m+1]\cup\left\\{0\right\\}$, let
$\\{\overline{v}_{m}=(v_{0},\ldots,v_{m}),\overline{w}_{m}=(w_{0},\ldots,w_{m})\\}\subseteq
S_{m}$ be two sequentially spanning sequences satisfying
$|\overline{v}_{m}\cap\overline{w}_{m}|=i$. For $\ell\geq m+1$ and
$s\in[\ell]\cup\left\\{0\right\\}$ let us denote by

$\displaystyle{\mathcal{E}\left(\overline{v}_{m},\overline{w}_{m},\ell,i,s\right)}\coloneqq$
$\displaystyle\left\\{\left\\{\overline{v}_{\ell}^{\prime}=\left(v_{0}^{\prime},\ldots,v_{\ell}^{\prime}\right),\overline{w}_{\ell}^{\prime}=\left(w_{0}^{\prime},\ldots,w_{\ell}^{\prime}\right)\right\\}\in
Y_{\ell}(s+i)\mid\forall 0\leq j\leq m\colon\left(v_{j}=v_{j}^{\prime}\land
w_{j}=w_{j}^{\prime}\right)\right\\}$ (6.6)

the set of all extensions of the pair
$\\{\overline{v}_{m},\overline{w}_{m}\\}\subseteq S_{m}$ to a pair
$\\{\overline{v}_{\ell}^{\prime},\overline{w}_{\ell}^{\prime}\\}\subseteq
S_{\ell}$ of sequentially spanning sequences of length $\ell$ satisfying
$\left|\overline{v}_{\ell}^{\prime}\cap\overline{w}_{\ell}^{\prime}\right|=i+s$.
As $\ell$ remains fixed throughout this section, we will drop the subscript
$\ell$ to ease notation and write

$\displaystyle
E\left(m,i,s\right)\coloneqq\max_{\left\\{\overline{v}_{m},\overline{w}_{m}\right\\}\in
Y_{m}(i)}\left|\mathcal{E}\left(\overline{v}_{m},\overline{w}_{m},\ell,i,s\right)\right|.$

In the next lemma we provide bounds on $E\left(m,i,s\right)$.

######  Lemma 6.2.

Let $m\in[n]$, $i\in[m+1]\cup\left\\{0\right\\}$ and
$s\in[\ell]\cup\left\\{0\right\\}$. For $1\leq j\leq\ell^{*}$ set

$\displaystyle
D_{j}\coloneqq\mathbb{1}_{\left\\{j=1\right\\}}C_{1}+\mathbb{1}_{\left\\{j>1\right\\}}\max\left\\{C_{j},3D_{j-1}\right\\}.$

Then,

  1. (a)

$C_{j}\leq D_{j}$;

  2. (b)

$E\left(m,i,s\right)\leq
8^{s}\left(\prod_{j=m+1}^{\ell}D_{j}^{2}\right)\Psi\left(m,i,s\right)$,

where

$\displaystyle\Psi\left(m,i,s\right)$
$\displaystyle\coloneqq\begin{cases}\mathbb{1}_{\left\\{s=0\right\\}}+\mathbb{1}_{\left\\{s>0\right\\}}\prod_{j=m+1}^{2m-i+1}\left(\frac{2m-i+2-j}{D_{j}}\right)^{2}\prod_{j=2m-i+2}^{s+i-1}D_{j}^{-1}&\text{
if }\ m-i+1<s/2\\\
\mathbb{1}_{\left\\{s=0\right\\}}+\mathbb{1}_{\left\\{s>0\right\\}}\prod_{j=m+1}^{m+\left\lfloor\frac{s}{2}\right\rfloor}\left(\frac{2m-i+2-j}{D_{j}}\right)^{2}\left(\mathbb{1}_{\left\\{s\text{
even }\right\\}}+\mathbb{1}_{\left\\{s\text{ odd
}\right\\}}\frac{2(m-\left\lfloor\frac{s}{2}\right\rfloor-i+1)+1}{D_{m+\left\lfloor\frac{s}{2}\right\rfloor+1}}\right)&\text{
else.}\end{cases}$ (6.7)

Let us first remark that the functions $D_{j}$ are only introduced to ensure
that the ratio $\frac{D_{j}}{D_{j-1}}$ is at least $3$ for all values of
$1\leq j\leq\ell^{*}$ (which does not hold for the functions $C_{j}$). To give
some further intuition on the bounds stated in 6.2, observe that the term
$\prod_{j=m+1}^{\ell}D_{j}^{2}$ is an upper bound on the number of extensions
of a pair $\\{\overline{v}_{m},\overline{w}_{m}\\}$ of sequences of length $m$
to a pair $\\{\overline{v}_{\ell}^{\prime},\overline{w}_{\ell}^{\prime}\\}$ of
sequences of lenght $\ell$, in which the extended sequences do not have to
overlap any further. In a sense, the function
$\Psi\left(\cdot,\cdot,\cdot\right)$ quantifies how much having overlap
restricts a pair of extensions. In particular, in order to extend a sequence
$\overline{v}_{m}$ by a vertex that is also appearing in $\overline{w}_{m}$,
the number of choices for this vertex are reduced from $C_{m+1}$ to the number
of vertices appearing in $\overline{w}_{m}$.

In order to prove 6.2, we will first show some general properties of the
function $\Psi\left(\cdot,\cdot,\cdot\right)$.

######  Lemma 6.3.

For any $(i,s)\in\mathbb{N}^{2}$ the following hold.

  1. (a)

The function $\Psi\left(\cdot,i,s\right)$, as defined in (6.7), is decreasing
in the first coordinate.

  2. (b)

For all $m\geq i-1$ and $s\geq 1$

$\displaystyle\sum_{j=m+1}^{\ell}\left(\frac{2(j+1-i)\Psi\left(j,i+1,s-1\right)}{D_{j}}+\frac{(j-i)^{2}\Psi\left(j,i+2,s-2\right)}{8{D_{j}}^{2}}\mathbb{1}_{\left\\{s\geq
2\right\\}}\right)\leq 8\Psi\left(m,i,s\right).$

The proof of 6.3 is simple but tedious and is therefore deferred to the
Appendix B. We proceed by showing 6.2.

###### Proof of 6.2.

Note first that Section LABEL:*lem:bound:seqoverlap:extensions (a) is a
trivial observation.

Continuing with Section LABEL:*lem:bound:seqoverlap:extensions (b) we will
prove the statement using induction on $s$, starting with the base case $s=0$.
By the definition of

$C_{j+1}:=\left|\left\\{w\in V\mid\overline{v}_{j+1}=(v_{0},\ldots,v_{j},w)\in
S_{j+1}\right\\}\right|,$

there are at most $C_{j+1}$ ways to extend a sequentially spanning sequence of
length $j$. Thus, sequentially extending both sequences (and ignoring any
potential overlaps) yields together with (a) the upper bound

$\displaystyle
E\left(m,i,0\right)\leq\prod_{j=m+1}^{\ell}C_{j}^{2}\leq\prod_{j=m+1}^{\ell}D_{j}^{2}=\left(\prod_{j=m+1}^{\ell}D_{j}^{2}\right)\Psi\left(m,i,0\right),$

proving the induction base.

We proceed with the induction hypothesis. Let
$\left\\{\overline{v}_{m},\overline{w}_{m}\right\\}\in Y_{m}(i)$, let
$s\in[\ell]$ and assume that Section LABEL:*lem:bound:seqoverlap:extensions
(b) holds for all $j\in[s-1]$. For a fixed index $m+1\leq j^{*}\leq\ell$ and
$\tau\in\\{1,2\\}$ let us consider the number
$E_{j^{*}}^{(\tau)}\left(m,i,s\right)$ of extensions
$\\{\overline{v}_{\ell}=(v_{0},\ldots,v_{\ell}),\overline{w}_{\ell}=(w_{0},\ldots,w_{\ell})\\}\subseteq
S_{\ell}$ satisfying $|\overline{v}_{j^{*}-1}\cap\overline{w}_{j^{*}-1}|=i$
and $|\overline{v}_{j^{*}}\cap\overline{w}_{j^{*}}|=i+\tau$, i.e., $j^{*}$ is
the first index larger than $m$ at which the extended sequences contain an
additional vertex that is also contained in the other sequence up to this
point.

We will compute $E_{j^{*}}^{(\tau)}\left(m,i,s\right)$ in three steps: First,
we will compute the number of possible extensions of $\overline{v}_{m}$ and
$\overline{w}_{m}$ to sequences $\overline{v}_{j^{*}-1}$ and
$\overline{w}_{j^{*}-1}$, then count the number of ways to extend those to
sequences $\overline{v}_{j^{*}}$ and $\overline{w}_{j^{*}}$ and finally extend
those to sequences $\overline{v}_{\ell}$ and $\overline{w}_{\ell}$.
Analogously to the induction base, there are at most
$\prod_{j=m+1}^{j^{*}-1}C_{j}^{2}$ ways to extend the sequences
$\overline{v}_{m}$ and $\overline{w}_{m}$ to sequences
$\overline{v}_{j^{*}-1}$ and $\overline{w}_{j^{*}-1}$. To compute the number
of ways how to further extend those sequences, we distinguish two cases.

  * Case 1:

$|\overline{v}_{j^{*}}\cap\overline{w}_{j^{*}}|=i+1$.
By definition of $j^{*}$, one of the following has to hold in this case.

    1. (1)

$v_{j^{*}}\in\\{\overline{w}_{j^{*}-1}\\}$ and
$w_{j^{*}}\notin\\{\overline{v}_{j^{*}}\\}$;

    2. (2)

$w_{j^{*}}\in\\{\overline{v}_{j^{*}-1}\\}$ and
$v_{j^{*}}\notin\\{\overline{w}_{j^{*}}\\}$;

    3. (3)

$v_{j^{*}}=w_{j^{*}}$.

In the first subcase, there are at most $C_{j^{*}}$ ways for picking
$w_{j^{*}}$. Furthermore, $v_{j^{*}}$ has to be one of the $j^{*}-i$ vertices
contained in
$\left\\{\overline{w}_{j^{*}-1}\right\\}\setminus\left\\{\overline{v}_{j^{*}-1}\right\\}$.
Thus, the number of extensions in this subcase can be bounded from above by
$C_{j^{*}}(j^{*}-i)$. The second subcase is symmetric to the first, so let us
continue with the last subcase. Clearly, if $v_{j^{*}}=w_{j^{*}}$ then it
follows that there are at most $C_{j^{*}}$ ways to extend the sequences. In
total, we obtain that the number of ways to extend $\overline{v}_{j^{*}-1}$
and $\overline{w}_{j^{*}-1}$ to $\overline{v}_{j^{*}}$ and
$\overline{w}_{j^{*}}$ is bounded from above by $C_{j^{*}}(2(j^{*}-i)+1)\leq
2C_{j^{*}}(j^{*}-i+1)$.

  * Case 2:

$|\\{\overline{v}_{j^{*}}\\}\cap\\{\overline{w}_{j^{*}}\\}|=i+2$.
In this case it follows that $v_{j^{*}}\in\\{\overline{w}_{j^{*}-1}\\}$ and
$w_{j^{*}}\in\\{\overline{v}_{j^{*}-1}\\}$. Similar to the previous case,
$v_{j^{*}}$ has to be one of the $j^{*}-i$ vertices contained in
$\left\\{\overline{w}_{j^{*}-1}\right\\}\setminus\left\\{\overline{v}_{j^{*}-1}\right\\}$
and analogously $w_{j^{*}}$ has to be one of the $j^{*}-i$ vertices contained
in
$\left\\{\overline{v}_{j^{*}-1}\right\\}\setminus\left\\{\overline{w}_{j^{*}-1}\right\\}$.
Thus, there are at most $(j^{*}-i)^{2}$ possibilities to extend.

It remains to bound the number of ways to extend the sequences
$\overline{v}_{j^{*}}$ and $\overline{w}_{j^{*}}$ to sequences
$\overline{v}_{\ell}$ and $\overline{w}_{\ell}$. In the first case, this
number is clearly given as $E\left(j^{*},i+1,s-1\right)$ and in the second
case as $E\left(j^{*},i+2,s-2\right)$. Putting everything together and using
the induction hypothesis Section LABEL:*lem:bound:seqoverlap:extensions (b) we
obtain

$\displaystyle E_{j^{*}}^{(1)}\left(m,i,s\right)$
$\displaystyle\leq\left(\prod_{j=m+1}^{j^{*}-1}C_{j}^{2}\right)2C_{j^{*}}(j^{*}-i+1)E\left(j^{*},i+1,s-1\right)$
$\displaystyle{\leq}\left(\prod_{j=m+1}^{j^{*}-1}C_{j}^{2}\right)2C_{j^{*}}(j^{*}-i+1)8^{s-1}\left(\prod_{j=j^{*}+1}^{\ell}D_{j}^{2}\right)\Psi\left(j^{*},i+1,s-1\right).$
(6.8)

Using Section LABEL:*lem:bound:seqoverlap:extensions (a) in (6.8) we thus
obtain

$\displaystyle E_{j^{*}}^{(1)}\left(m,i,s\right)$
$\displaystyle{\leq}\left(\prod_{j=m+1}^{j^{*}-1}D_{j}^{2}\right)2D_{j^{*}}(j^{*}-i+1)8^{s-1}\left(\prod_{j=j^{*}+1}^{\ell}D_{j}^{2}\right)\Psi\left(j^{*},i+1,s-1\right)$
$\displaystyle=8^{s-1}\left(\prod_{j=m+1}^{\ell}D_{j}^{2}\right)\frac{2(j^{*}-i+1)\Psi\left(j^{*},i+1,s-1\right)}{D_{j^{*}}}.$
(6.9)

Analogously to (6.8) and (6.9) we obtain for
$E_{j^{*}}^{(2)}\left(m,i,s\right)$ that

$\displaystyle E_{j^{*}}^{(2)}\left(m,i,s\right)\leq
8^{s-2}\left(\prod_{j=m+1}^{\ell}D_{j}^{2}\right)\frac{(j^{*}-i)\Psi\left(j^{*},i+2,s-2\right)}{D_{j^{*}}^{2}}.$
(6.10)

Summing over all possible values of $j^{*}$, it follows from (6.9) and (6.10)
that

$\displaystyle
E\left(m,i,s\right)\leq\sum_{j^{*}=m+1}^{\ell}E_{j^{*}}^{(1)}\left(m,i,s\right)+E_{j^{*}}^{(2)}\left(m,i,s\right)$
$\displaystyle\leq
8^{s-1}\left(\prod_{j=m+1}^{\ell}D_{j}^{2}\right)\sum_{j^{*}=m+1}^{\ell}\left(\frac{2(j^{*}+1-i)\Psi\left(j^{*},i+1,s-1\right)}{D_{j^{*}}}+\frac{(j^{*}-i)^{2}\Psi\left(j^{*},i+2,s-2\right)}{8{D_{j^{*}}}^{2}}\right).$
(6.11)

Finally, plugging the bounds from Section LABEL:*lem:bound:auxfunc (b) into
(6.11) we obtain

$\displaystyle E\left(m,i,s\right)\leq
8^{s}\left(\prod_{j=m+1}^{\ell}D_{j}^{2}\right)\Psi\left(m,i,s\right),$

completing the proof. ∎

We are now ready to proof 4.3.

###### Proof of 4.3.

Recall $\ell^{*}:=\left\lfloor\frac{n}{2}\right\rfloor$ and let
$\ell\in[\ell^{*}]\cup\\{0\\}$ and $i\in[\ell+1]$. Splitting the set
$Y_{\ell}(i)\coloneqq\left\\{\\{\overline{v}_{\ell},\overline{w}_{\ell}\\}\subseteq
S_{\ell}\mid\left|\overline{v}_{\ell}\cap\overline{w}_{\ell}\right|=i\right\\}$
into parts, depending on the first index $m$ at which a pair
$\left\\{\overline{v}_{\ell},\overline{w}_{\ell}\right\\}$ of sequentially
spanning sequences has non-empty overlap, we obtain

$\displaystyle|Y_{\ell}(i)|$
$\displaystyle\leq\sum_{m=0}^{\ell}\sum_{\\{\overline{v}_{m},\overline{w}_{m}\\}\in
Y_{m}^{(1)}}E\left(m,1,i-1\right)+\sum_{m=1}^{\ell}\sum_{\\{\overline{v}_{m},\overline{w}_{m}\\}\in
Y_{m}^{(2)}}E\left(m,2,i-2\right)$
$\displaystyle\leq\sum_{m=0}^{\ell}\left|Y_{m}^{(1)}\right|E\left(m,1,i-1\right)+\sum_{m=1}^{\ell}\left|Y_{m}^{(2)}\right|E\left(m,2,i-2\right).$

Together with the bounds on from 6.1 and Section
LABEL:*lem:bound:seqoverlap:extensions (b) it follows that

$\displaystyle|Y_{\ell}(i)|$
$\displaystyle{\leq}\sum_{m=0}^{\ell}\frac{2(m+1)|S_{m}|^{2}}{k^{n}}E\left(m,1,i-1\right)+\sum_{m=1}^{\ell}\frac{m(m+1)|S_{m}|^{2}}{C_{m}k^{n}}E\left(m,2,i-2\right).$
$\displaystyle{\leq}\sum_{m=0}^{\ell}\frac{2(m+1)|S_{m}|^{2}}{k^{n}}8^{i-1}\left(\prod_{j=m+1}^{\ell}D_{j}^{2}\right)\Psi\left(m,1,i-1\right)$
$\displaystyle+\sum_{m=1}^{\ell}\frac{m(m+1)|S_{m}|^{2}}{C_{m}k^{n}}8^{i-2}\left(\prod_{j=m+1}^{\ell}D_{j}^{2}\right)\Psi\left(m,2,i-2\right).$
(6.12)

Now recall that by 4.2 it holds that
$\left|S_{m}\right|=k^{n}\prod_{j=1}^{m}C_{j}$. In particular, it follows from
Section LABEL:*lem:bound:seqoverlap:extensions (a) that

$\displaystyle\frac{\left|S_{m}\right|^{2}}{k^{n}}\leq
k^{n}\left(\prod_{j=1}^{m}D_{j}^{2}\right)\quad\text{and}\quad\frac{\left|S_{m}\right|^{2}}{k^{n}C_{m}}\leq\frac{k^{n}\left(\prod_{j=1}^{m}D_{j}^{2}\right)}{D_{m}}.$
(6.13)

Plugging (6.13) into (6) and extracting common factors from both sums we get

$\displaystyle|Y_{\ell}(i)|$ $\displaystyle\leq
8^{i-1}k^{n}\left(\prod_{j=1}^{\ell}D_{j}^{2}\right)\left(\sum_{m=0}^{\ell}2(m+1)\Psi\left(m,1,i-1\right)+\sum_{m=1}^{\ell}\frac{m(m+1)}{8D_{m}}\Psi\left(m,2,i-2\right)\right)$
$\displaystyle\leq
8^{i-1}k^{n}\left(\prod_{j=1}^{\ell}D_{j}^{2}\right)\left(\ell+1\right)^{2}\left(\sum_{m=0}^{\ell}2\Psi\left(m,1,i-1\right)+\sum_{m=1}^{\ell}\frac{\Psi\left(m,2,i-2\right)}{8D_{m}}\right).$
(6.14)

By Section LABEL:*lem:bound:auxfunc (a), the function
$\Psi\left(\cdot,\cdot,\cdot\right)$ is decreasing in the first coordinate and
furthermore, the function $m\mapsto 1/D_{m}$ is decreasing in $m\in[\ell]$,
and thus we have

$\displaystyle\left(\sum_{m=0}^{\ell}2\Psi\left(m,1,i-1\right)+\sum_{m=1}^{\ell}\frac{\Psi\left(m,2,i-2\right)}{8D_{m}}\right)\leq\left(\sum_{m=0}^{\ell}2\Psi\left(0,1,i-1\right)+\sum_{m=1}^{\ell}\frac{\Psi\left(1,2,i-2\right)}{8D_{1}}\right)$
$\displaystyle\leq
2(\ell+1)\left(\Psi\left(0,1,i-1\right)+\frac{\Psi\left(1,2,i-2\right)}{D_{1}}\right)=2(\ell+1)\left(\prod_{j=1}^{i-1}D_{j}^{-1}+D_{1}^{-1}\prod_{j=2}^{i-1}D_{j}^{-1}\right)$
$\displaystyle=4(\ell+1)\left(\prod_{j=1}^{i-1}D_{j}^{-1}\right),$ (6.15)

where the penultimate equality is due to the definition (6.7) of
$\Psi\left(\cdot,\cdot,\cdot\right)$. Combining (6) and (6.15) we obtain

$\displaystyle|Y_{\ell}(i)|$
$\displaystyle{\leq}8^{i-1}k^{n}\left(\prod_{j=1}^{\ell}D_{j}^{2}\right)\left(\ell+1\right)^{2}\left(\sum_{m=0}^{\ell}\Psi\left(m,1,i-1\right)+\sum_{m=1}^{\ell}\frac{\Psi\left(m,2,i-2\right)}{8D_{m}}\right)$
$\displaystyle{\leq}8^{i-1}k^{n}\left(\prod_{j=1}^{\ell}D_{j}^{2}\right)\left(\ell+1\right)^{2}4(\ell+1)\left(\prod_{j=1}^{i-1}D_{j}^{-1}\right)\leq\frac{8^{i}k^{n}(\ell+1)^{3}\left(\prod_{j=1}^{\ell}D_{j}^{2}\right)}{\left(\prod_{j=1}^{i-1}D_{j}\right)}.$
(6.16)

To complete the proof, we need to replace the auxiliary functions $D_{j}$ with
the functions $C_{j}$. To that end, observe that by 4.2 it holds for all
$1\leq j\leq\ell^{*}-7$ that

$\displaystyle\frac{C_{j+1}}{C_{j}}=\frac{\binom{n-2j}{2}k^{2}}{\binom{n-2j+2}{2}}\geq
3,$

and thus in particular that $C_{j}=D_{j}$ for $1\leq j\leq\ell^{*}-6$. By the
construction of $D_{j}$ it now follows that

$\displaystyle D_{\ell^{*}-5}\leq 3D_{\ell^{*}-6}=3C_{\ell^{*}-6}\leq
3C_{\ell^{*}-5}.$

Repeating this step we obtain for $1\leq j\leq 6$ that

$\displaystyle D_{\ell^{*}-6+j}\leq 3^{j}C_{\ell^{*}-6+j},$

and thus

$\displaystyle\left(\prod_{j=1}^{\ell^{*}}D_{j}^{2}\right)=\left(\prod_{j=1}^{\ell^{*}-6}C_{j}^{2}\right)\left(\prod_{j=1}^{6}D_{\ell^{*}-6+j}^{2}\right)\leq\left(\prod_{j=1}^{\ell^{*}}C_{j}^{2}\right)\left(\prod_{j=1}^{6}3^{2j}\right)=3^{42}\left(\prod_{j=1}^{\ell^{*}}C_{j}^{2}\right).$

Clearly, this extends to arbitrary values of $1\leq\ell\leq\ell^{*}$, i.e.,

$\displaystyle\left(\prod_{j=1}^{\ell}D_{j}^{2}\right)\leq
3^{42}\left(\prod_{j=1}^{\ell}C_{j}^{2}\right).$ (6.17)

Combining (6.16) and (6.17) we obtain

$\displaystyle|Y_{\ell}(i)|\overset{\eqref{eq:prf:boundseqoverlap:5}}{\leq}\frac{8^{i}k^{n}(\ell+1)^{3}\left(\prod_{j=1}^{\ell}D_{j}^{2}\right)}{\left(\prod_{j=1}^{i-1}D_{j}\right)}\overset{\eqref{eq:Dj}}{\leq}\Theta(1)\frac{8^{i}k^{n}(\ell+1)^{3}\left(\prod_{j=1}^{\ell}C_{j}^{2}\right)}{\left(\prod_{j=1}^{i-1}C_{j}\right)}=\Theta(1)\frac{8^{i}(\ell+1)^{3}|S_{\ell}|^{2}}{|S_{i-1}|},$

where the last equality uses (4.1). ∎

We continue by showing that the expectation of $X_{i}$ tends to infinity for
all $0\leq i\leq\ell^{*}.$

###### Proof of 4.4.

Let $i\in[\ell^{*}]\cup\\{0\\}$. We start by bounding
$\mathbb{E}\left[X_{i}\right]$ from below. By (4.3) and 4.2 it holds that

$\displaystyle\mathbb{E}\left[X_{i}\right]\overset{\eqref{eq:expec(seqspannum)}}{=}|S_{i}|p^{i+1}\overset{\eqref{eq:Sell}}{=}\frac{n!}{(n-2i)!}(k-1)^{2i}2^{-i}k^{n+i^{2}-i}p^{i+1}$
$\displaystyle\geq\frac{n!}{(n-2i)!}(k-1)^{2i}2^{-i}k^{n+i^{2}-i}\left(200n^{-2}k^{-2\sqrt{n}+1}\right)^{i+1},$
(6.18)

where the last inequality uses $p\geq p^{*}:=200n^{-2}k^{-2\sqrt{n}+1}$. To
further bound this expression we will use the following estimates:

$\displaystyle\frac{n!}{(n-2i)!}$
$\displaystyle=n^{2i}\prod_{j=1}^{i}\left(1-\frac{j}{n}\right)\geq
n^{2i}\exp\left(-\frac{2i^{2}}{n}\right)\geq n^{2i}e^{-i};$
$\displaystyle(k-1)^{2i}$
$\displaystyle=k^{2i}\left(1-\frac{1}{k}\right)^{2i}\geq k^{2i}2^{-2i}.$

Plugging these into (6.18) and simplifying we obtain

$\displaystyle\mathbb{E}\left[X_{i}\right]\geq
n^{2i}e^{-i}k^{2i}2^{-2i}2^{-i}k^{n+i^{2}-i}\left(200n^{-2}k^{-2\sqrt{n}+1}\right)^{i+1}=200n^{-2}\left(\frac{200}{8e}\right)k^{i^{2}-i(2\sqrt{n}-2)+n-2\sqrt{n}+1}.$

It thus follows that

$\displaystyle\frac{\mathbb{E}\left[X_{i}\right]}{\Theta\left(n^{4}\right)8^{i+1}}$
$\displaystyle\geq\Theta(n^{-6})\left(\frac{200}{64e}\right)^{i}k^{i^{2}-i(2\sqrt{n}-2)+n-2\sqrt{n}+1}$
$\displaystyle\geq\Theta\left(n^{-6}\right)\left(\frac{10}{9}\right)^{i}k^{i^{2}-i(2\sqrt{n}-2)+n-2\sqrt{n}+1}.$
(6.19)

To derive a lower bound on (6.19) we focus on the the function
$\hat{g}:\mathbb{R}^{2}\to\mathbb{R},x\mapsto
x^{2}-x(2\sqrt{n}-2)+n-2\sqrt{n}+1$ in the exponent. Observing that the
function $\hat{g}$ defines a convex parabola centered at $\sqrt{n}-1$, it
takes its minimum value of $0$ at the minimiser $x=\sqrt{n}-1$. Thus, we
obtain that for all $i\in[\ell^{*}]\cup\\{0\\}$

$\displaystyle\frac{\mathbb{E}\left[X_{i}\right]}{\Theta(n^{4})8^{i+1}}\geq\Theta\left(n^{-6}\right)\left(\frac{10}{9}\right)^{\sqrt{n}-1}=\omega\left(1\right),$

completing the proof. ∎

Finally we show that in the case when $n$ is odd, say $n=2m+1$ for
$m\in\mathbb{N}_{0}$, we can always find an infected vertex to extend an
infected sequentially spanning sequence of length $m$.

###### Proof of 4.7.

Let $n=2m+1$ for $m\in\mathbb{N}_{0}$. For an arbitrary projection $H$ of
dimension $2m$, the number of vertices in $G$ that are not contained in $H$ is
clearly given as $(k-1)k^{2m}$. Thus, using $p\geq
p^{*}:=200n^{-2}k^{-2\sqrt{n}+1}$, the probability that none of these vertices
were initially infected, can be bounded from above by

$\displaystyle(1-p)^{(k-1)k^{2m}}\leq\exp\left(-pk^{2m}\right)\leq\exp\left(-k^{\frac{n}{2}}\right).$

Now observe that there are $nk$ projections of dimension $2m$ in $G$. Indeed,
there are $n$ ways for choosing the single coordinate in which a projection of
dimension $2m$ is not complete and $k$ further possibilities for choosing a
vertex of the base graph $K_{k}$ in this coordinate. Thus it follows by a
union bound that the probability that there exists a projection $H$ of
dimension $2m$ such that no vertex in $G\setminus H$ was initially infected
can be bounded from above by

$\displaystyle nk\exp\left(-k^{\frac{n}{2}}\right)=o(1).$

∎

##  7\. Concluding Discussion

In 1.1 we determined the asymptotic value of the critical probability up to
multiplicative constants:

$\displaystyle
p_{c}\left(\square_{i=1}^{n}K_{k},2\right)=\Theta\left(n^{-2}k^{-2\sqrt{n}+1}\right).$
(7.1)

The corresponding result for the case $k=2$ was proved in the earlier work of
Balogh and Bollobás[5] which was improved by Balogh, Bollobás and Morris[7]:

$\displaystyle\frac{16\lambda}{n^{2}}\left(1+\frac{\log
n}{\sqrt{n}}\right)2^{-2\sqrt{n}}\leq
p_{c}(\square_{i=1}^{n}K_{2},2)\leq\frac{16\lambda}{n^{2}}\left(1+\frac{5\log^{2}n}{\sqrt{n}}\right)2^{-2\sqrt{n}},$
(7.2)

where $\lambda\approx 1.166$. In order to improve our result, e.g., to obtain
a sharp threshold, proof techniques in this paper might be useful. One of the
key ingredients in our proof is the bound on the probability of a projection
of dimension $2\ell$ being internally spanned (see 3.2): This bound is off
precisely by factor $\lambda^{\ell}$, in comparison to the corresponding bound
to obtain (7.2). Getting more precise asymptotics on the probability of a
projection being internally spanned is the most crucial step to obtain a sharp
threshold.

######  Problem 7.1.

Determine a sharp threshold for $p_{c}\left(\square_{i=1}^{n}K_{k},2\right)$
for any $k\geq 3$.

The Hamming graph is a very natural example of a Cartesian product graph and
has quite useful properties, e.g., it is regular and vertex-transitive. We
believe the proof techniques in this paper are also applicable to similar
types of graphs and especially to Cartesian product graphs with different
kinds of base graphs. An interesting problem in this context is to determine a
set of minimal properties the base graphs have to satisfy in order to obtain a
threshold in the flavour of 1.1.

######  Problem 7.2.

Determine $p_{c}\left(G,2\right)$ for other types of Cartesian product graphs
$G$.

Lastly, we note that throughout this paper we only considered the infection
parameter $r=2$. For $r\geq 3$, the problem of determining the critical
probability $p_{c}\left(\square_{i=1}^{n}K_{k},r\right)$ is widely open even
for the case $k=2$ and $r=3$.

######  Problem 7.3.

Determine $p_{c}\left(\square_{i=1}^{n}K_{k},3\right)$ for arbitrary $k\geq
2$.

For the special case when $r=\left\lceil\frac{n}{2}\right\rceil$ and $k=2$,
i.e., in the so-called majority bootstrap percolation on the $n$-dimensional
hypercube $Q^{n}=[2]^{n}=\square_{i=1}^{n}K_{2}$, a sharp threshold was
established by Balogh, Bollobás and Morris in [9] and their results have been
extended to Cartesian products of bounded size regular graphs by Collares,
Erde, Geisler and Kang [20]. For arbitrary $r\geq 3$, Morrison and Noel
answered the extremal question of determining a smallest percolating set in
$Q^{n}$ in [32]; regarding the critical probability, Balogh, Bollobás and
Morris [7, Conjecture 6.3] conjectured the following in 2010, but there is
still no progress:

$\displaystyle
p_{c}\left(\square_{i=1}^{n}K_{2},r\right)=\exp\left(-\Theta\left(n^{1/2^{r-1}}\right)\right).$

The sharp threshold (7.2) suggests that the base of the exponential function
in the above conjecture would be two and thus the conjecture could be
reformulated as

$\displaystyle-\log_{2}p_{c}\left(\square_{i=1}^{n}K_{2},r\right)=\Theta\left(n^{1/2^{r-1}}\right).$

In view of our threshold result (7.1) we make an analogous conjecture:

######  Conjecture 7.4.

For arbitrary $r\geq 3$ and $k\geq 2$,

$\displaystyle-\log_{k}p_{c}\left(\square_{i=1}^{n}K_{k},r\right)=\Theta\left(n^{1/2^{r-1}}\right).$

## Acknowledgements

The authors are supported by the Austrian Science Fund (FWF) [10.55776/{W1230,
DOC183, F1002}]. For the purpose of open access, the authors have applied a CC
BY public copyright licence to any Author Accepted Manuscript version arising
from this submission.

## References

  * [1] Joan Adler and Uri Lev  “Bootstrap Percolation: Visualizations and Applications”  In _Brazilian Journal of Physics_ 33, 2003  DOI: 10.1590/S0103-97332003000300031
  * [2] M. Aizenman and J.. Lebowitz  “Metastability effects in bootstrap percolation”  In _J. Phys. A_ 21.19, 1988, pp. 3801–3813  URL: http://stacks.iop.org/0305-4470/21/3801
  * [3] Noga Alon and Joel H. Spencer  “The probabilistic method” With an appendix on the life and work of Paul Erdős, Wiley-Interscience Series in Discrete Mathematics and Optimization  John Wiley & Sons, Inc., Hoboken, NJ, 2008, pp. xviii+352  DOI: 10.1002/9780470277331
  * [4] Omer Angel and Brett Kolesnik  “Large deviations for subcritical bootstrap percolation on the Erdős-Rényi graph”  In _J. Stat. Phys._ 185.2, 2021, pp. Paper No. 816  DOI: 10.1007/s10955-021-02819-w
  * [5] József Balogh and Béla Bollobás  “Bootstrap percolation on the hypercube”  In _Probab. Theory Related Fields_ 134.4, 2006, pp. 624–648  DOI: 10.1007/s00440-005-0451-6
  * [6] József Balogh, Béla Bollobás, Hugo Duminil-Copin and Robert Morris  “The sharp threshold for bootstrap percolation in all dimensions”  In _Trans. Amer. Math. Soc._ 364.5, 2012, pp. 2667–2701  DOI: 10.1090/S0002-9947-2011-05552-2
  * [7] József Balogh, Béla Bollobás and Robert Morris  “Bootstrap percolation in high dimensions”  In _Combin. Probab. Comput._ 19.5-6, 2010, pp. 643–692  DOI: 10.1017/S0963548310000271
  * [8] József Balogh, Béla Bollobás and Robert Morris  “Bootstrap percolation in three dimensions”  In _Ann. Probab._ 37.4, 2009, pp. 1329–1380  DOI: 10.1214/08-AOP433
  * [9] József Balogh, Béla Bollobás and Robert Morris  “Majority bootstrap percolation on the hypercube”  In _Combin. Probab. Comput._ 18.1-2, 2009, pp. 17–51  DOI: 10.1017/S0963548308009322
  * [10] József Balogh, Yuval Peres and Gábor Pete  “Bootstrap percolation on infinite trees and non-amenable groups”  In _Combin. Probab. Comput._ 15.5, 2006, pp. 715–730  DOI: 10.1017/S0963548306007619
  * [11] József Balogh and Gábor Pete  “Random disease on the square grid”  In _Proceedings of the Eighth International Conference “Random Structures and Algorithms” (Poznan, 1997)_ 13, 1998, pp. 409–422  DOI: 10.1002/(SICI)1098-2418(199810/12)13:3/4<409::AID-RSA11>3.3.CO;2-5
  * [12] Robert A. Beeler, Rodney Keaton and Frederick Norwood  “Deterministic bootstrap percolation on trees”  In _Art Discrete Appl. Math._ 5.2, 2022, pp. Paper No. 2.0819  DOI: 10.26493/2590-9770.1344.20c
  * [13] Fabricio Benevides and Michał Przykucki  “Maximum percolation time in two-dimensional bootstrap percolation”  In _SIAM J. Discrete Math._ 29.1, 2015, pp. 224–251  DOI: 10.1137/130941584
  * [14] Marek Biskup and Roberto H. Schonmann  “Metastable behavior for bootstrap percolation on regular trees”  In _J. Stat. Phys._ 136.4, 2009, pp. 667–676  DOI: 10.1007/s10955-009-9798-x
  * [15] Béla Bollobás et al.  “Bootstrap percolation on Galton-Watson trees”  In _Electron. J. Probab._ 19, 2014, pp. no. 1327  DOI: 10.1214/EJP.v19-2758
  * [16] Milan Bradonjić and Iraj Saniee  “Bootstrap percolation on periodic trees”  In _2015 Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics (ANALCO)_ SIAM, Philadelphia, PA, 2015, pp. 89–96
  * [17] R. Cerf and F. Manzo  “The threshold regime of finite volume bootstrap percolation”  In _Stochastic Process. Appl._ 101.1, 2002, pp. 69–82  DOI: 10.1016/S0304-4149(02)00124-2
  * [18] Raphaël Cerf and Emilio N.. Cirillo  “Finite size scaling in three-dimensional bootstrap percolation”  In _Ann. Probab._ 27.4, 1999, pp. 1837–1850  DOI: 10.1214/aop/1022677550
  * [19] J Chalupa, P L Leath and G R Reich  “Bootstrap percolation on a Bethe lattice”  In _Journal of Physics C: Solid State Physics_ 12.1, 1979, pp. L31  DOI: 10.1088/0022-3719/12/1/008
  * [20] Maurício Collares, Joshua Erde, Anna Geisler and Mihyun Kang  “Universal behaviour of Majority Bootstrap percolation on high-dimensional geometric graphs” In preparation, 2024
  * [21] Peter Dukes, Jonathan Noel and Abel Romer  “Extremal bounds for 3-neighbor bootstrap percolation in dimensions two and three”  In _SIAM J. Discrete Math._ 37.3, 2023, pp. 2088–2125  DOI: 10.1137/22M1534195
  * [22] Mark Granovetter  “Threshold Models of Collective Behavior”  In _American Journal of Sociology_ 83.6, 1978, pp. 1420–1443  DOI: 10.1086/226707
  * [23] Janko Gravner, Christopher Hoffman, James Pfeiffer and David Sivakoff  “Bootstrap percolation on the Hamming torus”  In _Ann. Appl. Probab._ 25.1, 2015, pp. 287–323  DOI: 10.1214/13-AAP996
  * [24] Janko Gravner and Alexander E. Holroyd  “Slow convergence in bootstrap percolation”  In _Ann. Appl. Probab._ 18.3, 2008, pp. 909–928  DOI: 10.1214/07-AAP473
  * [25] Karen Gunderson and Michał Przykucki  “Lower bounds for bootstrap percolation on Galton-Watson trees”  In _Electron. Commun. Probab._ 19, 2014, pp. no. 427  DOI: 10.1214/ECP.v19-3315
  * [26] Ivailo Hartarsky and Lyuben Lichev  “The Maximal Running Time of Hypergraph Bootstrap Percolation”  In _SIAM J. Discrete Math._ 38.2, 2024, pp. 1462–1471  DOI: 10.1137/22M151995X
  * [27] Ivailo Hartarsky and Augusto Teixeira  “Bootstrap percolation is local”, 2024  arXiv:2404.07903 [math.PR]
  * [28] Alexander E. Holroyd  “Sharp metastability threshold for two-dimensional bootstrap percolation”  In _Probab. Theory Related Fields_ 125.2, 2003, pp. 195–224  DOI: 10.1007/s00440-002-0239-x
  * [29] Svante Janson, Tomasz Łuczak, Tatyana Turova and Thomas Vallier  “Bootstrap percolation on the random graph $G_{n,p}$”  In _Ann. Appl. Probab._ 22.5, 2012, pp. 1989–2047  DOI: 10.1214/11-AAP822
  * [30] Mihyun Kang and Tamás Makai  “Bootstrap percolation on $G(n,p)$ revisited”  In _Proceedings of the 27th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms—AofA’16_ Jagiellonian Univ., Dep. Theor. Comput. Sci., Kraków, 2016, pp. 12
  * [31] David Kempe, Jon Kleinberg and Éva Tardos  “Maximizing the spread of influence through a social network”  In _Theory Comput._ 11, 2015, pp. 105–147  DOI: 10.4086/toc.2015.v011a004
  * [32] Natasha Morrison and Jonathan A. Noel  “Extremal bounds for bootstrap percolation in the hypercube”  In _J. Combin. Theory Ser. A_ 156, 2018, pp. 61–84  DOI: 10.1016/j.jcta.2017.11.018
  * [33] Michał Przykucki  “Maximal percolation time in hypercubes under 2-bootstrap percolation”  In _Electron. J. Combin._ 19.2, 2012, pp. Paper 4113
  * [34] Thomas Przykucki  “Smallest percolating sets in bootstrap percolation on grids”  In _Electron. J. Combin._ 27.4, 2020, pp. Paper No. 4.3411  DOI: 10.37236/9582
  * [35] Gian-Paolo Scalia-Tomba  “Asymptotic final-size distribution for some chain-binomial processes”  In _Adv. in Appl. Probab._ 17.3, 1985, pp. 477–495  DOI: 10.2307/1427116
  * [36] Roberto H. Schonmann  “On the behavior of some cellular automata related to bootstrap percolation”  In _Ann. Probab._ 20.1, 1992, pp. 174–193  URL: http://links.jstor.org/sici?sici=0091-1798(199201)20:1%3C174:OTBOSC%3E2.0.CO;2-5&origin=MSN
  * [37] Assaf Shapira  “Metastable behavior of bootstrap percolation on Galton-Watson trees”  In _ALEA Lat. Am. J. Probab. Math. Stat._ 16.2, 2019, pp. 1089–1104  DOI: 10.30757/alea.v16-40
  * [38] Erik Slivken  “Bootstrap percolation on the Hamming torus with threshold 2”, 2017  arXiv:1407.2317 [math.PR]
  * [39] J. Berg and H. Kesten  “Inequalities with applications to percolation and reliability”  In _J. Appl. Probab._ 22.3, 1985, pp. 556–569  DOI: 10.1017/s0021900200029326

## Appendix A

Here we prove auxiliary results in Section 2.2 concerning deterministic
bootstrap percolation on the Hamming graph. Throughout this section, in order