# Bootstrap Percolation on the Binomial Random $k$-uniform Hypergraph

Mihyun Kang<EMAIL_ADDRESS>Institute of Discrete Mathematics
Graz University of Technology
8010 Graz, Austria  ,  Christoph Koch<EMAIL_ADDRESS>Institute of
Discrete Mathematics
Graz University of Technology
8010 Graz, Austria  and  Tamás Makai<EMAIL_ADDRESS>Department of
Mathematics
LMU Munich
80333 Munich, Germany

###### Abstract.

We investigate the behaviour of $r$-neighbourhood bootstrap percolation on the
binomial $k$-uniform random hypergraph $H_{k}(n,p)$ for given integers $k\geq
2$ and $r\geq 2$. In $r$-neighbourhood bootstrap percolation, infection
spreads through the hypergraph, starting from a set of initially infected
vertices, and in each subsequent step of the process every vertex with at
least $r$ infected neighbours becomes infected. For our analysis the set of
initially infected vertices is chosen uniformly at random from all sets of
given size. In the regime $n^{-1}\ll n^{k-2}p\ll n^{-1/r}$ we establish a
threshold such that if the number of initially infected vertices remains below
the threshold, then with high probability only a few additional vertices
become infected, while if the number of initially infected vertices exceeds
the threshold then with high probability almost every vertex becomes infected.
In fact we show that the probability of failure decreases exponentially.

##  1\. Introduction and main result

The $r$-neighbourhood bootstrap percolation process, which we refer to as
$r$-bootstrap percolation from this point on, was introduced by Chalupa,
Leath, and Reich [18] in the context of magnetic disordered systems. Since
then $r$-bootstrap percolation and its extensions have been used to describe
several complex propogation phenomena: from neuronal activity [4, 23] to the
dynamics of the Ising model at zero temperature [27].

In $r$-bootstrap percolation infection spreads over the vertices of a graph,
step by step following a deterministic rule. Starting from a set of initially
infected vertices, in each subsequent step every uninfected vertex, which has
at least $r$ infected neighbours, becomes infected. All other vertices remain
uninfected. Once a vertex has become infected, it remains infected forever.

Kang, Koch and Makai [33] introduced an extension of $r$-bootstrap percolation
to hypergraphs. Starting from a set of initially infected vertices in every
subsequent step every uninfected vertex becomes infected if it has at least
$r$ infected neighbours within the hypergraph, that is, there are at least $r$
infected vertices within the set of hyperedges containing the uninfected
vertex. (We note that this definition generalises $r$-bootstrap percolation to
the hypergraph setting in a weak sense, and a generalisation in a strong sense
will be discussed in Section 1.2.)

When considering $r$-bootstrap percolation the key question is the relation
between the set of initially infected vertices and the set of vertices
infected by the end of the process. Janson, Łuczak, Turova, and Vallier [32,
Theorem 3.1] analysed $r$-bootstrap percolation on the binomial random graph
$G(n,p)$ where every edge appears independently with probability $p$ and the
set of initially infected vertices, denoted by $A(0)$, is chosen uniformly at
random from all vertex sets of size $a$. They showed, among others, that for
$r\geq 2$ and $n^{-1}\ll p\ll n^{-1/r}$ there is a phase transition with
threshold $(1-1/r)\left(\tfrac{(r-1)!}{np^{r}}\right)^{1/(r-1)}$ in terms of
the number of initially infected vertices. In [34], this result was
strengthened by providing an exponential bound on the error probability. More
precisely, we have the following result on the size of $A_{f}$, the set of
vertices which become infected during the percolation process.

######  Theorem 1 ([32, 34]).

Given an integer $r\geq 2$, consider $r$-bootstrap percolation on $G(n,p)$
when $n^{-1}\ll p\ll n^{-1/r}$. Assume that the initial infection set is
chosen uniformly at random from the family of all sets of vertices of size
$a=a(n)$. Then for any fixed $\varepsilon>0$, with probability at least
$1-\exp\left(-\Omega\left((np^{r})^{-1/(r-1)}\right)\right)$, the following
hold.

  1. $(i)$

If $a\leq(1-\varepsilon)(1-1/r)\left(\tfrac{(r-1)!}{np^{r}}\right)^{1/(r-1)}$,
then $|A_{f}|=O\left(\left(\tfrac{1}{np^{r}}\right)^{1/(r-1)}\right)$.

  2. $(ii)$

If $a\geq(1+\varepsilon)(1-1/r)\left(\tfrac{(r-1)!}{np^{r}}\right)^{1/(r-1)}$,
then $|A_{f}|=(1-o(1))\,n$.

In this paper we generalise this result for the binomial random $k$-uniform
hypergraph $H_{k}(n,p)$, where every hyperedge (which is a $k$-element subset
of the vertex set $[n]:=\\{1,\ldots,n\\}$) is present independently with
probability $p$. In this setting, unlike the graph case, the infection of two
different vertices is no longer independent, since hyperedges may contain
multiple uninfected vertices. The major challenge lies in understanding these
dependencies and analysing their impact on the infection process.

###  1.1. Main result

Throughout the paper, for integers $k\geq 2$ and $r\geq 2$ we set

$\eta:=\eta(k,r)=\begin{cases}1&\mbox{if }r\geq 3,\\\ 2k-3&\mbox{if
}r=2,\end{cases}$ (1)

and define

$a^{*}:=a^{*}(k,r,n,p)=\left(\frac{(r-1)!}{\eta
n\left(\binom{n}{k-2}p\right)^{r}}\right)^{1/(r-1)}.$ (2)

In addition, we set

$a_{c}:=a_{c}(k,r,n,p)=\left(1-\frac{1}{r}\right)a^{*}.$ (3)

######  Theorem 2.

Given integers $k\geq 2$ and $r\geq 2$, consider $r$-bootstrap percolation on
$H_{k}(n,p)$ when $n^{-1}\ll n^{k-2}p\ll n^{-1/r}$. Assume the initial
infection set is chosen uniformly at random from the family of all sets of
vertices of size $a=a(n)$. Then for any fixed $\varepsilon>0$, with
probability $1-\exp(-\Omega(a^{*}))$ the following hold.

  1. $(i)$

If $a\leq(1-\varepsilon)a_{c}$, then $|A_{f}|\leq a^{*}$.

  2. $(ii)$

If $a\geq(1+\varepsilon)a_{c}$, then $|A_{f}|=(1-o(1))\,n$.

Theorem 2 shows in particular that there is a phase transition with respect to
the behaviour of $r$-bootstrap percolation when the number of initially
infected vertices reaches $a_{c}$. If the number of initially infected
vertices remains below the threshold $a_{c}$, then only a few additional
vertices become infected. On the other hand, if the number of initially
infected vertices is larger than the threshold, then almost every vertex
becomes infected by the end of the percolation process.

###  1.2. Related results

Recall that the key question concerning $r$-bootstrap percolation is to
establish the behaviour of the final infection set with respect to the set of
initially infected vertices. More precisely the typical questions asked are:
when does a random subset lead to (almost) every vertex becoming infected,
what is the size of the smallest subset which leads to (almost) every vertex
becoming infected, and the running time of the process. These questions have
been investigated over a wide range of graph classes. Various deterministic
graphs have been considered such as trees [13, 26], lattices [2, 10, 11, 17,
30], hypercubes [9] and expanders [19]. Several random graph models have also
been investigated, including the binomial random graph [7, 8, 25, 32, 34, 40,
41], the Chung-Lu model [5, 6, 28], preferential attachment graphs [1] and
many others [3, 14, 16, 21, 24, 35].

Less is known when the underlying structure for $r$-bootstrap percolation is a
hypergraph. Recently Cooley and Zalla [20] analysed the high-order
generalisation of $r$-bootstrap percolation in complete $k$-uniform
hypergraphs.

A generalisation of $r$-bootstrap percolation to hypergraphs in the strong
sense can also be defined. Again starting from a set of infected vertices, in
each subsequent step every uninfected vertex $v$ becomes infected if it is
contained in at least $r$ hyperedges, where every vertex other than $v$ is
infected. When $r=1$ this model was introduced, under the name of hypergraph
bootstrap percolation by Balogh, Bollobás, Morris and Riordan [12]. In
addition to 1-boostrap percolation, hypergraph bootstrap percolation
generalises a second bootstrap process called graph bootstrap percolation,
which was introduced by Bolobás [15] under the name weak saturation in 1968.
Graph bootstrap percolation acts on the edge set of a graph. More precisely,
for a given graph $F$, in each step of the process every edge is added which
is the last edge required to create a new copy of $F$. The connection between
the above two percolation processes can be observed, when the edges in the
graph correspond to vertices in the hypergraph and the hyperedges correspond
to the edge sets in copies of $F$.

Graph bootstrap percolation, and consequently hypergraph boostrap percolation,
have received significant attention: see e.g., [7, 29, 36, 38] and the
references within.

###  1.3. Heuristics for the percolation threshold

In the remainder of the paper we assume that $k,r\in\mathbb{N}_{\geq 2}$ are
given and $n\in\mathbb{N},p\in(0,1)$ satisfy

$n^{-1}\ll n^{k-2}p\ll n^{-1/r}.$

We call a $k$-element subset of $[n]$ simply a $k$-set.

There is a natural heuristic argument for the evolution of the number of
infected vertices over time, which leads to the percolation threshold $a_{c}$
as in (3).

Recall that $A(0)$ denotes the set of initially infected vertices. For each
$t\in\mathbb{N}$ we denote by $A(t)$ the set of vertices infected by the end
of step $t$. Our heuristic begins with an assumption that the evolution of
$A(t)$ would be well-approximated by a smooth function $\varphi$, whose
behaviour characterises the existence of a _bottleneck_ in the process. We
provide a heuristic suggesting both what $\varphi$ should be and why this
leads to the choice of $a^{*}$ and the percolation threshold $a_{c}$. For
simplicity we focus on the case $r\geq 3$. In step $t+1\in\mathbb{N}$, a
typical vertex becomes infected due to being contained in exactly $r$
hyperedges where each of these hyperedges contains precisely one (distinct)
vertex from $A(t)$ and in addition at least one of these hyperedges contains a
vertex in $A(t)\setminus A(t-1)$. Thus, at least heuristically speaking, the
approximation

$\displaystyle\mathbb{E}\left[|A(t+1)|\left|\right.A(t),\ldots,A(0)\right]$
$\displaystyle\approx|A(t)|+n\sum_{i=1}^{r}\frac{(|A(t)|-|A(t-1)|)^{i}|A(t-1)|^{r-i}}{i!(r-i)!}\left(\binom{n}{k-2}p\right)^{r}$

should be valid as long as only a small fraction of the vertices are infected.
In fact, the right-hand side simplifies to
$|A(t)|+\frac{|A(t)|^{r}-|A(t-1)|^{r}}{r!}n\left(\binom{n}{k-2}p\right)^{r}$.
Iterating yields a telescoping sum and we obtain

$\mathbb{E}\left[|A(t+1)|\left|\right.A(t),\ldots,A(0)\right]\approx|A(0)|+\frac{|A(t)|^{r}}{r!}n\left(\binom{n}{k-2}p\right)^{r},$
(4)

where we used $A(-1):=\emptyset$. Assuming further that $|A(t)|$ will be well-
approximated by its mean we obtain the forward difference equation

$|A(\lfloor(x+1/T)T\rfloor)|-|A(\lfloor xT\rfloor)|\approx\frac{|A(\lfloor
xT\rfloor)|^{r}}{r!}n\left(\binom{n}{k-2}p\right)^{r}-|A(\lfloor
xT\rfloor)|+|A(0)|,$ (5)

where we have rescaled time as $t=\lfloor xT\rfloor$ for some (arbitrary)
$T=T(n)\gg 1$. Now recall that the $r$-bootstrap percolation process stops if
and only if $|A(\lfloor(x+1/T)T\rfloor)|=|A(\lfloor xT\rfloor)|$, in other
words, when the forward difference vanishes. Rescaling by setting
$\alpha(x):=|A(\lfloor
xT\rfloor)|\left(n\left[\binom{n}{k-2}p\right]^{r}\right)^{\frac{1}{r-1}}$,
from (5) we obtain a simpler form

$\alpha(x+1/T)-\alpha(x)\approx\frac{\alpha(x)^{r}}{r!}-\alpha(x)+\alpha(0).$
(6)

Now we observe that if $\alpha$ were to follow a smooth trajectory
$\varphi\colon[0,\infty)\to\mathbb{R}$, i.e., $\alpha(x)\approx\varphi(x)$,
its derivative $g^{\prime}$ should obey
$\varphi^{\prime}(x)\approx\alpha(x+1/T)-\alpha(x)$ and thus $\varphi$ should
satisfy the following differential equation

$\varphi^{\prime}(x)=\frac{\varphi(x)^{r}}{r!}-\varphi(x)+\varphi(0),$ (7)

where

$\varphi(0)=|A(0)|\left(n\left[\binom{n}{k-2}p\right]^{r}\right)^{\frac{1}{r-1}}.$
(8)

As mentioned before the process stops, when $\varphi^{\prime}(x)=0$ and in the
following we will examine for which values of $\varphi(0)$ does
$\varphi^{\prime}(x)$ have a non-negative root.

In order to achieve this we will examine whether the process has a bottleneck,
to be characterised by an inflection point, which would translate to an
extremal point of $\varphi$ satisfying $\varphi^{\prime\prime}(x_{c})=0$. By
differentiating $\varphi^{\prime}(x)$ once more, we obtain

$\varphi^{\prime\prime}(x)=\left(\frac{\varphi(x)^{r-1}}{(r-1)!}-1\right)\varphi^{\prime}(x).$

Recalling our assumption that $\alpha(x)\approx\varphi(x)$ and the fact that
$\alpha(\cdot)$ is positive and non-decreasing, we would also assume
$\varphi^{\prime}(x)\geq 0$. In addition we expect the process to stop if
$\varphi^{\prime}(x)=0$, so we are only interested in the behaviour of the
function as long as $\varphi^{\prime}(x)>0$. Therefore the bottleneck point
should be defined as the earliest point in time such that
$\frac{\varphi(x)^{r-1}}{(r-1)!}-1=0$, i.e.,

$x_{c}:=\inf\left\\{x\geq
0\colon\varphi(x)=\left[(r-1)!\right]^{1/(r-1)}\right\\}.$

As $r$-bootstrap percolation is monotone in the number of initially infected
vertices, intuitively the threshold for almost every vertex becoming infected
should be when the process stops right as it reaches the bottleneck. That is,

$\frac{\varphi(x_{c})^{r}}{r!}-\varphi(x_{c})+\varphi(0)=0.$

As we are assuming the bottleneck exists, that is, $x_{c}<\infty$, a simple
calculation implies that this occurs when

$\varphi(0)=\varphi_{c}:=\left(1-\frac{1}{r}\right)\left[(r-1)!\right]^{1/(r-1)}.$

In addition, the above implies that, if $\varphi(0)\leq\varphi_{c}$ in (7)
then $\varphi^{\prime}(x)$ has at least one non-negative root, while if
$\varphi(0)>\varphi_{c}$ no such root exists. Using (8), ultimately the above
indicates a threshold for $r$-bootstrap percolation at

$a_{c}=\left(1-\frac{1}{r}\right)\left(\frac{(r-1)!}{n\left(\binom{n}{k-2}p\right)^{r}}\right)^{1/(r-1)},$

matching the result from (3).

###  1.4. Proof outline

When the number of infected vertices is small, that is, $o((n^{k-2}p)^{-1})$,
typically infection occurs when $r$ hyperedges intersect in exactly one
uninfected vertex and each of these hyperedges contains exactly one infected
vertex. For any $r\geq 2$ this implies that the vertex in the intersection of
the hyperedges becomes infected. However, if $r=2$, then in the following step
both of these hyperedges will contain 2 infected vertices and thus every other
vertex in these hyperedges will be infected as well, leading to $2k-3$
infected vertices in total instead of one and to the definition of $\eta$ in
(1).

In the subcritical regime, when $a<a_{c}$, our aim is to show that at most
$a^{*}$ vertices become infected. We start in Section 3 by modifying the
process, in a manner that leads to more infected vertices (Lemma 17), but is
easier to analyse.

In Section 4 we analyse the behaviour of this modified process. The FKG
inequality (Theorem 6) implies that the number of vertices infected in a step
is stochastically dominated by the sum of weighted Bernoulli random variables
(Corollary 21). Next we provide a trajectory, which resembles the solution of
the differential equation in (7), and prove that it also has a maximum (Claim
24). As long as the expected number of vertices infected in each step is
large, which occurs in the early stages of the process, we analyse the process
step by step. In every step we show that, provided the number of infected
vertices remained below the trajectory in each of the previous steps this will
also hold in the following step with sufficiently large probability (Lemma
26).

When the number of vertices infected in a single step is small this strategy
no longer provides sufficiently tight probability bounds and we establish an
upper bound on the total number of vertices infected after this point. Note
that any vertex which becomes infected in step $t+1$ must have a neighbour
which became infected in step $t$. Based on this we can construct a forest, by
selecting exactly one neighbouring vertex which was infected in the previous
step. This forest is generated by a branching process, where the number of
offspring for the individual vertices depends on the size of the previous
generations, that is, the previously infected vertices. Nevertheless, based on
the Dwass identity for Galton-Watson branching processes (Theorem 5) we show
that the total number of infected vertices remains small (Lemma 28).

In the supercritical regime, when $a>a_{c}$, we differentiate between the
vertices depending on the number of infected neighbours it has, more precisely
we consider the sets of vertices with at least $0,\ldots,r-1,r$ infected
neighbours. Then the set of infected vertices is the union of the set of
initially infected vertices and the set of vertices with at least $r$ infected
neighbours. Similarly to the subcritical regime we establish a trajectory for
the number of vertices in each of these parts, where the trajectory for the
number of infected vertices resembles (7). As a first step we show that until
$(n^{k-2}p)^{-1}$ vertices become infected the number of vertices in each part
remain above their respective trajectories with sufficiently large
probability. Note that the number of additional infected neighbours the
individual vertices acquire in a given step are dependent random variables. We
adapt a Chernoff-type bound for dependent random variables (Lemma 4) to
establish the probability that the number of vertices in the individual parts
remain above their trajectories after every step (Lemma 36). The number of
infected vertices will eventually exceed $(n^{k-2}p)^{-1}$ (Lemma 33), at
which point our estimates break down. A slightly modified versions of the
concentration result (Lemma 37) and a martingale argument (Lemma 38) imply
that once the number of infected vertices reaches $(n^{k-2}p)^{-1}$ almost
every vertex becomes infected in the following two steps with sufficiently
high probability. These results are shown in Section 5.

##  2\. Preliminaries

The following concentration result of McDiarmid [37] will be used throughout
the paper.

######  Theorem 3.

[37, Theorem 2.7] Let $(X_{i})_{1\leq i\leq n})$ be a sequence of independent
random variables. Define $X:=\sum_{i=1}^{n}X_{i}$. If there exists an
$M\in\mathbb{R}^{+}$ such that for each $1\leq i\leq n$,
$X_{i}\leq\mathbb{E}[X_{i}]+M$, then for all $\vartheta\geq 0$ we have

$\mathbb{P}[X\geq\mathbb{E}[X]+\vartheta]\leq\exp\left(-\frac{\vartheta^{2}}{2\left(\mathrm{Var}(X)+M\vartheta/3\right)}\right).$

The above inequality holds for independent random variables. We can prove that
a similar bound also holds for dependent Bernoulli random variables satisfying
mild conditions, which strengthens an earlier result due to Panconesi and
Srinivasan [39].

######  Lemma 4.

For $1\leq i\leq n$ let $X_{i}$ be (not necessarily independent) Bernoulli
random variables. Assume that there exists a constant $\lambda>0$ and a set of
independent Bernoulli random variables $\widehat{X}_{i}$ for $1\leq i\leq n$
such that for every $I\subseteq[n]$ we have

$\mathbb{E}\left[\prod_{i\in
I}X_{i}\right]\leq\lambda\mathbb{E}\left[\prod_{i\in
I}\widehat{X}_{i}\right].$

Define $X:=\sum_{i=1}^{n}X_{i}$ and
$\widehat{X}:=\sum_{i=1}^{n}\widehat{X}_{i}$. Then, for all $\vartheta\geq 0$
we have

$\mathbb{P}[X\geq\mathbb{E}[\widehat{X}]+\vartheta]\leq\lambda\exp\left(-\frac{\vartheta^{2}}{2(\mathrm{Var}(\widehat{X})+\vartheta/3)}\right).$

The proof of this result can be found in Appendix A. The following result on
the total number of progeny in a branching process also plays an important
role.

######  Theorem 5 (Dwass Identity).

[22] For an arbitrary Galton-Watson process let $Z_{i}$ denote the number of
individuals in the $i$-th generation and let $Z:=\sum_{i=0}^{\infty}Z_{i}$.
Then, for all integers $m,\ell\geq 0$ we have

$\mathbb{P}[Z=m|Z_{0}=\ell]=\frac{\ell}{m}\mathbb{P}[Z_{1}=m-\ell|Z_{0}=m].$

We also apply the FKG inequality (see e.g., [31, Theorem 2.12]) several times
in our proofs. A hypergraph property is called _increasing_ if it is preserved
under the addition of hyperedges, and it is _decreasing_ if it is preserved
under the removal of hyperedges.

######  Theorem 6 (FKG inequality).

Let $A$ be an increasing hypergraph property and $B$ be a decreasing
hypergraph property. Denote by $\mathcal{A}$ and $\mathcal{B}$ the events
that, in the random $k$-uniform hypergraph where each hyperedge is selected
independently with some probability $p_{e}$ has property $A$ and $B$,
respectively. Then we have

$\mathbb{P}[\mathcal{A}\cap\mathcal{B}]\leq\mathbb{P}[\mathcal{A}]\mathbb{P}[\mathcal{B}].$

Finally we will need the well-known Azuma’s inequality (see e.g., [31, Theorem
2.25])

######  Theorem 7 (Azuma’s inequality).

Let $(M_{t})_{t\in\mathbb{N}_{0}}$ be a real-valued supermartingale and let
$N\in\mathbb{N}$. Suppose that $|M_{i}-M_{i-1}|\leq c_{i}$ for all $1\leq
i\leq N$. Then for all $\vartheta\geq 0$ we have

$\mathbb{P}[X_{N}-X_{0}\geq\vartheta]\leq\exp\left(-\frac{\vartheta^{2}}{2\sum_{i=1}^{N}c^{2}_{i}}\right).$

##  3\. Preliminaries for subcritical regime: the query-process

In Sections 3 and 4 we consider the subcritical case, when the initial number
of infected vertices is below $a_{c}$. More precisely, throughout these
sections we assume that a constant $0<\varepsilon<1$ is given and the size of
the initial infection set satisfies

$a:=|A(0)|=(1-\varepsilon)a_{c}.$

In order to simplify the analysis, we modify the process slightly, in such a
way that the modified process provides a superset of the set of vertices
infected in the original process (Section 3.1). We will refer to this modified
process as the query-process. The query-process queries collections of
$k$-sets, where we establish whether every $k$-set in a collection is a
hyperedge or not. Vertices become infected only if every hyperedge within a
collection is present.

We show that starting from the same infection set every vertex which is
infected via $r$-bootstrap percolation is also infected by the query-process
(Lemma 17). We also establish that the trajectory for the number of infected
vertices in the query-process remains below $a^{*}$ (Lemma 25).

The main advantage of the modification is that the probability whether every
hyperedge in a collection is present in the hypergraph is stochastically
dominated by a sequence of independent random variables, which depend only on
the hyperedge probability $p$ and the number of hyperedges in the collection
(Lemma 20) and thus the number of infected vertices is stochastically
dominated by the sum of weighted Bernoulli random variables (Lemma 21).
However, the number of queries depends on the history of the process, more
precisely it depends on the number of vertices infected in the previous step
and the total number of vertices infected until this step. Based on this we
can show that, as long as the number of infected vertices remains below a
certain trajectory in each of the previous steps and the expected number of
infected vertices is large enough, the number of infected vertices in the next
step will also remain below the trajectory (Lemma 26).

However, once the expected number of infected vertices becomes small, the
previous method no longer provides a sufficiently tight concentration. Note
that any vertex which becomes infected in step $t$ must have a neighbour which
became infected in step $t-1$. In fact, once the number of vertices infected
in a given step is sufficiently small compared to the total number of infected
vertices, a typical vertex will have exactly one such neighbour. Based on this
we can construct a forest, by connecting every infected vertex to exactly one
of its neighbours which was infected during the previous step. This forest is
generated by a process resembling a branching process, with the main
difference that the number of offspring depends on the size of the previous
generations. Using the Dwass identity (Theorem 5) we show that the number of
vertices which become infected during the remaining stages of the process is
small (Lemmas 28).

###  3.1. An upper coupling

We start by describing an upper coupling, which we call the query-process,
informally and thereby introducing terminologies that will be used later.

The query-process is also an infection process which starts out from a set of
initially infected vertices. At the beginning of each step we construct
multiple families, where each family is a collection of $k$-sets. The rest of
the step is divided into rounds, where in each round we _examine_ one
collection in the family. First it is decided whether the collection of
$k$-sets will be _queried_ based on the results of all the previous queries
made during the current and the previous steps. If a collection is not queried
then it is _discarded_. A query is _successful_ if every $k$-set in the
collection is a hyperedge. Every hyperedge within a successful query is called
_exposed_.

Now we turn to the construction of the family of collections of $k$-sets.
Essentially our aim is to infect every vertex which has at least $r$ infected
neighbours or this should happen if every collection in the family was
queried. In addition, certain collections are added to the family in order to
compensate for vertices with $r$ infected neighbours, which can be found in
discarded collections. The constructions are displayed in Figure 1.

We start by adding every collection of $r$ many $k$-sets which intersect in
exactly one vertex $v$ and each $k$-set contains exactly one previously
infected vertex. We call such a collection a star collection (e.g., the triple
of the dotted $k$-sets in Figure 1(a). Any successful query of a star
collection will result either in every vertex within the $k$-set becoming
infected (when $r=2$) or in the vertex $v$ becoming infected (when $r\geq 3$).
In a subcritical query-process almost every vertex infected in a given step is
contained in a star.

Now if a vertex has $r$ infected neighbours, which are not in a star
collection, then either two of the hyperedges overlap in more than one vertex
or a hyperedge contains multiple infected vertices.

We add every collection of pairs of $k$-sets which overlap in at least 2
uninfected vertices and both hyperedges contain at least one infected vertex.
Such a collection is called a widely-overlapping collection (e.g., the pair of
the dotted $k$-sets in Figure 1(b)). Successfully querying such a collection
leads to the infection of every vertex in both of the $k$-sets.

Afterwards we add every collection of $k$-sets containing at least two
infected vertices, which have not been exposed until this step. When
successfully queried, every vertex in the $k$-set becomes infected. Such a
collection is called a heavily-infected collection (e.g., the dotted $k$-set
in Figure 1(c)).

Finally we consider the hyperedges which have been exposed and still contain
uninfected vertices. Note that only hyperedges in stars when $r\geq 3$ can
contain uninfected vertices. We add every collection consisting of a $k$-set,
containing an infected vertex which intersects an exposed hyperedge in an
uninfected vertex. Such a collection is a so-called neutron-star-adjacent
(e.g., the dotted $k$-set in Figure 1(d)). If such a hyperedge is successfully
queried, then we infect every vertex in the hyperedge and also every vertex in
any exposed hyperedge it intersects in an uninfected vertex.

We will introduce a final criteria to reduce the number of times a collection
of $k$-sets is added to each family. Ideally every collection of $k$-sets
would be added to each family at most once, e.g., once a star is added it will
never be added again. Note that this still allows for collections to be added
to a different family, e.g., if a collection consisting of a single $k$-set
was added to the family of heavily-infected collections it can be later added
to the family of neutron-star-adjacent collections. Instead of working with
the complicated conditions required for each collection to be added at most
once, we use simpler, but weaker conditions, in the sense that the number of
times a collection is added is significantly reduced, but some collection of
$k$-sets can be added multiple times.

If none of the collections has been discarded, or equivalently if every
collection was queried, then every vertex which has at least $r$ infected
neighbours would become infected. However, in order to simplify the analysis
of the process, some of these collections will not be queried. Thus the query
process might contain uninfected vertices with $r$ infected neighbours. In
Lemma 17 we show that any such vertex will become infected at a later stage in
the process.

(a) a star collection (b) a widely-overlapping collection (c) a heavily-
infected collection (d) a neutron-star adjacent collection Figure 1.
Collections of the query process.
Filled circles represent infected vertices, empty circles represent uninfected
vertices.
Ovals represent exposed hyperedges, dashed ovals represent a collection of
$k$-sets.

###  3.2. The query-process

Consider a $k$-uniform hypergraph $H(V,E)$ with vertex set $V$ and hyperedge
set $E$. We proceed to define the query-process formally. To this end we need
further definitions and notation that will be used to describe and analyse the
query-process.

Let $B(0)$ denote the initial infection set in the query-process. For each
$t\in\mathbb{N}$, denote by

  * •

$B(t)$ the set of vertices infected by step $t$ (and its complement
$B(t)^{C}$);

  * •

$F(t)$ the set of hyperedges exposed before the end of step $t$.

When considering the $(t+1)$-st step we rely on the sets $B(t),B(t-1),F(t)$
and $F(t-1)$. Note that $F(0)=\emptyset$, and we extend the domain by setting
$B(-1)=\emptyset$, $F(-1)=\emptyset$ in order to cover the $t=0$ case.

Before providing the algorithm, we introduce the rigorous definitions for each
family of collections of $k$-sets associated with the query-process we saw in
Section 3.1: star collections, widely-overlapping collections, heavily-
infected collections and neutron-star-adjacent collections in Definitions 8,
9, 10 and 11.

First we deal with the family of star collections. Recall that a star consists
of $r$ many $k$-sets which intersect in exactly one vertex and each $k$-set
contains exactly one infected vertex. This is covered by the first three
conditions of Definition 8, the first two conditions focus on the structural
properties, while the third condition establishes that the required infected
vertices are present. The final condition is there to ensure that we only
consider collections, which have not been added as a star collection during a
previous step, which we achieve by insisting that one of the infected
vertices, within the $k$-sets of the star collection, was infected in the
previous step.

######  Definition 8 (Star collections; see Figure 1(a)).

For each $t\in\mathbb{N}$, let $\mathcal{S}(t+1)$ be the family of $r$ many
$k$-sets $\mathcal{C}=\\{K_{1},\ldots,K_{r}\\}$ satisfying the following
conditions:

  * •

there exists a unique uninfected vertex $v\in B(t)^{C}$ within the
intersection of the $k$-sets, that is, $\\{v\\}=\cap_{K\in\mathcal{C}}K$;

  * •

any two $k$-sets in $\mathcal{C}$ intersect in exactly one vertex;

  * •

every $K\in\mathcal{C}$ contains exactly one infected vertex, that is, $|K\cap
B(t)|=1$;

  * •

there exists a $K\in\mathcal{C}$, containing a vertex infected in the previous
step, that is, $K\cap B(t)\backslash B(t-1)\neq\emptyset$.

We call $\mathcal{S}(t+1)$ the family of star collections (at step $t+1$ of
the query-process).

We continue with the family of widely-overlapping collections. Similarly to
star collections the first condition describes the structural property, that
is, we have two hyperedges which overlap in at least 2 uninfected vertices,
the second condition establishes that every hyperedge contains at least one
infected vertex, while the last condition is there to reduce the number of
times a collection is considered (as a widely-overlapping collection), that
is, one of the $k$-sets must contain a vertex infected in the previous step.

######  Definition 9 (Widely-overlapping collections; see Figure 1(b)).

For each $t\in\mathbb{N}$, denote by $\mathcal{W}(t+1)$ the family of pairs
$\\{K_{1},K_{2}\\}$ of $k$-sets satisfying the following conditions:

  * •

$K_{1}$ and $K_{2}$ overlap in at least 2 uninfected vertices, that is,
$|K_{1}\cap K_{2}\cap B(t)^{C}|\geq 2$;

  * •

every $K\in\\{K_{1},K_{2}\\}\\}$ contains at least one infected vertex that
is, $|K\cap B(t)|\geq 1$;

  * •

$K_{1}$ or $K_{2}$ contains a vertex infected in the previous step, that is
$(K_{1}\cup K_{2})\cap(B(t)\backslash B(t-1))\neq\emptyset$.

We call $\mathcal{W}(t+1)$ the family of widely-overlapping collections (at
step $t+1$ of the query-process).

Next we consider the family of heavily-infected collections. This time there
are no structural conditions as the collections consist of exactly one
$k$-set. The first condition establishes that the $k$-set contains multiple
infected vertices, while the last condition is there to reduce the number of
times a collection is added to the family of heavily-infected collections,
that is, at least one of the vertices was infected in the previous step.

######  Definition 10 (Heavily-infected collections; see Figure 1(c)).

For each $t\in\mathbb{N}$, let $\mathcal{H}(t+1)$ be the family of $k$-sets
$K$ which satisfy the following conditions:

  * •

$K$ contains at least two infected vertices, that is, $|K\cap B(t)|\geq 2$;

  * •

$K$ contains at least one vertex infected in the previous step, that is,
$K\cap B(t)\backslash B(t-1)\neq\emptyset$.

We call $\mathcal{H}(t+1)$ the family of heavily-infected collections (at step
$t+1$ of the query-process).

Finally we consider the family of neutron-star-adjacent collections. In
contrast to the previous families, which only depend on the set of infected
vertices at the end of the last two steps, this also depends on the set of
exposed hyperedges at the end of the last two steps. Here we are considering
$k$-sets, which intersect an exposed hyperedge in an uninfected vertex. Unlike
the previous cases, in order to reduce the number of times such a $k$-set is
considered, we not only have to consider $k$-sets which contain vertices
infected during the previous step, but also $k$-sets which intersect
hyperedges exposed during the previous step.

######  Definition 11 (Neutron-star-adjacent collections; see Figure 1(d)).

For each $t\in\mathbb{N}$, let $\mathcal{N}_{1}(t+1)$ denote the family of
$k$-sets $K$ which satisfy the following conditions:

  * •

$K$ contains a vertex infected in the previous step, that is, $K\cap
B(t)\backslash B(t-1)\neq\emptyset$;

  * •

there exists an uninfected vertex $u\in B(t)^{C}$ such that $u\in K$ and $u$
is incident to an exposed hyperedge $e\in F(t)$.

In addition, let $\mathcal{N}_{2}(t+1)$ denote the family of $k$-sets $K$,
which satisfy the following conditions:

  * •

$K$ contains at least one infected vertex, that is, $K\cap B(t)\neq\emptyset$;

  * •

there exists an uninfected vertex $u\in B^{C}(t)$ such that $u\in K$ and $u$
is incident to a hyperedge $e$ exposed in the previous step, that is, $e\in
F(t)\backslash F(t-1)$.

Set $\mathcal{N}(t+1):=\mathcal{N}_{1}(t+1)\cup\mathcal{N}_{2}(t+1)$. We call
$\mathcal{N}(t+1)$ the family of neutron-star-adjacent collections (at step
$t+1$ of the query-process).

Having established the families, Algorithm 1 describes one step of the query-
process.

Input:
$H(V,E),\,\mathcal{S}(t+1),\mathcal{W}(t+1),\mathcal{H}(t+1),\mathcal{N}(t+1),B(t),F(t)$

1 $\Phi\leftarrow F(t)$

2 $B\leftarrow B(t)$

3 forall  _$K\in\mathcal{N}(t+1)$_ do

4 if  _$K$ is not a previously exposed hyperedge ($K\not\in\Phi$) _ then

5 if  _$K\in E$ _ then

6 The hyperedge $K$ is exposed ($\Phi\leftarrow\Phi\cup\\{K\\}$)

7 Infect every vertex in every hyperedge $e\in F(t)$ incident to an uninfected
vertex in $K$

8 Infect every vertex in $K$

9 ($B\leftarrow B\cup K\cup\\{u\in e:e\in F(t)\quad and\quad K\cap e\cap
B(t)^{C}\neq\emptyset\\}$)

10

11

12forall  _$K\in\mathcal{H}(t+1)$_ do

13 if  _$K$ is not a previously exposed hyperedge ($K\not\in\Phi$) _ then

14 if  _$K\in E$ _ then

15 The hyperedge $K$ is exposed ($\Phi\leftarrow\Phi\cup K$)

16 Infect every vertex in $K$ ($B\leftarrow B\cup K$)

17

18

19forall  _$\\{K_{1},K_{2}\\}\in\mathcal{W}(t+1)$_ do

20 if  _neither $K_{1}$ nor $K_{2}$ is an exposed hyperedge
($\\{K_{1},K_{2}\\}\cap\Phi=\emptyset$)_ then

21 if  _$\\{K_{1},K_{2}\\}\subseteq E$_ then

22 The hyperedges $K_{1}$ and $K_{2}$ are exposed
($\Phi\leftarrow\Phi\cup\\{K_{1},K_{2}\\}$)

23 Infect every vertex in $K_{1}$ and $K_{2}$ ($B\leftarrow B\cup K_{1}\cup
K_{2}$)

24

25

26forall  _$\\{K_{1},\ldots,K_{r}\\}\in\mathcal{S}(t+1)$_ do

27 if  _none of the $k$-sets in $\\{K_{1},\ldots,K_{r}\\}$ has been previously
exposed ($\\{K_{1},\ldots,K_{r}\\}\cap\Phi=\emptyset$) _ then

28 if  _for every $e\in\Phi$ and $K\in\\{K_{1},\ldots,K_{r}\\}$ we have $e\cap
K\cap B(t)^{C}=\emptyset$ _ then

29 if  _$\\{K_{1},\ldots,K_{r}\\}\subseteq E$ _ then

30 The hyperedges in $\\{K_{1}\ldots,K_{r}\\}$ are exposed
($\Phi\leftarrow\Phi\cup\\{K_{1},\ldots,K_{r}\\}$ )

31 if  _$r=2$_ then

32 Infect every vertex in $K_{1}$ and $K_{2}$ ($B\leftarrow B\cup K_{1}\cup
K_{2}$)

33 else

34 Infect the vertex in the intersection of the $k$-sets ($B\leftarrow
B\cup\bigcap_{i=1}^{r}K_{i}$)

35

36

37

38

39$B(t+1)\leftarrow B$

40 $F(t+1)\leftarrow\Phi$

Output: $B(t+1),F(t+1)$

Algorithm 1 Query-process

As previously mentioned not every collection within the individual families is
queried. In particular if any of the conditions in lines 1, 1, 1, 1 or 1 fail,
for an element of the given family, then the collection is discarded.

###  3.3. Auxiliary results

In this section we discuss auxiliary results required to analyse the query-
process.

First we establish upper bounds on the sizes of the family $\mathcal{S}(t+1)$
of the star collections, the family $\mathcal{W}(t+1)$ of the widely-
overlapping collections, the family $\mathcal{H}(t+1)$of the heavily-infected
collections, and the family $\mathcal{N}(t+1)$ of the neutron-star adjacent
collections. Set

$N(t+1):=|\mathcal{N}(t+1)|,\quad H(t+1):=|\mathcal{H}(t+1)|,\quad
W(t+1):=|\mathcal{W}(t+1)|,\quad S(t+1):=|\mathcal{S}(t+1)|.$

A quick calculation establishes an upper bound on $S(t+1)$.

######  Observation 12.

We have

$S(t+1)\leq\frac{|B(t)|^{r}-|B(t-1)|^{r}}{r!}n\binom{n}{r-2}^{r}.$

Similarly we obtain an upper bound on $W(t+1)$.

######  Observation 13.

We have

$W(t+1)\leq|B(t)|(|B(t)|-|B(t-1)|)n^{2}\binom{n}{k-3}^{2}.$

Next we deduce an upper bound on $H(t+1)$.

######  Observation 14.

We have

$H(t+1)\leq|B(t)|(|B(t)|-|B(t-1)|)\binom{n}{k-2}.$

In order to give an upper bound on $N(t+1)$, we include here the following
estimate on the number of exposed hyperedges, which could be associated with a
neutron-star-adjacent collection.

######  Claim 15.

For every $t\geq 0$ the number of exposed hyperedges in $F(t)\setminus F(t-1)$
which still contain an uninfected vertex is at most $r|B(t)\setminus B(t-1)|$.

###### Proof.

By lines 1, 1, 1, 1, 1 and 1 in Algorithm 1 any exposed hyperedge which still
contains uninfected vertices must come from a star when $r\geq 3$. In addition
exposing a star, when $r\geq 3$ results in exactly one vertex becoming
infected. By Definition 8 and line 1 of Algorithm 1 each infected vertex is
responsible for at most $r$ such exposed hyperedges and the result follows. ∎

Finally we obtain an upper bound on $N(t+1)$.

######  Observation 16.

We have

$N(t+1)\leq 2kr(|B(t)|-|B(t-1)|)|B(t)|\binom{n}{k-2}.$

###### Proof.

Clearly

$N(t+1)\leq
k|B(t)|(|F(t)|-|F(t-1)|)\binom{n}{k-2}+k|F(t)|(|B(t)|-|B(t-1)|)\binom{n}{k-2}.$

The result then follows from Claim 15. ∎

###  3.4. Coupling $r$-boostrap percolation and the query-process

In this section we show that every vertex infected by $r$-boostrap percolation
is also infected by the query-process, assuming they run on the same
$k$-uniform hypergraph with the same initial infection set. Note that this is
not necessarily true for every step of the process, as the query-process may
contain uninfected vertices, which would have already been infected by
$r$-bootstrap percolation.

Roughly speaking the query-process focuses on adding the vertices infected
through star collections one at a time. Recall that a star collection consists
of $r$ hyperedges each containing exactly one infected vertex such that the
hyperedges overlap in exactly one vertex, which has to be uninfected. More
precisely these are considered as long as none of the hyperedges in the star
collection intersect or match any previously exposed hyperedges. Essentially
this means that we are excluding infections which result from hyperedges
containing multiple infected vertices, hyperedges overlapping in multiple
vertices or hyperedges which intersect an already exposed hyperedge. The
families of widely-overlapping, heavily-infected, and neutron-star-adjacent
collections are created in order to include the vertices which become infected
in such a manner as well. In the following lemma we provide a rigorous version
of this argument. Recall that $A_{f}$ denotes the set of vertices which become
infected during $r$-boostrap percolation. Similarly, let $B_{f}$ denote the
set of vertices which become infected during the query-process.

######  Lemma 17.

Given any (deterministic or random) hypergraph and a set of initially infected
vertices, every vertex infected by $r$-bootstrap percolation will also be
infected by the query-process, i.e.,

$A_{f}\subseteq B_{f}.$

###### Proof.

Assume for contradiction that $A_{f}\backslash B_{f}\neq\emptyset$. Select
$u\in A_{f}\backslash B_{f}$ such that $u$ becomes infected in step $s+1$,
that is, $u\in A(s+1)\backslash A(s)$ and $A(s)\subseteq B_{f}$. Note that
since $A(0)=B(0)\subseteq B_{f}$ such a vertex must exist. This means that
even though $u$ has at least $r$ infected neighbours in $B_{f}$, it remained
uninfected. Let $e_{1},\ldots,e_{\ell}$ be the set of hyperedges which contain
$u$ and at least one vertex in $A(s)$.

######  Claim 18.

For any $1\leq i\leq\ell$ and $t\geq 1$ we have
$e_{i}\not\in\mathcal{N}(t)\cup\mathcal{H}(t)$.

###### Proof.

Without loss of generality assume for contradiction that
$e_{1}\in\mathcal{N}(t)\cup\mathcal{H}(t)$ for some $t\geq 1$.

If $e_{1}$ has been successfully queried as a neutron-star-adjacent collection
or as a heavily-infected collection, then according to the lines 1 and 1 of
Algorithm 1 when $e_{1}\in\mathcal{N}(t)$ and lines 1 and 1 when
$e_{1}\in\mathcal{H}(t)$ the following conditions must hold: $e_{1}$ has not
been exposed by the time of the query and $e_{1}$ must be a hyperedge in the
hypergraph. In both of these cases, by lines 1 and 1 respectively, every
vertex in $e_{1}$ would become infected, a contradiction as $u\in e_{1}$
remains uninfected until the end of the process.

By assumption, $e_{1}\in E$, and thus we must have that the hyperedge $e_{1}$
was exposed before the query could occur. More precisely, it had to be exposed
during an earlier step, that is, $e_{1}\in F(t-1)$, as we start step $t$ by
querying the neutron-star-adjacent collections, which is followed by the
heavily-infected collections and in both cases exposing the hyperedge $e_{1}$
would result in every vertex within $e_{1}$, including $u$, becoming infected,
a contradiction.

When $r=2$ then lines 1,1,1,1 imply that every vertex within each exposed
hyperedge is infected, which implies that $u$ is also infected. This leads to
a contradiction and completes the proof of the $r=2$ case.

On the other hand, if $r\geq 3$, then the rule for infecting vertices within
star collections changes from infecting every vertex in the exposed hyperedges
(line 1) to infecting only one vertex (line 1) and thus $e_{1}$ must be in a
successfully queried collection of $r$ many $k$-sets
$\mathcal{C}\in\mathcal{S}(\tau)$, for some $\tau<t$.

Since $e_{1}$ is a $k$-set in $\mathcal{C}$ by Definition 8 it contains
exactly one infected vertex at the beginning of step $\tau$. Now
$\mathcal{C}\in\mathcal{S}(\tau)$ is successfully queried only if the
following conditions hold, no $k$-set $K\in\mathcal{C}$ has been exposed (line
1) or intersects an exposed hyperedge in an uninfected vertex (line 1). As
only vertices within exposed hyperedges can become infected, no additional
vertices within the $k$-sets in $\mathcal{C}$ are infected, until
$\mathcal{C}$ is queried. By line 1, only one vertex is infected, when
$\mathcal{C}$ is successfully queried, namely the vertex which is contained in
every $k$-set within $\mathcal{C}$. At this point $e_{1}$ will contain two
infected vertices, neither of which is $u$. In fact, this will hold until the
end of step $\tau$, as after this round only stars which share no uninfected
vertices with $e_{1}$ are queried (lines 1,1).

In the remainder of the proof we will show that $e_{1}$ is the only hyperedge
to contain a vertex in $B_{f}$ and an uninfected vertex in $e_{1}$. This in
turn implies, that the vertex $u$ has only two infected neighbours, leading to
a contradiction as by assumption it has $r\geq 3$ neighbours in $B_{f}$.

Assume for contradiction that there exists a hyperedge $\hat{e}$ containing at
least one vertex in $B_{f}$ and at least one uninfected vertex of $e_{1}$.
Note that $\hat{e}$ is a neutron-star-adjacent collection and would be
included either in $\mathcal{N}_{2}(\tau+1)$ or in $\mathcal{N}_{1}(\tau_{1})$
for some $\tau_{1}>\tau$. Denote by $\tau_{1}$ the first integer larger than
$\tau$ such that $\hat{e}\in\mathcal{N}(\tau_{1})$. Similarly as before, if
$\hat{e}$ were queried (line 1) as a neutron-star-adjacent collection, then
this query would be successful as $\hat{e}\subseteq E$ (line 1) and every
vertex of $e_{1}$, including $u$, would be infected (line 1). Since the family
of neutron-star-adjacent collections are the first to be considered in a given
step, there must exist a step $\tau^{\prime}<\tau_{1}$ such that $\hat{e}$ was
exposed in that step.

Recall that by the end of step $\tau$ no previously exposed hyperedge
intersects $e_{1}$ in an uninfected vertex, and thus $\hat{e}$ must have been
exposed between steps $\tau$ and $\tau_{1}$, that is,
$\tau<\tau^{\prime}<\tau_{1}$. Note that if $\hat{e}$ was exposed in step
$\tau^{\prime}$ it must contain a vertex which became infected in an earlier
step, $\tau^{\prime\prime}<\tau^{\prime}$. Now if
$\tau^{\prime\prime}\leq\tau$ then $\hat{e}\in\mathcal{N}(\tau+1)$ leading to
a contradiction as $\tau+1<\tau_{1}$. On the other hand if
$\tau^{\prime\prime}>\tau$ then $\hat{e}\in\mathcal{N}(\tau^{\prime\prime}+1)$
which is also a contradiction as
$\tau^{\prime\prime}+1\leq\tau^{\prime}<\tau_{1}$. ∎

######  Claim 19.

For any $1\leq i<j\leq\ell$ and $t\geq 1$ we have
$\\{e_{i},e_{j}\\}\not\in\mathcal{W}(t)$.

###### Proof.

Without loss of generality assume for contradiction that
$\\{e_{1},e_{2}\\}\in\mathcal{W}(t)$ for some $t\geq 1$. Similarly to the
family of neutron-star-adjacent collections and heavily-infected collections,
if neither of $\\{e_{1},e_{2}\\}$ was exposed before it was queried (line 1)
and $\\{e_{1},e_{2}\\}\subseteq E$, then by line 1 every vertex in
$e_{1},e_{2}$ will be infected. Clearly $e_{1},e_{2}\in E$ and thus at least
one of $e_{1}$ or $e_{2}$ must have been exposed earlier. In fact this can
only occur if $r\geq 3$ and there exists $\mathcal{C}\in\mathcal{S}(\tau)$ for
some $\tau\leq t$ such that $e_{1}\in\mathcal{C}$ or $e_{2}\in\mathcal{C}$, as
for every other family, every vertex within every exposed hyperedge becomes
infected (lines 1,1,1,1,1). Without loss of generality assume that
$e_{1}\in\mathcal{C}$.

By Definitions 8 and 9 we have $e_{2}\not\in\mathcal{C}$. Recall that $u$, a
vertex which remains uninfected throughout the process is found in both of the
hyperedges $e_{1},e_{2}$. Since $\mathcal{C}$ was successfully queried, by
line 1, the hyperedge $e_{2}$ has not been exposed before $\mathcal{C}$ was
queried, or during the remainder of step $\tau$. By Definition 9 the hyperedge
$e_{2}$ must contain a vertex other than $u$ which became infected in some
step $\tau^{\prime}<t$. If $\tau^{\prime}\leq\tau$, then
$e_{2}\in\mathcal{N}(\tau+1)$ otherwise
$e_{2}\in\mathcal{N}(\tau^{\prime}+1)$, by the definitions of
$\mathcal{N}_{1}(\tau+1)$ and $\mathcal{N}_{2}(\tau^{\prime}+1)$ in Definition
9. Now the only way $e_{2}$ is queried in a manner that leaves $u$, a vertex
of $e_{2}$, uninfected is, if $e_{2}$ has been exposed as part of a previously
successfully queried star collection. Recall that $e_{2}$ could not have been
exposed before the end of step $\tau$ and by line 1 it can not be part of an
exposed star collection during the later steps of the process. Therefore
$e_{2}$ will be successfully queried, in such a way that all of its vertices
become infected, leading to a contradiction. ∎

By Claim 18 none of the hyperedges $e_{1},\ldots,e_{\ell}$ can be contained in
$\mathcal{H}(t)$ for any $t\geq 1$, implying that each of these hyperedges
contains exactly one infected vertex in $B_{f}$. In addition by Claim 19 no
pair of hyperedges in $\\{e_{1},\ldots,e_{\ell}\\}$ was contained in
$\mathcal{W}(t)$ for any $t\geq 1$ and thus any pair of these hyperedges
intersect only in $u$ in $B_{f}^{C}$.

Therefore, as $u$ has $r$ infected neighbours in $A_{f}$ there must exist a
set $\mathcal{C}\subseteq\\{e_{1},\ldots,e_{\ell}\\}$, with $|\mathcal{C}|=r$
such that any pair of hyperedges in $\mathcal{C}$ intersect only in $u$. Now
$\mathcal{C}$ will be contained in the family $\mathcal{S}(t)$ for some $t\geq
1$. Let $\tau$ be the first time this holds and without loss of generality
assume that $\mathcal{C}=\\{e_{1},\ldots,e_{r}\\}$. A successful query of
$\mathcal{C}$ would have infected $u$, implying that either one of the
$e_{i}\in\mathcal{C}$ has been exposed previously (line 1) or one of the
$e_{i}\in\mathcal{C}$ intersects an exposed hyperedge in an uninfected vertex
(line 1).

Now if $e_{i}$ is exposed and $u$ is uninfected, then every other hyperedge
$e_{j}$ will become a neutron-star-adjacent collection in some later step.
Formally, for every $1\leq j\leq\ell$ with $j\neq i$ there is some step $t\geq
1$ such that $e_{j}\in\mathcal{N}(t)$ for some $t\geq 1$, contradicting Claim
18. On the other hand, if $e_{i}$ intersects a hyperedge in an uninfected
vertex, then we have that $e_{i}\in\mathcal{N}(t)$ for some $t\geq 1$, again
contradicting Claim 18. We conclude that no subset of
$\\{e_{1},\ldots,e_{\ell}\\}$ contains $r$ hyperedges which intersect only in
$u$.

We have already established that each hyperedge in
$\\{e_{1},\ldots,e_{\ell}\\}$ has at most one vertex in $B_{f}$. Together with
the fact that other than $u$ any pair of hyperedges in
$\\{e_{1},\ldots,e_{\ell}\\}$ can intersect only in infected vertices, and no
$r$ of them are vertex disjoint except for $u$ implies that $u$ has less than
$r$ infected neighbours at the end of the process, contradicting our
assumption that $u$ has at least $r$ infected neighbours. ∎

##  4\. Subcritical regime

###  4.1. Properties of the query-process

In the following we examine the behaviour of the query-process when the
underlying graph is the binomial random $k$-uniform hypergraph $H_{k}(n,p)$
with vertex set $V=[n]$ and hyperedge set $E$. Recall that we only query
collections, where none of the hyperedges have been exposed before. However
the query may contain unexposed hyperedges which have been part of
unsuccessfully queried collections. Intuitively, if a collection contains
$k$-sets which were part of an unsuccessful query, then the probability that
the current query is successful decreases. In the following lemma, we make
this argument rigorous by providing an upper bound for the probability of a
successful query, in a more general setting, which is independent of the
result of all previous queries.

######  Lemma 20.

Consider a process where collections of $k$-sets are subsequently queried,
with a restriction that no queried collection may contain any $k$-set from a
previously successfully queried collection, as in Algorithm 1. Then,
conditional on the results of all previous queries, the probability that a
collection $\mathcal{C}$ of $k$-sets is successfully queried is at most
$p^{|\mathcal{C}|}$.

###### Proof.

Denote by $E_{1},\ldots,E_{\ell}$ the collections of $k$-sets which were
unsuccessfully queried before $\mathcal{C}$ was examined and by
$S_{1},\ldots,S_{j}$ the $k$-sets which were part of a successful query before
$\mathcal{C}$ was examined. Let $S=\bigcup_{i=1}^{j}S_{i}$ and define
$E_{i}^{\prime}=E_{i}\backslash S$ for $i=1,\ldots,\ell$. Since $E_{i}$ was
unsuccessfully queried we have $E_{i}\setminus S\neq\emptyset$. The event
$E_{i}\subseteq E$ and $E_{i}^{\prime}\subseteq E$ are denoted by
$\mathcal{E}_{i}$ and $\mathcal{E}_{i}^{\prime}$ respectively and define
$\overline{\mathcal{E}}=\bigcap_{i=1}^{\ell}\overline{\mathcal{E}_{i}}$ and
$\overline{\mathcal{E}^{\prime}}=\bigcap_{i=1}^{\ell}\overline{\mathcal{E}^{\prime}_{i}}$.
Finally let $\mathcal{S}$ be the event that $S\subseteq E$.

Note that for every $1\leq i\leq\ell$ we have
$\mathcal{S}\cap\overline{\mathcal{E}_{i}}=\mathcal{S}\cap\overline{\mathcal{E}^{\prime}_{i}}$
and thus
$\mathcal{S}\cap\overline{\mathcal{E}}=\mathcal{S}\cap\overline{\mathcal{E}^{\prime}}$.
In addition, $\mathcal{C}\subseteq E$ and $\mathcal{S}$ are increasing events,
while the event $\overline{\mathcal{E}^{\prime}}$ is decreasing. Therefore, we
have

$\displaystyle\mathbb{P}[\mathcal{C}\subseteq
E,\mathcal{S},\overline{\mathcal{E}}]$
$\displaystyle=\mathbb{P}[\mathcal{C}\subseteq
E,\mathcal{S},\overline{\mathcal{E}^{\prime}}]$
$\displaystyle\leq\mathbb{P}[\mathcal{C}\subseteq
E,\mathcal{S}]\mathbb{P}[\overline{\mathcal{E}^{\prime}}]$
$\displaystyle(\text{by FKG (Theorem~{}\ref{thm:FKG})}).$

Using the fact that $S=\bigcup_{i=1}^{j}S_{i}$ is disjoint of both the
collection $\mathcal{C}$ and every $E_{i}^{\prime}$, we have

$\displaystyle\mathbb{P}[\mathcal{C}\subseteq
E,\mathcal{S}]\mathbb{P}[\overline{\mathcal{E}^{\prime}}]$
$\displaystyle=\mathbb{P}[\mathcal{C}\subseteq
E]\mathbb{P}[\mathcal{S}]\mathbb{P}[\overline{\mathcal{E}^{\prime}}]$
$\displaystyle(\text{because }\mathcal{C}\cap S=\emptyset)$
$\displaystyle=\mathbb{P}[\mathcal{C}\subseteq
E]\mathbb{P}[\mathcal{S},\overline{\mathcal{E}^{\prime}}]$
$\displaystyle(\text{because }S\cap E_{i}^{\prime}=\emptyset).$

Again using
$\mathcal{S}\cap\overline{\mathcal{E}}=\mathcal{S}\cap\overline{\mathcal{E}^{\prime}}$
we have

$\displaystyle\mathbb{P}[\mathcal{C}\subseteq
E]\mathbb{P}[\mathcal{S},\overline{\mathcal{E}^{\prime}}]$
$\displaystyle=\mathbb{P}[\mathcal{C}\subseteq
E]\mathbb{P}[\mathcal{S},\overline{\mathcal{E}}]=p^{|\mathcal{C}|}\mathbb{P}[\mathcal{S},\overline{\mathcal{E}}].$

We conclude that

$\mathbb{P}[\mathcal{C}\subset E,\mathcal{S},\overline{\mathcal{E}}]\leq
p^{|\mathcal{C}|}\mathbb{P}[\mathcal{S},\overline{\mathcal{E}}],$

and result follows after dividing both sides by
$\mathbb{P}[\mathcal{S},\overline{\mathcal{E}}]$. ∎

Using the previous lemma we estimate the distribution of the infected
vertices.

######  Corollary 21.

Given $\mathcal{N}(t+1),\mathcal{H}(t+1),\mathcal{W}(t+1)$ and
$\mathcal{S}(t+1)$, the number of vertices infected in step $t+1$ is
stochastically dominated by

$k^{2}\mathrm{Bin}(N(t+1),p)+k\mathrm{Bin}(H(t+1),p)+2k\mathrm{Bin}(W(t+1),p^{2})+\eta\mathrm{Bin}(S(t+1),p^{r}),$

where $\eta:=(2k-3)\mathbbm{1}_{r=2}+\mathbbm{1}_{r\geq 3}$ is as defined in
(1).

###### Proof.

Lemma 20 implies that the number of successful queries within the individual
families are stochastically dominated by
$\mathrm{Bin}(N(t+1),p),\mathrm{Bin}(H(t+1),p),\mathrm{Bin}(W(t+1),p^{2})$ and
$\mathrm{Bin}(S(t+1),p^{r})$, respectively. A successful query leads to
different number of infected vertices depending on which family the queried
collection of $k$-sets was contained in. Since the hyperedges of $F(t)$
overlap only in infected vertices we have that any $k$-set not contained in
$F(t)$ can share an uninfected vertex with at most $k-1$ hyperedges in $F(t)$
and thus every neutron-star-adjacent collection (comprised of a single $k$-set
by definition), causes at most $k^{2}$ vertices to become infected, after a
successful query. When considering a heavily-infected collection (comprised of
a single $k$-set by definition) only the vertices within the $k$-set become
infected leading to at most $k$ infected vertices, in case of a successful
query. Any widely-over-lapping collection (comprised of two $k$-sets by
definition) contains at most $2k$ vertices, all of which are infected, after a
successful query. Because $\eta=2k-3$ when $r=2$ and $\eta=1$ when $r\geq 3$,
the successful query of a star collection leads to exactly $\eta$ infected
vertices for any $r\geq 2$. ∎

###  4.2. Bounding trajectory

In the following we establish the expected trajectory for the number of
infected vertices. Recall that

$a:=|A(0)|=|B(0)|=(1-\varepsilon)a_{c}.$

Throughout the remainder of this section we assume that $\delta>0$ satisfies

$1/(1+\delta)>(1-\varepsilon)^{r-1}.$

For convenience of notation define $B(-1)=\emptyset$. Based on the heuristic
that (4) holds, and under the assumption that in every step the number of
infected vertices exceeds its expectation by at most a $(1+\delta)$ factor, we
define the following bounding trajectory.

######  Definition 22 (Bounding trajectory).

We define the sequence $b(t)$ by setting $b(-1)=0$, $b(0)=|B(0)|$ and for each
integer $t\geq 0$

$\displaystyle b(t+1)$
$\displaystyle:=(1+\delta)\eta\frac{b(t)^{r}}{r!}n\left[\binom{n}{k-2}p\right]^{r}+b(0).$

Moreover, for every integer $t\geq-1$ we set

$\beta(t):=\frac{b(t)}{a^{*}},$

where $a^{*}$ is as defined in (2). We call the function $\beta$ the
_trajectory associated to the query-process_.

In the following we express $\beta$ using a recursion.

######  Claim 23.

For every integer $t\geq 0$ we have

$\displaystyle\beta(t+1)=(1+\delta)\frac{\beta(t)^{r}}{r}+\beta(0).$

###### Proof.

By Definition 22 we have

$\displaystyle\beta(t+1)$
$\displaystyle=(1+\delta)\eta\frac{\beta(t)^{r}(a^{*})^{r-1}}{r!}n\left[\binom{n}{k-2}p\right]^{r}+\beta(0)$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:scaling}}}{{=}}(1+\delta)\eta\frac{\beta(t)^{r}}{r!}\left(\frac{(r-1)!}{\eta
n\left(\binom{n}{k-2}p\right)^{r}}\right)n\left[\binom{n}{k-2}p\right]^{r}+\beta(0)$
$\displaystyle=(1+\delta)\frac{\beta(t)^{r}}{r}+\beta(0).$

∎

Based on the heuristic in Section 1.3 we expect $\beta(t)$ to also have a
maximum. We will prove a slightly weaker statement, namely that $\beta\leq
x_{0}$ where $x_{0}$ is the smallest positive solution of the equation:

$x_{0}=(1+\delta)\frac{x_{0}^{r}}{r}+\beta(0).$ (9)

First we prove that a solution exists.

######  Claim 24.

If $\beta(0)=(1-\varepsilon)(1-1/r)$, then $x_{0}$, defined in (9), satisfies

$\beta(0)<x_{0}<(1+\delta)^{-1/(r-1)}<1.$

###### Proof.

First we observe that the function $h(x):=x-(1+\delta)x^{r}/r$ is strictly
increasing and continuous on the interval $(0,(1+\delta)^{-1/(r-1)})$. Since
$h(\beta(0))\leq\beta(0)$ and

$h\left(\left(\frac{1}{1+\delta}\right)^{1/(r-1)}\right)=\left(\frac{1}{1+\delta}\right)^{1/(r-1)}\left(1-\frac{1}{r}\right)>(1-\varepsilon)\left(1-\frac{1}{r}\right)=\beta(0),$

such a solution exists. ∎

Now we can show that $\beta(t)<x_{0}$ for every $t\geq 0$, and thus by Claim
24 we have $b(t)\leq a^{*}x_{0}<a^{*}$.

######  Lemma 25.

Assume that $\beta(t)\leq(1-\xi)x_{0}$ for some $0<\xi<1$. Then there exists a
$0<\xi^{\prime}<1$ such that $\beta(t+1)\leq(1-\xi^{\prime})x_{0}$.

###### Proof.

By Claim 23 and $\beta(t)\leq(1-\xi)x_{0}$ we have

$\displaystyle\beta(t+1)$
$\displaystyle=(1+\delta)\frac{\beta(t)^{r}}{r}+\beta(0)\leq(1+\delta)\frac{(1-\xi)^{r}x_{0}^{r}}{r}+\beta(0).$

Adding and subtracting $(1-\xi)^{r}\beta(0)$ and using the definition of
$x_{0}$ from (9) gives

$\displaystyle(1+\delta)\frac{(1-\xi)^{r}x_{0}^{r}}{r}+\beta(0)$
$\displaystyle=(1-\xi)^{r}\left((1+\delta)\frac{x_{0}^{r}}{r}+\beta(0)\right)+(1-(1-\xi)^{r})\beta(0)$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:boundx}}}{{=}}(1-\xi)^{r}x_{0}+(1-(1-\xi)^{r})\beta(0).$

Using $\beta(0)\leq\beta(t)\leq(1-\xi)x_{0}$ and some simple algebra leads to

$\displaystyle(1-\xi)^{r}x_{0}+(1-(1-\xi)^{r})\beta(0)$
$\displaystyle\leq(1-\xi)^{r}x_{0}+(1-(1-\xi)^{r})(1-\xi)x_{0}$
$\displaystyle=(1-\xi(1-(1-\xi)^{r}))x_{0}.$

Since $0<\xi<1$, we have $0<1-(1-\xi)^{r}<1$, and setting
$\xi^{\prime}=\xi(1-(1-\xi)^{r})$ completes the proof. ∎

###  4.3. Remaining below the trajectory

We have established that the trajectory for the number of infected vertices
remains below $a^{*}$. In the remainder of the section we show that, with
sufficiently high probability, the number of infected vertices remains bounded
from above by the trajectory.

We start by showing that as long as the number of infected vertices does not
significantly exceed its expectation in each of the previous steps, this also
holds with sufficiently high probability in the following step. Let
$\mathcal{G}_{t}$ denote the event that for every $0<\tau\leq t$ we have
$|B(\tau)|-|B(\tau-1)|\leq b(\tau)-b(\tau-1)$.

######  Lemma 26.

For every $t\geq 1$, conditional on $\mathcal{G}_{t}$ we have

$|B(t+1)|-|B(t)|\leq b(t+1)-b(t)$

with probability at least $1-\exp(-\delta^{2}(b(t+1)-b(t))/(2k^{2}))$.

###### Proof.

We start by establishing an upper bound on the expected number of infected
vertices. By Claim 24 and Lemma 25 we have

$b(t)\binom{n}{k-2}p\leq
a^{*}\binom{n}{k-2}p=\Theta\left(\left(n\binom{n}{k-2}p\right)^{-1/(r-1)}\right)=o(1).$
(10)

In addition, by Definition 22 and $b(0)\leq b(t)\leq b(t+1)$ we have

$\displaystyle b(t+1)-b(t)$
$\displaystyle=(1+\delta)\eta\frac{b(t)^{r}-b(t-1)^{r}}{r!}n\left[\binom{n}{k-2}p\right]^{r}$
$\displaystyle=\left(b(t)-b(t-1)\right)\Omega\left(b(0)^{r-1}n\left[\binom{n}{k-2}p\right]^{r}\right).$

Recall that $b(0)=|A(0)|=\Omega(a^{*})$. Thus by (2)

$\displaystyle b(t+1)-b(t)$
$\displaystyle=\left(b(t)-b(t-1)\right)\Omega\left((a^{*})^{r-1}n\left[\binom{n}{k-2}p\right]^{r}\right)$
$\displaystyle=\Omega(b(t)-b(t-1)).$ (11)

In the following we consider the expected number of successful queries in each
of the individual families.

We start with the family of neutron-star-adjacent collections. By Observation
16 we have

$N(t+1)p\leq 2rk(|B(t)|-|B(t-1)|)|B(t)|\binom{n}{k-2}p.$

By assumption we have $|B(\tau)|-|B(\tau-1)|\leq b(\tau)-b(\tau-1)$ for every
$\tau\leq t$ implying that $|B(t)|-|B(t-1)|\leq b(t)-b(t-1)$ and $B(t)\leq
b(t)$. Therefore

$N(t+1)p=O\left((b(t)-b(t-1))b(t)\binom{n}{k-2}p\right)\stackrel{{\scriptstyle\eqref{eq:exnn}}}{{=}}o(b(t)-b(t-1))\stackrel{{\scriptstyle\eqref{eq:sameorder}}}{{=}}o(b(t+1)-b(t)).$

The following two calculations are done similarly. When considering the number
of heavily-infected collections we start from Observation 14, which implies

$\displaystyle H(t+1)p$
$\displaystyle\leq(|B(t)|-|B(t-1)|)|B(t)|\binom{n}{k-2}p=o(b(t+1)-b(t)).$

In addition, if we consider widely-overlapping pairs of $k$-sets, then by
Observation 13 we have

$\displaystyle W(t+1)p^{2}$
$\displaystyle\leq|B(t)|(|B(t)|-|B(t-1)|)n^{2}\binom{n}{k-3}^{2}p^{2}=o\left(b(t+1)-b(t)\right).$

Finally we consider stars. Similarly as before, by assumption we have
$|B(\tau)|-|B(\tau-1)|\leq b(\tau)-b(\tau-1)$ for every $\tau\leq t$ and thus
$|B(t)|-|B(t-1)|\leq b(t)-b(t-1)$, $B(t)\leq b(t)$ and $B(t-1)\leq b(t-1)$.
Therefore

$\displaystyle|B(t)|^{r}-|B(t-1)|^{r}$
$\displaystyle=(|B(t)|-|B(t-1)|)\sum_{\rho=0}^{r-1}|B(t)|^{\rho}|B(t-1)|^{r-1-\rho}$
$\displaystyle\leq(b(t)-b(t-1))\sum_{\rho=0}^{r-1}b(t)^{\rho}b(t-1)^{r-1-\rho}$
$\displaystyle=b(t)^{r}-b(t-1)^{r}.$

Together with Observation 12 this implies

$\displaystyle S(t+1)p^{r}$
$\displaystyle\leq\frac{|B(t)|^{r}-|B(t-1)|^{r}}{r!}n\left(\binom{n}{k-2}\right)^{r}p^{r}$
$\displaystyle\leq\frac{b(t)^{r}-b(t-1)^{r}}{r!}n\left(\binom{n}{k-2}\right)^{r}p^{r}$
$\displaystyle=\frac{b(t+1)-b(t)}{(1+\delta)\eta},$

where the last equality follows from Definition 22.

By Corollary 21 we have that $|B(t+1)|-|B(t)|$ is stochastically dominated by

$k^{2}\mathrm{Bin}(N(t+1),p)+k\mathrm{Bin}(H(t+1),p)+2k\mathrm{Bin}(W(t+1),p^{2})+\eta\mathrm{Bin}(S(t+1),p^{r}).$

Together with the previous calculations this implies
$\mathbb{E}[|B(t+1)|-|B(t)|]\leq(1+o(1))(b(t+1)-b(t))/(1+\delta)$ and applying
Theorem 3 gives us

$\displaystyle\mathbb{P}[(|B(t+1)|-|B(t)|)\geq b(t+1)-b(t)]$
$\displaystyle\leq\exp\left(-\frac{(1+o(1))\delta^{2}(b(t+1)-b(t))^{2}}{2((b(t+1)-b(t))+k^{2}(b(t+1)-b(t))/3)}\right)$
$\displaystyle\leq\exp\left(-\frac{\delta^{2}(b(t+1)-b(t))}{2k^{2}}\right),$

as required. ∎

The previous Lemma provides sufficiently high probabilities when the expected
number of vertices infected in a given step is large, that is,
$\Omega(a^{*})$. However, the expected number of infected vertices decreases
gradually and thus after a while it will be impossible to establish tight
concentration on a step by step basis, and we will require a different method.
In particular we approximate the newly infected vertices with a Galton-Watson
branching process and show that it dies out quickly using the Dwass identity.
We start by providing an upper bound on the size of a Galton-Watson process.

######  Lemma 27.

Consider a Galton-Watson process where the number of offspring is the sum of
weighted Bernoulli random variables, that is, $\sum_{i=1}^{k}w_{i}Be(p_{i})$,
such that $\mu:=\sum_{i=1}^{k}w_{i}p_{i}<1$ for $w_{i}\in\mathbb{R}^{+}$ and
$p_{i}\in(0,1)$ for each $1\leq i\leq k$. Set $M=\max_{i=1,\ldots,k}w_{i}$ and
denote by $Z_{j}$ the number of individuals in the $j$-th generation and by
$Z$ the total number of individuals in the process. Then for any
$\chi\geq\mu/(1-\mu)$ and $\ell\in\mathbb{N}$ we have

$\mathbb{P}\left[Z>(1+\chi)\ell\mid
Z_{0}=\ell\right]\leq\frac{\exp\left(-(1-(1+\chi)^{-1}-\mu)^{2}(1+\chi)\ell/(3M)\right)}{1-\exp\left(-(1-(1+\chi)^{-1}-\mu)^{2}(1+\chi)/(3M)\right)}.$

###### Proof.

By the Dwass identity (Theorem 5) we have that for any $m>(1+\chi)\ell$,

$\mathbb{P}\left[Z=m\mid
Z_{0}=\ell\right]=\frac{\ell}{m}\mathbb{P}\left[Z_{1}=m-\ell\mid
Z_{0}=m\right]<\mathbb{P}\left[Z_{1}=m-\ell\mid Z_{0}=m\right],$

where the last inequality is due to $\frac{\ell}{m}<\frac{1}{1+\chi}\leq
1-\mu<1$, and thus

$\mathbb{P}\left[Z>(1+\chi)\ell\mid
Z_{0}=\ell\right]\leq\sum_{m>(1+\chi)\ell}\mathbb{P}\left[Z_{1}=m-\ell\mid
Z_{0}=m\right].$

Using $m>(1+\chi)\ell$ and that the expected number of offspring in the
branching process is $\mu$ gives

$\displaystyle\mathbb{P}\left[Z_{1}=m-\ell\mid Z_{0}=m\right]$
$\displaystyle\leq\mathbb{P}\left[Z_{1}\geq m-\ell\mid Z_{0}=m\right]$
$\displaystyle=\mathbb{P}\left[Z_{1}-\mathbb{E}\left[Z_{1}\mid
Z_{0}=m\right]\geq m-\ell-\mathbb{E}\left[Z_{1}\mid Z_{0}=m\right]\mid
Z_{0}=m\right]$
$\displaystyle\leq\mathbb{P}\left[Z_{1}-\mathbb{E}\left[Z_{1}\mid
Z_{0}=m\right]\geq m-\frac{1}{1+\chi}m-\mu m\mid Z_{0}=m\right].$

Since $\chi\geq\mu/(1-\mu)$ we have

$1-\frac{1}{1+\chi}-\mu\geq 0$

and thus Theorem 3 implies

$\displaystyle\mathbb{P}\left[Z_{1}=m-\ell\mid Z_{0}=m\right]$
$\displaystyle\leq\exp\left(-\frac{(1-(1+\chi)^{-1}-\mu)^{2}}{3M}m\right),$

where we use $\mathrm{Var}(Z_{1}\mid Z_{0}=m)\leq M\mathbb{E}\left[Z_{1}\mid
Z_{0}=m\right]\leq Mm.$

∎

Recall that $\mathcal{G}_{t}$ is the event that for every $0<\tau\leq t$ we
have $|B(\tau)|-|B(\tau-1)|\leq b(\tau)-b(\tau-1)$.

######  Lemma 28.

Set $\chi=4/\delta$. Let $t_{0}$ be such that $b(t_{0}-1)=(1-\xi)x_{0}a^{*}$
where

$\left[\left(\frac{1+\delta}{1+\delta/2}\right)^{1/(r-1)}-1\right]\frac{1}{\chi}>\xi.$
(12)

Then

$\mathbb{P}\left[|B_{f}|\geq\frac{a^{*}}{(1+\delta/2)^{1/(r-1)}}\mid\mathcal{G}_{t_{0}}\right]\leq\exp\Big{(}-\Omega\big{(}b(t_{0})-b(t_{0}-1)\big{)}\Big{)}.$

###### Proof.

By Lemma 25 and Definition 22 we have $b(t)\leq x_{0}a^{*}$ for every $t\geq
0$, which together with $b(t_{0}-1)=(1-\xi)x_{0}a^{*}$ implies
$b(t_{0})-b(t_{0}-1)\leq\xi x_{0}a^{*}$, thus

$b(t_{0}-1)+(1+\chi)(b(t_{0})-b(t_{0}-1))\leq(1-\xi)x_{0}a^{*}+(1+\chi)\xi
x_{0}a^{*}=(1+\xi\chi)x_{0}a^{*}.$ (13)

Using the upper bound on $x_{0}$ from Claim 24 and (12) gives

$\displaystyle(1+\xi\chi)x_{0}$ $\displaystyle\stackrel{{\scriptstyle
Clm~{}\ref{lem:boundx}}}{{\leq}}\frac{1+\xi\chi}{(1+\delta)^{1/(r-1)}}\stackrel{{\scriptstyle\eqref{eq:xicond}}}{{\leq}}\frac{1}{(1+\delta/2)^{r-1}}.$

Together with (13) this implies

$b(t_{0}-1)+(1+\chi)(b(t_{0})-b(t_{0}-1))\leq\frac{a^{*}}{(1+\delta/2)^{r-1}}=:a^{\prime}.$
(14)

Note that if $\mathcal{G}_{t_{0}}$ holds then $B(t_{0}-1)\leq b(t_{0}-1)$,
therefore an upper bound on the probability that the total number of vertices
infected after step $t_{0}-1$ is at least $(1+\chi)(b(t_{0})-b(t_{0}-1))$ is
an upper bound on the probability that $|B_{f}|\geq a^{\prime}$.

Forest construction. We construct a forest from the vertices in
$B_{f}\backslash B(t_{0}-1)$. The roots of the individual trees in the forest
are the vertices in $B(t_{0})\setminus B(t_{0}-1)$. For $t\geq t_{0}$ we will
assign each vertex infected in step $t+1$, that is, each vertex in the set
$B(t+1)\backslash B(t)$, to at least one vertex infected in the previous step,
that is, a vertex in $B(t)\backslash B(t-1)$, and then discard some edges to
transform this into a tree.

In order to achieve this we will consider subsets of
$\mathcal{S}(t+1),\mathcal{W}(t+1),\mathcal{H}(t+1)$ and $\mathcal{N}(t+1)$
associated to one vertex $u\in B(t)\setminus B(t-1)$ as follows:

  * •

$\mathcal{S}_{u}(t+1)\subseteq\mathcal{S}(t+1)$, where one of the $k$-sets in
the collection contains $u$;

  * •

$\mathcal{W}_{u}(t)\subseteq\mathcal{W}(t)$, where one of the $k$-sets in the
pair contains $u$;

  * •

$\mathcal{H}_{u}(t+1)\subseteq\mathcal{H}(t)$, where the $k$-set contains $u$;

  * •

$\mathcal{N}_{u}(t+1)\subseteq\mathcal{N}(t+1)$ be the set of $k$-sets
satisfying one of the following conditions:

    * –

$K\in\mathcal{N}_{1}(t+1)$ and $u\in K$;

    * –

$K\in\mathcal{N}_{2}(t+1)$ and there exists $e\in F(t)\setminus F(t-1)$ such
that $K\cap e\cap B(t)^{C}\neq\emptyset$ and $u\in e$.

We say that $u\in B(t)\setminus B(t-1)$ is a potential parent of $v\in
B(t+1)\setminus B(t)$ if one of the following two options hold. First, if
there exists a successfully queried collection of $k$-sets in
$\mathcal{S}_{u}(t+1),\mathcal{W}_{u}(t+1)$, or $\mathcal{H}_{u}(t+1)$, where
one of the hyperedges in the collection contains $v$. Second, if there exists
a successfully queried $k$-set $K\in\mathcal{N}_{u}(t+1)$ such that either
$v\in K$ or $v\in e$ for some hyperedge $e$ which intersects $K$ in an
uninfected vertex, that is $K\cap e\cap B(t)^{C}\neq\emptyset$. This is
visualised in Figure 2.

$v$$u$(a) stars$u$$v$$v_{1}$$v_{2}$$v_{3}$$u$$v_{4}$ (b) widely-overlapping
$u$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{2}$$v_{1}$$u_{2}$$u_{1}$ (c) heavily-
infected
$u_{1}$$u_{2}$$v_{1}$$v_{2}$$u_{2}$$v_{4}$$u_{1}$$v_{1}$$v_{2}$$v_{3}$ (d)
neutron-star adjacent $u_{1}$$u_{2}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$ Figure 2.
Potential parents.
Empty circles represent uninfected vertices, while the filled circles
represent infected vertices. Red circles were infected in step $t+1$, blue in
step $t$ and black in the first $t-1$ steps.

Note that $\mathcal{S}(t+1)=\bigcup_{u\in B(t)\setminus
B(t-1)}\mathcal{S}_{u}(t+1)$ and the analogous statements hold for
$\mathcal{W}(t+1),\mathcal{H}(t+1)$ and $\mathcal{N}(t+1)$. Therefore, every
vertex $v\in B(t+1)\backslash B(t)$ has at least one potential parent. As we
would like this relationship to be unique for every vertex $v$, we assign a
unique parent, say the smallest vertex $u$, and thus for any $u_{1},u_{2}$ the
set of offspring of $u_{1}$ and $u_{2}$ are disjoint.

This construction is reminiscent of a branching process, except the offspring
distribution of the individual vertices depends on the current state, in
particular on the size of the sets
$\mathcal{S}_{u}(t+1),\mathcal{W}_{u}(t+1),\mathcal{H}_{u}(t+1)$, and
$\mathcal{N}_{u}(t+1)$. In the following we will remove this dependence.

For $i\geq 0$ let $M_{i}=|B(t_{0}+i)\setminus B(t_{0}+i-1)|$. Consider a
stopping condition when $\sum_{i=0}^{j}M_{i}$ becomes larger than
$(1+\chi)(b(t_{0})-b(t_{0}-1))$, i.e., we define the random variable

$M^{\prime}_{i}=\left\\{\begin{array}[]{ll}M_{i}&\mbox{if
}\sum_{j=0}^{i-1}M^{\prime}_{j}<(1+\chi)(b(t_{0})-b(t_{0}-1)),\\\
0&\mbox{otherwise},\end{array}\right.$

and similarly as before let $M^{\prime}=\sum_{i=0}^{\infty}M^{\prime}_{i}$.
Clearly

$\mathbb{P}[M\geq(1+\chi)(b(t_{0})-b(t_{0}-1))\mid\mathcal{G}_{t}]=\mathbb{P}[M^{\prime}\geq(1+\chi)(b(t_{0})-b(t_{0}-1))\mid\mathcal{G}_{t}].$

Now consider the offspring distribution of a vertex in the $i$-th generation
of $M^{\prime}$. Recall that the successful query of a star collection leads
to $\eta$ infected vertices, the successful query of a widely-overlapping
collection infects at most $2k$ infected vertices, the successful query of a
heavily-infected collection results in at most $k$ vertices becoming infected
and the successful query of a neutron-star-adjacent collection gives at most
$k^{2}$ infected vertices. Therefore, by mimicking the proof of Corollary 21,
Lemma 20 implies that the number of offspring is stochastically dominated by

$k^{2}\mathrm{Bin}(|\mathcal{N}_{u}(t+1)|,p)+k\mathrm{Bin}(|\mathcal{H}_{u}(t+1)|,p)+2k\mathrm{Bin}(|\mathcal{W}_{u}(t+1)|,p^{2})+\eta\mathrm{Bin}(|\mathcal{S}_{u}(t+1)|,p^{r}).$

If the process has not stopped yet, then we have
$b(t_{0}-1)+\sum_{j=0}^{i}M_{j}^{\prime}\leq a^{\prime}$ and following the
calculations in Observations 12, 13, 14 and 16 we deduce that

  1. (a)

$|\mathcal{N}_{u}(t+1)|\leq 2rka^{\prime}\binom{n}{k-2}$;

  2. (b)

$|\mathcal{H}_{u}(t+1)|\leq a^{\prime}\binom{n}{k-2}$;

  3. (c)

$|\mathcal{W}_{u}(t+1)|\leq n^{2}a^{\prime}\binom{n}{k-3}^{2}$;

  4. (d)

$|\mathcal{S}_{u}(t+1)|\leq n\binom{a^{\prime}}{r-1}\binom{n}{k-2}^{r}$.

Thus we deduce that the offspring distribution is stochastically dominated by

$k^{2}\mathrm{Bin}\left(3rka^{\prime}\binom{n}{k-2},p\right)+2k\mathrm{Bin}\left(n^{2}a^{\prime}\binom{n}{k-3}^{2},p^{2}\right)+\eta\mathrm{Bin}\left(n\binom{a^{\prime}}{r-1}\binom{n}{k-2}^{r},p^{r}\right),$
(15)

and note that this also holds after the stopping time.

Coupling with Galton-Watson process. Denote by $Z$ the Galton-Watson process
with $b(t_{0})-b(t_{0}-1)$ roots where the number of children of every vertex
follows (15). Since $\mathcal{G}_{t_{0}}$ holds, the number of roots in
$M^{\prime}$ is at most the number of roots in $Z$ and the offspring
distribution for $Z$ stochastically dominates the offspring distribution for
any vertex in $M^{\prime}$ implying

$\mathbb{P}[M^{\prime}\geq(1+\chi)(b(t_{0})-b(t_{0}-1))\mid\mathcal{G}_{t}]\leq\mathbb{P}[Z\geq(1+\chi)(b(t_{0})-b(t_{0}-1))].$

Note that the expected number of offspring of an individual in $Z$ is

$3rk^{3}a^{\prime}\binom{n}{k-2}p+2kn^{2}a^{\prime}\binom{n}{k-3}^{2}p^{2}+\eta
n\binom{a^{\prime}}{r-1}\binom{n}{k-2}^{r}p^{r}\stackrel{{\scriptstyle\eqref{eq:scaling},\eqref{eq:aprimecalc}}}{{\leq}}\frac{1}{1+\delta/3},$

and the maximal weight is $k^{2}$.

Note that

$\chi=\frac{4}{\delta}>\frac{3}{\delta}=\frac{(1+\delta/3)^{-1}}{1-(1+\delta/3)^{-1}}.$

Therefore by Lemma 27 we have

$\mathbb{P}[Z\geq(1+\chi)(b(t_{0})-b(t_{0}-1))]=\exp\left(-\Omega\left(b(t_{0})-b(t_{0}-1)\right)\right),$

and the statement follows. ∎

###  4.4. Proof of Theorem 2 $(i)$

Using Lemma 26 we can bound the number of vertices infected in a given step. A
repeated application of this lemma allows us to show that the number of
vertices which become infected in a step decreases sufficiently over a bounded
number of steps. Then we complete the proof by applying Lemma 28. In this
section we focus on the interaction of these two lemmas, and in particular we
determine the number of steps required for the conditions of Lemma 28 to be
met and calculate the relevant probabilities using the union bound.

###### Proof of Theorem 2 $(i)$.

Set $\chi=4/\delta$. For any fixed $\xi^{\prime}>0$ satisfying
$\left[\left(\frac{1+\delta}{1+\delta/2}\right)^{1/(r-1)}-1\right]\frac{1}{\chi}>\xi^{\prime}$
let $t_{0}(\xi^{\prime})$ be the smallest value of $t$ such that
$\beta(t-1)\geq(1-\xi^{\prime})x_{0}$. First we show that
$t(\xi^{\prime})=O(1)$ and $\beta(\tau+1)-\beta(\tau)=\Omega(1)$ for every
$\tau\leq t_{0}(\xi^{\prime})$.

Assume that $\beta(\tau)\leq(1-\xi^{\prime})x_{0}$. Claim 24 implies that
$x_{0}\leq(1+\delta)^{-1/(r-1)}$ and note that the function
$(1+\delta)y^{r}/r-y$ is monotone decreasing on the interval $[0,x_{0}]$.
Therefore by Definition 22

$\displaystyle\beta(\tau+1)-\beta(\tau)$
$\displaystyle=(1+\delta)\frac{\beta(\tau)^{r}}{r}+\beta(0)-\beta(\tau)$
$\displaystyle\geq(1+\delta)\frac{(1-\xi^{\prime})^{r}x_{0}^{r}}{r}+\beta(0)-(1-\xi^{\prime})x_{0}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:boundx}}}{{=}}(1-\xi^{\prime})^{r}(x_{0}-\beta(0))+\beta(0)-(1-\xi^{\prime})x_{0}$
$\displaystyle=(1-(1-\xi^{\prime})^{r})\beta(0)-(1-\xi^{\prime})(1-(1-\xi^{\prime})^{r-1})x_{0}.$
(16)

Next we bound $\beta(0)$ from bellow. By (9) we have

$\displaystyle\beta(0)=x_{0}-(1+\delta)\frac{x_{0}^{r}}{r}=x_{0}\left(1-(1+\delta)\frac{x_{0}^{r-1}}{r}\right)\stackrel{{\scriptstyle
Clm.\ref{lem:boundx}}}{{\geq}}x_{0}\left(1-\frac{1}{r}\right).$ (17)

Together (16) and (17) imply

$\displaystyle\beta(\tau+1)-\beta(\tau)$
$\displaystyle\geq(1-(1-\xi^{\prime})^{r})\beta(0)-(1-\xi^{\prime})(1-(1-\xi^{\prime})^{r-1})x_{0}$
$\displaystyle\geq(1-(1-\xi^{\prime})^{r})\left(1-\frac{1}{r}\right)x_{0}-(1-\xi^{\prime})(1-(1-\xi^{\prime})^{r-1})x_{0}.$

Since $0<\xi^{\prime}<1$ and $r\geq 2$, using the summation formula for the
geometric series gives

$\displaystyle\frac{1-(1-\xi^{\prime})^{r}}{r}\leq\xi^{\prime}\frac{1+(r-1)(1-\xi^{\prime})}{r}=\xi^{\prime}-\frac{r-1}{r}(\xi^{\prime})^{2},$

and we also have

$\displaystyle(1-(1-\xi^{\prime})^{r})-(1-\xi^{\prime})(1-(1-\xi^{\prime})^{r-1})=\xi^{\prime}.$

Together these imply

$\displaystyle\beta(\tau+1)-\beta(\tau)$
$\displaystyle\geq\frac{r-1}{r}(\xi^{\prime})^{2}x_{0}.$

Therefore in every step before $t_{0}(\xi^{\prime})$ the value of $\beta(t)$
increases by at least $(r-1)(\xi^{\prime})^{2}x_{0}/r>0$ implying
$t_{0}(\xi^{\prime})=O(1)$ and $\beta(\tau+1)-\beta(\tau)=\Omega(1)$ for every
$\tau\leq t_{0}(\xi^{\prime})$.

Now fix $\xi^{\prime}$, set $t_{0}=t_{0}(\xi^{\prime})$ and define $\xi$
implicitly by $\beta(t_{0}-1)=(1-\xi)x_{0}$. Lemma 26 implies that for every
$0<t\leq t_{0}$ we have $|B(t)|-|B(t-1)|\leq b(t)-b(t-1)$ with probability
$1-\exp(-\Omega(a^{*}))$ and Lemma 28 implies that with probability
$1-\exp(-\Omega(a^{*}))$ the total number of infected vertices is at most
$a^{*}$, completing the proof.

∎

##  5\. supercritical regime

In this section we turn our attention to the supercritical regime of Theorem
2. Throughout this section we assume that a constant $0<\varepsilon<1$ is
given and the size of the initial infection set satisfies

$a:=|A(0)|=(1+\varepsilon)a_{c}.$

Similarly to the previous section we define a new process, called mild
$r$-bootstrap percolation, which will infect overall fewer vertices than the
original $r$-bootstrap percolation. In particular, in each step we activate
the right amount of vertices from the set of infected vertices, which have
never been active before, and only expose the hyperedges which contain exactly
one vertex which was activated in this step and no additional infected
vertices. When $r\geq 3$, for a given vertex we count the number of its active
neighbours within the hypergraph spanned by the hyperedges exposed so far and
infect it, when the number of active neighbours reaches $r$. When $r=2$ the
situation is slightly different. If a vertex has two active neighbours within
the hyperedges exposed so far, then obviously it becomes infected. Following
the rules of $r$-bootstrap percolation, this implies that every vertex within
its neighbourhood, with respect to the hyperedges exposed so far, would also
become infected, as every hyperedge contains an active vertex which is
infected. Therefore in each step we add every vertex which has two active
neighbours, and every vertex in its neighbourhood, within the hyperedges
exposed until this step.

The majority of the proof for the supercritical regime of Theorem 2 considers
the case when the number of infected vertices is small, that is,
$o((n^{k-2}p)^{-1})$. In order to establish the probability that a given
vertex becomes infected, we will not only need to track the number of infected
vertices, but also the number of vertices which have at least $i$ active
neighbours for $0\leq i\leq r$. We start by establishing some properties of
mild $r$-bootstrap percolation within one step. Then we establish for each $i$
the trajectory for the number of vertices with at least $i$ active neighbours
and do similarly for the number of infected vertices. In addition, we prove
that the typical behaviour of the process in fact follows these trajectories
as long as the number of infected vertices remains small (Lemma 36), which
guarantees a steady increase in the number of infected vertices, until roughly
$(n^{k-2}p)^{-1}$ vertices become infected. After this point the process
finishes in 2 steps (Lemmas 37 and 38).

###  5.1. Lower coupling via mild $r$-bootstrap percolation

In mild $r$-bootstrap percolation the set of infected vertices is denoted by
$C(t)$ and set $C(0)=A(0)$. Let $C_{f}$ denote the set of vertices which
become infected during mild $r$-bootstrap percolation. We also introduce
$\widehat{C}(t)\subseteq C(t)$ which contains the vertices which have been
already activated and set $\widehat{C}(0)=\emptyset$. In addition, we require
the sets $C_{i}(t)\subseteq V\setminus C(0)$ for $0\leq i\leq r$, which
contain the subset of the vertices with at least $i$ active neigbhours.
Finally we let $F(t)$ denote the set of hyperedges exposed until the end of
step $t$, with $F(0)=\emptyset$.

In step $t+1$ of the process we select a sufficiently large set
$\widehat{C}^{\prime}(t+1)\subseteq C(t)\setminus\widehat{C}(t)$, where the
exact size of this set is defined in (27), and expose every hyperedge which
contains exactly one vertex in $\widehat{C}^{\prime}(t+1)$ and no vertex in
$C(t)$. Denote this set of hyperedges by $F^{\prime}(t+1)$. First set
$\widehat{C}(t+1)=\widehat{C}(t)\cup\widehat{C}^{\prime}(t+1)$ and
$F(t+1)=F(t)\cup F^{\prime}(t+1)$. In addition let $C_{i}(t+1)$ contain every
vertex in $C_{i}(t)$ and every vertex found in $C_{j}(t)$ which has at least
$i-j$ neighbours in $\widehat{C}^{\prime}(t+1)$ in the hypergraph spanned by
$F^{\prime}(t+1)$. Finally we define the set of infected vertices. When $r\geq
3$, we simply have $C(t+1)=C(t)\cup C_{r}(t+1)$. On the other hand, when
$r=2$, the set $C(t+1)$ contains every vertex in $C(t)$ and every vertex in
the closed neighbourhood of $C_{2}(t+1)\setminus C_{2}(t)$ within the
hypergraph spanned by $F(t+1)$.

Note that changing the step in which a vertex becomes infected, has no affect
on the final set of infected vertices. Moreover, infection will spread only to
a smaller set if some infected vertices remain inactive. Together with the
fact that in mild $r$-bootstrap percolation only a subset of the hyperedges
are exposed when determining whether a vertex becomes infected, we have

$C_{f}\subseteq A_{f}.$

###  5.2. Properties of mild $r$-bootstrap percolation

The aim of this section is to establish some properties of mild $r$-bootstrap
percolation which will lead to lower bounds for the number of vertices added
to $C_{i}(t)$ and $C(t)$ in a single step, during the early stages of the
process.

Roughly speaking, when we add every vertex in a hyperedge to a set, that is,
for $C_{1}(t)$ and $C(t)$ when $r=2$, there is a strong correlation between
two vertices being added to the set. In the remaining cases, namely for
$C_{i}(t)$ when $2\leq i\leq r$ and $C(t)$ for $r\geq 3$, this is no longer
the case, as in these cases two vertices will rarely be found in the same
hyperedge. We require separate arguments for these two cases, which will be
discussed in the remainder of this section, starting with the latter.

In our approach we will use Lemma 4 (for dependent random variables) to
provide an upper bound on the lower tail for the number of vertices added to
$C_{i}(t)$ in a given step. As Lemma 4 provides an upper bound on the upper
tail of a random variable, we will use it to derive an upper bound on the
number of vertices not added to $C_{i}(t)$ in a given step. In the following
lemma we show that the associated random variables satisfy the condition of
Lemma 4.

######  Lemma 29.

Consider $H_{k}(n,p)$ with vertex set $V=[n]$ and hyperedge set $E$. Let
$U,V^{\prime}\subseteq V$ be two disjoint subsets with $|V^{\prime}|=o(n)$
while $U$ satisfies both $|U|=\Omega(a_{c})$ and $|U|=o((n^{k-2}p)^{-1})$.
Denote by $E^{\prime}\subseteq E$ the set of hyperedges which contain exactly
one vertex in $U$ and no vertices in $V^{\prime}$. Consider $W\subseteq
V\setminus(U\cup V^{\prime})$ and an arbitrary function
$g:W\to\\{1,\ldots,r\\}$ such that $|\\{u:g(u)=1\\}|=o(n)$. For $u\in W$ let
$Z_{u}$ be the indicator random variable for the event that $u$ has less then
$g(u)$ neighbours in $U$, within the graph spanned by $E^{\prime}$. Then we
have for every $I\subseteq W$

$\mathbb{E}\left[\prod_{i\in I}Z_{i}\right]\leq\mathbb{E}\left[\prod_{i\in
I}\widehat{Z}_{i}\right],$

where $\widehat{Z}_{u}$ for $u\in W$ forms a set of independent Bernoulli
random variables satisfying

$\mathbb{P}[\widehat{Z}_{u}=1]=1-(1-o(1))\frac{|U|^{g(u)}}{g(u)!}\left(\binom{n}{k-2}p\right)^{g(u)}.$

###### Proof.

The statement follows if for arbitrary $I\subset W$ and $u\in W\backslash I$
we have

$\mathbb{P}\left[Z_{u}=1|\bigwedge_{i\in
I}Z_{i}=1\right]\leq\mathbb{P}\left[\widehat{Z}_{u}=1|\bigwedge_{i\in
I}\widehat{Z}_{i}=1\right]=\mathbb{P}[\widehat{Z}_{u}=1]=1-(1-o(1))\frac{|U|^{g(u)}}{g(u)!}\left(\binom{n}{k-2}p\right)^{g(u)}$

or equivalently

$\mathbb{P}\left[Z_{u}=0|\bigwedge_{i\in
I}Z_{i}=1\right]\geq(1-o(1))\frac{|U|^{g(u)}}{g(u)!}\left(\binom{n}{k-2}p\right)^{g(u)}.$

Fix $I\subset W$ and $u\in W\backslash I$. Denote by $\Phi_{u}$ the set of
$k$-sets satisfying the following conditions:

  * •

the $k$-set contains $u$;

  * •

the $k$-set contains exactly one vertex in $U$;

  * •

the $k$-set contains no vertex in $V^{\prime}$;

  * •

the $k$-set contains no vertex in the set $\\{w:g(w)=1\\}$.

Let $\mathcal{F}_{u}$ be a family of $g(u)$ sized subsets of $\Phi_{u}$ such
that for every $\mathcal{C}\in\mathcal{F}_{u}$ we have that any pair of
$k$-sets in $\mathcal{C}$ are vertex disjoint except for $u$. For two families
of $k$-sets $\mathcal{C}$ and $\Phi$, we introduce the notation
$\mathcal{E}_{\mathcal{C},\Phi}$ for the event $\mathcal{C}\cap\Phi\subseteq
E$ and $\mathcal{D}_{\mathcal{C},\Phi}$ for the event
$(\Phi\setminus\mathcal{C})\cap E=\emptyset$. In particular, for
$\mathcal{C}\in\mathcal{F}_{u}$ we have $\mathcal{E}_{\mathcal{C},\Phi_{u}}$
is the event $\\{\mathcal{C}\subseteq E\\}$ and
$\mathcal{D}_{\mathcal{C},\Phi_{u}}$ is the event
$\\{(\Phi_{u}\backslash\mathcal{C})\cap E=\emptyset\\}$. Thus

$\mathbb{P}\left[Z_{u}=0|\bigwedge_{i\in
I}Z_{i}=1\right]\geq\sum_{\mathcal{C}\in\mathcal{F}_{u}}\mathbb{P}\left[\mathcal{E}_{\mathcal{C},\Phi_{u}},\mathcal{D}_{\mathcal{C},\Phi_{u}}|\bigwedge_{i\in
I}Z_{i}=1\right].$ (18)

Let $\Phi_{u,I}\subseteq\Phi_{u}$ be the set of $k$-sets which contain at
least one vertex in $I$. Since the appearance of any $k$-set not containing a
vertex in $I$ is independent of the event $\\{\bigwedge_{i\in I}Z_{i}=1\\}$,
we have for any $\mathcal{C}\in\mathcal{F}_{u}$

$\mathbb{P}\left[\mathcal{E}_{\mathcal{C},\Phi_{u}},\mathcal{D}_{\mathcal{C},\Phi_{u}},\bigwedge_{i\in
I}Z_{i}=1\right]=p^{|\mathcal{C}\backslash\Phi_{u,I}|}(1-p)^{|\Phi_{u}\backslash\Phi_{u,I}|}\mathbb{P}\left[\mathcal{E}_{\mathcal{C},\Phi_{u,I}},\mathcal{D}_{\mathcal{C},\Phi_{u,I}},\bigwedge_{i\in
I}Z_{i}=1\right].$ (19)

For $\mathcal{C}\in\mathcal{F}_{u}$ define $U_{\mathcal{C}}\subseteq I$ as the
set of vertices in $I$ which are contained in a $k$-set in $\mathcal{C}$.
Recall that every vertex $v\in U_{\mathcal{C}}$ is contained in exactly one
$k$-set in $\mathcal{C}$ and $g(v)\geq 2$. Therefore, conditional on
$\mathcal{E}_{\mathcal{C},\Phi_{u}}$, if $v$ is not contained in any hyperedge
within $E^{\prime}$ in addition to the hyperedge within $\mathcal{C}$, then
$Z_{v}=1$. Denote the event that none of the hyperedges in
$E^{\prime}\setminus\mathcal{C}$ contain $v$ by $\mathcal{I}_{\mathcal{C},v}$.
Then

$\mathbb{P}\left[\mathcal{E}_{\mathcal{C},\Phi_{u,I}},\mathcal{D}_{\mathcal{C},\Phi_{u,I}},\bigwedge_{i\in
I}Z_{i}=1\right]\geq\mathbb{P}\left[\mathcal{E}_{\mathcal{C},\Phi_{u,I}},\mathcal{D}_{\mathcal{C},\Phi_{u,I}},\bigwedge_{v\in
U_{\mathcal{C}}}\mathcal{I}_{\mathcal{C},v},\bigwedge_{i\in I\backslash
U_{\mathcal{C}}}Z_{i}=1\right].$ (20)

Out of the four events on the right-hand side of (20) only the first one
depends on the hyperedges in $\mathcal{C}\cap\Phi_{u,I}$ and thus

$\mathbb{P}\left[\mathcal{E}_{\mathcal{C},\Phi_{u,I}},\mathcal{D}_{\mathcal{C},\Phi_{u,I}},\bigwedge_{v\in
U_{\mathcal{C}}}\mathcal{I}_{\mathcal{C},v},\bigwedge_{i\in I\backslash
U_{\mathcal{C}}}Z_{i}=1\right]=p^{|\mathcal{C}\cap\Phi_{u,I}|}\mathbb{P}\left[\mathcal{D}_{\mathcal{C},\Phi_{u,I}},\bigwedge_{v\in
U_{\mathcal{C}}}\mathcal{I}_{\mathcal{C},v},\bigwedge_{i\in I\backslash
U_{\mathcal{C}}}Z_{i}=1\right].$ (21)

Note that each of the events
$\mathcal{D}_{\mathcal{C},\Phi_{u,I}},\bigwedge_{i\in I\backslash
U_{\mathcal{C}}}Z_{i}=1$ and $\mathcal{I}_{\mathcal{C},v}$ for $v\in
U_{\mathcal{C}}$ is decreasing, therefore the FKG inequality (Theorem 6)
implies

$\mathbb{P}\left[\mathcal{D}_{\mathcal{C},\Phi_{u,I}},\bigwedge_{v\in
U_{\mathcal{C}}}\mathcal{I}_{\mathcal{C},v},\bigwedge_{i\in I\backslash
U_{\mathcal{C}}}Z_{i}=1\right]\geq(1-p)^{|\Phi_{u,I}|}\mathbb{P}\left[\bigwedge_{i\in
I\backslash U_{\mathcal{C}}}Z_{i}=1\right]\prod_{v\in
U_{\mathcal{C}}}\mathbb{P}[\mathcal{I}_{\mathcal{C},v}].$ (22)

Putting (19)-(22) together we have

$\mathbb{P}\left[\mathcal{E}_{\mathcal{C},\Phi_{u}},\mathcal{D}_{\mathcal{C},\Phi_{u}},\bigwedge_{i\in
I}Z_{i}=1\right]\geq p^{g(u)}(1-p)^{|\Phi_{u}|}\mathbb{P}\left[\bigwedge_{i\in
I\backslash U_{\mathcal{C}}}Z_{i}=1\right]\prod_{v\in
U_{\mathcal{C}}}\mathbb{P}[\mathcal{I}_{\mathcal{C},v}].$ (23)

Recall that $|U|=o((n^{k-2}p)^{-1})$ thus

$\displaystyle(1-p)^{|U|\binom{n}{k-2}}$
$\displaystyle\geq\exp\left(-|U|\binom{n}{k-2}\frac{p}{1-p}\right)\geq\exp(-o(1))=1-o(1).$
(24)

As the number of $k$-sets containing $v$ and a vertex in $U$ is at most
$|U|\binom{n}{k-2}$, by (24) for every $v\in U_{\mathcal{C}}$ we have
$\mathbb{P}[\mathcal{I}_{\mathcal{C},v}]=1-o(1)$. In addition we have
$|U_{\mathcal{C}}|\leq kg(u)=O(1)$, implying $\prod_{v\in
U_{\mathcal{C}}}\mathbb{P}[\mathcal{I}_{\mathcal{C},v}]=1-o(1)$. Together with
$|\Phi_{u}|\leq|U|\binom{n}{k-2}$ and (23) this implies

$\displaystyle\mathbb{P}\left[\mathcal{E}_{\mathcal{C},\Phi_{u}},\mathcal{D}_{\mathcal{C},\Phi_{u}}|\bigwedge_{i\in
I}Z_{i}=1\right]$
$\displaystyle=\frac{\mathbb{P}[\mathcal{E}_{\mathcal{C},\Phi_{u}},\mathcal{D}_{\mathcal{C},\Phi_{u}},\bigwedge_{i\in
I}Z_{i}=1]}{\mathbb{P}[\bigwedge_{i\in I}Z_{i}=1]}$
$\displaystyle\geq(1-o(1))p^{g(u)}(1-p)^{|U|\binom{n}{k-2}}\frac{\mathbb{P}[\bigwedge_{i\in
I\backslash U_{\mathcal{C}}}Z_{i}=1]}{\mathbb{P}[\bigwedge_{i\in I\backslash
U_{\mathcal{C}}}Z_{i}=1]}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:noedge}}}{{\geq}}(1-o(1))p^{g(u)}.$

Therefore in order to complete our estimate for the right hand side of (18) we
only need to establish $|\mathcal{F}_{u}|$. Recall that $\mathcal{F}_{u}$ is
the family of $g(u)$ sized subsets of $\Phi_{u}$ such that for every
$\mathcal{C}\in\mathcal{F}_{u}$ we have that for any pair of $k$-sets in
$\mathcal{C}$ are vertex disjoint except for $u$.

Since the size of the sets $U,V^{\prime}$ and $\\{w:g(w)=1\\}$ is $o(n)$, we
have

$|\Phi_{u}|\geq|U|\binom{(1-o(1))n}{k-2}.$

This in turn implies

$\binom{|\Phi_{u}|}{g(u)}\geq(1-o(1))\frac{|U|^{g(u)}}{g(u)!}\binom{n}{k-2}^{g(u)},$

as $\binom{(1-o(1))n}{k-2}=(1-o(1))\binom{n}{k-2}$.

Since the number of sets in $\binom{\Phi_{u}}{g(u)}$ where the two $k$-sets
overlap in a vertex other than $u$ is

$O\left(\left.|U|^{g(u)}\binom{n}{k-2}^{g(u)}\right/|U|\right)=o\left(\binom{|\Phi_{u}|}{g(u)}\right),$

we have

$|\mathcal{F}_{u}|=(1-o(1))\frac{|U|^{g(u)}}{g(u)!}\binom{n}{k-2}^{g(u)}$

and the statement follows.

∎

The previous lemma will be used to establish a lower bound on $C_{i}(t)$ when
$2\leq i\leq r$, and also for $C(t)$ when $r\geq 3$. However, as mentioned
earlier, a different approach is needed for $C_{1}(t)$ and $C(t)$ when $r=2$.
Roughly speaking, $C_{1}(t)$ increases in every step with the vertices
contained in the hyperedges of $F^{\prime}(t+1)$, and when $r=2$, $C(t)$
increases with vertices in the closed neighbourhoods of $C_{2}(t+1)\setminus
C_{2}(t)$. By considering how hyperedges intersect, the following lemma
ensures that a typical hyperedge contributes $k-1$ vertices to $C_{1}(t)$ and
an element in $C_{2}(t+1)\setminus C_{2}(t)$ typically contributes $2k-3$
vertices to $C(t)$, when $r=2$.

For a positive integer $\ell\geq 2$ a set of hyperedges
$e_{1},\ldots,e_{\ell}$ is called an intersecting $\ell$-tuple with respect to
$U$, if for every $1\leq i<\ell$, $e_{i}$ intersects $e_{i+1}$ in a vertex in
$V\setminus U$. If two hyperedges in an intersecting $\ell$-tuple intersect in
more than one vertex, which may include a vertex in $U$, we call it a
strongly-intersecting $\ell$-tuple with respect to $U$.

######  Lemma 30.

Consider $H_{k}(n,p)$ with vertex set $V=[n]$ and hyperedge set $E$. Let
$U,V^{\prime}\subseteq V$ be two disjoint subsets with $|V^{\prime}|=o(n)$
while $U$ satisfies both $|U|=\Omega(a_{c})$ and $|U|=o((n^{k-2}p)^{-1})$.
Denote by $E^{\prime}\subseteq E$ the set of hyperedges which contain exactly
one vertex in $U$ and no vertices in $V^{\prime}$. Assume that we are given a
set of hyperedges $F$, each containing at least one vertex in $V^{\prime}$ and
are vertex disjoint in $V\setminus(U\cup V^{\prime})$. Furthermore assume that
$|F|=O(|U|n^{k-1}p)$.

Then for any $\ell\leq r$ with probability $1-o(\exp(-|U|)$ we have that in
the hypergraph spanned by $E^{\prime}\cup F$ the number of intersecting
$(\ell+1)$-tuples and the number of strongly-intersecting $\ell$-tuples with
respect to $U\cup V^{\prime}$ is $o(|U|^{\ell}n^{\ell(k-2)+1}p^{\ell}).$

###### Proof.

Consider the following process to establish the set of intersecting
$(\ell+1)$-tuples and the strongly-intersecting $\ell$-tuples. Denote by
$\Phi_{U}$ the set of $k$-sets containing exactly one vertex in $U$, and no
vertices in $V^{\prime}$. Next we create the family $\mathcal{F}_{0}$
consisting of subsets of $\Phi_{U}\cup F$, which form an intersecting
$(\ell+1)$-tuple or a strongly-intersecting $\ell$-tuple. In the following we
will provide an algorithm which finds every intersecting $(\ell+1)$-tuple and
strongly-intersecting $\ell$-tuple reminiscent of the query-process in Section
3.2. Consider the elements $\mathcal{C}\in\mathcal{F}_{0}$ one by one, but we
do not query every element we consider. An element is queried only if
$\mathcal{C}\cap\Phi_{U}$ does not contain a hyperedge, which can be found in
a previously successfully queried element. In addition the element
$\mathcal{C}\in\mathcal{F}_{0}$ is successfully queried if it was queried and
$\mathcal{C}\subseteq E^{\prime}\cup F$. The first stage of the process is
complete, once every element in $\mathcal{F}_{0}$ has been considered. Let
$\mathcal{Y}_{0}$ be the set of hyperedges, which are found in a successfully
queried element.

For $i\geq 1$ denote by $\mathcal{Y}_{i}$ the set of hyperedges in
$E^{\prime}\cup F$, which intersect a hyperedge from $\mathcal{Y}_{i-1}$ in
$V\setminus(U\cup V^{\prime})$. Note that any intersecting $(\ell+1)$-tuple
and strongly-intersecting $\ell$-tuple must contain at least one hyperedge in
$\mathcal{Y}_{0}$ and any remaining hyperedges in
$\mathcal{Y}_{1},\ldots,\mathcal{Y}_{i}$ for some $i\leq\ell$. Denote by
$\mathcal{F}_{i}\subseteq\Phi_{U}\setminus\left(\bigcup_{j=0}^{i-1}\mathcal{Y}_{j}\right)$
the set of $k$-sets, which intersect a hyperedge in $\mathcal{Y}_{i-1}$ in a
vertex in $V\setminus(U\cup V^{\prime})$. For $1\leq i\leq\ell$ repeatedly
query every element of $\mathcal{F}_{i}$ to obtain $\mathcal{Y}_{i}$.

We start by obtaining an upper bound on $\mathbb{E}[|\mathcal{Y}_{0}|]$. Lemma
20 implies that $|\mathcal{Y}_{0}|$ is stochastically dominated by independent
Bernoulli random variables, and denote the sum of these random variables as
$Y_{0}$. Now both $|\Phi_{U}|p=O(|U|n^{k-1}p)$ and $|F|=O(|U|n^{k-1}p)$, which
together with $|U|n^{k-2}p=o(1)$ and $|U|=\omega(1)$ implies:

$\mathbb{E}[Y_{0}]=o\left(|U|^{\ell}n^{\ell(k-2)+1}p^{\ell}\right).$

Together with the concentration result in Theorem 3 we then have

$\mathbb{P}\left[Y_{0}=o\left(|U|^{\ell}n^{\ell(k-2)+1}p^{\ell}\right)\right]=1-\exp\left(-\omega\left(|U|^{\ell}n^{\ell(k-2)+1}p^{\ell}\right)\right).$

Since $\ell\leq r$ we have

$\displaystyle|U|^{\ell-1}n^{\ell(k-2)+1}p^{\ell}$
$\displaystyle=\Omega\left(\left(\frac{1}{nn^{r(k-2)}p^{r}}\right)^{(\ell-1)/(r-1)}(n^{k-2}p)^{\ell-1}n^{k-1}p\right)$
$\displaystyle=\Omega\left(\left(\frac{1}{n^{k-1}p}\right)^{(\ell-1)/(r-1)}n^{k-1}p\right)=\Omega(1),$
(25)

and thus

$\mathbb{P}\left[|\mathcal{Y}_{0}|=o\left(|U|^{\ell}n^{\ell(k-2)+1}p^{\ell}\right)\right]\geq\mathbb{P}\left[Y_{0}=o\left(|U|^{\ell}n^{\ell(k-2)+1}p^{\ell}\right)\right]=1-o\left(\exp\left(-|U|\right)\right).$

Similarly as before by Lemma 20 we have $|\mathcal{Y}_{i}\cap E^{\prime}|$ is
stochastically dominated by the binomial random variable
$Y_{i}=\mathrm{Bin}(|U|(k-1)|\mathcal{Y}_{i-1}|n^{k-2},p)$. Now conditional on
$|\mathcal{Y}_{i-1}|=o\left(|U|^{\ell}n^{\ell(k-2)+1}p^{\ell}\right)$ we have
$\mathbb{E}[Y_{i}]=o\left(|U|^{\ell}n^{\ell(k-2)+1}p^{\ell}\right)$ as
$|U|n^{k-2}p=o(1)$. Together with Theorem 3 and (25) we have

$\displaystyle\mathbb{P}\left[|\mathcal{Y}_{i}\cap
E^{\prime}|=o\left(|U|^{\ell}n^{\ell(k-2)+1}p^{\ell}\right)\mid|\mathcal{Y}_{i-1}|=o\left(|U|^{\ell}n^{\ell(k-2)+1}p^{\ell}\right)\right]$
$\displaystyle\quad\geq\mathbb{P}\left[Y_{i}=o\left(|U|^{\ell}n^{\ell(k-2)+1}p^{\ell}\right)\mid|\mathcal{Y}_{i-1}|=o\left(|U|^{\ell}n^{\ell(k-2)+1}p^{\ell}\right)\right]=1-o\left(\exp\left(-|U|\right)\right).$

In addition, as the hyperedges in $F$ are vertex disjoint in $V\setminus(U\cup
V^{\prime})$, we also have $|\mathcal{Y}_{i}\cap F|\leq k|\mathcal{Y}_{i-1}|$.
Therefore with probability $1-o(\exp(-|U|))$ all the $\mathcal{Y}_{i}$, for
$1\leq i\leq\ell$ have the right size and the result follows. ∎

###  5.3. Bounding trajectory

Similarly to the subcritical regime we establish a trajectory for the number
of infected vertices and in addition for the number of vertices with at least
$i$ active neighbours for $1\leq i\leq r$. Recall that
$|A(0)|=|C(0)|=(1+\varepsilon)a_{c}$ and let $0<\delta<1$ satisfy
$(1+\varepsilon)(1-\delta)>1$.

######  Definition 31.

Let $\eta$ and $a^{*}$ be as defined in (1) and (2). Set $c_{0}(t):=n$ for all
integers $t\geq 0$ and for $1\leq i\leq r$ let $c_{i}(0):=0$. Finally set
$c(-1):=0$ and $c(0):=|C(0)|$. Then for all integers $t\geq 0$ and $1\leq
i\leq r-1$ we define

$\displaystyle c_{i}(t+1)$
$\displaystyle:=\sum_{j=0}^{i-1}c_{j}(t)\frac{(c(t)-c(t-1))^{i-j}}{(i-j)!}\left(\binom{n}{k-2}p\right)^{i-j}+c_{i}(t);$
$\displaystyle c_{r}(t+1)$
$\displaystyle:=(1-\delta)\sum_{j=0}^{r-1}c_{j}(t)\frac{(c(t)-c(t-1))^{r-j}}{(r-j)!}\left(\binom{n}{k-2}p\right)^{r-j}+c_{r}(t);$
$\displaystyle c(t+1)$ $\displaystyle:=\eta c_{r}(t+1)+c(0).$

Finally let $\gamma(t):=c(t)/a^{*}$ for all integers $t\geq-1$ and call
$\gamma$ the trajectory associated with mild $r$-bootstrap percolation.

We also provide a simpler form for these values.

######  Claim 32.

For $0\leq i<r$ and $t\geq-1$ we have

$c_{i}(t+1)=\frac{c(t)^{i}}{i!}n\left(\binom{n}{k-2}p\right)^{i};$
$c_{r}(t+1)=(1-\delta)\frac{c(t)^{r}}{r!}n\left(\binom{n}{k-2}p\right)^{r};$

and

$c(t+1)=(1-\delta)\eta\frac{c(t)^{r}}{r!}n\left(\binom{n}{k-2}p\right)^{r}+c(0).$

###### Proof.

The proof is by induction. Note that the statement holds when $t=-1$ and when
$i=0$. Now assume the statement holds for $t$. If $1\leq i<r$, then the
induction hypothesis for the individual $c_{j}(t)$ when $j\leq i$ leads to

$\displaystyle c_{i}(t+1)$
$\displaystyle=\sum_{j=0}^{i-1}c_{j}(t)\frac{(c(t)-c(t-1))^{i-j}}{(i-j)!}\left(\binom{n}{k-2}p\right)^{i-j}+c_{i}(t)$
$\displaystyle=\sum_{j=0}^{i-1}\frac{c(t-1)^{j}}{j!}n\left(\binom{n}{k-2}p\right)^{j}\frac{(c(t)-c(t-1))^{i-j}}{(i-j)!}\left(\binom{n}{k-2}p\right)^{i-j}+\frac{c(t-1)^{i}}{i!}n\left(\binom{n}{k-2}p\right)^{i}$
$\displaystyle=n\left(\binom{n}{k-2}p\right)^{i}\left(\frac{c(t-1)^{i}}{i!}+\sum_{j=0}^{i-1}\frac{c(t-1)^{j}}{j!}\frac{(c(t)-c(t-1))^{i-j}}{(i-j)!}\right).$

For the first statement it only remains to show

$c(t-1)^{i}+i!\sum_{j=0}^{i-1}\frac{c(t-1)^{j}}{j!}\frac{(c(t)-c(t-1))^{i-j}}{(i-j)!}=c(t)^{i},$

which follows from the binomial theorem as the left hand side is equivalent to
the expansion of $((c(t)-c(t-1))+c(t-1))^{i}$. The proof for $c_{r}(t)$ is
analogous, from which $c(t)$ follows immediately. ∎

By an argument analogous to the proof of Claim 23, that is, replacing
$1+\delta$ and $\beta$ with $1-\delta$ and $\gamma$ respectively, we have

$\gamma(t+1)=(1-\delta)\frac{\gamma(t)^{r}}{r}+\gamma(0).$ (26)

We expect that $\gamma(t)$ does not have a maximum, or equivalently
$\gamma(t+1)-\gamma(t)$ is bounded from below.

From (26), we obtain the lower bound

$\displaystyle\gamma(t+1)-\gamma(t)$
$\displaystyle=(1-\delta)\frac{\gamma(t)^{r}-\gamma(t-1)^{r}}{r}$
$\displaystyle=(1-\delta)(\gamma(t)-\gamma(t-1))\sum_{j=0}^{r-1}\frac{\gamma(t)^{j}\gamma(t-1)^{r-j-1}}{r}$
$\displaystyle\geq(1-\delta)(\gamma(t)-\gamma(t-1))\gamma(t-1)^{r-1}.$

This implies that if there exists a $t$ such that
$\gamma(t-1)^{r-1}>(1-\delta)^{-1}$ or equivalently
$c(t-1)>a^{*}(1-\delta)^{-1/(r-1)}$, then the sequence $c(t)$ converges to
infinity. In fact, if $\gamma(t-1)^{r-1}\geq(1+\nu)(1-\delta)^{-1}$ for some
fixed $\nu>0$, then $c(\tau+1)-c(\tau)$ increases by at least a factor of
$1+\nu$ in every step $\tau\geq t$.

In order to prove our result we require not only that $\gamma(t)$ does not
have a maximum, but also that the one step change in each step is sufficiently
large to show appropriate tail bounds on a step by step basis.

######  Lemma 33.

There exists $\Delta>0$ independent of $n$ such that for every $t\geq 0$ we
have $\gamma(t+1)-\gamma(t)>\Delta$.

###### Proof.

Using (26) and that
$\gamma(0)=(1+\varepsilon)a_{c}/a^{*}=(1+\varepsilon)(1-r^{-1})$ we have

$\displaystyle\gamma(t+1)-\gamma(t)$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:nuratio}}}{{=}}(1-\delta)\frac{\gamma(t)^{r}}{r}+\gamma(0)-\gamma(t)$
$\displaystyle=(1-\delta)\frac{\gamma(t)^{r}}{r}-\gamma(t)+(1+\varepsilon)\left(1-\frac{1}{r}\right).$

For $x\geq 0$ the function $(1-\delta)x^{r}/r-x$ has its minimum at
$x=(1-\delta)^{-1/(r-1)}$, implying

$\displaystyle(1-\delta)\frac{\gamma(t)^{r}}{r}-\gamma(t)+(1+\varepsilon)\left(1-\frac{1}{r}\right)$
$\displaystyle\geq\left(\frac{1}{1-\delta}\right)^{1/(r-1)}\left(\frac{1}{r}-1\right)+(1+\varepsilon)\left(1-\frac{1}{r}\right)$
$\displaystyle=\left(1+\varepsilon-\left(\frac{1}{1-\delta}\right)^{1/(r-1)}\right)\left(1-\frac{1}{r}\right)$
$\displaystyle>\left(1+\varepsilon-\frac{1}{1-\delta}\right)\left(1-\frac{1}{r}\right).$

Recall that $(1+\varepsilon)(1-\delta)>1$ and thus

$\Delta:=\left(1+\varepsilon-\frac{1}{1-\delta}\right)\left(1-\frac{1}{r}\right)=\left(\frac{(1+\varepsilon)(1-\delta)-1}{1-\delta}\right)\left(1-\frac{1}{r}\right)>0.$

∎

Therefore the value of $\gamma(t)$ increases by at least $\Delta$ in every
step. Thus for any $\nu>0$, in a bounded number of steps, depending only on
$\varepsilon,\delta$ and $\nu$, we have
$\gamma(t-1)>((1+\nu)/(1-\delta))^{1/(r-1)}$.

In the last claim of this section we show that if $c(t)-c(t-1)$ is small then
so is $c(t)$.

######  Claim 34.

Assume that $c(t)=c(t-1)+o((n^{k-2}p)^{-1})$. Then we have

$c(t)=o((n^{k-2}p)^{-1}).$

###### Proof.

Using $c(t)\leq c(t-1)+o((n^{k-2}p)^{-1})$, either $c(t)=o((n^{k-2}p)^{-1})$
or $c(t)=O(c(t-1))$. We only have to show that the statement holds in the
latter case. By Claim 32 we have

$c(t)=\Theta\left(c(t-1)^{r}n(n^{k-2}p)^{r}\right),$

as $c(0)=O(c(\tau)^{r}n((n^{k-2}p)^{r})$ for any $\tau\geq 0$. Together with
$c(t)=O(c(t-1))$ this implies

$c(t-1)^{r}=O\left(c(t-1)n^{-1}(n^{k-2}p)^{-r}\right)$

or equivalently

$c(t-1)=O\left((n^{k-2}p)^{-1}(n^{k-1}p)^{-1/(r-1)}\right)=o((n^{k-2}p)^{-1}),$

and we can deduce $c(t)=o((n^{k-2}p)^{-1})$ in this case as well. ∎

###  5.4. Following the trajectory

In this section we show that as long as the number of vertices added to each
of the classes in the previous steps stays above its trajectory this also
holds in the next step. We start by providing the definition for the size of
$\widehat{C}^{\prime}(t)$,

$|\widehat{C}^{\prime}(t+1)|=\left\\{\begin{array}[]{ll}\min\\{c(t),|C(t)|\\}-|\widehat{C}(t)|&\mbox{
if }|C(t)\setminus\widehat{C}(t)|<(n^{k-2}p\zeta)^{-1}\\\
(n^{k-2}p\zeta)^{-1}&\mbox{ if
}(n^{k-2}p\zeta)^{-1}\leq|C(t)\setminus\widehat{C}(t)|<(n^{k-2}p)^{-1}\zeta^{1/2}\\\
(n^{k-2}p)^{-1}\zeta^{1/2}&\mbox{ if
}(n^{k-2}p)^{-1}\zeta^{1/2}\leq|C(t)\setminus\widehat{C}(t)|,\end{array}\right.$
(27)

where $\zeta=(n^{k-1}p)^{1/(r+1)}$.

Next we calculate the one step expected increase in the size of the sets
$C_{i}(t)$.

######  Claim 35.

Assume that $c(t)\leq|C(t)|\leq c(t-1)+(n^{k-2}p)^{-1}/\zeta$ and for every
$0\leq i<r$ we have $|C_{i}(t)|\geq(1-o(1))c_{i}(t)$. Then

$\mathbb{E}[|C_{r}(t+1)\setminus
C_{r}(t)|]\geq(1-o(1))(1-\delta)^{-1}(c_{r}(t+1)-c_{r}(t)).$

If in addition $|C_{i}(t)|\leq c_{i}(t+1)$ for $2\leq i<r$, then we have

$\mathbb{E}[|C_{i}(t+1)\setminus C_{i}(t)|]\geq(1-o(1))(c_{i}(t+1)-c_{i}(t)).$

###### Proof.

Recall that
$|\widehat{C}^{\prime}(t+1)|\geq\min\\{c(t),|C(t)|\\}-|\widehat{C}(t)|\geq
c(t)-c(t-1).$ We are exposing hyperedges which contain exactly one vertex in
$\widehat{C}^{\prime}(t+1)$ and no vertex in $C(t)$. By Claim 34 we have
$|C(t)|=o((n^{k-2}p)^{-1})=o(n)$, thus for $2\leq i\leq r$

$\mathbb{E}[|C_{i}(t+1)\setminus
C_{i}(t)|]\geq\sum_{j=0}^{i-1}(1-o(1))\frac{(c(t)-c(t-1))^{i-j}}{(i-j)!}\left(\binom{n}{k-2}p\right)^{i-j}|C_{j}(t)\setminus(C_{j+1}(t)\cup
C(t))|.$ (28)

As $c(t)-c(t-1)=o((n^{k-2}p)^{-1})$, we have

$\frac{(c(t)-c(t-1))^{i-j}}{(i-j)!}\left(\binom{n}{k-2}p\right)^{i-j}$

is monotone increasing in $j$. Therefore removing an element of
$C_{j}(t)\setminus(C_{j+1}(t)\cup C(t))$, for some $0\leq j\leq i-1$ will only
decrease the value of (28). Then for any sets $C_{j}^{\prime}\subseteq
C_{j}(t)\setminus(C_{j+1}^{\prime}\cup C(t))$ for $0\leq j\leq i-1$ where
$C_{i}^{\prime}(t)=C_{i}(t)$ we have

$\displaystyle\mathbb{E}[|C_{i}(t+1)\setminus C_{i}(t)|]$
$\displaystyle\geq\sum_{j=0}^{i-1}(1-o(1))\frac{(c(t)-c(t-1))^{i-j}}{(i-j)!}\left(\binom{n}{k-2}p\right)^{i-j}|C_{j}(t)\setminus(C_{j+1}(t)\cup
C(t))|$
$\displaystyle\geq\sum_{j=0}^{i-1}(1-o(1))\frac{(c(t)-c(t-1))^{i-j}}{(i-j)!}\left(\binom{n}{k-2}p\right)^{i-j}|C_{j}^{\prime}(t)|.$

Assume that for every $0\leq j\leq i-1$ one can construct $C_{j}^{\prime}$
such that for $0\leq j\leq i-1$ we have
$|C_{j}^{\prime}|\geq(1-o(1))c_{j}(t)$. Then we have

$\displaystyle\mathbb{E}[|C_{i}(t+1)\setminus C_{i}(t)|]$
$\displaystyle\geq\sum_{j=0}^{i-1}(1-o(1))\frac{(c(t)-c(t-1))^{i-j}}{(i-j)!}\left(\binom{n}{k-2}p\right)^{i-j}c_{j}(t).$

The statement then follows as by definition this last term is
$(1-o(1))(c_{i}(t+1)-c_{i}(t))$, when $2\leq i<r$ and
$(1-o(1))(1-\delta)^{-1}(c_{r}(t+1)-c_{r}(t))$ when $i=r$.

In the remainder of the proof we focus on the construction of the
aforementioned $C_{j}^{\prime}$ and will consider two cases when $t=0$ and
$t>0$.

If $t=0$, then $C_{0}(0)=V\setminus C(0)$ and for $1\leq j\leq i-1$ we have
$C_{j}(0)=\emptyset$. Setting $C_{j}^{\prime}=C_{j}(0)$ for $0\leq j\leq i-1$
implies that $|C_{j}^{\prime}(t)|\geq(1-o(1))c_{j}(t)$.

Now consider $t>0$. We will select the sets $C_{j}^{\prime}$ consecutively
starting with $j=i-1$ and consider the remaining values of $j$ in a decreasing
order. For every $0\leq j\leq i-1$ we choose $C_{j}^{\prime}$ to contain an
arbitrary subset of $C_{j}(t)\setminus(C_{j+1}^{\prime}\cup C(t))$, with size
$(1-o(1))c_{j}(t)$. In the following we show that such a subset exists, using
induction on $j$.

By Claim 34 we have $|C(t)|=o((n^{k-2}p)^{-1})$. In addition, for $0\leq j\leq
r-1$

$c_{j}(t)\geq
c_{r-1}(1)=\Omega(a_{c}^{r-1}n(n^{k-2}p)^{r-1})=\Omega((n^{k-2}p)^{-1}),$

and thus

$|C_{j}(t)\setminus C(t)|\geq(1-o(1))c_{j}(t).$ (29)

Note that $|C_{i}(t)\setminus C(t)|\leq c_{i}(t+1)$, as either $i<r$ and this
follows from our assumption $|C_{i}(t)|\leq c_{i}(t+1)$ or $i=r$, in which
case it is a consequence of $C_{r}(t)\subseteq C(t)$. Recall that $c_{j+1}(t)$
is monotone increasing in $t$, therefore using (29) we have for $0\leq j\leq
i-1$

$|C_{j}(t)\setminus(C_{j+1}^{\prime}\cup C(t))|\geq|C_{j}(t)\setminus
C(t)|-|C_{j+1}^{\prime}\setminus C(t)|\geq(1-o(1))c_{j}(t)-c_{j+1}(t+1).$

By Claim 32 and since $c(t)-c(t-1)=o((n^{k-2}p)^{-1})$ for $0\leq j\leq i-1$
we have

$c_{j+1}(t+1)-c_{j+1}(t)=O\left((c(t)-c(t-1))c(t)^{j}n(n^{k-2}p)^{j+1}\right)=o(c(t)^{j}n(n^{k-2}p)^{j})=o(c_{j}(t)).$

Together with Claim 34 a repeated application of Claim 32 gives for $0\leq
j\leq i-1$ that

$c_{j+1}(t)=O(c(t-1)n^{k-2}pc_{j}(t))=o(c_{j}(t))$

and we conclude that $|C_{j}(t)\setminus(C_{j+1}^{\prime}\cup
C(t))|\geq(1-o(1))c_{j}(t)$ for every $0\leq j\leq i-1$. Thus we were able to
identify sets $C_{j}^{\prime}\subseteq C_{j}(t)\setminus(C(t)\cup
C_{j+1}^{\prime})$ such that $|C_{j}^{\prime}|\geq(1-o(1))c_{j}(t)$,
completing the proof. ∎

Define $\Xi(0)=\emptyset$ and $\Xi(t+1)=\Xi(t)\cup\Xi^{\prime}(t+1)$ where
$\Xi^{\prime}(t+1)\subseteq F^{\prime}(t+1)$ is the set of hyperedges which
intersect another hyperedge of $F^{\prime}(t+1)$ both in a vertex of
$\widehat{C}^{\prime}(t)$ and in a vertex of $V\setminus C(t)$. In the
following lemma we consider the one step change in our random variables.

######  Lemma 36.

Assume $c(t)\leq|C(t)|\leq c(t-1)+(n^{k-2}p)^{-1}/\zeta$ and that for every
$0\leq i<r$ we have $|C_{i}(t)|\geq(1-o(1))c_{i}(t)$. If
$|F(t)|\leq(1+o(1))c(t)\binom{n}{k-1}p$ and
$\Xi(t)=o\left(c(t)n^{k-1}p\right)$, then with probability

$1-\exp(-\delta^{2}(c(t+1)-c(t))/16)-o(\exp(-(c(t)-c(t-1))))$

the following events hold.

  1. (I)

For every $0\leq i<r$ we have $|C_{i}(t+1)|\geq(1-o(1))c_{i}(t+1)$;

  2. (II)

$|C(t+1)|-|C(t)|\geq c(t+1)-c(t)$;

  3. (III)

$|F(t+1)|\leq(1+o(1))c(t+1)\binom{n}{k-1}p$;

  4. (IV)

$\Xi(t+1)=o\left(c(t+1)n^{k-1}p\right)$.

###### Proof.

By definition
$|\widehat{C}^{\prime}(t+1)|\geq\min\\{c(t),|C(t)|\\}-|\widehat{C}(t)|\geq
c(t)-c(t-1).$

We start by proving (I). This holds deterministically when $i=0$ as for every
$t\geq 0$ we have $c_{0}(t)=n$ and $|C_{0}(t)|=|V\setminus C(0)|=(1-o(1))n$.

Next for $i=1$, let $\mathcal{L}$ denote the set of hyperedges in
$F^{\prime}(t+1)$, which contain only elements in $C_{0}(t)\setminus
C_{1}(t)$. By Claim 34 we have

$|C_{1}(t)|\leq k|F(t)|=o(n)$ (30)

and thus by Theorem 3 with probability $1-o(\exp(-(c(t)-c(t-1))))$ we have

$|\mathcal{L}|\geq(1-o(1))(c(t)-c(t-1))\binom{n}{k-1}p.$

Recall that $|\widehat{C}^{\prime}(t+1)|\geq c(t)-c(t-1)$, which together with
Lemma 33 implies $|\widehat{C}^{\prime}(t+1)|=\Omega(a^{*})=\Omega(a_{c})$. In
addition Claim 34 implies $|\widehat{C}^{\prime}(t+1)|\leq
c(t-1)+o((n^{k-2}p)^{-1})=o((n^{k-2}p)^{-1})$. Together with (30) we have
verified that the conditions for Lemma 30 are met when
$U=\widehat{C}^{\prime}(t+1)$,
$V^{\prime}=C_{1}(t)\setminus\widehat{C}^{\prime}(t+1)$ and $F=\emptyset$. So
with probability $1-o(\exp(-(c(t)-c(t-1))))$ almost every pair of hyperedges
in $\mathcal{L}$ is vertex disjoint (except possibly for a vertex in
$\widehat{C}^{\prime}(t+1)$), and we not only have

$|C_{1}(t+1)\setminus C_{1}(t)|\geq(1-o(1))(c_{1}(t+1)-c_{1}(t)),$

but also (IV).

Now fix $2\leq i\leq r$. For $u\in V\setminus(C_{i}(t)\cup C(t))$ let
$X_{u,i}$ be the indicator random variable for the event $u\in C_{i}(t+1)$.
Let $X_{i}=\sum_{u\in V\setminus(C_{i}(t)\cup C(t))}X_{u,i}$. Assign for every
$u\in V\setminus(C_{i}(t)\cup C(t))$ an independent Bernoulli random variable
$\widehat{X}_{u,i}$ such that

$\mathbb{P}[\widehat{X}_{u,i}=1]=(1-o(1))\frac{(c(t)-c(t-1))^{i-j}}{(i-j)!}\left(\binom{n}{k-2}p\right)^{i-j},$

and denote by $\widehat{X}_{i}=\sum_{u\in V\setminus(C_{i}(t)\cup
C(t))}\widehat{X}_{u,i}$. Then
$\mathbb{E}[\widehat{X}_{u,i}]=(1-o(1))\mathbb{E}[X_{u,i}]$ and thus also
$\mathbb{E}[\widehat{X}_{i}]=(1-o(1))\mathbb{E}[X_{i}]$.

Define $Z_{u,i}=1-X_{u,i}$ and $\widehat{Z}_{u,i}=1-\widehat{X}_{u,i}$.
Similarly as before we will also need the sums $Z_{i}=\sum_{u\in
V\setminus(C_{i}(t)\cup C(t))}Z_{u,i}$ and $\widehat{Z}_{i}=\sum_{u\in
V\setminus(C_{i}(t)\cup C(t))}\widehat{Z}_{u,i}$.

Next we apply Lemma 29. Recall that $\widehat{C}^{\prime}(t+1)$ satisfies both
$|\widehat{C}^{\prime}(t+1)|=\Omega(a_{c})$ and
$|\widehat{C}^{\prime}(t+1)|=o((n^{k-2}p)^{-1})$. Also by (30) and
$|C(0)|=o(n)$ we have $|C(t)|=o(n)$. Set $U=\widehat{C}^{\prime}(t+1)$,
$V^{\prime}=C(t)\setminus\widehat{C}^{\prime}(t+1)$,
$W=V\setminus(C_{i}(t)\cup U\cup V^{\prime})$ and for $w\in
W\cap(C_{j}(t)\setminus C_{j+1}(t))$ let $g(w)=i-j$. By (30) we also have
$|C_{i-1}(t)\setminus C_{i}(t)|\leq|C_{1}(t)|=o(n)$, and thus $|\\{w\in
W:g(w)=1\\}|=o(n)$. Then Lemma 29 implies for every $I\subseteq W$ that

$\mathbb{E}\left[\prod_{u\in I}Z_{u,i}\right]\leq\mathbb{E}\left[\prod_{u\in
I}\widehat{Z}_{u,i}\right].$

Note that
$\mathrm{Var}(\widehat{Z}_{i})=\mathrm{Var}(\widehat{X}_{i})\leq\mathbb{E}[\widehat{X}_{i}]$
thus Lemma 4 implies for any $\lambda>0$ that

$\displaystyle\mathbb{P}\left[X_{i}\leq(1-\lambda)\mathbb{E}[\widehat{X}_{i}]\right]$
$\displaystyle=\mathbb{P}\left[Z_{i}\geq\mathbb{E}[\widehat{Z}_{i}]+\lambda\mathbb{E}[\widehat{X}_{i}]\right]$
$\displaystyle\leq\exp\left(-(1-o(1))\lambda^{2}\frac{\mathbb{E}[\widehat{X}_{i}]^{2}}{2(\mathbb{E}[\widehat{X}_{i}]+\mathbb{E}[\widehat{X}_{i}]/3)}\right)$
$\displaystyle\leq\exp\left(-\lambda^{2}\frac{\mathbb{E}[\widehat{X}_{i}]}{3}\right).$
(31)

In order to complete the proof of (I) we consider the case $1<i<r$. Let
$\lambda$ satisfy

$\left(\frac{c(t+1)-c(t)}{c_{i}(t+1)-c_{i}(t)}\right)^{1/2}\ll\lambda\ll 1,$

and note that such a $\lambda$ exists. Note that we may assume that
$|C_{i}(t)|\leq c_{i}(t+1)$, as otherwise (I) follows. Then by (31), Claim 35
and $\mathbb{E}[\widehat{X}_{i}]=(1-o(1))\mathbb{E}[X_{i}]$ we have

$\displaystyle\mathbb{P}[X_{i}\leq(1-o(1))(1-\lambda)(c_{i}(t+1)-c_{i}(t))]$
$\displaystyle\leq\exp\left(-(1-o(1))\lambda^{2}\frac{(c_{i}(t+1)-c_{i}(t))}{3}\right)$
$\displaystyle=o\left(\exp\left(-\delta^{2}(c(t+1)-c(t))/16\right)\right)$

due to our choice of $\lambda$. Completing the proof of (I).

Now if $i=r$ we select $\lambda=\delta/2$. Therefore by (31), Claim 35 and

$\mathbb{E}[\widehat{X}_{i}]=(1-o(1))\mathbb{E}[X_{i}]=(1-o(1))\mathbb{E}[|C_{i}(t+1)\setminus
C_{i}(t)|]$

we have

$\mathbb{P}\left[X_{r}\leq\left(1+\frac{\delta}{2}\right)(c_{r}(t+1)-c_{r}(t))\right]\leq\exp\left(-(1+o(1))\delta^{2}\frac{c(t+1)-c(t)}{12}\right).$

When $r\geq 3$ one can derive (II) as $C(t+1)\setminus
C(t)=C_{r}(t+1)\setminus C_{r}(t)$, for every $t\geq 0$.

On the other hand, if $r=2$, we have $C(t+1)\setminus C(t)$ consists of the
vertices in $C_{2}(t+1)\setminus C_{2}(t)$ and their neighbours in the
hypergraph spanned by $F(t+1)$. Our goal is to show that with probability
$1-o(\exp(c(t)-c(t-1)))$ almost every vertex in $C_{2}(t+1)\setminus C_{2}(t)$
is responsible for $2k-3$ infections. For a vertex to be involved in less than
$2k-3$ vertices becoming infected, it has to be either part of an intersecting
3-tuple, a strongly intersecting 2-tuple or within a hyperedge of $\Xi(t)$.
Using Theorem 3 and

$n^{k-1}pc(t)(c(t)-c(t-1))n^{k-2}p=\Theta(c(t)-c(t-1))=\Theta(c_{2}(t)-c_{2}(t-1)),$

we have with probability $1-o(\exp(-(c(t)-c(t-1))))$ that the number of
hyperedges intersecting $\Xi(t)$ is $o(c_{2}(t)-c_{2}(t-1))$. Note that in
$F(t)\setminus\Xi(t)$ either every vertex is infected or exactly one vertex is
infected, and thus every hyperedge in $F(t)\setminus\Xi(t)$, which still
contains uninfected vertices, must be vertex disjoint, except for possibly a
vertex in $\widehat{C}(t)$. By Lemma 30 with probability
$1-o(\exp(-(c(t)-c(t-1)))$ both the number of intersecting 3-tuples and the
number of strongly intersecting 2-tuples, which rely on the hyperedges in
$F^{\prime}(t+1)$ and $F(t)\setminus\Xi(t)$ is $o(c_{2}(t+1)-c_{2}(t))$.
Therefore with probability $1-o(\exp(-(c(t)-c(t-1)))$ almost every vertex in
$C_{2}(t+1)\setminus(C_{2}(t)\cup C(t))$ results in $2k-3$ infections,
completing the proof of (II).

Finally, by Theorem 3 we have with probability $1-o(\exp(-(c(t)-c(t-1)))$ we
have

$F^{\prime}(t+1)\leq(1+o(1))(c(t)-c(t-1))\binom{n}{k-1}p,$

proving (III). ∎

###  5.5. The last two steps

In the following two lemmas we consider what happens in mild $r$-bootstrap
percolation after $|C(t)\setminus\widehat{C}(t)|$ becomes sufficiently large,
and show that almost every vertex becomes infected in the next two steps.

######  Lemma 37.

Consider $H_{k}(n,p)$ with vertex set $V=[n]$ and hyperedge set $E$. Let
$U,V^{\prime}\subseteq V$ be two disjoint subsets with $|V^{\prime}|=o(n)$
while $|U|=(n^{k-2}p)^{-1}/\zeta$. Denote by $E^{\prime}\subseteq E$ the set
of hyperedges which contain exactly one vertex in $U$ and no vertices in
$V^{\prime}$. Denote by $E^{\prime}\subseteq E$ the set of hyperedges which
contain exactly one vertex in $U$ and no vertex in $V^{\prime}$. Then with
probability $1-o(\exp(-a^{*}))$ the number of vertices in $V\setminus(U\cup
V^{\prime})$ with at least $r$ neighbours in $U$, in the subgraph spanned by
$E^{\prime}$, is at least $(n^{k-2}p)^{-1}\zeta^{1/2}$ and
$|E^{\prime}|=o(n)$.

###### Proof.

For $u\in V\setminus(U\cup V^{\prime})$ let $X_{u}$ be the indicator random
variable that $u$ has at least $r$ neighbours in $U$. Let $\widehat{X}_{u}$ be
independent Bernoulli random variables such that

$\mathbb{P}[\widehat{X}_{u}=1]=(1-o(1))\frac{|U|^{r}}{r!}\left(\binom{n}{k-2}p\right)^{r}.$

In addition, define $Z_{u}=1-X_{u}$ and $\widehat{Z}_{u}=1-\widehat{X}_{u}$,
and denote by $X,\widehat{X},Z,\widehat{Z}$ the sum over $V\setminus(U\cup
V^{\prime})$ of the $X_{u},\widehat{X}_{u},Z_{u},\widehat{Z}_{u}$,
respectively. Note that $|U|=o((n^{k-2}p)^{-1})$ and

$|U|=\frac{1}{n^{k-2}p\zeta}=\frac{1}{n^{k-2}p(n^{k-1}p)^{1/(r+1)}}=\omega\left(\left(\frac{1}{n\left(n^{k-2}p\right)^{r}}\right)^{1/(r-1)}\right)=\omega(a^{*}).$

Then by Lemma 29 (setting $g(w)=r$ for every $w\in V\setminus(U\cup
V^{\prime})$) and using Lemma 4 with
$\mathrm{Var}(\widehat{Z})=\mathrm{Var}(\widehat{X})\leq\mathbb{E}[\widehat{X}]$
implies

$\displaystyle\mathbb{P}\left[X\leq\mathbb{E}[\widehat{X}]/2\right]$
$\displaystyle=\mathbb{P}\left[Z\geq\mathbb{E}[\widehat{Z}]+\mathbb{E}[\widehat{X}]/2\right]\leq\exp\left(-\frac{\mathbb{E}[\widehat{X}]}{12}\right).$

The first part of the statement follows as

$\displaystyle\mathbb{E}[\widehat{X}]=(1-o(1))n\binom{|U|}{r}\left(\binom{n}{k-2}p\right)^{r}$
$\displaystyle=\Omega\left(n\left(\frac{1}{n^{k-2}p\zeta}\right)^{r}(n^{k-2}p)^{r}\right)=\Omega\left(\frac{1}{(n^{k-2}p)}\zeta\right)=\omega(a^{*}).$

As for the bound on $|E^{\prime}|$, this follows from Theorem 3 and
$n/\zeta\geq(n^{k-2}p\zeta)^{-1}=\omega(a^{*})$.

∎

######  Lemma 38.

Consider $H_{k}(n,p)$ with vertex set $V=[n]$ and hyperedge set $E$. Let
$U,V^{\prime}\subseteq V$ be two disjoint subsets with $|V^{\prime}|=o(n)$
while $|U|=(n^{k-2}p)^{-1}\zeta^{1/2}$. Denote by $E^{\prime}\subseteq E$ the
set of hyperedges which contain exactly one vertex in $U$ and no vertex in
$V^{\prime}$. Then with probability $1-o(\exp(-a^{*}))$ there are $o(n)$
vertices in $V\setminus(U\cup V^{\prime})$ which have less than $r$ neighbours
in $U$, within the subgraph spanned by $E^{\prime}$.

###### Proof.

Consider an arbitrary ordering on vertices in $V\setminus(U\cup V^{\prime})$,
and denote the $i$-th element by $v_{i}$. Let $Z_{i}$ be the indicator random
variable that $v_{i}$ has less than $r$ neighbours in $U$. Define the
martingale $M_{0}=0$ and for $i\geq 1$

$M_{i}=M_{i-1}+Z_{i}-\mathbb{E}[Z_{i}\mid Z_{1},\ldots,Z_{i-1}].$

Let $(z_{1},...,z_{i-1})\in\\{0,1\\}^{n}$ such that
$\sum_{j=1}^{i-1}z_{j}=o(n)$ and for $\ell=0,1$ denote by
$W_{\ell}=\\{j<i:z_{j}=\ell\\}$. Let $\Phi$ be the set of $k$-sets, which
contain a vertex in $U$, a vertex $v_{j}$ with $j<i$ such that $z_{j}=1$, and
no vertex in $V^{\prime}$, that is, $\Phi$ is the set of $k$-sets which are
exposed and contain a vertex in $W_{1}$. Finally for $\Psi\subseteq\Phi$ let
$\mathcal{E}_{\Psi}$ be the event that $F^{\prime}(t+1)\cap\Phi=\Psi$. Then,
for any $\Psi$ such that $\mathcal{E}_{\Psi}\subseteq\bigwedge_{j\in
W_{1}}Z_{j}=z_{j}$, by applying the FKG inequality (Thyeorem 6) in the
conditional probability space $\mathcal{E}_{\Psi}$ we have

$\mathbb{E}\left[Z_{i}\mid\bigwedge_{j=1}^{i-1}Z_{j}=z_{j},\mathcal{E}_{\Psi}\right]=\mathbb{E}\left[Z_{i}\mid\bigwedge_{j\in
W_{0}}Z_{j}=z_{j},\mathcal{E}_{\Psi}\right]\leq\mathbb{E}[Z_{i}\mid\mathcal{E}_{\Psi}]\leq\mathbb{E}[Z_{i}\mid\mathcal{E}_{\emptyset}],$

where in the last step we use that removing hyperedges from the hypergraph
increases the probability of the event $\\{Z_{i}=1\\}$. As this holds for
every $\Psi\subseteq\Phi$ satisfying
$\mathcal{E}_{\Psi}\subseteq\bigwedge_{j\in W_{1}}Z_{j}=z_{j}$ and exposing
the hyperedges within $\Phi$ determines the values of $\\{Z_{j}\\}_{j\in
W_{1}}$ we also have

$\mathbb{E}\left[Z_{i}\mid\bigwedge_{j=1}^{i-1}Z_{j}=z_{j}\right]\leq\mathbb{E}[Z_{i}\mid\mathcal{E}_{\emptyset}].$
(32)

For $u\in U$ let $\mathcal{N}_{u}$ be the event that $u$ is a neighbour of
$v_{i}$. Since the event $\mathcal{E}_{\emptyset}$ excludes every hyperedge,
which contains one of tbe $o(n)$ vertices associated with $W_{1}$ we have

$\mathbb{P}[\mathcal{N}_{u}\mid\mathcal{E}_{\emptyset}]\geq
1-(1-p)^{(1-o(1))\binom{n}{k-2}}\geq
1-\exp\left((1-o(1))\binom{n}{k-2}p\right)=(1-o(1))\binom{n}{k-2}p.$

Note that in the conditional space $\mathcal{E}_{\emptyset}$ the events
$\mathcal{N}_{u}$ are mutually independent, as each hyperedge contains one
vertex in $u$. In addition a vertex can have at most $r-1$ neighbours in $U$
when $Z_{i}=1$. Since the expected number of vertices $u\in U$ for which
$\mathcal{N}_{u}$ holds is $\Omega(\zeta^{1/2})$ by Theorem 3 we have

$\mathbb{P}[Z_{i}=1\mid\mathcal{E}_{\emptyset}]\leq e^{-\zeta^{1/4}}.$ (33)

Next we introduce a stopping time for the martingale

$M_{i}^{\prime}=\left\\{\begin{array}[]{ll}M_{i}&\mbox{if
}\sum_{j=1}^{i-1}Z_{j}\leq(na_{c})^{1/2}+ne^{-\zeta^{1/4}}\quad\mbox{and}\quad
M_{i-1}^{\prime}\leq(na_{c})^{1/2}\\\ M_{i-1}^{\prime}&\mbox{if
}\sum_{j=1}^{i-1}Z_{j}>(na_{c})^{1/2}+ne^{-\zeta^{1/4}}\quad\mbox{or }\quad
M_{i-1}^{\prime}>(na_{c})^{1/2}.\end{array}\right.$

Azuma’s inequality (Theorem 7) implies that

$\mathbb{P}[M^{\prime}_{|V^{\prime}\setminus
U|}>(na_{c})^{1/2}]\leq\exp\left(-a_{c}/2\right)$

and thus we have with probability $1-e^{-a_{c}/2}$ that
$M_{i}^{\prime}\leq(na_{c})^{1/2}$ for every $1\leq i\leq|V\setminus(U\cup
V^{\prime})|$.

Now assume $M_{i}^{\prime}\leq(na_{c})^{1/2}$ for every $1\leq
i\leq|V\setminus(U\cup V^{\prime})|$. We will show inductively that
$M_{i}=M_{i}^{\prime}$ for every $0\leq i\leq|V\setminus(U\cup V^{\prime})|$.
Clearly this holds if $i=0$. Using the induction hypothesis for $i-1$ together
with (32) and (33) implies

$\sum_{j=1}^{i-1}Z_{j}\leq(na_{c})^{1/2}+ne^{-\zeta^{1/4}},$

and thus $M_{i}=M_{i}^{\prime}$. Using $M_{|V\setminus(U\cup
V^{\prime})|}=M_{|V\setminus(U\cup V^{\prime})|}^{\prime}\leq(na_{c})^{1/2}$
an analogous argument gives

$\sum_{j=1}^{|V\setminus(U\cup
V^{\prime})|}Z_{j}\leq(na_{c})^{1/2}+ne^{-\zeta^{1/4}}=o(n),$

completing the proof. ∎

###  5.6. Proof of Theorem 2 $(ii)$

###### Proof of Theorem 2 $(ii)$.

Recall that $\zeta=(n^{k-1}p)^{1/(r+1)}$ and note that
$(n^{k-2}p)^{-1}/\zeta=\omega(a^{*})$. Denote by $t_{0}$ the first step $t$
such that $|C(t)\setminus\widehat{C}(t)|\geq(n^{k-2}p)^{-1}/\zeta$. We will
apply Lemma 36 repeatedly until step $t_{0}$. Note that if we assume that the
statement of Lemma 36 holds for every step $\tau\leq t$ for some $t<t_{0}-1$
then, as this implies $|\widehat{C}(t)|=c(t)$, the conditions of Lemma 36 are
satisfied in the following step as well. By Lemma 33 after a bounded number of
steps we have $(c(t+1)-c(t))/(c(t)-c(t-1))>1+\nu$ for some fixed $\nu$.
Therefore there exists a step $t_{1}$, such that
$c(t_{1}+1)-c(t_{1})\geq(n^{k-2}p)^{-1}/\zeta$. Under the assumption that the
statement of Lemma 36 holds for every step $\tau\leq t_{0}$ we also have
$t_{0}\leq t_{1}$.

Next we establish the probability that the statement of Lemma 36 holds in
every step up to $t_{0}$. By the union bound this probability is at least

$1-\sum_{t=0}^{\infty}\exp(-\delta^{2}(c(t+1)-c(t))/16)-o(\exp(-(c(t)-c(t-1))).$

Again using the fact that after a bounded number of steps we have that
$(c(t+1)-c(t))/(c(t)-c(t-1))>1+\nu$ for some fixed $\nu$ and since Lemma 33
implies $c(t+1)-c(t)=\Omega(a^{*})$ we conclude

$1-\sum_{t=0}^{\infty}\exp(-\delta^{2}(c(t+1)-c(t))/16)-o(\exp(-(c(t)-c(t-1)))=1-\exp(-\Omega(a^{*})).$

By Claim 34 we have $|\widehat{C}(t_{0})|=c(t_{0})=o((n^{k-2}p)^{-1})$, which
together with Lemma 36 (III) implies $|C(t_{0})|\leq k|F(t_{0})|+|C(0)|=o(n)$.

Next we apply Lemma 37 where $U$ is an arbitrary $(n^{k-2}p)^{-1}/\zeta$ sized
subset of $C(t_{0})\setminus\widehat{C}(t_{0})$ and $V^{\prime}=C(t_{0})$.
Thus with probability $1-\exp(-a^{*})$ at least $(n^{k-2}p)^{-1}\zeta^{1/2}$,
but at most $o(n)$ additional vertices become infected.

As the number of infected vertices at the end of step $t_{0}$ was $o(n)$ and
in step $t_{0}+1$ this was increased by an additional $o(n)$ infected vertices
the result follows from Lemma 38. ∎

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

## References

  * [1] M. A. Abdullah and N. Fountoulakis.  A phase transition in the evolution of bootstrap percolation processes on preferential attachment graphs.  Random Structures Algorithms, 52(3):379–418, 2018.
  * [2] M. Aizenman and J. Lebowitz.  Metastability effects in bootstrap percolation.  J. Phys. A, 21(19):3801–3813, 1988.
  * [3] H. Amini.  Bootstrap percolation and diffusion in random graphs with given vertex degrees.  Electron. J. Combin., 17(1):Research Paper 25, 20, 2010.