# Universal behaviour of majority bootstrap percolation on high-dimensional
geometric graphs

Maurício Collares and Joshua Erde and Anna Geisler and Mihyun Kang  Institute
of Discrete Mathematics, Graz University of Technology, Steyrergasse 30, 8010
Graz, Austria<EMAIL_ADDRESS>{erde, geisler<EMAIL_ADDRESS>
###### Abstract.

Majority bootstrap percolation is a monotone cellular automata that can be
thought of as a model of infection spreading in networks. Starting with an
initially infected set, new vertices become infected once more than half of
their neighbours are infected. The average case behaviour of this process was
studied on the $n$-dimensional hypercube by Balogh, Bollobás and Morris, who
showed that there is a phase transition as the typical density of the
initially infected set increases: For small enough densities the spread of
infection is typically local, whereas for large enough densities typically the
whole graph eventually becomes infected. Perhaps surprisingly, they showed
that the critical window in which this phase transition occurs is bounded away
from $1/2$, and they gave bounds on its width on a finer scale. In this paper
we consider the majority bootstrap percolation process on a class of high-
dimensional geometric graphs which includes many of the graph families on
which percolation processes are typically considered, such as grids, tori and
Hamming graphs, as well as other well-studied families of graphs such as
(bipartite) Kneser graphs, including the odd graph and the middle layer graph.
We show similar quantitative behaviour in terms of the location and width of
the critical window for the majority bootstrap percolation process on this
class of graphs.

###### 1991 Mathematics Subject Classification:

60K35, 60C05 (Primary)

##  1\. Introduction

###  1.1. Motivation

Bootstrap percolation is a process on a graph which models the spread of an
infection through a population. This model was first considered by Chalupa,
Leath and Reich [20] to describe and analyse magnetic systems, and has been
widely used to describe other interacting particle systems, see [37].

More generally, in the physical sciences and in particular statistical
physics, models in which a system evolves according to a set of ‘local’ and
homogeneous update rules are known as _cellular automata_. This includes the
Ising model or lattice gas automata [31, 36]. Bootstrap percolation is then an
example of a _monotone_ cellular automaton – the ‘state’ (infected or
uninfected) of each site can only change in one direction, and the update rule
is _homogeneous_ (the same for each vertex) and _local_ (determined by the
states of the neighbours).

These models were first analysed rigorously by Schonmann [50]. A related
model, introduced by Bollobás [16], is weak saturation, in which the edges of
a graph $G$ get activated if they complete a copy of a fixed graph $H$.
Bootstrap percolation has been used to model various processes, from the zero-
temperature Ising model in physics [27] to neural networks [5] or opinion
spreading processes in sociology [30]. For a survey on monotone cellular
automata results related to bootstrap percolation see [47] and for physical
applications [46].

The bootstrap percolation process on a graph $G$ evolves in discrete time
steps, which we call _rounds_ , starting with an initial set $A_{0}\subseteq
V(G)$ of infected vertices. In each round, new vertices become infected if at
least a certain threshold $r$ of their neighbours have already been infected.
Since infected vertices never recover, the set $A_{i}$ of vertices which are
infected by the $i$-th round is non-decreasing. In other words, we have a
sequence of sets $A_{0}\subseteq A_{1}\subseteq\ldots$ where
$A_{i}=A_{i-1}\cup\left\\{v\in V(G)\colon\left|N(v)\cap
A_{i-1}\right|\geqslant r\right\\}$ for $i\in\mathbb{N}.$ We will refer to
this process as _$r$ -neighbour bootstrap percolation_. If the infection
spreads to the entire population, i.e., if $\bigcup_{i=0}^{\infty}A_{i}=V(G)$,
then the initial set $A_{0}$ is said to _percolate_ on $G$.

It is apparent that given a graph $G$ and an initially infected set $A_{0}$,
the $r$-neighbour bootstrap percolation process is deterministic, and so each
subset $A_{0}\subseteq V(G)$ is either percolating or non-percolating.
Typically, given a graph or a family of graphs, one can ask about the _worst
case_ or extremal behaviour – what are the ‘minimal’ percolating sets [14, 25,
48] – or about the _typical_ behaviour – are ‘most’ sets percolating or non-
percolating? A natural way to frame the latter question is to look at the
probability $\Phi(p,G)$ that a _random_ subset of a fixed density $p$
percolates. More precisely, in random bootstrap percolation, given a graph $G$
and $p\in(0,1)$, we let ${\bf A}_{p}$ be a $p$-random subset of $V(G)$ where
each vertex in $V(G)$ is included in ${\bf A}_{p}$ independently with
probability $p$ and define

$\Phi(p,G):=\mathbb{P}[{\bf A}_{p}\text{ percolates on }G].$

Since the $r$-neighbour bootstrap percolation process is monotone, it is clear
that the probability of percolation $\Phi(p,G)$ is monotonically increasing in
$p$. It follows from standard results on the existence of thresholds for
monotone graph properties [29] that there is a _threshold_ for random
bootstrap percolation – the percolation probability transitions continuously
from almost $0$ to almost $1$ in a very small window around the _critical
probability_

$p_{c}(G):=\inf\left\\{p\in(0,1)\colon\Phi(p,G)\geqslant\frac{1}{2}\right\\}.$

In this paper we will consider this process on a family of graphs
$(G_{n})_{n\in\mathbb{N}}$, where the critical probability $p_{c}(G_{n})$ is
then a function of $G_{n}$. Asymptotically, this transition from percolation
almost never to almost surely then happens in some _critical window_ , an
interval $I_{n}\subseteq[0,1]$ below which $\Phi(p,G_{n})=o_{n}(1)$ and above
which $\Phi(p,G_{n})=1-o_{n}(1)$. We say there is a _sharp threshold_ if the
width of the critical window is small in comparison to the critical
probability, i.e., if the quotient satisfies

$\lim_{n\to\infty}\frac{|I_{n}|}{p_{c}(G_{n})}=0.$

In the first appearance of bootstrap percolation [20] the authors gave some
bounds for the location and width of the critical window in bootstrap
percolation on the _Bethe lattice_. Subsequent work in the area of physics
also focused on lattice-like structures and observed threshold phenomena [1].
The simplest examples of lattices, and the most well-studied in terms of
bootstrap percolation, come from finite grids $[n]^{d}$ and in particular the
_$d$ -dimensional hypercube_ $[2]^{d}$, which we will denote by $Q_{d}$.
Holroyd [35] demonstrated the existence of a sharp threshold in $2$-neighbour
bootstrap percolation in two-dimensional grids $[n]^{2}$, i.e., the case
$r=d=2$ and for arbitrary $n\in\mathbb{N}$. In three dimensions, bounds on the
critical probability for $r=3$ were determined by Cerf and Cirillo [18]. Later
work of Balogh, Bollobás and Morris [7, 9, 10] showed that there is a sharp
threshold in grids in arbitrary dimension. Cerf and Manzo [19] gave the
critical probability for all finite grids with $3\leqslant r\leqslant d$ up to
constant factors. This line of work culminated in the breakthrough result of
Balogh, Bollobás, Duminil-Copin and Morris [8], which gave a sharp threshold
in all dimensions:

######  Theorem 1.1 ([8, Theorem 1]).

Let $d\geqslant r\geqslant 1$ and consider the random $(r+1)$-neighbour
bootstrap percolation process. Then

$p_{c}\left([n]^{d}\right)=\left(\frac{\lambda(d,r)+o(1)}{\log_{r}(n)}\right)^{d-r},$

where $\lambda(d,r)$ is an explicit constant depending on $d$ and $r$, and
$\log_{r}$ is the iterated logarithm.

Here, and throughout the paper, our asymptotics will be in terms of the
parameter $n$ unless otherwise stated.

As well as in lattice-like graphs, the typical behaviour of bootstrap
percolation has been considered on many other graph classes such as binomial
random graphs [38, 40], inhomogeneous random graphs [28] and infinite trees
[13].

In many physical applications there is a related model which is also natural
to consider, where a vertex becomes infected once at least half of its
neighbours have been infected [27]. We call this process the _majority
bootstrap percolation process_. Note that, in general, this update rule is no
longer homogeneous, as we have a different infection threshold $r(v)=d(v)/2$
for each vertex $v$. However, for $d$-regular graphs, this is again an example
of $r$-neighbour bootstrap percolation with $r=d/2$. Note that, when analysing
the asymptotic behaviour of this process on a family of regular graphs
$(G_{n})_{n\in\mathbb{N}}$, even though the infection threshold $r$ is fixed
for each $G_{n}$, it might vary as a function of $n$.

It is not hard to see that, for any $n$-regular graph $G$ whose order is sub-
exponential in $n$, there is a sharp threshold for percolation in the random
majority bootstrap percolation process near the point $p=\frac{1}{2}$. Indeed,
by standard concentration results, if $p>\frac{1}{2}+\varepsilon$, then with
probability tending to one as $n\to\infty$ more than half of the neighbours of
_every_ vertex in $G$ will lie in the initially infected set, and so the
process will percolate after a single round. Conversely, if
$p<\frac{1}{2}-\varepsilon$, then with probability tending to one as
$n\to\infty$ less than half the neighbours of _every_ vertex in $G$ will lie
in the initially infected set, and so the process will stabilise with the
infected set being the initial set, which is most likely not the entire vertex
set.

Whilst this behaviour cannot be _universal_ to all $n$-regular graphs
(consider for example a disjoint union of many copies of a fixed $n$-regular
graph), it was shown by Bollobás, Balogh and Morris [11] that this sharp
threshold occurs as well for graphs of order super-exponential in $n$ which
satisfy certain nice structural properties. The key point here is to have some
control on the _neighbourhood expansion_ of the host graph, to ensure that all
vertices at distance $i$ from a fixed vertex $x$ have ‘many’ neighbours at
distance $i+1$ from $x$.

######  Theorem 1.2 ([11, Theorem 2.2], informal).

Let $G$ be a regular graph whose order is sufficiently small in terms of the
neighbourhood expansion of the graph and consider the random majority
bootstrap percolation process. Then

$p_{c}(G)=\frac{1}{2}+o(1).$

Furthermore, in the case of the hypercube, they looked at the location and
width of the critical window on a finer scale, and found that the point
$p=\frac{1}{2}$ actually lies outside, and in fact above, the critical window.

######  Theorem 1.3 ([11, Theorem 2.1]).

Let $Q_{n}$ be the $n$-dimensional hypercube and consider the random majority
bootstrap percolation process where the set of initially infected vertices is
a $p$-random subset ${\bf A}_{p}$ with

$p:=\frac{1}{2}-\frac{1}{2}\sqrt{\frac{\log n}{n}}+\frac{\lambda\log\log
n}{\sqrt{n\log n}}.$

Then

$\lim_{n\to\infty}\Phi(p,Q_{n})=\left\\{\begin{array}[]{c@{\quad\textup{if}
\quad}l}0&\lambda\leqslant-2,\\\\[4.30554pt]
1&\lambda>\frac{1}{2}.\end{array}\right.$

Since in this context it makes sense to consider the critical probability as
having an ‘expansion’ around $p=\frac{1}{2}$, it will be useful to introduce
some definitions so as to be able to talk about the strength of bounds on the
location and width of the critical window.

Suppose a property has a critical window of the form $I=p_{1}+p_{2}+\ldots\pm
p_{k}$ where $p_{i}=o_{n}(p_{i-1})$ for each $2\leqslant i<k$ and
$p_{k}=O_{n}(p_{k-1})$. Then, whenever $p_{i}=o_{n}(p_{i-1})$ we say that
$p_{i}$ is the _$i$ -th term_ in the expansion of the critical probability and
the _width_ of the critical window is at most $p_{k}$. In this way, Theorem
1.3 determines the first two terms in the expansion of the critical
probability to be $p_{1}=\frac{1}{2}$ and $p_{2}=-\frac{1}{2}\sqrt{\frac{\log
n}{n}}$, and bounds the width of the critical window to be
$O\left(\frac{\log\log n}{\sqrt{n\log n}}\right)$ for random majority
bootstrap percolation on the $n$-dimensional hypercube.

###  1.2. Main Results

The aim of this paper is to investigate the random majority bootstrap
percolation process on _high-dimensional geometric_ graphs. The
$n$-dimensional hypercube has many equivalent representations: For example, it
is the nearest neighbour graph on the set of points $\\{0,1\\}^{n}$; it is the
Cayley graph of $\mathbb{Z}_{2}^{n}$ with the standard generating set; it is
the Cartesian product of $n$ copies of a single edge; and it is the skeleton
of a particularly simple convex polytope in $\mathbb{R}^{n}$ – all of which in
some sense witness the fact that $Q_{n}$ is high-dimensional.

We will study the majority bootstrap percolation process on other graphs with
similar high-dimensional representations. For example, many natural classes of
lattice-like graphs can be realised as Cartesian products of small graphs,
such as grids, tori and Hamming graphs, which are the Cartesian products of
paths, cycles and complete graphs, respectively. Such graphs are commonly
studied in percolation theory [2, 24, 26, 32] and in particular in the context
of bootstrap percolation [14, 41].

Another well-studied class of high-dimensional graphs are Kneser graphs and
bipartite Kneser graphs, which encode how different subsets of a fixed set
intersect. Of particular interest here are the middle layers graph $M_{n}$ and
the odd graph $O_{n}$ whose combinatorial properties have been extensively
studied [15, 49, 42]. The odd graph $O_{n}$ belongs to the family of
_generalised odd graphs_ that are related to incidence geometries and in
particular to _near polygons_ , see [17]. Another well-known example of a
generalised odd graph is the $(n-1)$-dimensional _folded hypercube_
$\tilde{Q}_{n}$ obtained by joining each pair of antipodal points in the
hypercube $Q_{n-1}$. This graph has also commonly been used as a lower-
diameter alternative to the hypercube in the context of network topology [4].
Percolation processes have also been considered on some of these graphs, in
the context of the transference of combinatorial results to sparse random
substructures [12].

In this paper we will study a general class
$\mathcal{H}=\bigcup_{K\in\mathbb{N}}\mathcal{H}(K)$ of graphs satisfying
certain structural properties (see Section 3 for formal definition), which are
satisfied by various high-dimensional geometric graphs, and in particular the
graphs listed above. Roughly speaking, $\mathcal{H}(K)$ consists of graphs
whose structure is _close_ – in a quantitative manner in terms of the
parameter $K$ – to being controlled by some coordinate system, which may only
be defined locally with respect to each vertex and need not be globally
coherent, where edges correspond to changing a single coordinate.

We will show that there is a certain _universal behaviour_ to the random
majority bootstrap percolation process on graphs in the class
$\mathcal{H}(K)$, which is controlled in some way by the degree sequence, and
we will in particular determine the first few terms in the expansion of the
critical probability for regular graphs in $\mathcal{H}(K)$. In fact, we show
that the critical window does not contain $\frac{1}{2}$, for _arbitrary_
graphs $G$ in the class $\mathcal{H}(K)$, where the upper and lower boundary
of the critical window are functions of the minimum and maximum degree of $G$,
denoted by $\delta(G)$ and $\Delta(G)$, respectively.

Our main theorem is as follows.

######  Theorem 1.4.

Let $(G_{n})_{n\in\mathbb{N}}$ be a sequence of graphs in $\mathcal{H}(K)$ for
some $K\in\mathbb{N}$ such that $\delta(G_{n})\to\infty$ as $n\to\infty$ and
let $p=p(n)\in[0,1]$. Consider the random majority bootstrap percolation
process where the set of initially infected vertices is a $p$-random subset
${\bf A}_{p}$. Then for any constant $\varepsilon>0$,

$\lim_{n\to\infty}\Phi(p,G_{n})=\left\\{\begin{array}[]{c@{\quad\textup{if}
\quad}l}0&p<\frac{1}{2}-\left(\frac{1}{2}+\varepsilon\right)\sqrt{\frac{\log\delta(G_{n})}{\delta(G_{n})}},\\\\[4.30554pt]
1&p>\frac{1}{2}-\left(\frac{1}{2}-\varepsilon\right)\sqrt{\frac{\log\Delta(G_{n})}{\Delta(G_{n})}}.\end{array}\right.$

In particular, if the graphs $G_{n}$ are regular, then Theorem 1.4 determines
the first two terms in the expansion of the critical probability, as in
Theorem 1.3 for the hypercube.

######  Corollary 1.5.

Let $(G_{n})_{n\in\mathbb{N}}$ be a sequence of $d$-regular graphs in
$\mathcal{H}(K)$ for some $K\in\mathbb{N}$ such that $d=d(n)\to\infty$ as
$n\to\infty$ and let $p=p(n)\in[0,1]$. Consider the random majority bootstrap
percolation process where the set of initially infected vertices is a
$p$-random subset ${\bf A}_{p}$. Then for any constant $\varepsilon>0$,

$\lim_{n\to\infty}\Phi(p,G_{n})=\left\\{\begin{array}[]{c@{\quad\textup{if}
\quad}l}0&p<\frac{1}{2}-\left(\frac{1}{2}+\varepsilon\right)\sqrt{\frac{\log
d}{d}},\\\\[4.30554pt]
1&p>\frac{1}{2}-\left(\frac{1}{2}-\varepsilon\right)\sqrt{\frac{\log
d}{d}}.\end{array}\right.$

In particular, this holds if $G_{n}$ is

  * •

an $n$-dimensional regular Cartesian product graph whose base graphs have
bounded size;

  * •

the $n$-dimensional middle layer graph $M_{n}$;

  * •

the $n$-dimensional odd graph $O_{n}$; or

  * •

the $n$-dimensional folded hypercube $\tilde{Q}_{n}$.

Note that $M_{n}$, $O_{n}$ and $\tilde{Q}_{n}$ are $n$-regular.

Corollary 1.5 shows that for _$d$ -regular_ graphs in $\mathcal{H}(K)$ there
is a sharp percolation threshold for the random majority bootstrap percolation
process. More precisely, we find that the behaviour in Theorem 1.3, when
scaled correctly, is in some way _universal_ for these high-dimensional
graphs, in that the first two terms in the expansion of the critical
probability are $\frac{1}{2}-\frac{1}{2}\sqrt{\frac{\log d}{d}}$ and the
critical window has width $o\left(\sqrt{\frac{\log d}{d}}\right)$: In other
words, for any _$d$ -regular_ graph $G$ in $\mathcal{H}(K)$, the critical
probability satisfies

$p_{c}(G)=\frac{1}{2}-\frac{1}{2}\sqrt{\frac{\log
d}{d}}+o\left(\sqrt{\frac{\log d}{d}}\right).$

###  1.3. Proof Techniques

In [11] Balogh, Bollobás and Morris show that, at least in the $n$-dimensional
hypercube, the event that a vertex becomes infected is in some sense ‘locally
determined’. Indeed, for the $1$-statement they show that with probability
tending to one as $n\to\infty$ (whp) every vertex becomes infected after at
most eleven rounds. For the $0$-statement they analyse a related process,
which stochastically dominates the majority bootstrap percolation process, and
show that whp this process stabilises after three rounds, and in fact whp a
positive proportion of the vertices remains uninfected. Note that whether or
not a vertex $v$ is infected after $k$ rounds only depends on the set of
initially infected vertices at distance at most $k$ from $v$.

A key tool in our proof of Theorem 1.4 is that the degree distributions of
graphs in $\mathcal{H}(K)$ are locally quite ‘flat’, in the sense that the
degrees in a small neighbourhood of a vertex $v$ are relatively close to the
degree of $v$. Roughly, such graphs look _locally approximately regular_. If,
as in the work of Balogh, Bollobás and Morris [11], we expect the probability
that a vertex $v$ becomes infected to be ‘locally determined’, we might hope
that for each vertex $v$ there is a critical probability $\tilde{p}_{c}(v)$,
which depends only on its degree $d(v)$, such that significantly above this
threshold it is very likely that $v$ becomes infected, whereas significantly
below this threshold there is a positive probability that $v$ remains
uninfected, at least for the first few rounds of the process. In particular,
we should expect the process to percolate when $p\gg\max_{v\in
V(G)}\tilde{p}_{c}(v)$, and we should expect the process not to percolate when
$p\ll\min_{v\in V(G)}\tilde{p}_{c}(v)$.

Let us describe in more detail how we make this heuristic argument precise.
For the $1$-statement we note that, since we are considering probabilities
close to $\frac{1}{2}$, the probability that a vertex is not infected in the
first round is roughly $\frac{1}{2}$. We first show that, for each $v\in V(G)$
when $p$ is above $\tilde{p}_{c}(v):=\frac{1}{2}-\frac{1}{2}\sqrt{\frac{\log
d(v)}{d(v)}}$, the probability that $v$ is _not infected_ after two rounds is
already much smaller, at most $\frac{1}{4}$ (Lemma 4.1).

We then bootstrap this result twice, first to show that the probability that
$v$ is not infected after five rounds is exponentially small in $d(v)$ (Lemma
4.2), and then again to show that the probability that $v$ is not infected
after eleven rounds is super-exponentially small in $d(v)$ (Lemma 4.3). Since
we assume that the graphs in $\mathcal{H}(K)$ are not too large, roughly of
exponential order, this is sufficient to deduce the $1$-statement using a
union bound. To avoid dependencies when bootstrapping our results, and to
simplify our analysis, we actually analyse a slightly more restrictive
bootstrap percolation process, which is dominated by the original process,
where the local infection parameter $r(v)$ is slightly larger than
$\frac{d(v)}{2}$. This broad strategy for proving the 1-statement follows the
approach of [11].

A key property of graphs in $\mathcal{H}(K)$ which allows us to bootstrap
these results is a certain “fractal self-symmetry” which roughly says we can
split those graphs into many copies of (lower-dimensional) graphs having the
same structural properties. This property has also been key to the study of
bond and site percolation on high-dimensional graphs [22, 23, 24].

For the $0$-statement, we analyse a slight variant of the majority bootstrap
process which dominates the original process, where the infection parameter
$r$ varies over time, starting slightly below $\frac{d(v)}{2}$ and increasing
to $\frac{d(v)}{2}$ in a finite number of rounds. This idea, which originates
in [11], allows us to assume that vertices which become infected in round $i$
for $i>1$ have a significant number of neighbours which became infected in
round $i-1$. We first show that in this new process, a vertex which is not
infected by the second round is extremely unlikely to become infected in the
third round, and so whp this process stabilises after two rounds (Lemma 5.1).
Here, a judicious choice of parameterisation simplifies the analysis of this
process, allowing us to conclude that the process stabilises after only two
rounds. We then conclude by showing that whp some vertices are not infected by
the second round (Lemma 5.2).

The paper is structured as follows: In Section 2 we introduce some notation
and probabilistic tools that we use. In Section 3 we explicitly describe the
structural assumptions satisfied by our class $\mathcal{H}(K)$ of high-
dimensional graphs. The proof of Theorem 1.4 is then split up into a proof of
the $1$-statement in Section 4 and a proof of the $0$-statement in Section 5,
with some of the technical details deferred to Sections 6 and 7. Afterwards we
give specific examples of several graphs that are contained in the class
$\mathcal{H}$ of graphs in Section 8. We close with a discussion of the limits
of the techniques used and some open questions in Section 9.

##  2\. Preliminaries

For $n\in\mathbb{N}$ we denote by $[n]$ the set of integers up to $n$, i.e.,
$[n]:=\\{1,\dots,n\\}$. Given $y,z\in\mathbb{R}$ we will write $y\pm z$ to
denote the interval $[y-z,y+z]$. Similar to $O(\cdot)$ notation, an inclusion
is meant whenever $\pm$ appears in the context of an equality. For example,
$x=y\pm z$ means that $x\in[y-z,y+z]$. Whenever the base of a logarithm is not
specified, we use the natural logarithm, i.e., $\log x=\ln x=\log_{e}x$. For
ease of presentation we will omit floor and ceiling signs in calculations.

###  2.1. Probabilistic tools

In this section we will state a number of probabilistic tools which are used
throughout the paper.

We will assume knowledge of Markov’s and Chebyshev’s inequalities as standard
(see [3] for basic probabilistic background). However, through the paper we
will need much more precise tail bounds, both from above and below, for
binomial and related distributions. The first is a standard form of the
Chernoff bounds, see for example [3, Appendix A].

######  Lemma 2.1.

Let $d\in\mathbb{N}$, $0<p<1$, and $X\sim\operatorname{Bin}(d,p)$. Then

  1. $(a)$

For every $t\geqslant 0$,

$\mathbb{P}\big{[}|X-dp|\geqslant
t\big{]}\;\leqslant\;2\exp\left(-\frac{2t^{2}}{d}\right);$

  2. $(b)$

For every $b\geqslant 1$,

$\mathbb{P}[X\geqslant bdp]\leqslant\left(\frac{e}{b}\right)^{bdp}.$

At times we will also need an anti-concentration result for binomial random
variables. As these converge in distribution to a normal distribution we will
derive these from tail bounds for the standard normal distribution $N(0,1)$.
Proofs can be found in [51, Section 5.6].

######  Lemma 2.2.

For $d\in\mathbb{N}$, $p=p(d)\in(0,1)$ and $f(d)=o(d^{1/6})$, it holds that

$\mathbb{P}\left[\frac{\operatorname{Bin}(d,p)-dp}{\sqrt{dp(1-p)}}\geqslant
f(d)\right]=(1+o(1))\mathbb{P}\left[N(0,1)\geqslant f(d)\right].$

Moreover, if $f(d)\to\infty$ as $d\to\infty$, the probability that the
standard normal distribution exceeds $f(d)$ satisfies

$\mathbb{P}[N(0,1)\geqslant
f(d)]=\frac{1+o(1)}{f(d)\sqrt{2\pi}}\exp\left(-\frac{f(d)^{2}}{2}\right).$

Since binomial random variables can be written as sums of independent
Bernoulli random variables, the standard inequality due to Hoeffding [33]
readily implies the following lemma.

######  Lemma 2.3.

Let $k,d_{1},\ldots,d_{k}\in\mathbb{N}$ and $p\in(0,1)$. Let
$X_{i}\sim\operatorname{Bin}(d_{i},p)$ for each $i\in[k]$, let
$Y=\sum_{i=1}^{k}iX_{i}$, and let $D(k)=\sum_{i=1}^{k}i^{2}d_{i}$. Then, for
every $\tau>0$,

$\mathbb{P}\big{[}Y\geqslant\mathbb{E}[Y]+\tau\big{]}\leqslant\exp\left(-\frac{2\tau^{2}}{D(k)}\right)\leqslant\exp\left(-\frac{2\tau^{2}}{k\cdot\mathbb{E}[Y]}\right).$

We will also need the following lemma from [11] which broadly tells us that,
if we think of a $\operatorname{Bin}(n,p)$ random variable as the number of
successful trials in a sequence of $n$ independent trials with success
probability $p$, then there is only a slight correlation between the result
and the outcome of the first trial.

######  Lemma 2.4 ([11], Lemmas 3.8 and 3.9).

Let $d\in\mathbb{N}$, let $p=p(d)=\frac{1}{2}-o(1)$. Let $X_{1},\ldots,X_{d}$
be independent and identically distributed $\textup{Ber}(p)$ random variables
and let $X=\sum_{i=1}^{d}X_{i}\sim\operatorname{Bin}(d,p)$. Then, for any
$0\leqslant m=m(d)\leqslant d/2$,

$\mathbb{P}\left[X\geqslant
m\nonscript\>\middle|\nonscript\>\mathopen{}X_{1}=1\right]=\big{(}1+o(1)\big{)}\,\mathbb{P}\big{[}X\geqslant
m\big{]}$

and

$\mathbb{P}\left[X_{1}=1\nonscript\>\middle|\nonscript\>\mathopen{}X\geqslant
m\right]=\big{(}1+o(1)\big{)}\,\mathbb{P}\big{[}X_{1}=1\big{]}.$

By induction and the law of total probability, it follows from Lemma 2.4 that
for any bounded $k\in\mathbb{N}$ and any
$\varepsilon=(\varepsilon_{1},\ldots,\varepsilon_{k})\in\\{0,1\\}^{k}$,

$\mathbb{P}\big{[}X\geqslant
m\nonscript\>\big{|}\nonscript\>\mathopen{}X_{1}=\varepsilon_{1},\ldots,X_{k}=\varepsilon_{k}\big{]}=\big{(}1+o(1)\big{)}\,\mathbb{P}\big{[}X\geqslant
m\big{]}.$

Finally we will need the fact that the median of a binomial random variable is
essentially equal to its mean, see for example [39, Theorem 1].

######  Proposition 2.5.

Let $X\sim\operatorname{Bin}(d,p)$. Then the median of $X$ is either
$\lfloor\mathbb{E}[X]\rfloor$ or $\lceil\mathbb{E}[X]\rceil$, and thus
$\mathbb{P}[X\geqslant C]\geqslant\frac{1}{2}$ for any integer $C$ such that
$C\leqslant\mathbb{E}[X]$.

##  3\. Nice structural properties of geometric graphs

In this section we discuss the properties of the graphs in the class
$\mathcal{H}(K)$. Roughly, one can think of these graphs as having a structure
which is in some sense _close_ to being governed by some _local coordinate
system_ , where edges are only allowed between vertices which differ in a
single coordinate. Crucially there are only ever a bounded number of
neighbours in each coordinate.

Given a graph $G$ we will write $d(G)$ for the average degree of $G$,
$\delta(G)$ for the minimum degree of $G$ and $\Delta(G)$ for the maximum
degree of $G$. Given two vertices $x,y\in V(G)$ we will write
$\operatorname{dist}_{G}(x,y)$ for the _distance_ between $x$ and $y$ in $G$,
that is, the length of the shortest $x-y$ path in $G$. Given
$k\in\mathbb{N}\cup\\{0\\}$ and $x\in V(G)$ we let

$B_{G}(x,k):=\\{y\in V(G)\colon\operatorname{dist}_{G}(x,y)\leqslant k\\}$

be the _ball of radius $k$_ centred at $x$ and

$S_{G}(x,k):=B_{G}(x,k)\setminus B_{G}(x,k-1)$

be the _sphere of radius $k$_ centred at $x$, where $S_{G}(x,0):=\\{x\\}$.
Note that $B_{G}(x,0)=\\{x\\}$, $S_{G}(x,1)=N_{G}(x)$, and
$B_{G}(x,1)=\\{x\\}\cup N_{G}(x)$. When the underlying graph $G$ is clear from
the context, we will omit the subscript in this notation.

Given $K\in\mathbb{N}$ define the _class $\mathcal{H}(K)$ of geometric graphs_
recursively by taking the single-vertex graph $K_{1}\in\mathcal{H}(K)$ and
then taking every graph $G$ satisfying Properties P1, P2, P3, P4, P5 and P6
below.

######  Property P1 (Locally almost regular).

For every $x\in V(G)$, $\ell\in\mathbb{N}$ and $y\in S(x,\ell)$, we have

$|d(x)-d(y)|\leqslant K\ell.$

In this case we say that $G$ is _locally $K$-almost regular_. Heuristically,
vertices at a small distance should agree in almost all their coordinates, and
so their degrees, which are the sum of the number of neighbours in each
coordinate, should be similar.

######  Property P2 (Bounded backwards expansion).

For every $x\in V(G)$, $\ell\in\mathbb{N}$ and $y\in S(x,\ell)$, we have

$|N(y)\cap B(x,\ell)|\leqslant K\ell.$

In this case we say that $G$ has _$K$ -bounded backwards expansion_. Note that
having bounded backwards expansion is qualitatively equivalent to having good
_neighbourhood expansion_ as in Theorem 1.2 from [11]. Heuristically, a vertex
$y$ at distance $\ell$ from $x$ differs from $x$ in at most $\ell$
coordinates, and the only neighbours of $y$ which are not further away from
$x$ also differ in a subset of these coordinates. Note that Properties P1 and
P2 imply that

$|S(x,\ell)|=\Theta(d(x)^{\ell}).$

######  Property P3 (Typical local structure).

For every $x\in V(G)$ there is a set $D\subseteq V(G)\setminus\\{x\\}$ of
_non-typical_ vertices such that for every $\ell\in\mathbb{N}$ the following
hold:

  1. $(i)$

$|D\cap S(x,\ell)|\leqslant K^{\ell-1}d(x)^{\ell-1}$;

  2. $(ii)$

$|D\cap N(y)|\leqslant K\ell$ for every vertex $y\in S(x,\ell)\setminus D$;

  3. $(iii)$

every two vertices in $S(x,\ell)\setminus D$ have at most one common neighbour
in $S(x,\ell+1)\setminus D$.

For every graph $G$ that fulfils Property P3 and every $x\in V(G)$, we set

$S_{0}(x,\ell):=S(x,\ell)\setminus D.$

Heuristically, since the number of neighbours in each coordinate is always
bounded, a typical vertex at distance $\ell$ from $x$ differs in precisely
$\ell$ coordinates from $x$. The set $D$ takes care of the non-typical
vertices, as well as taking into account the ‘error’ in our approximate
coordinate system. Conditions i and ii say that the set $D$ is small and
locally sparse, whereas Condition iii clarifies a property we should expect of
$S_{0}(x,\ell)$ – if two vertices $u$ and $w$ differ from $x$ in precisely
$\ell$ coordinates there is at most one vertex $v$ which differs from $x$ in
precisely $\ell+1$ coordinates and differs from $u$ and $w$ in a single
coordinate.

######  Property P4 (Projection).

For every $x\in V(G)$, $\ell\in\mathbb{N}$ and $y\in S(x,\ell)$, there is a
subgraph $G(y)$ of $G$ such that the following hold:

  1. $(i)$

$y\in V(G(y))$;

  2. $(ii)$

$G(y)\in\mathcal{H}(K)$;

  3. $(iii)$

$V(G(y))\cap B(x,\ell-1)=\varnothing$;

  4. $(iv)$

$|d_{G(y)}(w)-d_{G}(w)|\leqslant K\ell$ for all $w\in V(G(y))$.

In this case we say that $G$ has the _$K$ -projection property_.
Heuristically, the idea here is that vertices at a short distance will only
differ in a small number of ‘coordinates’, and by fixing these coordinates and
allowing the others to vary, we should obtain a lower-dimensional graph $G(y)$
with similar properties to $G$ which is disjoint from $B(x,\ell-1)$. This
property reflects a notion of fractal self-symmetry of the graph.

We note that in all our applications, the graphs $G(y)$ can in fact be taken
to be a ‘lower dimensional’ graph with a similar description to $G$. For
example, in the case of the hypercube these projections can be taken to be
subcubes, although in general they might come from a slightly more general
family than the original graph $G$.

######  Property P5 (Separation).

For every $x\in V(G)$, $\ell\in\mathbb{N}$ and $y\in S_{0}(x,\ell)$, we have

$|B(y,2\ell-1)\cap S_{0}(x,\ell)|\leqslant\ell K^{\ell-1}d(x)^{\ell-1}.$

In this case we say that $G$ satisfies the _$K$ -separation property_.
Heuristically, vertices in $S_{0}(x,\ell)\subseteq S(x,\ell)$ will typically
differ from $x$ in $\ell$ coordinates, and so for each vertex $y\in
S_{0}(x,\ell)$ the vertices in $B(y,2\ell-1)\cap S_{0}(x,\ell)$ will typically
agree with $y$ in one coordinate in which it differs from $x$, leaving one
fewer ‘degree of freedom’ for the choice of such vertices.

In particular, the $K$-separation property implies the following separation
lemma.

######  Lemma 3.1 (Separating partition).

Suppose $G$ satisfies Properties P3 and P5 for some $K\in\mathbb{N}$. For each
$x\in V(G)$ and $\ell\in\mathbb{N}$, there exists a partition $\mathcal{P}$ of
$S(x,\ell)$,

$S(x,\ell)=P_{1}\cup\dots\cup P_{m},$

into $m$ disjoint sets $P_{1},\ldots,P_{m}$ such that the following hold:

  1. $(i)$

$m\leqslant(\ell+1)K^{\ell-1}d(x)^{\ell-1}$;

  2. $(ii)$

$\operatorname{dist}(y_{1},y_{2})\geqslant 2\ell$ for all distinct
$y_{1},y_{2}\in P_{j}$ and every $j\in[m]$.

###### Proof.

By Property P3 there are at most $K^{\ell-1}d(x)^{\ell-1}$ vertices in $D\cap
S(x,\ell)$. Choose a new partition class $P_{i}$ for each such vertex.

Choose the partition of $S_{0}(x,\ell)$ greedily by putting each vertex $w\in
S_{0}(x,\ell)$ in the first partition class such that the distance condition
is satisfied. For $y\in S_{0}(x,\ell)$, by Property P5 we have
$|B(y,2\ell-1)\cap S_{0}(x,\ell)|\leqslant\ell K^{\ell-1}d(x)^{\ell-1}$. Thus
we get at most this many partition classes for $S_{0}(x,\ell)$.

Combining the number of partition classes from $S(x,\ell)\cap D$ and
$S_{0}(x,\ell)$ proves the claim. ∎

We note that while Properties P1, P2, P3, P4 and P5 make assertions for each
$\ell\in\mathbb{N}$, in fact in the proof of Theorem 1.4 we will only need
these properties for $\ell\leqslant 6$. Finally, our proof methods require
that the graph $G$ is not too large.

######  Property P6 (Exponential order).

$G$ has at most $\exp(K\delta(G))$ vertices.

##  4\. Proof of the 1-statement of Theorem 1.4

Throughout the rest of the paper we assume that $G$ is a graph in
$\mathcal{H}(K)$ for some $K\in\mathbb{N}$ (so $G$ satisfies Properties P1,
P2, P3, P4, P5 and P6 for this $K$), and all asymptotics will be as
$\delta(G)\to\infty$.

In this section we will prove the 1-statement of Theorem 1.4: For any
$\varepsilon>0$, if

$p>\frac{1}{2}-\left(\frac{1}{2}-\varepsilon\right)\sqrt{\frac{\log\Delta(G)}{\Delta(G)}},$

then

$\Phi(p,G):=\mathbb{P}[{\bf A}_{p}\text{ percolates on }G]\to 1.$

In fact, we will prove that

$\mathbb{P}[\exists x\in V(G):x\notin A_{11}]=o(1).$

Along the proof we will introduce auxiliary lemmas, but their proofs are
deferred to Section 6.

For each vertex $x\in V(G)$ let

$\sigma(x):=\sqrt{\frac{\log d(x)}{d(x)}}$

and choose the probability $p$ to be significantly larger than

$\tilde{p}_{c}(x):=\frac{1}{2}-\frac{1}{2}\sigma(x).$

More precisely, for $c<\frac{1}{2}$ we let

$p:=\frac{1}{2}-c\sigma(x).$

Since the initially infected set of vertices $A_{0}$ is distributed as a
$p$-random subset ${\bf A}_{p}$ of $V(G)$, the probability that a vertex $x$
lies in $A_{0}$ is approximately $\frac{1}{2}$. We start by showing that the
probability that $x$ is infected after the first two rounds is already
significantly larger than $\frac{1}{2}$.

In fact, we will show a slightly stronger statement, bounding the probability
that a vertex $x$ is infected in the first two rounds of a slightly weaker
infection process, where the threshold to infect a vertex $v$ is raised from
$\frac{d(v)}{2}$ to $\frac{d(v)}{2}+m$ for some fixed
$m\in\mathbb{N}\cup\\{0\\}$. More precisely, we define recursively
$A_{0}(m):=A_{0}$ and for each $i\in\mathbb{N}\cup\\{0\\}$

$A_{i+1}(m):=A_{i}(m)\cup\left\\{v\in V(G)\colon|A_{i}(m)\cap
N(v)|\geqslant\frac{d(v)}{2}+m\right\\}.$

Note that if $m=0$, then $A_{i}=A_{i}(m)$ for all $i\in\mathbb{N}$ and that
for any $m\geqslant 0$,

$A_{i}(m)\subseteq A_{i}\text{ for all }i\in\mathbb{N}.$

The event that a vertex $x$ is infected by the second round depends only on
vertices at distance at most two from $x$. More precisely, whether $x$ is
infected in the second round only depends on how many neighbours of $x$ are
infected initially and how many are infected in the first round. The number of
initially infected neighbours is given by a binomial random variable with
expectation $d(x)/2-c\sqrt{d(x)\log d(x)}$, and so in order to infect $x$ in
the second round, on average we need around $c\sqrt{d(x)\log d(x)}$ many
additional neighbours of $x$ to be infected in the first round.

For each neighbour of $x$ there is a small but non-negligible chance that it
is infected in the first round. Indeed, since the number of initially infected
neighbours of a vertex is distributed binomially, we can use the anti-
concentration statement in Lemma 2.2 to calculate quite precisely the
probability that it is infected in the first round, which is around
$\Omega\left(d(x)^{-2c^{2}}\right)$ as we will show later, and so the expected
number of neighbours of $x$ which will be infected in the first round is of
order $\Omega\left(d(x)^{1-2c^{2}}\right)\gg\sqrt{d(x)\log d(x)}$.
Furthermore, the local structure of graphs in $\mathcal{H}(K)$ ensures that
for two neighbours of $x$ the events that they get infected in the first round
are close to independent. This allows us to show that it is reasonably likely
that $x$ will be infected in the second round using a second moment argument.

######  Lemma 4.1.

Let $m\in\mathbb{N}\cup\\{0\\}$, $x\in V(G)$, $c<\frac{1}{2}$,
$p=\frac{1}{2}-c\sigma(x)$ and $A_{0}\sim{\bf A}_{p}$. If there is a
$K\in\mathbb{N}$ such that $G\in\mathcal{H}(K)$, then

$\mathbb{P}\left[x\in A_{2}(m)\right]\geqslant\frac{3}{4}+o(1).$

We note that for the proof of Lemma 4.1 we will only need Properties P1, P2
and P3 (see Section 6).

Next we show that, above the probability
$\tilde{p}_{c}(x)=\frac{1}{2}-\frac{1}{2}\sigma(x)$, the probability that a
vertex $x$ is not infected shrinks quickly, from a constant probability in the
second round to an exponentially small one by the fifth round.

Let us sketch the main ideas. If a vertex $x$ is not infected by the fifth
round, then there is a subset $T^{\prime}\subseteq N(x)$ of size
$\frac{d(x)}{2}$ which is not infected by the fourth round. Since no vertex in
$T^{\prime}$ is infected by the fourth round, and each vertex in $T^{\prime}$
has approximately degree $d(x)$ there are at most roughly $d(x)|T^{\prime}|/2$
many edges from $T^{\prime}$ to $A_{3}$. However, using the explicit structure
of our graph $G\in\mathcal{H}(K)$, it is easy to show that the number of edges
from $T^{\prime}$ to the sphere $S(x,2)$ is approximately $d(x)|T^{\prime}|$.

Since, by Lemma 4.1, each vertex is in $A_{2}$ (and hence also in $A_{3}$)
with probability larger than say $2/3$, it should be very unlikely that fewer
than half the edges from $T^{\prime}$ to $S(x,2)$ go to vertices in $A_{3}$.
However, due to the dependencies between the events that vertices in $S(x,2)$
lie in $A_{3}$, it is difficult to make this precise.

Instead, we look one round further – if many vertices in $T=N(T^{\prime})\cap
S(x,2)$ are not infected by the third round then we again find that at most
half of the edges from $T$ to the sphere $S(x,3)$ go to vertices in $A_{2}$.
However, by Lemma 3.1 we can partition $S(x,3)$ into $O(d^{2})$ sets whose
pairwise distance is at least $4$. In particular, in any partition class the
events that the vertices lie in $A_{2}$ are mutually independent. By a double-
counting argument we can find one partition class $B\subseteq S(x,3)$ in which
less than half of the edges from $T$ to $B$ go to vertices in $A_{2}$, which
is very unlikely since each vertex in $B$ lies in $A_{2}$ with probability at
least $2/3$ and these events are independent.

However, whether the vertices in $B$ lie in $A_{2}$ might still depend on the
sets of initially infected vertices in $S(x,1)$ and $S(x,2)$ which also
influence our choices of $T^{\prime},T$ and $B$. To get around this issue we
use Property P4 to find for each $y\in B$ a slightly smaller graph
$G(y)\in\mathcal{H}(K)$ with $G(y)\subseteq G\setminus B(x,2)$, where the
vertex degrees and structure are approximately preserved. This guarantees that
infection with a slightly increased threshold in $G(y)$ is sufficient to imply
infection in $G$, and allows us to apply Lemma 4.1 to $y$ inside the subgraph
$G(y)$.

######  Lemma 4.2.

Let $x\in V(G)$, $c<\frac{1}{2}$, and $p=\frac{1}{2}-c\sigma(x)$. If there is
a $K\in\mathbb{N}$ such that $G\in\mathcal{H}(K)$, then there exists a
$\beta>0$ (independent of $x$) such that

$\mathbb{P}\big{[}x\notin A_{5}\big{]}\leqslant\exp\bigl{(}-\beta
d(x)\bigr{)}.$

We note that for the proof of Lemma 4.2 we will use Properties P1, P2, P3, P4
and P5 (see Section 6).

Finally, we bootstrap Lemma 4.2 to show that after six more rounds the
probability that a vertex is not infected shrinks even further, and becomes
super-exponentially small. Since the order of the graphs in Theorem 1.4 are
exponential in their vertex degrees, this will be enough to deduce that, above
an appropriate threshold, whp all vertices will become infected by the
eleventh round.

Here we can afford to be slightly less careful than in Lemma 4.2. If a vertex
$x$ is not infected by the $k$-th round, it is relatively easy to show that
the number of vertices at distance $\ell$ which are not infected by the
$(k-\ell)$-th round must be growing like $\Theta\left(d(x)^{\ell}\right)$. In
particular, if $x$ is not infected by the eleventh round, there is some set
$T^{\prime}$ with $\Theta(d(x)^{6})$ many vertices in the sphere $S(x,6)$
which are uninfected by the fifth round. By Lemma 3.1 we can partition
$S(x,6)$ into $O(d(x)^{5})$ many sets within which all vertices have pairwise
distance at least twelve. By an averaging argument, some partition class $P$
must contain a large number of vertices in $T^{\prime}$. However, since the
events that the vertices of $P$ are not infected by the fifth round are
independent, and each is unlikely by Lemma 4.2, it follows from Chernoff’s
inequality (Lemma 2.1) that it is extremely unlikely that any partition class
contains a large number of vertices in $T^{\prime}$.

######  Lemma 4.3.

Let $x\in V(G)$, $c<\frac{1}{2}$, and $p=\frac{1}{2}-c\sigma(x)$. If there is
a $K\in\mathbb{N}$ such that $G\in\mathcal{H}(K)$, then there exists a
$\beta>0$ (independent of $x$) such that

$\mathbb{P}\big{[}x\notin A_{11}\big{]}<\exp\bigl{(}-\beta d(x)^{2}\bigr{)}.$

We note that for the proof of Lemma 4.3 we will use Properties P1, P2, P3, P4
and P5 (see Section 6).

We are now in a position to prove the $1$-statement of Theorem 1.4.

###### Proof of $1$-statement in Theorem 1.4.

Let $K\in\mathbb{N}$ and let $(G_{n})_{n\in\mathbb{N}}$ be a sequence of
graphs such that $G_{n}\in\mathcal{H}(K)$ and $\delta(G_{n})\to\infty$ as
$n\to\infty$. We write $G\coloneqq G_{n}$.

Let $\varepsilon>0$ and let

$p>\frac{1}{2}-\left(\frac{1}{2}-\varepsilon\right)\sqrt{\frac{\log\Delta(G)}{\Delta(G)}}.$

Since $d\mapsto\frac{1}{2}-\left(\frac{1}{2}-\varepsilon\right)\sqrt{(\log
d)/d}$ is an increasing function in $d$, by Lemma 4.3 there exists $\beta>0$
such that for every $x\in V(G)$

$\mathbb{P}\left[x\notin A_{11}\right]\leqslant\exp(-\beta
d(x)^{2})\leqslant\exp(-\beta\delta(G)^{2}).$

Hence, by Property P6 we have $|V(G)|\leqslant\exp(K\delta(G))$ and so

$\displaystyle 1-\Phi(p,G)=\mathbb{P}[{\bf A}_{p}\text{ does not percolate on
}G]\ $ $\displaystyle\leqslant\mathbb{P}[\exists x\in V(G):x\notin A_{11}]$
$\displaystyle\leqslant|V(G)|\cdot\exp(-\beta\delta(G)^{2})=o(1),$ (1)

concluding the proof. ∎

######  Remark 4.4.

As mentioned before, Lemmas 4.1, 4.2 and 4.3 do not use Property P6. The union
bound in the last step of (1) is the only use of Property P6 in the proof
above. Therefore, the $1$-statement also holds for graphs satisfying
Properties P1, P2, P3, P4 and P5 and $|V(G)|=\exp(o(\delta(G)^{2}))$.

##  5\. Proof of the 0-statement of Theorem 1.4

In this section we will prove the 0-statement of Theorem 1.4: For any
$\varepsilon>0$, if

$p<\frac{1}{2}-\left(\frac{1}{2}+\varepsilon\right)\sqrt{\frac{\log\delta(G)}{\delta(G)}},$

then

$\Phi(p,G):=\mathbb{P}[{\bf A}_{p}\text{ percolates on }G]\to 0.$

Along the proof we will need some auxiliary lemmas, which are proved in
Section 7. In fact, instead of directly analysing the majority bootstrap
percolation process, we will analyse a generalised process which dominates the
original majority bootstrap percolation process. This new process introduced
in [11] is called the _$\operatorname{Boot}_{k}(\gamma)$ process_: Given
$k\in\mathbb{N}$ and some function $\gamma\colon V(G)\to\mathbb{R}^{+}$, we
recursively define $\hat{A}_{0}:=A_{0}$ and for each
$\ell\in\mathbb{N}\cup\\{0\\}$

$\hat{A}_{\ell+1}:=\hat{A}_{\ell}\cup\left\\{x\in
V(G):\left|N(x)\cap\hat{A}_{\ell}\right|\geqslant\frac{d(x)}{2}-\max\\{0,k-\ell\\}\cdot\gamma(x)\right\\}.$

In other words, the initial infection set is the same as in the majority
bootstrap percolation process, but the infection spreads more easily in the
first $k$ rounds. More precisely, a vertex $x$ is infected in the first round
if it has $d(x)/2-k\cdot\gamma(x)$ infected neighbours, and this requirement
is gradually strengthened over the first $k$ rounds. After the $k$-th round,
the process evolves exactly as the majority bootstrap percolation process
would do.

In particular, given $A_{0}$, we note that

$A_{i}\subseteq\hat{A}_{i}\quad\text{ for all}\quad i\in\mathbb{N}.$

Crucially, however, if a vertex $x$ becomes infected in round $\ell+1\leqslant
k$ of the $\operatorname{Boot}_{k}(\gamma)$ process, then at least $\gamma(x)$
of its neighbours must have become infected in round $\ell$. This simplifies
the task of showing a vertex does _not_ become infected.

For our application, we fix $k=2$ and for each $x\in V(G)$ we let

$\gamma(x):=\sqrt{\frac{d(x)}{\vartheta(d(x))}},$

where $\vartheta(d)=\sqrt{\log d}$. Our goal is to show that if $p$ is small
enough, i.e, $p\leqslant\frac{1}{2}-c\sqrt{\frac{\log\delta(G)}{\delta(G)}}$
for $c>1/2$, then whp

$\hat{A}_{2}=\hat{A}_{3}\neq V(G).$

In other words, whp the process $\operatorname{Boot}_{2}(\gamma)$ stabilises
after two rounds. Therefore,

$\bigcup_{i=0}^{\infty}A_{i}\subseteq\bigcup_{i=0}^{\infty}\hat{A}_{i}=\hat{A}_{2}\neq
V(G)$

and hence the majority bootstrap percolation process does not percolate.

Note that our choice of the parameter $\gamma(\cdot)$ simplifies the argument
presented in [11] and allows us to study the first three instead of four
rounds of the process, while obviating the need for some of the counting
arguments given in [11]. The choice of this parameter has to be such that
$\gamma(x)$ is asymptotically smaller than $d(x)\sigma(x)=\sqrt{d(x)\log
d(x)}$. Our choice of $\gamma(x)$ to be very close to this bound allows us to
simplify the argument, at the cost of giving a weaker bound on the width of
the critical window.

We start by showing that it is very likely that the
$\operatorname{Boot}_{2}(\gamma)$ process stabilises by the second round, by
bounding the probability that a vertex is infected in the third round. Recall
that, as defined in Section 4,

$\sigma(x):=\sqrt{\frac{\log d(x)}{d(x)}}$

for each vertex $x$.

######  Lemma 5.1.

Let $x\in V(G)$, $c>\frac{1}{2}$ and $p=\frac{1}{2}-c\sigma(x)$. If there is a
$K\in\mathbb{N}$ such that $G\in\mathcal{H}(K)$, then there exists a $\beta>0$
(independent of $x$) such that

$\mathbb{P}[x\in\hat{A}_{3}\setminus\hat{A}_{2}]\leqslant\exp\left(-\beta\gamma(x)^{2}\log
d(x)\right).$

We note that the proof of Lemma 5.1 uses Properties P1, P2 and P3 (see Section
7).

We will also need to show that it is unlikely that the
$\operatorname{Boot}_{2}(\gamma)$ process fully percolates by the second
round. Since it is very likely that around half of the vertices are initially
infected, and we can quite precisely bound the probability that a vertex is
infected in the first round, it will be sufficient to bound the probability
that a vertex is infected in the second round.

######  Lemma 5.2.

Let $x\in V(G)$, $c>\frac{1}{2}$ and $p=\frac{1}{2}-c\sigma(x)$. If there is a
$K\in\mathbb{N}$ such that $G\in\mathcal{H}(K)$, then

$\mathbb{P}[x\in\hat{A}_{2}\setminus\hat{A}_{1}]\leqslant\exp\left(-\sqrt{d(x)}\right).$

We note that the proof of Lemma 5.2 needs Properties P1, P2 and P3 (see
Section 7).

Finally, we observe that Lemmas 5.1 and 5.2 together with Property P6 imply
that whp the $\operatorname{Boot}_{2}(\gamma)$-process stabilises after the
second round, without fully percolating. We are now ready to prove the
$0$-statement of our main theorem.

###### Proof of the 0-statement of Theorem 1.4.

Let $K\in\mathbb{N}$ and let $(G_{n})_{n\in\mathbb{N}}$ be a sequence of
graphs such that $G_{n}\in\mathcal{H}(K)$ and $\delta(G_{n})\to\infty$ as
$n\to\infty$. We write $G:=G_{n}$.

Let $\varepsilon>0$ and let

$p\leqslant\frac{1}{2}-\left(\frac{1}{2}+\varepsilon\right)\sqrt{\frac{\log\delta(G)}{\delta(G)}}.$

Again, since the function
$d\mapsto\frac{1}{2}-\left(\frac{1}{2}+\varepsilon\right)\sqrt{(\log d)/d}$ is
increasing in $d$, it follows from Lemma 5.2 that for every $x\in V(G)$

$\mathbb{P}\big{[}x\in\hat{A}_{2}\setminus\hat{A}_{1}\big{]}=o(1).$

Furthermore, since $\gamma(x)=o(\sigma(x)d(x))$, it is a simple consequence of
Chernoff’s inequality (Lemma 2.1) that for every $x\in V(G)$

$\mathbb{P}\big{[}x\in\hat{A}_{1}\setminus\hat{A}_{0}\big{]}\leqslant\mathbb{P}\Big{[}\operatorname{Bin}\bigl{(}d(x),p\bigr{)}\geqslant\frac{d(x)}{2}-2\gamma(x)\Big{]}=o(1).$

Hence, by Markov’s inequality whp
$\big{|}\hat{A}_{2}\setminus\hat{A}_{0}\big{|}=o\bigl{(}|V(G)|\bigr{)}$. It
follows from Chernoff’s inequality (Lemma 2.1) that whp
$\big{|}\hat{A}_{0}\big{|}=\big{|}A_{0}\big{|}\leqslant\frac{3}{4}|V(G)|$, and
hence whp

$\big{|}\hat{A}_{2}\big{|}=\big{|}\hat{A}_{2}\setminus\hat{A}_{0}\big{|}+\big{|}\hat{A}_{0}\big{|}<|V(G)|.$

On the other hand, by Lemma 5.1 there exists $\beta>0$ such that for every
$x\in V(G)$

$\mathbb{P}\big{[}x\in\hat{A}_{3}\setminus\hat{A}_{2}\big{]}=\exp\left(-\beta\gamma(x)^{2}\log
d(x)\right)=\exp\bigl{(}-\omega(\delta(G))\bigr{)}.$

By Property P6, we have $|V(G)|\leqslant\exp(K\delta(G))$, and using the union
bound we get that whp $\hat{A}_{3}=\hat{A}_{2}$. It follows that whp
$A_{i}\subseteq\hat{A}_{i}=\hat{A}_{2}\neq V(G)$ for all $i\geqslant 2$.
Therefore

$\Phi(p,G):=\mathbb{P}[{\bf A}_{p}\text{ percolates on
}G]=\mathbb{P}\left[\bigcup_{i=0}^{\infty}A_{i}=V(G)\right]=o(1),$

completing the proof. ∎

##  6\. Eleven rounds suffice

In this section we prove the auxiliary lemmas (Lemmas 4.1, 4.2 and 4.3) needed
for the proof of the $1$-statement of Theorem 1.4 in Section 4.

Throughout this section we let $x\in V(G)$, $c<\frac{1}{2}$,
$p=\frac{1}{2}-c\sigma(x)$, where $\sigma(x)=\sqrt{\frac{\log d(x)}{d(x)}}$,
and we fix a $K\in\mathbb{N}$ such that $G\in\mathcal{H}(K)$. We start the
section with a simple corollary of the Central Limit Theorem (Lemma 2.2).

######  Lemma 6.1.

Let $d^{\prime}=\Theta(d(x))$ and $C\in\mathbb{R}$ be a constant. Then

$\mathbb{P}\left[\operatorname{Bin}(d^{\prime},p)\geqslant\frac{d^{\prime}}{2}+C\right]=(1+o(1))\mathbb{P}\left[\operatorname{Bin}(d^{\prime},p)\geqslant\frac{d^{\prime}}{2}\right].$

###### Proof.

Observe that since $(d^{\prime})^{-1/2}\ll\sigma(x)\ll(d^{\prime})^{-1/3}$,
the function

$f_{L}(d^{\prime})\coloneqq\frac{cd^{\prime}\sigma(x)+L}{\sqrt{d^{\prime}p(1-p)}}$

satisfies $1\ll f_{L}\ll(d^{\prime})^{1/6}$ for any constant $L$. Therefore,
by Lemma 2.2, it suffices to show that

$\mathbb{P}[N(0,1)\geqslant
f_{C}(d^{\prime})]=(1+o(1))\mathbb{P}[N(0,1)\geqslant f_{0}(d^{\prime})].$ (2)

Since $|f_{C}-f_{0}|=O((d^{\prime})^{-1/2})$, we may estimate

$\frac{1}{f_{C}\cdot\sqrt{2\pi}}\cdot\exp\left(-\frac{f_{C}^{2}}{2}\right)=\frac{1+o(1)}{f_{0}\cdot\sqrt{2\pi}}\cdot\exp\biggl{(}-\frac{f_{0}^{2}}{2}+O\bigl{(}(f_{C}-f_{0})\cdot
f_{0}\bigr{)}\biggr{)}=\frac{1+o(1)}{f_{0}\cdot\sqrt{2\pi}}\cdot\exp\left(-\frac{f_{0}^{2}}{2}\right).$

By the second part of Lemma 2.2, this implies (2), hence proving the lemma. ∎

We proceed to prove the aforementioned auxiliary lemmas.

###  6.1. Proof of Lemma 4.1

As in Lemma 4.1, we let $m\in\mathbb{N}\cup\\{0\\}$ and aim to prove

$\mathbb{P}\left[x\in A_{2}(m)\right]\geqslant\frac{3}{4}+o(1).$

Let $X_{0}:=N(x)\cap A_{0}$ be the set of neighbours of $x$ which are
initially infected and note that

$|X_{0}|\sim\operatorname{Bin}(d(x),p).$

Next we let

$X_{1}:=N(x)\cap(A_{1}(m)\setminus A_{0})$

be the set of the neighbours of $x$ which become infected in the first round.
We note that $x\in A_{2}(m)$ if and only if either $x\in A_{0}$ or
$|X_{0}|+|X_{1}|\geqslant\frac{d(x)}{2}+m$, and so we have

$\mathbb{P}\left[x\in A_{2}(m)\right]=\mathbb{P}\left[x\in
A_{0}\right]+\mathbb{P}\left[x\notin
A_{0}\right]\cdot\mathbb{P}\Big{[}|X_{0}|+|X_{1}|\geqslant\frac{d(x)}{2}+m\nonscript\>\Big{|}\nonscript\>\mathopen{}x\notin
A_{0}\Big{]}.$ (3)

In order to calculate the second term in (3) we consider the event
$\mathcal{E}_{0}$ that $|X_{0}|\geqslant\frac{d(x)}{2}+m-\ell$ and the event
$\mathcal{E}_{1}$ that $|X_{1}|\geqslant\ell$ for a judicious choice of
$m\leqslant\ell\leqslant\frac{d(x)}{2}+m$ which will be given later. By (3),
we have

$\displaystyle\mathbb{P}\left[x\in A_{2}(m)\right]$
$\displaystyle=\mathbb{P}\left[x\in A_{0}\right]+\mathbb{P}\left[x\notin
A_{0}\right]\cdot\mathbb{P}\left[\mathcal{E}_{0}\wedge\mathcal{E}_{1}\nonscript\>\middle|\nonscript\>\mathopen{}x\notin
A_{0}\right]$
$\displaystyle=p+(1-p)\cdot\mathbb{P}\left[\mathcal{E}_{0}\nonscript\>\middle|\nonscript\>\mathopen{}x\not\in
A_{0}\right]\cdot\mathbb{P}\left[\mathcal{E}_{1}\nonscript\>\middle|\nonscript\>\mathopen{}\mathcal{E}_{0}\wedge\left(x\notin
A_{0}\right)\right]$
$\displaystyle=p+(1-p)\cdot\mathbb{P}\left[\mathcal{E}_{0}\right]\cdot\mathbb{P}\left[\mathcal{E}_{1}\nonscript\>\middle|\nonscript\>\mathopen{}\mathcal{E}_{0}\wedge\left(x\notin
A_{0}\right)\right],$ (4)

where the last equality is because $\mathcal{E}_{0}$ is independent of the
event that $x\notin A_{0}$.

For ease of notation, let us write $\mathbb{P}^{*}$ for the probability
distribution conditioned on the events $\\{x\notin A_{0}\\}$ and
$\mathcal{E}_{0}$. Note that, for $y\in N(x)$, we may use the independence of
the events $\\{y\notin A_{0}\\}$ and $\\{x\notin A_{0}\\}$ as well as Lemma
2.4 on correlations to deduce that

$\displaystyle\mathbb{P}^{*}\left[y\notin A_{0}\right]=\mathbb{P}[y\notin
A_{0}\mid(x\notin A_{0})\wedge\mathcal{E}_{0}]=\mathbb{P}[y\notin
A_{0}\nonscript\>\big{|}\nonscript\>\mathopen{}\mathcal{E}_{0}]=(1+o(1))(1-p).$
(5)

We begin with estimating the conditional expectation of $|X_{1}|$.

######  Claim 6.2.

$\mathbb{E}^{*}\big{[}|X_{1}|\big{]}=\mathbb{E}\big{[}|X_{1}|\mid(x\notin
A_{0})\wedge\mathcal{E}_{0}\big{]}=\Omega\left(\frac{d(x)^{1-2c^{2}}}{\sqrt{\log
d(x)}}\right).$

###### Proof of Claim 6.2.

Let us suppose that $x\notin A_{0}$ and let $y\in N(x)$. We have

$\displaystyle\mathbb{P}^{*}\Big{[}y\in X_{1}\Big{]}=\mathbb{P}^{*}[y\notin
A_{0}]\cdot\mathbb{P}^{*}\Big{[}|N(y)\cap
A_{0}|\geqslant\frac{d(y)}{2}+m\nonscript\>\Big{|}\nonscript\>\mathopen{}y\notin
A_{0}\Big{]}.$ (6)

To bound the second term in (6), we note that
$\big{|}N(y)\cap\big{(}\\{x\\}\cup N(x)\big{)}\big{|}\leqslant K$ by Property
P2. Furthermore, we have $d(y)\geqslant d(x)-K$ since $G$ is $K$-locally
almost regular by Property P1. Hence, conditioned on the events $\\{x,y\notin
A_{0}\\}$ and $\mathcal{E}_{0}$, $|N(y)\cap A_{0}|$ stochastically dominates a
$\operatorname{Bin}(d^{\prime},p)$ random variable for $d^{\prime}:=d(x)-2K$.
Recalling that $p=\frac{1}{2}-c\sigma(x)=\frac{1}{2}-c\sqrt{\frac{\log
d(x)}{d(x)}}$, we have

$\mathbb{P}^{*}\left[|N(y)\cap
A_{0}|\geqslant\frac{d(y)}{2}+m\nonscript\>\middle|\nonscript\>\mathopen{}y\not\in
A_{0}\right]\geqslant\mathbb{P}\left[\operatorname{Bin}\left(d^{\prime},p\right)\geqslant\frac{d^{\prime}}{2}+m+K\right].$
(7)

From (6), (5), (7) and Lemma 6.1, we obtain

$\displaystyle\mathbb{P}^{*}\big{[}y\in
X_{1}\big{]}\geqslant(1+o(1))(1-p)\cdot\mathbb{P}\left[\operatorname{Bin}\left(d^{\prime},p\right)\geqslant\frac{d^{\prime}}{2}\right].$
(8)

We will bound the second term on the right-hand side of (8) by applying Lemma
2.2 for $\operatorname{Bin}(d^{\prime},p)$. To do that, we need to scale the
binomial random variable accordingly. Note that

$d^{\prime}\left(\frac{1}{2}-p\right)=cd^{\prime}\sigma(x)=\left(1+O\left(\frac{1}{d(x)}\right)\right)c\sqrt{d(x)\log
d(x)}$

and

$d^{\prime}p(1-p)=d^{\prime}\left(\frac{1}{4}-c^{2}\sigma(x)^{2}\right)=\left(1+O\left(\frac{\log
d(x)}{d(x)}\right)\right)\frac{d(x)}{4}.$

We may apply Lemma 2.2 to bound the right-hand side of (7) and get

$\mathbb{P}\left[\operatorname{Bin}\left(d^{\prime},p\right)\geqslant\frac{d^{\prime}}{2}\right]=(1+o(1))\mathbb{P}[N(0,1)\geqslant
f(d^{\prime})]$ (9)

for

$f(d^{\prime}):=\frac{d^{\prime}(1/2-p)}{\sqrt{d^{\prime}p(1-p)}}=\left(1+O\left(\frac{\log
d(x)}{d(x)}\right)\right)2c\sqrt{\log d(x)}.$

For this value of $f$, we may estimate

$\displaystyle\mathbb{P}[N(0,1)\geqslant f(d^{\prime})]$
$\displaystyle=\frac{1+o(1)}{f(d^{\prime})\sqrt{2\pi}}\exp\left(-\frac{1}{2}f(d^{\prime})^{2}\right)$
$\displaystyle=\frac{1+o(1)}{2c\sqrt{2\pi\log d(x)}}\exp\bigl{(}-2c^{2}\log
d(x)+O(1)\bigr{)}$ $\displaystyle=\Omega\left(\frac{d(x)^{-2c^{2}}}{\sqrt{\log
d(x)}}\right).$ (10)

Hence, by (8), (9) and (10), we obtain

$\mathbb{E}^{*}\left[|X_{1}|\right]=d(x)\cdot\mathbb{P}^{*}\Big{[}y\in
X_{1}\Big{]}=\Omega\left(\frac{d(x)^{1-2c^{2}}}{\sqrt{\log d(x)}}\right),$
(11)

as desired. ∎

We now proceed towards bounding the conditional variance of $|X_{1}|$. Let $M$
be the set of pairs of distinct vertices $y,z\in N(x)$ that have _at most_ two
common neighbours (including $x$). We continue with the following claim, which
states the events $\\{y\in X_{1}\\}$ and $\\{z\in X_{1}\\}$ for such pairs are
not closely correlated.

######  Claim 6.3.

If $(y,z)\in M$, then

$\mathbb{P}^{*}\left[(y\in X_{1})\wedge(z\in X_{1})\right]-\mathbb{P}^{*}[y\in
X_{1}]\cdot\mathbb{P}^{*}[z\in X_{1}]=o\left(\mathbb{P}^{*}[y\in
X_{1}]\cdot\mathbb{P}^{*}[z\in X_{1}]\right).$

###### Proof.

Let $d^{\prime}=d-2K$, $d^{\prime}_{0}=d/2+m-4K$ and
$d^{\prime}_{1}=d/2+m+4K$. We claim that for $w\in\\{y,z\\}$,

$\mathbb{P}\big{[}\operatorname{Bin}(d^{\prime},p)\geqslant
d^{\prime}_{0}\big{]}\geqslant\mathbb{P}^{*}\left[w\in
X_{1}\nonscript\>\middle|\nonscript\>\mathopen{}w\notin
A_{0}\right]\geqslant\mathbb{P}\big{[}\operatorname{Bin}(d^{\prime},p)\geqslant
d^{\prime}_{1}\big{]}.$ (12)

Indeed, assume $w=y$ without loss of generality, and observe that

$\displaystyle\mathbb{P}^{*}\left[y\in
X_{1}\nonscript\>\middle|\nonscript\>\mathopen{}y\notin A_{0}\right]$
$\displaystyle\geqslant\mathbb{P}^{*}\left[y\in
X_{1}\nonscript\>\middle|\nonscript\>\mathopen{}(y\notin A_{0})\wedge(N(y)\cap
N(x)\cap A_{0}=\varnothing)\right]$ $\displaystyle=\mathbb{P}\left[y\in
X_{1}\nonscript\>\middle|\nonscript\>\mathopen{}(x,y\notin
A_{0})\wedge(N(y)\cap N(x)\cap A_{0}=\varnothing)\right],$
$\displaystyle\geqslant\mathbb{P}\left[\operatorname{Bin}(d(y)-K,p)\geqslant
d(y)/2+m\right].$

where the first step follows by stochastic domination. Since $d(y)=d\pm K$ by
Property P1, this proves the last inequality in (12). A similar argument,
conditioning on $N(y)\cap N(x)\subseteq A_{0}$ instead and using that
$\mathbb{P}[\operatorname{Bin}(d^{\prime},p)\geqslant
d_{0}^{\prime}]\geqslant\mathbb{P}[\operatorname{Bin}(d(y),p)\geqslant
d_{0}^{\prime}+3K]$, proves the first inequality.

Let $F=\\{w\in V(G)\setminus\\{x,y,z\\}:|N(w)\cap\\{x,y,z\\}|\geqslant 2\\}$,
and observe that $|F|\leqslant 2K$ by Property P2 and our assumption that $y$
and $z$ have at most one common neighbour besides $x$. Since $F$ contains
$N(y)\cap N(z)$, if we condition on $(F\cup\\{x,y,z\\})\cap A_{0}$ then the
events $\\{y\in X_{1}\\}$ and $\\{z\in X_{1}\\}$ are conditionally independent
and binomially distributed and so by a similar argument, conditioning on
either $F=\varnothing$ or $F\subseteq A_{0}$ allows us to deduce that

$\mathbb{P}\big{[}\operatorname{Bin}(d^{\prime},p)\geqslant
d^{\prime}_{0}\big{]}^{2}\geqslant\mathbb{P}^{*}\left[(y\in X_{1})\wedge(z\in
X_{1})\nonscript\>\middle|\nonscript\>\mathopen{}y,z\notin
A_{0}\right]\geqslant\mathbb{P}\big{[}\operatorname{Bin}(d^{\prime},p)\geqslant
d^{\prime}_{1}\big{]}^{2}.$ (13)

By (12), (13) and Lemma 6.1, we obtain

$\mathbb{P}^{*}\left[(y\in X_{1})\wedge(z\in
X_{1})\nonscript\>\middle|\nonscript\>\mathopen{}y,z\notin
A_{0}\right]=(1+o(1))\mathbb{P}^{*}\left[y\in
X_{1}\nonscript\>\middle|\nonscript\>\mathopen{}y\notin
A_{0}\right]\cdot\mathbb{P}^{*}\left[z\in
X_{1}\nonscript\>\middle|\nonscript\>\mathopen{}z\notin A_{0}\right].$ (14)

Therefore, it only remains to show that

$\mathbb{P}^{*}[y,z\notin A_{0}]=(1+o(1))\mathbb{P}^{*}[y\notin
A_{0}]\cdot\mathbb{P}^{*}[z\notin A_{0}],$ (15)

since multiplying (14) and (15) finishes the proof of the lemma. To do so, let
$\mathbb{P}^{\prime}$ the probability measure obtained by conditioning on
$\\{x\notin A_{0}\\}$, and observe that, by Bayes’ theorem,

$\mathbb{P}^{*}[y,z\notin A_{0}]=\mathbb{P}^{\prime}[y,z\notin
A_{0}\nonscript\>\big{|}\nonscript\>\mathopen{}\mathcal{E}_{0}]=\frac{\mathbb{P}^{\prime}[\mathcal{E}_{0}\nonscript\>\big{|}\nonscript\>\mathopen{}y,z\notin
A_{0}]}{\mathbb{P}^{\prime}[\mathcal{E}_{0}]}\cdot\mathbb{P}^{\prime}[y,z\notin
A_{0}].$ (16)

The fraction is $1+o(1)$ by Lemma 2.4. Since $\mathbb{P}^{\prime}[y,z\notin
A_{0}]=\mathbb{P}[y,z\notin A_{0}]=(1-p)^{2}$ and $\mathbb{P}^{*}[y\notin
A_{0}]\mathbb{P}^{*}[z\notin A_{0}]=(1+o(1))(1-p)^{2}$ by (5), (16) implies
(15) and proves the lemma. ∎

As a direct consequence of Claim 6.3 we have

$\displaystyle\sum_{(y,z)\in M}\mathbb{P}^{*}\left[(y\in X_{1})\wedge(z\in
X_{1})\right]-\mathbb{P}^{*}[y\in X_{1}]\cdot\mathbb{P}^{*}[z\in
X_{1}]=o\left(\mathbb{E}^{*}[|X_{1}|]^{2}\right).$ (17)

This allows us to obtain our bound on the conditional variance of $|X_{1}|$.

######  Claim 6.4.

$\mathbb{V}^{*}\left[|X_{1}|\right]=o\left(\mathbb{E}^{*}[|X_{1}|]^{2}\right).$

$x$$N(x)$$S(x,2)$$X_{0}$$X_{1}$ Figure 1. The set $X_{0}=N(x)\cap A_{0}$ is
depicted in blue, and the set $X_{1}=N(x)\cap(A_{1}\setminus A_{0})$ is
depicted patterned. The red pair of vertices has two common neighbours in
$S(x,2)$ and is thus in $M^{\prime}$, while the yellow pair of vertices has
just one common neighbour in $S(x,2)$.

###### Proof of Claim 6.4.

Let $M^{\prime}$ be the set of pairs of distinct vertices in $N(x)$ that have
strictly more than two common neighbours (see Figure 1), which we will call
bad pairs. We claim that $|M^{\prime}|=O(d(x))$. Indeed,
$|\binom{N(x)}{2}\setminus\binom{S_{0}(x,1)}{2}|=O(d(x))$ by Property P3i, so
there are only $O(d(x))$ bad pairs not contained in $S_{0}(x,1)$. Also due to
Property P3i, we have that $N(x)\cup(D\cap S(x,2))$ has size $O(d(x))$, and
due to Property P2 each of its elements can be a common neighbour of $O(1)$
many pairs of neighbours of $x$, contributing $O(d(x))$ many bad pairs in
total. Since by Property P3iii any two vertices in $S_{0}(x,1)$ have at most
one common neighbour in $S_{0}(x,2)$, there are no further bad pairs to
consider. Summing up, we have

$\displaystyle|M^{\prime}|=O(d(x)).$ (18)

From (17) and (18) it follows that

$\displaystyle\mathbb{V}^{*}\left[|X_{1}|\right]$ $\displaystyle=\sum_{y,z\in
N(x)}\mathbb{P}^{*}\left[(y\in X_{1})\wedge(z\in
X_{1})\right]-\mathbb{P}^{*}[y\in X_{1}]\cdot\mathbb{P}^{*}[z\in X_{1}]$
$\displaystyle\leqslant\sum_{(y,z)\in M}\mathbb{P}^{*}\left[(y\in
X_{1})\wedge(z\in X_{1})\right]-\mathbb{P}^{*}[y\in
X_{1}]\cdot\mathbb{P}^{*}[z\in X_{1}]$
$\displaystyle\qquad+\mathbb{E}^{*}[|X_{1}|]+|M^{\prime}|$
$\displaystyle\leqslant
o\left(\mathbb{E}^{*}[|X_{1}|]^{2}\right)+O(d(x))=o\left(\mathbb{E}^{*}[|X_{1}|]^{2}\right),$

finishing the claim. ∎

###### Proof of Lemma 4.1.

Recall that $|X_{0}|\sim\operatorname{Bin}(d(x),p)$, where
$p=\frac{1}{2}-c\sigma(x)=\frac{1}{2}-c\sqrt{\frac{\log d(x)}{d(x)}}$ for
$c<1/2$. Taking $\ell:=\mathbb{E}^{*}\left[|X_{1}|\right]/2$ we have
$\ell=\Omega\bigl{(}d(x)^{1-2c^{2}}/\sqrt{\log d(x)}\bigr{)}$ by Claim 6.2,
and thus

$\mathbb{E}[|X_{0}|]=\left(\frac{1}{2}-c\sigma(x)\right)d(x)=\frac{d(x)}{2}-c\sqrt{d(x)\log
d(x)}>\frac{d(x)}{2}+m-\ell.$ (19)

By Proposition 2.5 we then have

$\mathbb{P}[\mathcal{E}_{0}]=\mathbb{P}\left[|X_{0}|\geqslant\frac{d(x)}{2}+m-\ell\right]\geqslant\frac{1}{2}.$
(20)

Furthermore, by Claims 6.2 and 6.4 it follows from Chebyshev’s inequality that

$\mathbb{P}^{*}\left[\mathcal{E}_{1}\right]=1-\mathbb{P}^{*}\left[|X_{1}|<\ell\right]=1-\mathbb{P}^{*}\left[|X_{1}|<\frac{\mathbb{E}^{*}\left[|X_{1}|\right]}{2}\right]=1-o(1).$
(21)

Recalling from (4) that $\mathbb{P}[x\in
A_{2}(m)]=p+(1-p)\cdot\mathbb{P}[\mathcal{E}_{0}]\cdot\mathbb{P}^{*}[\mathcal{E}_{1}]$
and using (20) and (21),

$\displaystyle\mathbb{P}\left[x\in A_{2}(m)\right]$ $\displaystyle\geqslant
p+(1-o(1))\frac{1-p}{2}\geqslant\frac{3}{4}+o(1),$

finishing the proof of the lemma. ∎

######  Remark 6.5.

Let $\lambda\in\mathbb{R}$ satisfy $\lambda>1/2$, and assume now that $c$ may
depend on $d(x)$. The inequality in (19) holds as long as

$c<\frac{1}{2}-\frac{\lambda\log\log d(x)}{\log d(x)}.$

Using this, one may check that the $1$-statement of Theorem 1.4 holds for
every

$p\geqslant\frac{1}{2}-\frac{1}{2}\sqrt{\frac{\log\Delta(G)}{\Delta(G)}}+\frac{\lambda\log\log\Delta(G)}{\sqrt{\Delta(G)\log\Delta(G)}},$

recovering the bound obtained in [11, Theorem 2.1] (see Theorem 1.3) if
$G\in\mathcal{H}(K)$ is $n$-regular.

###  6.2. Proof of Lemma 4.2

In this section we will prove Lemma 4.2 about the existence of a constant
$\beta>0$ (independent of $x$) such that

$\mathbb{P}\big{[}x\notin A_{5}\big{]}\leqslant\exp\bigl{(}-\beta
d(x)\bigr{)}.$

Throughout this section we let $0<\alpha_{1}\ll\alpha_{2}\ll\alpha_{3}\ll
K^{-10}$ be sufficiently small constants and let $d=d(x)$.

Let $\mathcal{E}$ be the event that $|N(x)\cap
A_{0}|\geqslant\left(\frac{1}{2}-\alpha_{1}\right)d$. Since $|N(x)\cap
A_{0}|\sim\operatorname{Bin}(d,p)$ and $p=\frac{1}{2}-o(1)$, by Chernoff’s
inequality (Lemma 2.1) it holds that

$\mathbb{P}[\mathcal{E}]\geqslant 1-\exp\left(-\frac{\alpha_{1}d}{2}\right).$
(22)

In what follows we may assume that $\mathcal{E}$ holds deterministically.

Suppose that $x\notin A_{5}$. Then, less than $\frac{d}{2}$ of the vertices in
$N(x)$ are infected by the fourth round. In particular, there is some subset
$T^{\prime}\subseteq N(x)$ with $|T^{\prime}|=\frac{d}{2}$ such that
$T^{\prime}\cap A_{4}=\varnothing$. Similarly, by Property P1, each vertex
$y\in T^{\prime}$ has less than $\frac{d(y)}{2}\leqslant\frac{d+K}{2}$
neighbours in $A_{3}$. Since $T^{\prime}\subseteq N(x)=S(x,1)$, it follows
that

$\phi(T^{\prime}):=e\left(T^{\prime},A_{3}\cap
S(x,2)\right)<\frac{(d+K)d}{4}.$

Hence, in order to prove Lemma 4.2, it will be sufficient to show that

$\sum_{\begin{subarray}{c}T^{\prime}\subseteq N(x)\setminus A_{0}\\\
|T^{\prime}|=\frac{d}{2}\end{subarray}}\mathbb{P}\left[\phi(T^{\prime})<\frac{(d+K)d}{4}\right]\leqslant
e^{-\alpha_{2}d}.$ (23)

Note that, since we are assuming $\mathcal{E}$ holds, the number of possible
sets $T^{\prime}\subseteq N(x)\setminus A_{0}$ with $|T^{\prime}|=\frac{d}{2}$
is at most

$\binom{\left(\frac{1}{2}+\alpha_{1}\right)d}{d/2}=\binom{\left(\frac{1}{2}+\alpha_{1}\right)d}{\alpha_{1}d}\leqslant\left(\frac{e\left(\frac{1}{2}+\alpha_{1}\right)}{\alpha_{1}}\right)^{\alpha_{1}d}\leqslant\left(\frac{e}{\alpha_{1}}\right)^{\alpha_{1}d}\leqslant
e^{\alpha_{2}d},$ (24)

by our choice of $\alpha_{1}$ and $\alpha_{2}$. Therefore, the following claim
readily implies (23).

######  Claim 6.6.

For each $T^{\prime}\subseteq N(x)$ with $|T^{\prime}|=\frac{d}{2}$,

$\mathbb{P}\left[\phi(T^{\prime})<\frac{d^{2}}{4}+c\sqrt{d^{3}\log
d}\right]\leqslant e^{-2\alpha_{2}d}.$ (25)

###### Proof of Claim 6.6.

Let $T^{\prime}\subseteq N(x)$ with $|T^{\prime}|=\frac{d}{2}$ be fixed, and
let

$T:=N(T^{\prime})\cap S(x,2)$

(see Figure 2). By Properties P1 and P2, we have
$e(T^{\prime},T)=\frac{d^{2}}{2}+O(d)$ and
$|T|\geqslant\frac{d^{2}}{2K}+O(d)$. In particular, since
$p=\frac{1}{2}-c\sigma(x)$, the expected size of $e(T^{\prime},T\cap A_{0})$
is $\frac{d^{2}}{4}-\frac{c}{2}\sqrt{d^{3}\log d}+o(d^{3/2})$ and so, by
Hoeffding’s inequality (Lemma 2.3) and the fact that every vertex of $T$ has
at most $2K$ backwards neighbours by Property P2, we obtain

$\mathbb{P}\left[e(T^{\prime},T\cap A_{0})<\frac{d^{2}}{4}-c\sqrt{d^{3}\log
d}\right]<\exp\left(-\frac{c^{2}d\log d}{2K}\right).$ (26)

$x$$N(x)$$S(x,2)$$S(x,3)$$T^{\prime}$$T$ Figure 2. The set
$T^{\prime}\subseteq N(x)\setminus A_{4}$ is depicted patterned. We will
estimate the density of certain types of edges between $T=N(T^{\prime})\cap
S(x,2)$ and $S_{0}(x,3)$, where $D\cap S(x,3)$ is depicted in grey. Applying
Lemma 3.1, we obtain a partition $S_{0}(x,3)$ into sets of vertices with
pairwise distance at least $6$.

In particular, we can bound (25) by showing that it is (exponentially in $d$)
unlikely that very few vertices in $T$ are in $A_{3}\setminus A_{0}$ as in the
following claim, which will be proved after finishing the proof of Claim 6.6.

######  Claim 6.7.

$\displaystyle\mathbb{P}\left[\left|T\cap\left(A_{3}\setminus
A_{0}\right)\right|\leqslant 2c\sqrt{d^{3}\log
d}\right]\leqslant\exp(-3\alpha_{2}d).$

To finish the proof, note that $e(T^{\prime},T\cap(A_{3}\setminus
A_{0}))\geqslant|T\cap(A_{3}\setminus A_{0})|$ since every vertex of $T$ has a
neighbour in $T^{\prime}$. It then follows from (26) and Claim 6.7 that

$\displaystyle\mathbb{P}\left[\phi(T^{\prime})<\frac{d^{2}}{4}+c\sqrt{d^{3}\log
d}\right]$ $\displaystyle\leqslant\mathbb{P}\left[e(T^{\prime},T\cap
A_{0})+\left|T\cap\left(A_{3}\setminus
A_{0}\right)\right|<\frac{d^{2}}{4}+c\sqrt{d^{3}\log d}\right]$
$\displaystyle\leqslant\exp\left(-\frac{c^{2}d\log
d}{2K}\right)+\exp(-3\alpha_{2}d)\leqslant\exp(-2\alpha_{2}d),$

establishing Claim 6.6. ∎

###### Proof of Claim 6.7.

We first note that by an application of Chernoff’s inequality (Lemma 2.1),

$\mathbb{P}\left[\left|T\setminus
A_{0}\right|\geqslant\frac{d^{2}}{8K}\right]\geqslant
1-\exp\left(-\Omega(d^{2})\right).$ (27)

We will assume in what follows that this holds deterministically.

Recall that $G$ is locally $K$-almost regular by Property P1, so every vertex
in $T\subseteq S(x,2)$ has degree $d\pm 2K$. Since $G$ has $K$-bounded
backwards expansion by Property P2, every vertex in $S(x,2)$ has at most $2K$
neighbours in $S(x,1)\cup S(x,2)$. Furthermore, by Property P3ii, we have that
every vertex $y\in S_{0}(x,2)$ has at most $2K$ neighbours in $D$, and so it
follows that every such $y$ has at least $d(y)-4K\geqslant d-6K$ neighbours in
$S_{0}(x,3)$. Moreover, $e(T\setminus S_{0}(x,2),S_{0}(x,3))=O(d^{2})$ by
Properties P1 and P3i. Therefore,

$e\left(T\setminus A_{0},S_{0}(x,3)\right)=\left|T\setminus A_{0}\right|(d\pm
6K)+O(d^{2})=\left|T\setminus A_{0}\right|d+O(d^{2}).$ (28)

Suppose now that the event in the claim statement,
$\left|T\cap\left(A_{3}\setminus A_{0}\right)\right|\leqslant
2c\sqrt{d^{3}\log d}$, holds. Every vertex $y\in T\setminus A_{3}$ has at most
$\frac{d(y)}{2}\leqslant\frac{d}{2}+K$ neighbours in $S_{0}(x,3)\cap A_{2}$
and hence

$\displaystyle e\left(T\setminus A_{0},S_{0}(x,3)\cap A_{2}\right)$
$\displaystyle\leqslant\left|T\setminus
A_{3}\right|\left(\frac{d}{2}+K\right)+\left|T\cap\left(A_{3}\setminus
A_{0}\right)\right|(d+2K)$ $\displaystyle\leqslant\left|T\setminus
A_{0}\right|\left(\frac{d}{2}+K\right)+3c\sqrt{d^{5}\log d}.$ (29)

Hence, it follows from (28) and (29) that

$\displaystyle e\left(T\setminus A_{0},S_{0}(x,3)\setminus A_{2}\right)$
$\displaystyle=e\left(T\setminus A_{0},S_{0}(x,3)\right)-e\left(T\setminus
A_{0},S_{0}(x,3)\cap A_{2}\right)$ $\displaystyle\geqslant\left|T\setminus
A_{0}\right|\cdot\frac{d}{2}-4c\sqrt{d^{5}\log d}.$ (30)

Therefore, the average density from $T\setminus A_{0}$ to $S_{0}(x,3)\setminus
A_{2}$ is at least around half the density from $T\setminus A_{0}$ to
$S_{0}(x,3)$. We will restrict ourselves to a subset $B$ of $S_{0}(x,3)$ with
a similar property such that distinct vertices in $B$ lie at distance at least
four in $G$, in order to ensure the events that the vertices of $B$ lie in
$A_{2}$ are independent.

Using Lemma 3.1, we can find a partition $\mathcal{P}$ of $S_{0}(x,3)$ with
$|\mathcal{P}|\leqslant 4K^{2}d^{2}$ (see Figure 2) such that, for each
$P\in\mathcal{P}$, the family of events $\left\\{y\in A_{2}:y\in P\right\\}$
is independent. We claim that there must be some $P\in\mathcal{P}$ such that

$e\left(T\setminus A_{0},P\setminus
A_{2}\right)\geqslant\max\left\\{\frac{5}{12}e\left(T\setminus
A_{0},P\right),\alpha_{3}d\right\\}.$ (31)

Indeed, assume every $P\in\mathcal{P}$ violates (31). Then let
$\mathcal{P}_{1}$ be the family of sets $P\in\mathcal{P}$ such that
$e\left(T\setminus A_{0},P\setminus A_{2}\right)<\alpha_{3}d$. Similarly, let
$\mathcal{P}_{2}$ be the family of sets $P\in\mathcal{P}$ such that
$e\left(T\setminus A_{0},P\setminus A_{2}\right)<\frac{5}{12}e\left(T\setminus
A_{0},P\right)$. Then we have

$\displaystyle e\left(T\setminus A_{0},S_{0}(x,3)\setminus A_{2}\right)$
$\displaystyle\leqslant\sum_{P\in\mathcal{P}_{1}}e\left(T\setminus
A_{0},P\setminus A_{2}\right)+\sum_{P\in\mathcal{P}_{2}}e\left(T\setminus
A_{0},P\setminus A_{2}\right)$
$\displaystyle\leqslant|\mathcal{P}|\alpha_{3}d+\sum_{P\in\mathcal{P}}\frac{5}{12}e\left(T\setminus
A_{0},P\right)$ $\displaystyle\leqslant
4\alpha_{3}K^{2}d^{3}+\frac{5}{12}e\left(T\setminus A_{0},S_{0}(x,3)\right)$
$\displaystyle\leqslant\left|T\setminus
A_{0}\right|d\cdot\left(\frac{5}{12}+32K^{3}\alpha_{3}+O(1/d)\right),$ (32)

where the last line follows from (27) and (28). If $\alpha_{3}$ is
sufficiently small, however, this contradicts (6.2). Since we assumed
$|T\cap\left(A_{3}\setminus A_{0}\right)|\leqslant 2c\sqrt{d^{3}\log d}$,
combining (32) with (27) proves that

$\mathbb{P}\left[\left|T\cap\left(A_{3}\setminus A_{0}\right)\right|\leqslant
2c\sqrt{d^{3}\log
d}\right]\leqslant\exp\left(-\Omega(d^{2})\right)+\sum_{P\in\mathcal{P}}\mathbb{P}\left[P\text{
satisfies }\eqref{e:Tsteps13unlikely}\right].$ (33)

We now show that the right-hand side of (33) is small. Let $P$ be such that
(31) holds. For each $y\in P$, consider the event $\\{y\in A_{2}\\}$, which we
denote by $\mathcal{E}_{y}$. By Lemma 4.1, for each $y\in P$ we have
$\mathbb{P}\left[\mathcal{E}_{y}\right]\geqslant\frac{3}{4}+o(1)\geqslant\frac{2}{3}$,
and since all vertices in $P$ are at pairwise distance at least four, the
events $\left\\{\mathcal{E}_{y}\colon y\in P\right\\}$ are mutually
independent.

However, the event $\mathcal{E}_{y}$ is _not_ independent of $B(x,2)\cap
A_{0}$, and so in particular not independent of the distribution of $T\cap
A_{0}$. To get around this issue, we will use the $K$-projection property
(Property P4) for $\ell=3$, which implies that for every $y\in P$ there is a
subgraph $G(y)\subseteq G$ which is also in $\mathcal{H}(K)$, contains $y$, is
disjoint from $B(x,2)$ and satisfies $d_{G(y)}(w)\geqslant d_{G}(w)-3K$ for
any $w\in V(G(y))$ (see Figure 3).

$x$$N(x)$$S(x,2)$$S(x,3)$$y_{1}$$y_{2}$$G(y_{1})$$G(y_{2})$ Figure 3. For two
vertices $y_{1},y_{2}\in S_{0}(x,3)$, by applying Property P4 there exist
subgraphs $G(y_{1})$ and $G(y_{2})$ that are disjoint from $B(x,2)$ and lie in
$\mathcal{H}(K)$.

In particular, recall $\sigma(x)=\sqrt{\frac{\log d(x)}{d(x)}}$ and observe
that

$\sigma(x)=(1+o(1))\sqrt{\frac{\log d_{G(y)}(y)}{d_{G(y)}(y)}}.$

Let us consider the bootstrap percolation process restricted on $G(y)$ with
the set of initially infected vertices $A^{y}_{0}(m):=A_{0}\cap V(G(y))$ and
infection threshold of $r(w)=\frac{d(w)}{2}+m$ for each $w\in G(y)$. For each
$i\in\mathbb{N}$ we define

$A^{y}_{i}(m):=A^{y}_{i-1}(m)\cup\left\\{w\in
V(G(y))\;:\;\left|N_{G(y)}(w)\cap
A^{y}_{i-1}(m)\right|\geqslant\frac{d_{G(y)}(w)}{2}+m\right\\}.$

Applying Lemma 4.1 to $G(y)$ with $m=2K$, we deduce that

$\mathbb{P}\left[y\in
A^{y}_{2}(2K)\right]\geqslant\frac{3}{4}+o(1)\geqslant\frac{2}{3}.$ (34)

However, since
$\frac{d_{G(y)}(w)}{2}\geqslant\frac{d_{G}(w)-3K}{2}\geqslant\frac{d_{G}(w)}{2}-2K$
for each $w\in V(G(y))$, it follows that

$A^{y}_{2}(2K)\subseteq A_{2}$

and hence we can deduce that $\mathbb{P}\left[y\in
A_{2}\right]\geqslant\frac{2}{3}$ for each $y\in P$.

At this point, we expose the initially-infected vertices in $T$, i.e., the set
$T\cap A_{0}$. By Property P2, we have that each vertex of $P\subseteq
S_{0}(x,3)$ has at most $3K$ neighbours in $T\subseteq S(x,2)$. For each
$i\in[3K]$, let $b_{i}$ be the number of elements of $P$ with $i$ neighbours
in $T\setminus A_{0}$. It follows that $e\left(T\setminus
A_{0},P\right)=\sum_{i=1}^{3K}ib_{i}$ and $e\left(T\setminus A_{0},P\setminus
A_{2}\right)$ is stochastically dominated by $Y=\sum_{i=1}^{3K}iB_{i}$, where
$B_{i}\sim\operatorname{Bin}\left(b_{i},\frac{1}{3}\right)$. Letting

$\tau\coloneqq\max\left\\{\frac{5}{12}\sum_{i=1}^{3K}ib_{i},\alpha_{3}d\right\\}-\frac{1}{3}\sum_{i=1}^{3K}ib_{i}\geqslant\max\left\\{\frac{1}{12}\left(\sum_{i=1}^{3K}ib_{i}\right),\frac{1}{5}a_{3}d\right\\},$

we have by Hoeffding’s inequality (Lemma 2.3) that

$\displaystyle\mathbb{P}\left[P\text{ satisfies
}\eqref{e:Tsteps13unlikely}\right]\leqslant\mathbb{P}\left[Y\geqslant\frac{1}{3}\sum_{i=1}^{3K}ib_{i}+\tau\right]\leqslant\exp\left(-\frac{2\tau^{2}}{3K\cdot\mathbb{E}[Y]}\right).$

Using that

$\displaystyle 3\cdot\mathbb{E}[Y]=\sum_{i=1}^{3K}ib_{i}\leqslant
12\tau\qquad\text{ and
}\qquad\frac{\tau}{6K}\geqslant\frac{\alpha_{3}d}{30K}\geqslant 4\alpha_{2}d,$

we then have that $\mathbb{P}[P\text{ satisfies
\eqref{e:Tsteps13unlikely}}]\leqslant\exp(-4\alpha_{2}d)$. Since
$|\mathcal{P}|=O(d^{2})$, we obtain by (33) and the union bound that

$\displaystyle\mathbb{P}\left[\left|T\cap\left(A_{3}\setminus
A_{0}\right)\right|\leqslant 2c\sqrt{d^{3}\log
d}\right]\leqslant\exp\left(-3\alpha_{2}d\right),$

proving Claim 6.7. ∎

We are now ready to finish the proof of Lemma 4.2.

###### Proof of Lemma 4.2.

Note that by (22) and (23), we have

$\mathbb{P}\left[x\not\in
A_{5}\right]\leqslant\exp\left(-\frac{\alpha_{1}d}{2}\right)+\exp(-\alpha_{2}d)\leqslant\exp\left(-\frac{\alpha_{1}d}{4}\right),$

and so Lemma 4.2 holds with $\beta=\alpha_{1}/4$. ∎

###  6.3. Proof of Lemma 4.3

In this section we will prove Lemma 4.3 about the existence of a constant a
$\beta>0$ (independent of $x$) such that

$\mathbb{P}\big{[}x\notin A_{11}\big{]}\leqslant\exp\bigl{(}-\beta
d(x)^{2}\bigr{)}.$

Throughout this section we let $d=d(x)$.

###### Proof of Lemma 4.3.

Suppose that $x\notin A_{11}$, and let $T_{\ell}\coloneqq S(x,\ell)\setminus
A_{11-\ell}$. By definition, no vertex of $T_{\ell}$ is infected by time
$11-\ell$. Therefore, each $y\in T_{\ell}$ has at most $d(y)/2$ neighbours in
$A_{11-(\ell+1)}$. Hence, by Properties P1 and P2, each vertex of $T_{\ell}$
has at least $(d-3K\ell)/2$ neighbours in $T_{\ell+1}$. Moreover, since $G$
has $K$-bounded backwards expansion (Property P2), every vertex in
$S(x,\ell+1)$ has at most $K(\ell+1)$ neighbours in $S(x,\ell)$. Therefore,

$|T_{\ell+1}|\geqslant\frac{|T_{\ell}|\cdot(d-3K\ell)}{2K(\ell+1)}=\Omega\big{(}|T_{\ell}|\cdot
d\big{)}.$

Since we are assuming $x\notin A_{11}$, we have $|T_{0}|=1$, and therefore by
induction there exists a constant $\alpha>0$ such that
$|T_{\ell}|\geqslant\alpha d^{\ell}$ for every $0\leqslant\ell\leqslant 6$.
Hence, if $x\notin A_{11}$, we may take a subset $T^{\prime}\subseteq
T_{6}=S(x,6)\setminus A_{5}$ of size $\alpha d^{6}$.

By Lemma 3.1 there is a partition $S(x,6)=P_{1}\cup\dots\cup P_{m}$ where
$m=O\left(d^{5}\right)$ such that $\operatorname{dist}(y_{1},y_{2})\geqslant
12$ for each $j\in[m]$ and distinct $y_{1},y_{2}\in P_{j}$. We claim that for
$\varepsilon\ll\alpha$ sufficiently small there is some $j\in[m]$ such that

$|P_{j}|\geqslant\varepsilon d\qquad\text{and}\qquad|P_{j}\cap
T^{\prime}|\geqslant\varepsilon|P_{j}|.$ (35)

Indeed, $|S(x,6)|=O(d^{6})$ by Property P1. Hence, if (35) fails to hold for
every $j\in[m]$, then

$|T^{\prime}|\leqslant\varepsilon dm+\varepsilon|S(x,6)|<\alpha d^{6},$

a contradiction.

Let $P$ be such that (35) holds. For each $y\in P$, consider the event
$\\{y\notin A_{5}\\}$, which we denote by $\mathcal{E}_{y}$. The events
$\left\\{\mathcal{E}_{y}\colon y\in P\right\\}$ are independent, and by Lemma
4.2 there is some $\beta^{\prime}>0$ (independent of $y$) such that
$\mathbb{P}\left[y\not\in A_{5}\right]\leqslant\exp(-\beta^{\prime}d(y))$ for
every $y\in P$. Since $d(y)\geqslant d/2$ for every $y\in P$, we have that
$|P\setminus A_{5}|$ is stochastically dominated by a
$\operatorname{Bin}(|P|,p^{\prime})$ random variable with
$p^{\prime}\coloneqq\exp(-\beta^{\prime}d/2)$. By (35) and Chernoff’s
inequality (Lemma 2.1b), there is some constant
$\beta^{\prime\prime}(\beta^{\prime},\varepsilon)>0$ such that

$\mathbb{P}\big{[}|P\cap
T^{\prime}|\leqslant\varepsilon|P|\big{]}\leqslant\mathbb{P}\big{[}|P\setminus
A_{5}|\geqslant\varepsilon|P|\big{]}\leqslant\left(\frac{ep^{\prime}}{\varepsilon}\right)^{\varepsilon|P|}\leqslant\exp\left(-\beta^{\prime\prime}d^{2}\right).$
(36)

By a union bound over the partition classes $P_{j}$ ($j\in[m]$), we obtain

$\displaystyle\mathbb{P}\left[x\not\in
A_{11}\right]\leqslant\mathbb{P}\Big{[}\text{some }P_{j}\text{ satisfies
}\eqref{e:Bjprop}\Big{]}\leqslant
m\exp\left(-\beta^{\prime\prime}d^{2}\right)\leqslant\exp\left(-\frac{\beta^{\prime\prime}d^{2}}{2}\right),$

and so the statement holds with $\beta=\beta^{\prime\prime}/2$. ∎

##  7\. Dominating process: stabilisation after two rounds

In this section we prove the auxiliary lemmas (Lemma 5.1–Lemma 5.2) needed for
the proof of the $0$-statement of Theorem 1.4 in Section 5. Throughout this
section we let $x\in V(G)$, $c>\frac{1}{2}$, $\vartheta(d)=\sqrt{\log d}$,

$\sigma(x)=\sqrt{\frac{\log
d(x)}{d(x)}},\qquad\gamma(x)=\sqrt{\frac{d(x)}{\vartheta(d(x))}},$

and $p=\frac{1}{2}-c\sigma(x)$. To ease notation let $d=d(x)$,
$\sigma=\sigma(x)$ and $\gamma=\gamma(x)$. Assume there is a $K\in\mathbb{N}$
such that $G\in\mathcal{H}(K)$.

Observe that if $w\in V(G)$ is such that $\operatorname{dist}(x,w)$ is
constant, then by Property P1 and the asymptotic estimates $\log(d+O(1))/\log
d=1+O(1/d)$ and $\sqrt{1+O(1/d)}=1+O(1/d)$,

$\gamma(w)=\gamma\cdot\left(1+O\left(\frac{1}{d(x)}\right)\right)=\gamma+o(1).$
(37)

###  7.1. Proof of Lemma 5.1

In this section we will prove Lemma 5.1 about the existence of a constant
$\beta>0$ (independent of $x$) such that

$\mathbb{P}[x\in\hat{A}_{3}\setminus\hat{A}_{2}]\leqslant\exp\left(-\beta\gamma(x)^{2}\log
d(x)\right).$

Let $\mathcal{W}$ be the set of pairs $(W_{1},W_{2})$ with $W_{i}\subseteq
S_{0}(x,i)$ satisfying

$W_{2}\subseteq
N(W_{1}),\qquad|W_{1}|=\gamma-3K,\qquad|W_{2}|=(\gamma-3K)^{2}/2K,$

which will be called _witnesses_. The _weight_ of a witness $(W_{1},W_{2})$ is
defined as $\zeta(W_{2})\coloneqq e(W_{2},S_{0}(x,3))$. We observe that, for
every $(W_{1},W_{2})\in\mathcal{W}$, we have

$\zeta(W_{2})=|W_{2}|(d+O(1)),$ (38)

since every vertex of $W_{2}$ has degree $d\pm 2K$ by Property P1 and every
vertex of $S_{0}(x,2)$ has at most $4K$ neighbours outside $S_{0}(x,3)$ by
Properties P2 and P3ii.

The definition of witness is motivated by the following claim (see Figure 4).

$x$$N(x)$$S(x,2)$$W_{1}$$w$$W_{2}^{\prime}$$W_{2,w}$ Figure 4. For a vertex
$x\in(\hat{A}_{3}\setminus\hat{A}_{2})$ there is a set $W_{1}\subseteq
S_{0}(x,1)\cap(\hat{A}_{2}\setminus\hat{A}_{1})$ of size $\gamma-3K$. For each
$w\in W_{1}$ there is a set $W_{2,w}\subseteq
S_{0}(x,2)\cap\hat{A}_{1}\setminus\hat{A}_{0}$, and their union is
$W_{2}^{\prime}$, which contains a subset $W_{2}$ of size exactly
$(\gamma-3K)^{2}/2K$.

######  Claim 7.1.

If $x\in\hat{A}_{3}\setminus\hat{A}_{2}$, there exists a witness
$(W_{1},W_{2})\in\mathcal{W}$ such that

$Z\geqslant\mathbb{E}[Z]+(c\sigma d-3\gamma)|W_{2}|,$

where $Z=Z(W_{2}):=e\bigl{(}W_{2},S_{0}(x,3)\cap\hat{A}_{0}\bigr{)}$.

###### Proof of Claim 7.1.

We start by observing that, by definition of the
$\operatorname{Boot}_{2}(\gamma)$ process, entering $\hat{A}_{3}$ requires
$d/2$ infected neighbours, while entering $\hat{A}_{2}$ requires only
$d/2-\gamma$ ones. Therefore, the event
$\\{x\in\hat{A}_{3}\setminus\hat{A}_{2}\\}$ implies the existence of a set
$W_{1}^{\prime}\subseteq S(x,1)\cap(\hat{A}_{2}\setminus\hat{A}_{1})$ of
recently-infected neighbours of $x$ of size $|W_{1}^{\prime}|=\gamma$. Since
$|D\cap N(x)|\leqslant 1\leqslant 3K$ by Property P3i, we may take a subset
$W_{1}\subseteq W_{1}^{\prime}\cap S_{0}(x,1)$ of size $\gamma-3K$.

Similarly, since each $w\in W_{1}$ is in $\hat{A}_{2}\setminus\hat{A}_{1}$, it
has $\gamma(w)\geqslant\gamma-1$ neighbours in
$\hat{A}_{1}\setminus\hat{A}_{0}$, where the inequality uses (37). Moreover,
since each $w\in S_{0}(x,1)$ has at most $K$ neighbours in $B(x,1)$ by
Property P2 and at most $K$ neighbours in $D$ by Property P3ii, for each $w\in
W_{1}$ the set $W_{2,w}\coloneqq N(w)\cap
S_{0}(x,2)\cap(\hat{A}_{1}\setminus\hat{A}_{0})$ has size at least $\gamma-3K$
(see Figure 4). Moreover, every element of

$W_{2}^{\prime}:=\bigcup_{w\in W_{1}}W_{2,w}$

has at most $2K$ neighbours in $W_{1}$ by Property P2, and so
$|W_{2}^{\prime}|\geqslant\frac{(\gamma-3K)^{2}}{2K}$ by double counting. We
may therefore choose a $W_{2}\subseteq W_{2}^{\prime}$ of size
$\frac{(\gamma-3K)^{2}}{2K}$.

It remains to show that $Z(W_{2})\geqslant\mathbb{E}[Z(W_{2})]+(\sigma
d-3\gamma)|W_{2}|$. By definition of $\zeta$ and $Z$, we have
$\mathbb{E}[Z]=\zeta p$. On the other hand,
$W_{2}\subseteq\hat{A}_{1}\setminus\hat{A}_{0}$ by construction. Therefore, by
Properties P1, P2 and P3ii, every $w\in W_{2}\subseteq S_{0}(x,2)$ has at
least $\frac{d(w)}{2}-2\gamma(w)-4K=\frac{d}{2}-2\gamma+O(1)$ neighbours in
$S_{0}(x,3)\cap\hat{A}_{0}$. Since $p=1/2-c\sigma$, using (38) we obtain

$Z(W_{2})\geqslant|W_{2}|(d/2-2\gamma+O(1))=\zeta/2-|W_{2}|(2\gamma+O(1))\geqslant\zeta
p+(c\sigma d-3\gamma)|W_{2}|,$

where we used that $\zeta p=(\zeta/2)-c\sigma|W_{2}|(d+O(1))$ and $\gamma\gg
1\gg c\sigma$ in the last inequality. ∎

Therefore, if the process has not stabilised after three rounds, there is a
witness such that $Z$ exceeds its expectation. On the other hand, the next
claim shows that this is a low probability event. To simplify notation, we set
$s\coloneqq(\gamma-3K)^{2}/2K$ in the remainder of this section. Recall that
every witness $(W_{1},W_{2})$ has $|W_{2}|=s$.

######  Claim 7.2.

Let $s\in\mathbb{N}$. For every witness $(W_{1},W_{2})$, we have

$\mathbb{P}\left[Z(W_{2})\geqslant\mathbb{E}[Z]+(c\sigma
d-3\gamma)s\right]\leqslant\exp\left(-(2+o(1))c^{2}s\log d\right),$

where $Z=Z(W_{2}):=e\bigl{(}W_{2},S_{0}(x,3)\cap\hat{A}_{0}\bigr{)}$.

###### Proof of Claim 7.2.

Recall that by Property P2, a vertex in $S_{0}(x,3)$ has at most $3K$
neighbours in $S(x,2)$. For $i\in[3K]$, let $X_{i}$ be the set of elements of
$S_{0}(x,3)$ having $i$ neighbours in $W_{2}$. We have

$\zeta=\zeta(W_{2})=\sum_{i=1}^{3K}i\cdot|X_{i}|,$

and letting $M\coloneqq\sum_{i=1}^{3K}i^{2}|X_{i}|$ we have by Lemma 2.3 that,
for any $t\geqslant 0$,

$\mathbb{P}\left[Z(W_{2})\geqslant\mathbb{E}[Z]+t\right]\leqslant\exp\left(-\frac{2t^{2}}{M}\right).$
(39)

Let $X_{\geqslant 2}$ be the set of elements of $S_{0}(x,3)$ having at least
two neighbours in $W_{2}$. Observe that $|X_{\geqslant
2}|\leqslant\binom{|W_{2}|}{2}\leqslant\frac{\gamma^{4}}{2}=o(sd)$, since any
two elements of $S_{0}(x,2)$ have at most one neighbour in $S_{0}(x,3)$ by
Property P3iii. Therefore, recalling (38), we have

$M=\sum_{i=1}^{3K}i^{2}|X_{i}|\leqslant|X_{1}|+o(sd)\leqslant(1+o(1))\zeta=(1+o(1))sd$

and with $t=(c\sigma d-3\gamma)s$ the right hand-side of (39) is

$\exp\left(-\frac{2s^{2}(c\sigma
d-3\gamma)^{2}}{(1+o(1))sd}\right)\leqslant\exp\left(-(2+o(1))sc^{2}\sigma^{2}d\right)=\exp(-(2+o(1))c^{2}s\log
d),$

since $\sigma d\gg\gamma$. This proves the claim. ∎

We are now ready to prove Lemma 5.1.

###### Proof of Lemma 5.1.

Suppose there is an $x\in\hat{A}_{3}\setminus\hat{A}_{2}$ and consider the
witness $(W_{1},W_{2})$ from Claim 7.1. Recall that every witness satisfies
$|W_{2}|=s=(\gamma-3K)^{2}/2K$. Since $W_{2}\subseteq N(W_{1})$ and $\gamma
d/s=\Theta(d/\gamma)=\Theta(\sqrt{d\vartheta})$, for each $W_{1}\subseteq
N(x)$ there are at most

$\binom{|N(W_{1})|}{s}\leqslant\binom{\gamma
d}{s}\leqslant\exp\Bigl{(}(1/2+o(1))s\log d\Bigr{)}$

choices for $W_{2}$ with $|W_{2}|=s$. Therefore, we may use Claim 7.2 and the
union bound to obtain

$\mathbb{P}\left[x\in\hat{A}_{3}\setminus\hat{A}_{2}\right]\leqslant\exp\Bigl{(}(1/2+o(1))s\log
d-(2+o(1))c^{2}s\log d\Bigr{)}.$

There is some $\varepsilon>0$ such that $c=\frac{1}{2}+\varepsilon$, and
therefore

$\mathbb{P}\left[x\in\hat{A}_{3}\setminus\hat{A}_{2}\right]\leqslant\exp(-(2\varepsilon+o(1))s\log
d)\leqslant\exp\left(-\frac{\varepsilon}{2K}\cdot\gamma^{2}\log d\right),$

and so Lemma 5.1 holds with $\beta=\frac{\varepsilon}{2K}$. ∎

###  7.2. Proof of Lemma 5.2

In this section we will prove Lemma 5.2, claiming

$\mathbb{P}[x\in\hat{A}_{2}\setminus\hat{A}_{1}]\leqslant\exp\left(-\sqrt{d(x)}\right).$

The proof is very similar to the proof of Lemma 5.1 in the previous section.
As in the proof of Claim 7.1, since $x\in\hat{A}_{2}\setminus\hat{A}_{1}$,
there exists a set $W^{\prime}\subseteq
N(x)\cap(\hat{A}_{1}\setminus\hat{A}_{0})$ of size $\gamma$. Take $W$ to be a
subset $W^{\prime}\cap S_{0}(x,1)$ of size $\gamma-1$, which is possible by
Property P3i, and define

$\zeta^{\prime}:=e(W,S_{0}(x,2)).$

By Properties P2 and P3ii, each $w\in W\subseteq S_{0}(x,1)$ has at most $2K$
neighbours outside $S_{0}(x,2)$. Together with Property P1 this implies that

$\zeta^{\prime}=|W|(d+O(1)).$ (40)

Moreover, since every $w\in W$ is infected in the first round, we have

$|N(w)\cap S_{0}(x,2)\cap\hat{A}_{0}|\geqslant
d(w)/2-2\gamma+O(1)=d/2-2\gamma+O(1),$

and so

$Z^{\prime}(W)\coloneqq
e(W,S_{0}(x,2)\cap\hat{A}_{0})\geqslant|W|(d/2-2\gamma+O(1))\geqslant\zeta^{\prime}p+(c\sigma
d-3\gamma)|W|,$

observing that $\mathbb{E}[Z^{\prime}]=\zeta^{\prime}p$.

By Property P2, every vertex in $S_{0}(x,2)$ has at most $2K$ neighbours in
$W\subseteq B(x,2)$. If we let $X^{\prime}_{i}$ denote the set of elements of
$S_{0}(x,2)$ with $i$ neighbours in $W$ for $i\in[2K]$, we have that

$\zeta^{\prime}=\sum_{i=1}^{2K}i|X^{\prime}_{i}|.$

Similarly as in the proof of Claim 7.2, let $X^{\prime}_{\geqslant 2}$ be the
set of elements of $S_{0}(x,2)$ having at least two neighbours in $W$. We have
$|X^{\prime}_{\geqslant 2}|\leqslant\binom{|W|}{2}\leqslant\gamma^{2}=o(\gamma
d)$, since any two elements of $S_{0}(x,1)$ have at most one common neighbour
in $S_{0}(x,2)$ by Property P3iii, and therefore, by (40),

$\sum_{i=1}^{2K}i^{2}|X^{\prime}_{i}|\leqslant|X^{\prime}_{1}|+o(\gamma
d)\leqslant(1+o(1))\zeta^{\prime}=(1+o(1))\gamma d.$

By Lemma 2.3, for $t=|W|(c\sigma d-3\gamma)$ we have that

$\mathbb{P}[Z^{\prime}(W)\geqslant\mathbb{E}[Z^{\prime}]+t]\leqslant\exp\left(-\frac{2(\gamma-1)^{2}(c\sigma
d-3\gamma)^{2}}{(1+o(1))\gamma d}\right)=\exp\left(-(2+o(1))c^{2}\gamma\log
d\right).$ (41)

Moreover, since $W\subseteq N(x)$ and
$d/(\gamma-1)=\Theta(\sqrt{d\vartheta})$, there are at most

$\binom{d}{\gamma-1}\leqslant\exp\Bigl{(}(1/2+o(1))\gamma\log d\Bigr{)}$ (42)

choices for $W$. Combining (41) and (42) and using the fact that $c>1/2$ we
obtain

$\mathbb{P}[x\in\hat{A}_{2}\setminus\hat{A}_{1}]\leqslant\exp\left(-(1+o(1))2c^{2}\gamma\log
d+(1/2+o(1))\gamma\log d\right)\leqslant\exp(-\Omega(\gamma\log d)).$

Since $\log d\gg\vartheta(d)$, it follows that $\gamma\log d\gg\sqrt{d}$,
finishing the proof of Lemma 5.2.

##  8\. Examples of geometric graphs

We dedicate this section to the illustration of the class
$\mathcal{H}=\bigcup_{K\in\mathbb{N}}\mathcal{H}(K)$ of high-dimensional
geometric graphs by giving some examples of graph classes that are contained
in $\mathcal{H}$. In addition to the formal proofs that the required
properties are satisfied, we provide some intuition about the _local
coordinate system_ that makes these graphs _high-dimensional_.

###  8.1. Cartesian Product graphs

######  Definition 8.1.

For $n\in\mathbb{N}$ let $(H_{i})_{i\in[n]}$ be a sequence of connected
graphs, called _base graphs_. We define the _(Cartesian) product graph_
$G=\mathbin{\Box}_{i=1}^{n}H_{i}$ as the graph with vertex set

$V(G)\coloneqq\prod_{i=1}^{n}V(H_{i})=\\{(x_{1},\dots,x_{n})\mid x_{i}\in
V(H_{i})\text{ for all }i\in[n]\\}$

and with edge set

$E(G)\coloneqq\left\\{\bigl{\\{}x,y\bigr{\\}}\colon\text{ there is some
}i\in[n]\text{ such that }\\{x_{i},y_{i}\\}\in E(H_{i})\text{ and
}x_{j}=y_{j}\text{ for all }j\neq i\right\\}.$

In the case of product graphs, there is a clear coordinate system coming from
the product structure.

######  Lemma 8.2.

Let $C>1$ be a constant and let $H_{1},\ldots,H_{n}$ be graphs such that
$1<|H_{i}|\leqslant C$ for all $i\in[n]$. Then
$G_{n}=\mathbin{\Box}_{i=1}^{n}H_{i}\in\mathcal{H}(C)$ for all
$n\in\mathbb{N}$.

###### Proof.

Write $G\coloneqq G_{n}$. Given distinct vertices $x,y\in V(G)$, let us define

$I(x,y)\coloneqq\\{i\in[n]\colon x_{i}\neq y_{i}\\},$

noting that $1\leqslant|I(x,y)|\leqslant\operatorname{dist}(x,y)$.

###### Proof of Property P1.

This property of (Cartesian) product graphs was already observed by Lichev
[44]. Indeed, given $x\in V(G)$, $\ell\in\mathbb{N}$ and $y\in S(x,\ell)$, we
see that

$|d(x)-d(y)|=\left|\sum_{i\in[n]}d_{H_{i}}(x_{i})-\sum_{i\in[n]}d_{H_{i}}(y_{i})\right|=\left|\sum_{i\in
I(x,y)}(d_{H_{i}}(x_{i})-d_{H_{i}}(y_{i}))\right|\leqslant C|I(x,y)|\leqslant
C\ell.$

###### Proof of Property P2.

Given $x\in V(G)$, $\ell\in\mathbb{N}$ and $y\in S(x,\ell)$, the neighbours of
$y$ in $B(x,\ell)$ must differ from $y$ in coordinates in $I(x,y)$. Hence
there are at most $C\ell$ neighbours of $y$ in $B(x,\ell)$ as
$|I(x,y)|\leqslant\ell$.

###### Proof of Property P3.

Given $x\in V(G)$ let

$D\coloneqq\\{y\in V(G)\;:\;|I(x,y)|\neq\operatorname{dist}(x,y)\\},$

so that for all $\ell\in\mathbb{N}$

$S_{0}(x,\ell)\coloneqq S(x,\ell)\setminus D=\\{y\in
S(x,\ell)\;:\;|I(x,y)|=\ell\\}.$

Since a vertex in $S(x,\ell)\cap D$ differs from $x$ in at most $\ell-1$
coordinates it is clear that $|S(x,\ell)\cap D|\leqslant
C^{\ell-1}\binom{n}{\ell-1}\leqslant C^{\ell-1}d^{\ell-1}$, and so i holds.
Furthermore, if $y\in S_{0}(x,\ell)$, then a neighbour of $y$ in $D$ must
differ from $y$ in some coordinate in $I(x,y)$, and hence there are at most
$C\ell$ of them, and so ii holds. Finally, if $w,y\in S_{0}(x,\ell)$ are
distinct, and have a common neighbour $z\in S_{0}(x,\ell+1)$, then it is easy
to verify that $|I(x,w)\cup I(x,y)|=\ell+1$ and hence there is a unique common
neighbour $z\in S_{0}(x,\ell+1)$ which agrees with $w$ on $I(x,w)$, with $y$
on $I(x,y)$ and with $x$ on $[n]\setminus(I(x,w)\cup I(x,y))$. Hence iii
holds.

###### Proof of Property P4.

We induct on the dimension $n$ of the product graph $G_{n}$. For the base
case, it is easy to verify that if $|V(G)|\leqslant C$, then
$G\in\mathcal{H}(C)$. Let $x\in V(G),\ell\in\mathbb{N}$ and $y\in S(x,\ell)$.
Let $G(y)\coloneqq\left(\mathbin{\Box}_{i\not\in
I(x,y)}H_{i}\right)\mathbin{\Box}\left(\mathbin{\Box}_{i\in
I(x,y)}\\{y_{i}\\}\right)$. Clearly $y\in V(G(y))$ and $V(G(y))\cap
B(x,\ell-1)=\varnothing$.

Furthermore, for any $w\in V(G(y))$,

$|d_{G(y)}(w)-d_{G}(w)|=\left|\sum_{i\not\in
I(x,y)}d_{H_{i}}(w_{i})-\sum_{i\in[n]}d_{H_{i}}(w_{i})\right|=\sum_{i\in
I(x,y)}d_{H_{i}}(w_{i})\leqslant C|I(x,y)|\leqslant C\ell.$

Finally, since $|I(x,y)|\geqslant 1$, $G(y)$ is a product graph of dimension
at most $n-1$, and so by the induction hypothesis $G(y)\in\mathcal{H}(C)$.

###### Proof of Property P5.

Let $x\in V(G)$, $\ell\in\mathbb{N}$ and $y\in S_{0}(x,\ell)$. Let

$Z\coloneqq B(y,2\ell-1)\cap S_{0}(x,\ell)=\\{z\in
S_{0}(x,\ell)\;:\;\operatorname{dist}(z,y)\leqslant 2\ell-1\\}.$

Note that, for any $x\in V(G)$, $y\in S_{0}(x,\ell)$ and $z\in S_{0}(x,\ell)$
we have $I(x,z)\mathbin{\triangle}I(x,y)\subseteq I(y,z)$ and since
$|I(x,z)|=|I(x,y)|=\ell$, we have
$|I(x,z)\mathbin{\triangle}I(x,y)|=2|I(x,z)\setminus I(x,y)|$. Hence,

$\operatorname{dist}(y,z)\geqslant|I(y,z)|\geqslant|I(x,z)\mathbin{\triangle}I(x,y)|=2|I(x,z)\setminus
I(x,y)|.$ (43)

Rearranging this we have

$|I(x,z)\setminus
I(x,y)|\leqslant\frac{1}{2}\left(\operatorname{dist}(y,z)\right)<\ell,$

for every $z\in Z$. And hence,

$Z\subseteq Z^{\prime}\coloneqq\\{z\in S(x,\ell)\colon|I(x,z)\setminus
I(x,y)|\leqslant\ell-1\\},$

The choices for $z\in Z^{\prime}$ may be bounded by first choosing $I(x,z)$ of
size $\ell$ with $I(x,z)\cap I(x,y)\neq\varnothing$ and then choosing the
values for the coordinates in $I(x,z)$. Therefore,

$|Z^{\prime}|\leqslant\ell\binom{n-1}{\ell-1}C^{\ell-1}\leqslant\ell
C^{\ell-1}d(x)^{\ell-1}$

since $d(x)\geqslant n$.

###### Proof of Property P6.

Finally, it is clear that $|V(G)|\leqslant C^{n}$ and $\delta(G)\geqslant n$,
and hence $|V(G)|\leqslant\exp(\log
C\cdot\delta(G))\leqslant\exp(C\delta(G))$.

This concludes the proof of Lemma 8.2. ∎

######  Remark 8.3.

In particular, the $n$-dimensional hypercube is in $\mathcal{H}(2)$ and we can
pick $D=\varnothing$ in this case.

Note that, under the condition of Lemma 8.2, all degrees in $G_{n}$ are in
$\Theta(n)$, and so $\delta(G_{n})$ and $\Delta(G_{n})$ differ by at most a
constant multiplicative factor. In particular, Theorem 1.4 implies that for
_any_ such product graph, the critical window has width
$O\left(\sqrt{\frac{\log n}{n}}\right)$.

###  8.2. The middle layer and odd graphs

######  Definition 8.4.

The _middle layer graph_ $M_{n}$ is the graph whose vertices are all vectors
of length $2n-1$ where either $n$ or $n-1$ many entries are $1$, while all
other entries are $0$. Two vertices are connected if they differ in exactly
one coordinate.

We note that the middle layer graph is not a (Cartesian) product graph, since
it can be seen to have girth six. Note that the middle layer graph is a
subgraph of a hypercube, i.e., $M_{n}\subseteq Q_{2n-1}$, and again here there
is a clear coordinate system underlying the graph structure. Furthermore,
$M_{n}$ is an isometric subgraph of $Q_{2n-1}$, i.e.,
$\operatorname{dist}_{M_{n}}(u,v)=\operatorname{dist}_{Q_{2n-1}}(u,v)$ for all
$u,v\in V(M_{n})$. Since $Q_{2n-1}\in\mathcal{H}(2)$, this allows us to
transfer some properties from the hypercube directly.

######  Lemma 8.5.

The middle layer graph $M_{n}\in\mathcal{H}(4)$ for all $n\in\mathbb{N}$.

###### Proof.

Let $G=M_{n}$. Given distinct vertices $x,y\in V(G)$, let us define

$I(x,y)\coloneqq\\{i\in[n]\colon x_{i}\neq y_{i}\\},$

noting that $|I(x,y)|=\operatorname{dist}(x,y)$.

###### Proof of Property P1.

$G$ is $n$-regular.

###### Proof of Property P2.

The property is preserved under taking isometric subgraphs.

###### Proof of Property P3.

For every $x\in V(G)$ let $D=\varnothing$, so that for all $\ell\in\mathbb{N}$
we have $S_{0}(x,\ell)=S(x,\ell)$ and thus i and ii hold trivially. Since iii
is satisfied by the hypercube $Q_{2n-1}$ with $D=\varnothing$, and is
preserved under taking isometric subgraphs, it also holds in $M_{n}$ with
$D=\varnothing$.

###### Proof of Property P4.

We induct on $n$. Let $x\in V(G),\ell\in\mathbb{N}$ and $y\in S(x,\ell)$.
Assume first that $\ell$ is even. Let $V(y)=\prod_{i\in
I(x,y)}\\{y_{i}\\}\times\prod_{i\notin I(x,y)}\\{0,1\\}$ and set
$G(y)=G[V(y)]$, i.e., we fix the coordinates where $y$ differs from $x$ and
let the other coordinates vary. It is easy to verify that $G(y)$ is isomorphic
to $M_{n-\ell/2}$ and so by the induction hypothesis, we have
$G(y)\in\mathcal{H}(4)$. Furthermore, since $M_{n}$ is $n$-regular and
$M_{n-\ell/2}$ is $(n-\ell/2)$-regular, it follows that for any $w\in
V(G(y))$, we have $|d_{G(y)}(w)-d_{G}(w)|=\ell/2$. Finally, it is simple to
check that $y\in V(G(y))$ and $V(G(y))\cap B(x,\ell-1)=\varnothing$.

The case when $\ell$ is odd is similar: we fix an extra coordinate to balance
the number of fixed $0$ coordinates the number of fixed $1$ coordinates.

###### Proof of Property P5.

The property is satisfied by the hypercube $Q_{2n-1}$ with $D=\varnothing$ and
$K=2$, and is preserved under taking isometric subgraphs. However, the degrees
of vertices are not the same in both of these graphs. Nevertheless, since
$Q_{2n-1}$ is $(2n-1)$-regular and $M_{n}$ is $n$-regular, it follows that for
each $y\in S_{M_{n}}(x,\ell)$,

$|B_{M_{n}}(y,2\ell-1)\cap S_{M_{n}}(x,\ell)|\leqslant\ell
2^{\ell-1}(2n-1)^{\ell-1}\leqslant\ell 4^{\ell-1}d_{M_{n}}(y)^{\ell-1}.$

###### Proof of Property P6.

Since $V(M_{n})\subseteq V(Q_{2n-1})$, we have $|V(M_{n})|\leqslant 2^{2n-1}$
and it follows that $|V(G)|\leqslant\exp(4\delta(M_{n}))$.

This concludes the proof of Lemma 8.5. ∎

We also consider the _odd graph_ , which is a special _Kneser graph_.

######  Definition 8.6.

For $n,k\in\mathbb{N}$ with $n\geqslant k$ the _Kneser graph_ $K(n,k)$ is the
graph with vertex set $V(K(n,k))=[n]^{(k)}=\binom{[n]}{k}$ consisting of all
the $k$-element subsets of $[n]$, where two $k$-element subsets are adjacent
in $K(n,k)$ if they are disjoint.

Instead of directly proving that $O_{n}\coloneqq K(2n-1,n-1)$ lies in
$\mathcal{H}$ we will use the fact, which is essentially folklore, that
$M_{n}$ and $O_{n}$ are locally isomorphic as follows.

######  Lemma 8.7.

Let $x\in[2n-1]^{(n-1)}$ and let $\ell<n-1$. Then $B_{O_{n}}(x,\ell)\cong
B_{M_{n}}(x,\ell)$.

###### Proof.

Let $x\in V(O_{n})$, so $x$ is a subset of $[2n-1]$ of size $n-1$. We define a
map between the balls $B_{O_{n}}(x,\ell)$ and $B_{M_{n}}(x,\ell)$. For each
$k\in\bigl{[}\lfloor\frac{\ell}{2}\rfloor\bigr{]}$ and $y\in S_{O_{n}}(x,2k)$
we map the set $y$ to its indicator function in $\\{0,1\\}^{2n-1}$. For every
$k\in\bigl{[}\lfloor\frac{\ell-1}{2}\rfloor\bigr{]}$ and $y\in
S_{O_{n}}(x,2k+1)$ we map $y$ to the indicator function of its complement
$[2n-1]\setminus y$. Note that the complement has size $n$ and hence
corresponds to a vertex in $V(M_{n})$.

The map obtained in this way is indeed an isomorphism: If $y,z\in
B_{O_{n}}(x,\ell)$ are such that $\\{y,z\\}\in E(O_{n})$, then $y\cap
z=\varnothing$. Since the odd girth of $O_{n}$ is $2n-1$, without loss of
generality $y\in S_{O_{n}}(x,2k)$ for some
$k\in\bigl{[}\lfloor\frac{\ell}{2}\rfloor\bigr{]}$ and $z\in
S_{O_{n}}(x,2k^{\prime}+1)$ for some
$k^{\prime}\in\bigl{[}\lfloor\frac{\ell-1}{2}\rfloor\bigr{]}$, where
$k^{\prime}=k\pm 1$. But then $y\subseteq[2n-1]\setminus z$ and hence the
image of the edge $\\{y,z\\}$ under the mapping is an edge in $E(M_{n})$. A
similar argument shows that every edge in $B_{M_{n}}(x,\ell)$ is the image of
an edge in $B_{O_{n}}(x,\ell)$ under the mapping and hence, this mapping gives
an isomorphism from $B_{O_{n}}(x,\ell)$ to $B_{M_{n}}(x,\ell)$ for any
$\ell<n-1$. ∎

So the odd graph $O_{n}$ is ‘locally’ isomorphic to a graph, i.e., the middle
layer graph $M_{n}$, which we have already shown lies in $\mathcal{H}$.

As Properties P1, P2, P3 and P5 are all of local nature, they continue to hold
in $O_{n}$ for $\ell<n-1$, which is already sufficient for our proof.
Furthermore, since the diameter of $O_{n}$ is $n-1$, there is only one further
case to consider, in which all of the properties above are trivially satisfied
with say $K=4$, for which also Property P6 trivially holds.

Finally, it remains to show that Property P4 holds in $O_{n}$. Let $x\in
V(O_{n})$, $\ell\in\mathbb{N}$ and $y\in S(x,\ell)$.

Assume first that $\ell=2k$ is even. By the structure of the odd graph, the
sets $a\coloneqq x\setminus y$ and $b\coloneqq y\setminus x$ have size $k$.
Pick a set $a^{\prime}\subseteq x\cap y$ and a set
$b^{\prime}\subseteq[2n-1]\setminus(x\cup y)$, both of size $k$ and set

$V(y)\coloneqq\left\\{v\in V(O_{n})\,\middle|\begin{array}[]{l}\big{(}(b\cup
a^{\prime}\subseteq v)\wedge((b^{\prime}\cup a)\cap
v=\varnothing)\big{)}\;\vee\\\ \big{(}(b^{\prime}\cup a\subseteq
v)\wedge((b\cup a^{\prime})\cap
v=\varnothing)\big{)}\;\phantom{\vee}\end{array}\right\\}.$

Let $G(y)$ be the induced subgraph of $O_{n}$ on the vertex set $V(y)$. Then
$y\in V(G(y))$ as $b\cup a^{\prime}\subseteq y\text{ and }(b^{\prime}\cup
a)\cap y=\varnothing$. For each vertex $w\in V(y)$ we obtain $|w\cap
x|\geqslant k$ and $|w\setminus x|\geqslant k$. The former inequality implies
that $\operatorname{dist}(x,w)\geqslant 2k+1$ if $\operatorname{dist}(x,w)$ is
odd, and the latter implies that $\operatorname{dist}(x,w)\geqslant 2k$
otherwise, and thus $w\notin B(x,\ell-1)$. Furthermore, $G(y)$ can be seen to
be isomorphic to $M_{n-\ell}$ under the mapping which takes each $w\in V(y)$
with $b^{\prime}\cup a\subseteq w\text{ and }(b\cup a^{\prime})\cap
w=\varnothing$ to its complement. Thus by Lemma 8.5 we have
$G(y)\in\mathcal{H}(4)$ and since $G$ is $n$-regular and $M_{n-\ell}$ is
$(n-\ell)$-regular we get $|d_{G(y)}(w)-d_{G}(w)|=\ell\leqslant 4\ell$ for
each $w\in V(y)$.

The case when $\ell=2k+1$ is similar. In this case, $a\coloneqq x\cap y$ is a
set of size $k$ and $b\coloneqq[2n-1]\setminus(x\cup y)$ is a set of size
$k+1$. Pick a set $a^{\prime}\subseteq x\setminus y$ of size $k$ and a set
$b^{\prime}\subseteq y\setminus x$ of size $k+1$, and consider the set $V(y)$
as defined above. Taking $G(y)$ to be the induced subgraph of $O_{n}$ on
$V(y)$, we note that $y\in V(G(y))$ as $b^{\prime}\cup a\subseteq y\text{ and
}(b\cup a^{\prime})\cap y=\varnothing$. Again, for each vertex $w\in V(y)$ we
obtain $|w\cap x|\geqslant k$ and $|w\setminus x|\geqslant k+1$ and thus
$w\notin B(x,\ell-1)$. As before, $G(y)$ can be seen to be isomorphic to
$M_{n-\ell}$ under the mapping which takes each $w\in V(y)$ with $b\cup
a^{\prime}\subseteq v\text{ and }(b^{\prime}\cup a)\cap v=\varnothing$ to its
complement and the degrees in $G$ and $G(y)$ differ by $\ell$.

######  Lemma 8.8.

The odd graph $O_{n}\in\mathcal{H}(4)$ for all $n\in\mathbb{N}$.

###  8.3. The folded hypercube

######  Definition 8.9.

For $n\in\mathbb{N}$ the _folded hypercube_ $\tilde{Q}_{n}$ is a graph on the
same vertex set as the $(n-1)$-dimensional hypercube, i.e.,
$V(\tilde{Q}_{n-1})=\\{0,1\\}^{n-1}$. It is obtained from $Q_{n-1}$ by joining
each vertex $x$ to its antipodal vertex $\tilde{x}$, where $\tilde{x}$ is the
vertex differing from $x$ in every coordinate. That is, $\tilde{Q}_{n}$ is
obtained by adding all edges $\\{x,\tilde{x}\\}$ to the edge set of $Q_{n-1}$.

We can think of the underlying coordinate system here as being
$\\{0,1\\}^{n}$, where the first $n-1$ coordinates represent the ‘actual’
vertex $v\in V(Q_{n-1})$ and the final coordinate represents movement to the
antipodal point.

We note that it is relatively easy to see that the folded hypercube is not
expressible as the product of bounded order graphs. Indeed, as we will see
shortly, $\tilde{Q}_{n}$ is locally isomorphic to $Q_{n}$, and so every
connected subgraph of $\tilde{Q}_{n}$ of bounded order is a subgraph of a
hypercube. However, it is easy to show that any product graph in which every
factor is a subgraph of a hypercube is at most as dense as a hypercube, and
$\tilde{Q}_{n}$ has strictly more edges than $Q_{n-1}$. In fact, with more
care, it can be shown that $\tilde{Q}_{n}$ is not expressible as a Cartesian
product even with factors of unbounded order.

As with $M_{n}$ and $O_{n}$, the folded hypercube is ‘locally’ isomorphic to a
graph, i.e., the hypercube $Q_{n}$, which we have already shown lies in
$\mathcal{H}$. Indeed the following is shown in [43].

######  Lemma 8.10.

Let $x\in\\{0,1\\}^{n-1}$ and $y\in\\{0,1\\}^{n}$ and let
$\ell<\left\lfloor\frac{n}{2}\right\rfloor$. Then
$B_{\tilde{Q}_{n}}(x,\ell)\cong B_{Q_{n}}(y,\ell)$.

As before, since by Remark 8.3 we have $Q_{n}\in\mathcal{H}(2)$, and
Properties P1, P2, P3 and P5 are all of local nature, they continue to hold in
$\tilde{Q}_{n}$ for $\ell<\left\lfloor\frac{n}{2}\right\rfloor$, which is
already sufficient for our proof. Furthermore, since the diameter of
$\tilde{Q}_{n}$ is $\left\lfloor\frac{n}{2}\right\rfloor$, there is only one
further case to consider, in which all of the properties are trivially
satisfied with say $K=3$, for which also Property P6 trivially holds.

Finally, it is a simple exercise to show that Property P4 holds in
$\tilde{Q}_{n}$. Indeed, since all vertices at distance at most $\ell-1$ from
a vertex $x$ differ from $x$ or $\tilde{x}$ in at most $\ell-1$ coordinates,
given a vertex $w\in S_{\tilde{Q}_{n}}(x,\ell)$ it is easy to find a subgraph
of $\tilde{Q}_{n}$ containing $w$ which is isomorphic to $Q_{n-2\ell+2}$ and
disjoint from $B_{\tilde{Q}_{n}}(x,\ell-1)$ by fixing appropriately chosen
coordinate sets similarly as in the proof of Lemma 8.2.

######  Lemma 8.11.

The folded hypercube $\tilde{Q}_{n}\in\mathcal{H}(3)$ for all
$n\in\mathbb{N}$.

##  9\. Discussion

In this paper we extended the results of Balogh, Bollobás and Morris [11] to a
large class of high-dimensional geometric graphs. It is perhaps natural to ask
what the limits of our proof methods are, and what structural conditions are
necessary to exhibit a similar behaviour in terms of the location and width of
the critical window, which in both cases seem to be controlled by the local
structure of the graphs.

######  Question 9.1.

Let $G$ be an $n$-regular graph. Under what assumptions are the first two
terms in the expansion of the critical probability of majority bootstrap
percolation in $G$ given by $\frac{1}{2}-\frac{1}{2}\sqrt{\frac{\log n}{n}}$?

Our proof methods seem to rely on the high-dimensional geometric structure of
the graphs, however there are many other graphs which seem inherently high-
dimensional which our results do not cover. For example, the _halved cube_ is
the graph on $\\{0,1\\}^{n}$ where two vertices are adjacent if they have
Hamming distance exactly two. Geometrically, this is the $1$-skeleton of the
polytope constructed from an _alternation_ of a hypercube. Whilst this graph
is regular and highly symmetric, the presence of many triangles, and indeed
large cliques in every neighbourhood, cause the property of bounded backwards
expansion (Property P2) to fail and so the graph does not lie in the class
$\mathcal{H}$ as defined in Section 3. Furthermore, motivated by the case of
the middle layer graph and the odd graph, it would be interesting to know if
similar behaviour is present in (bipartite) Kneser graphs with a larger range
of parameters or in other graphs arising from intersecting set systems such as
Johnson graphs. Here, whilst the graphs still display a sort of fractal self-
symmetry, an issue arises with the quantitative aspects of Property P4, since
the degrees in these projections drop too quickly and this effect dominates
the variations in the number of infected vertices in a vertex’s neighbourhood.
Another interesting example comes from the _permutahedron_ , a well-studied
graph which like the hypercube has many equivalent ‘high-dimensional’
representations. Here, whilst Properties P1, P2, P3, P4 and P5 are satisfied,
the graph is too large to satisfy Property P6, superexponential in its
regularity. In a forthcoming paper [21] we will show that the analogue of
Corollary 1.5 also holds in the permutahedron.

In comparison to Theorem 1.3, we give a weaker bound on the width of the
critical window. As pointed out in Remark 6.5, our methods recover the upper
bound in Theorem 1.3, that is, if $\lambda>\frac{1}{2}$ and

$p=\frac{1}{2}-\frac{1}{2}\sqrt{\frac{\log\Delta(G_{n})}{\Delta(G_{n})}}+\frac{\lambda\log\log\Delta(G_{n})}{\sqrt{\Delta(G_{n})\log\Delta(G_{n})}},$

then $\lim_{n\to\infty}\Phi(p,G_{n})=1$. However, in the $0$-statement
slightly stronger structural assumptions and more delicate counting arguments
are required to further bound the width in this manner. Since some of these
structural assumptions do not hold in all of our examples (for example in
$M_{n}$ and $O_{n}$), and also for ease of presentation, we have given a
simpler exposition which just determines the first two terms in the expansion
of the critical probability. However, these extra assumptions and counting
arguments will be necessary in order to determine the threshold for the
permutahedron, and so the details of how to recover the stronger bound on the
width of the critical window will be covered in [21].

In the light of the dependence of our bounds on the minimum and maximum
degree, it is also interesting to ask what can happen when the host graph is
irregular. Whilst Theorem 1.4 implies that the critical window is still
bounded away from $\frac{1}{2}$ for graphs in $\mathcal{H}$, it is not clear
if the second term in the expansion of the critical probability is controlled
by the maximum degree, the minimum degree or the average degree of the graph
(if by any of them). In the particular case where $G$ is a product of many
_stars_ , we will show in a forthcoming paper [21] that the upper bound in
Theorem 1.4 is in fact tight, but it is not clear if this behaviour is
universal even in irregular product graphs.

It is perhaps also interesting to consider how the process evolves with other
non-constant infection thresholds. For example, if we take $r(v)=\alpha\cdot
d(v)$ for some constant $\alpha>0$, then the arguments in this paper (with the
application of Hoeffding’s inequality in (39) replaced by an application of
[45, Theorem 2.7]) show that for $d$-regular graphs in $\mathcal{H}$ the
$r$-neighbour bootstrap percolation process undergoes a similar transition
around

$p=\alpha-\sqrt{\alpha(1-\alpha)}\cdot\sqrt{\frac{\log d}{d}},$

and likely this will remain true when $\alpha$ is a very slowly shrinking
function of $d$. It would be interesting to consider what happens for smaller
$\alpha$, for example $d^{-\beta}$ for some $0<\beta<1$.

######  Question 9.2.

Let $G$ be an $d$-regular high-dimensional graph and consider the
$r$-neighbour bootstrap percolation process where $r=\sqrt{d}$. What can we
say about the location and width of the critical window?

In another direction, for small constant values of the infection threshold
$r$, the average case behaviour of the $r$-neighbour bootstrap percolation
process on the hypercube has also been considered, where in particular for
$r=2$ a threshold for percolation was determined by Balogh and Bollobás [6]
and a sharper threshold was shown by Balogh, Bollobás and Morris [9]. It would
be interesting to know if a corresponding threshold could be determined in
other high-dimensional graphs, see [41] for an analysis of bootstrap
percolation on Hamming graphs. Moreover, even for the hypercube $Q_{n}$, very
little is known about the typical behaviour of the process for $r\geqslant 3$,
see for example [9, Conjecture 6.3].

The majority bootstrap percolation process has also been studied in the
binomial random graph $G(m,q)$ [34, 52]. Perhaps surprisingly, in [34] it is
shown that if the edge probability $q$ is close to the connectivity threshold,
then the first two terms in the expansion of the critical probability for
$G(m,q)$ agree with those given by Bollobás, Balogh and Morris for the
hypercube $Q_{n}$ in Theorem 1.3, taking $n=(m-1)q$ to be the expected degree
of a vertex. The authors conjecture that this behaviour is in fact universal
to all approximately regular graphs with a similar density to the hypercube
and sufficiently strong expansion properties. In this context, it would be
interesting to study the majority bootstrap percolation process on random
subgraphs of high-dimensional graphs, in particular of the hypercube, above
the connectivity threshold.

######  Question 9.3.

Let $(Q_{n})_{q}$ denote a random subgraph of the hypercube $Q_{n}$, in which
each edge of $Q_{n}$ is retained independently with probability $q\in(0,1)$.
What is the critical probability for majority bootstrap percolation on
$(Q_{n})_{q}$ for $q>\frac{1}{2}$?

### Acknowledgements

The authors were supported in part by the Austrian Science Fund (FWF)
[10.55776/{DOC183, F1002, P36131, W1230}]. 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] 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
  * [2] M. Ajtai, J. Komlós and E. Szemerédi  “Largest random component of a $k$-cube”  In _Combinatorica_ 2.1, 1982, pp. 1–7  DOI: 10.1007/BF02579276
  * [3] N. Alon and J.. Spencer  “The probabilistic method”, Wiley Series in Discrete Mathematics and Optimization  John Wiley & Sons, Inc., Hoboken, NJ, 2016, pp. xiv+375
  * [4] A. El-Amawy and S. Latifi  “Properties and performance of folded hypercubes”  In _IEEE Transactions on Parallel & Distributed Systems_ 2.01 IEEE Computer Society, 1991, pp. 31–42
  * [5] H. Amini  “Bootstrap percolation in living neural networks”  In _J. Stat. Phys._ 141.3, 2010, pp. 459–475  DOI: 10.1007/s10955-010-0056-z
  * [6] J. Balogh and B. 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
  * [7] J. Balogh and B. Bollobás  “Sharp thresholds in bootstrap percolation”  In _Physica A: Stat. Mechanics Applications_ 326.3, 2003, pp. 305–312  DOI: https://doi.org/10.1016/S0378-4371(03)00364-9
  * [8] J. Balogh, B. Bollobás, H. Duminil-Copin and R. 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
  * [9] J. Balogh, B. Bollobás and R. Morris  “Bootstrap percolation in high dimensions”  In _Combin. Probab. Comput._ 19.5-6, 2010, pp. 643–692  DOI: 10.1017/S0963548310000271
  * [10] J. Balogh, B. Bollobás and R. Morris  “Bootstrap percolation in three dimensions”  In _Ann. Probab._ 37.4, 2009, pp. 1329–1380  DOI: 10.1214/08-AOP433
  * [11] J. Balogh, B. Bollobás and R. Morris  “Majority bootstrap percolation on the hypercube”  In _Combin. Probab. Comput._ 18.1-2, 2009, pp. 17–51  DOI: 10.1017/S0963548308009322
  * [12] J. Balogh, B. Bollobás and B.. Narayanan  “Transference for the Erdős-Ko-Rado theorem” Id/No e23  In _Forum Math. Sigma_ 3, 2015, pp. 18  DOI: 10.1017/fms.2015.21
  * [13] J. Balogh, Y. Peres and G. Pete  “Bootstrap percolation on infinite trees and non-amenable groups”  In _Combin. Probab. Comput._ 15.5, 2006, pp. 715–730  DOI: 10.1017/S0963548306007619
  * [14] M. Bidgoli, A. Mohammadian and B. Tayfeh-Rezaie  “Percolating sets in bootstrap percolation on the Hamming graphs and triangular graphs”  In _European J. Combin._ 92, 2021, pp. Paper No. 10325616  DOI: 10.1016/j.ejc.2020.103256
  * [15] N. Biggs  “Some odd graph theory”, Combinatorial mathematics, 2nd int. Conf., New York 1978, Ann. New York Acad. Sci. 319, 71-81 (1979)., 1979
  * [16] B. Bollobás  “Weakly $k$-saturated graphs”  In _Beiträge zur Graphentheorie (Kolloquium, Manebach, 1967)_ B. G. Teubner Verlagsgesellschaft, Leipzig, 1968, pp. 25–31
  * [17] A.. Brouwer, A.. Cohen and A. Neumaier  “Distance-regular graphs” 18, Ergeb. Math. Grenzgeb., 3. Folge  Berlin etc.: Springer-Verlag, 1989
  * [18] R. Cerf and E… Cirillo  “Finite size scaling in three-dimensional bootstrap percolation”  In _Ann. Probab._ 27.4, 1999, pp. 1837–1850  DOI: 10.1214/aop/1022677550
  * [19] 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
  * [20] J. Chalupa, P.. Leath and G.. Reich  “Bootstrap percolation on a Bethe lattice”  In _J. Phys. C: Solid State Physics_ 12.1, 1979, pp. L31  DOI: 10.1088/0022-3719/12/1/008
  * [21] M Collares, J. Erde, A Geisler and M. Kang  “Majority bootstrap percolation on the permutahedron and other high-dimensional graphs” In preparation
  * [22] Maurício Collares, Joseph Doolittle and Joshua Erde  “The evolution of the permutahedron”, 2024  arXiv:2404.17260 [math.CO]
  * [23] S. Diskin and M. Krivelevich  “Supercritical site percolation on the hypercube: small components are small”  In _Comb. Probab. Comput._ 32.3, 2023, pp. 422–427  DOI: 10.1017/S0963548322000323
  * [24] Sahar Diskin, Joshua Erde, Mihyun Kang and Michael Krivelevich  “Percolation on high-dimensional product graphs”, 2022  arXiv:2209.03722 [math.CO]
  * [25] P. Dukes, J. Noel and A. 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
  * [26] P. Erdős and J. Spencer  “Evolution of the $n$-cube”  In _Comput. Math. Appl._ 5.1, 1979, pp. 33–39  DOI: 10.1016/0898-1221(81)90137-1
  * [27] L.. Fontes, R.. Schonmann and V. Sidoravicius  “Stretched exponential fixation in stochastic Ising models at zero temperature”  In _Comm. Math. Phys._ 228.3, 2002, pp. 495–518  DOI: 10.1007/s002200200658
  * [28] N. Fountoulakis, M. Kang, C. Koch and T. Makai  “A phase transition regarding the evolution of bootstrap processes in inhomogeneous random graphs”  In _Ann. Appl. Probab._ 28.2, 2018, pp. 990–1051  DOI: 10.1214/17-AAP1324
  * [29] E. Friedgut  “Every monotone graph property has a sharp threshold”  In _Proc. Amer. Math. Soc._ 124, 1999  DOI: 10.1090/S0002-9939-96-03732-X
  * [30] M. Granovetter  “Threshold models of collective behavior”  In _Amer. J. Sociology_ 83.6, 1978, pp. 1420–1443  DOI: 10.1086/226707
  * [31] J. Hardy, Y. Pomeau and O. Pazzis  “Time evolution of a two-dimensional classical lattice system”  In _Phys. Rev. Lett._ 31 American Physical Society, 1973, pp. 276–279  DOI: 10.1103/PhysRevLett.31.276
  * [32] M. Heydenreich and R. Hofstad  “Random graph asymptotics on high-dimensional tori”  In _Comm. Math. Phys._ 270.2, 2007, pp. 335–358  DOI: 10.1007/s00220-006-0152-8
  * [33] W. Hoeffding  “Probability inequalities for sums of bounded random variables”  In _J. Amer. Statist. Assoc._ 58, 1963, pp. 13–30  URL: http://links.jstor.org/sici?sici=0162-1459(196303)58:301%3C13:PIFSOB%3E2.0.CO;2-D&origin=MSN
  * [34] C. Holmgren, T. Juškevičius and N. Kettle  “Majority bootstrap percolation on $G(n,p)$”  In _Electron. J. Comb._ 24.1, 2017, pp. research paper p1.132  URL: www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p1
  * [35] A.. 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
  * [36] E. Ising  “Beitrag zur Theorie des Ferromagnetismus”  In _Zeitschrift für Physik_ 31, 1925, pp. 253–258  DOI: https://doi.org/10.1007/BF02980577
  * [37] Emmanuel Jacob et al.  “Interacting particle systems”  In _ESAIM, Proc. Surv._ 60, 2017, pp. 246–265  DOI: 10.1051/proc/201760246
  * [38] S. Janson, T Łuczak, T. Turova and T. 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
  * [39] R. Kaas and J.. Buhrman  “Mean, median and mode in binomial distributions”  In _Statist. Neerlandica_ 34.1, 1980, pp. 13–18  DOI: 10.1111/j.1467-9574.1980.tb00681.x
  * [40] M. Kang and T. 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
  * [41] Mihyun Kang, Michael Missethan and Dominik Schmid  “Bootstrap percolation on the high-dimensional Hamming graph”, 2024  arXiv:2406.13341 [math.CO]
  * [42] H.. Kierstead and W.. Trotter  “Explicit matchings in the middle levels of the Boolean lattice”  In _Order_ 5.2, 1988, pp. 163–171  DOI: 10.1007/BF00337621
  * [43] S. Klavžar, J. Koolen and H.. Mulder  “Graphs which locally mirror the hypercube structure”  In _Inf. Process. Lett._ 71.2, 1999, pp. 87–90  DOI: 10.1016/S0020-0190(99)00089-7
  * [44] L. Lichev  “The giant component after percolation of product graphs”  In _J. Graph Theory_ 99.4, 2022, pp. 651–670  DOI: 10.1002/jgt.22758
  * [45] Colin McDiarmid  “Concentration”  In _Probabilistic methods for algorithmic discrete mathematics_ Berlin: Springer, 1998, pp. 195–248
  * [46] R. Morris  “Bootstrap percolation, and other automata”  In _European J. Combin._ 66, 2017, pp. 250–263  DOI: 10.1016/j.ejc.2017.06.024
  * [47] R. Morris  “Monotone cellular automata”  In _Surveys in combinatorics 2017_ 440, London Math. Soc. Lecture Note Ser.  Cambridge Univ. Press, Cambridge, 2017, pp. 312–371
  * [48] N. Morrison and J.. 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
  * [49] T. Mütze  “Proof of the middle levels conjecture”  In _Proc. Lond. Math. Soc. (3)_ 112.4, 2016, pp. 677–713  DOI: 10.1112/plms/pdw004
  * [50] R.. 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
  * [51] Joel Spencer and Laura Florescu  “Asymptopia” 71, Stud. Math. Libr.  Providence, RI: American Mathematical Society (AMS), 2014
  * [52] S.. Stefánsson and T. Vallier  “Majority bootstrap percolation on the random graph ${G}(n,p)$”, 2015  arXiv:1503.07029 [math.PR]