2.1. Notation

Given a host metric space $\Omega$ and a point $\textbf{x}\in \Omega$ , we write $B_r(\textbf{x})$ for the ball in $\Omega$ of radius r centred at $\textbf{x}$ . We use $\vert S\vert$ to denote the size of S if S is a finite set, and the Lebesgue measure of S otherwise. Given $\textbf{x}\in \mathbb{R}^d$ , we denote by $\|\textbf{x}\|$ the standard Euclidean $\ell_2$ -norm of $\textbf{x}$ .

We use standard graph theoretic terminology and Landau big-O notation throughout the paper. In particular, given a graph H and a subset of its vertex set X, we denote by H[X] the subgraph of H induced by X and by $H-X$ the subgraph of H induced by $V(H)\setminus X$ .

2.2. Probabilistic tools

The following lemma, taken from [Reference Balister, Bollobás, Sarkar and Walters6, Lemma 1], greatly facilitates calculations of event probabilities, and we shall make extensive use of it throughout the paper.

Lemma 1. (Estimating probabilities for Poisson point processes.) Let $A\subset R^d$ be measurable, and let $\rho\ge0$ be a real number such that $\rho|A|\in\mathbb{Z}$ . Then the probability that a Poisson process in $\mathbb{R}^d$ with intensity 1 has precisely $\rho|A|$ points in the region A is given by

\begin{align*} \exp\left\{(\rho-1-\rho\log\rho)|A|+O(\log_+\rho|A|)\right\}, \end{align*}

with the convention that $0\log 0=0$ , and $\log_+ x=\max(\log x,1)$ .

Furthermore, by standard properties of Poisson point processes (see e.g. Kingman [Reference Kingman32]), note that the following are equivalent:

• taking as the vertex set of $G_{n,r}^d$ the outcome $\mathcal{P}$ of a Poisson point process of intensity 1 on $T_n^d$ , and then infecting each vertex of $\mathcal{P}$ independently at random with probability $p\in (0,1)$ to obtain $A_{0}$ ;

• letting $A_0$ be the outcome of a Poisson point process of intensity p on $T_{n}^d$ , and taking as the vertex set of $G_{n,r}^d$ the union $\mathcal{P}$ of $A_0$ and of the outcome of a Poisson point process of intensity $1-p$ on $T_{n}^d$ .

We will thus be able to jump back and forth between these two equivalent ways of constructing $\mathcal{P}$ , adopting whichever point of view makes our calculations simplest.

At several points in the paper, we will need to count the number of copies of a ‘local’ event inside $T_{n}^d$ , and the next lemma gives us some simple tools to do this. Let $\Gamma =\mathbb{Z}^d\cap [0, n^{1/d}]^d$ ; this may be identified with a d-dimensional grid of points inside $T^d_n$ . Given an event E defined for point-sets in $T^d_n$ , for every $\textbf{x}\in \Gamma$ we let $E(\textbf{x})$ denote the collection of point-sets in $T^d_n$ whose translates by $\textbf{x}$ belong to E; in other words, a configuration of initially uninfected and initially infected points $(\mathcal{P}\setminus A_{0}, A_{0})$ belongs to $E(\textbf{x})$ if and only if $(\mathcal{P}\setminus A_0-\textbf{x}, A_0-\textbf{x})$ belongs to E.

We say that an event E is Cr-bounded if it is determined by what happens (i.e. which points are present/initially infected) within a ball of radius Cr of the origin $\textbf{0}$ , for some constant $C>0$ . For such an event, we define $\textbf{E}=(\unicode{x1D7D9}_{E(\textbf{x})})_{\textbf{x}\in \Gamma}$ to be the $\Gamma$ -dimensional zero–one vector recording for which $\textbf{x}\in \Gamma$ the event $E(\textbf{x})$ occurs. Given a Cr-bounded event E, let $N_E\;:\!=\;\sum_{\textbf{x}}{\unicode{x1D7D9}}_{E(\textbf{x})}$ denote the number of $\textbf{x}\in \Gamma$ for which $E(\textbf{x})$ occurs.

(i) If $c>1$ , then with probability $1-o(1)$ we have $N_E=0$ .

(ii) If $c<1$ , then with probability $1-o(1)$ we have $N_E=n^{1-c+o(1)}$ .

2.3. Elementary considerations on the Bradonjić–Saniee model

Consider the Bradonjić–Saniee bootstrap percolation model in dimension $d\geq 1$ with $\alpha_d r^d=a\log n$ and $a>1$ fixed. When $\theta<p$ and n is large, most vertices will immediately see more than $a\theta\log n<ap\log n$ infected neighbours, so that most uninfected vertices will immediately become infected. However, this is not the whole story. Indeed, even when $\theta$ is much smaller than p, there is still a chance that some vertex somewhere might see far fewer than its expected $a\log n$ neighbours (infected or not); if it in fact sees fewer than $\theta a\log n$ neighbours, then it can never become infected. In the other direction, even when $\theta>p$ , there could still be a chance that some vertex somewhere will see far more than its expected $pa\log n$ infected neighbours, perhaps as many as $\theta a\log n$ , so that the infection could spread first to, and then from, that vertex.

Roughly speaking, an analysis of the Bradonjić–Saniee model must grapple with three separate questions: whether the infection starts to spread at all, whether it continues to spread to most of the graph, and whether it finally infects every vertex. Each of these requires a separate analysis, even in one dimension. As a simple consequence of the probabilistic tools we have introduced, however, we can readily answer here the question of when the infection starts at all, strengthening and generalizing [Reference Bradonjić and Saniee15, Theorem 1].

Proposition 1. For $a>1$ and $0<p<\theta<1$ fixed, let

\begin{align*} f_{\textrm{start}}(a,p,\theta)\;:\!=\;a(p-\theta+\theta\log(\theta/p)). \end{align*}

Then, if $f_{\textrm{start}}(a,p,\theta)<1$ , w.h.p. at least one initially uninfected vertex is infected in the first round of the bootstrap percolation process. If, however, $f_{\textrm{start}}(a,p,\theta)>1$ , then w.h.p. no initially uninfected vertex ever becomes infected.

Proof. Write X for the number of vertices which initially see more than $a\theta\log n$ infected neighbours in $G_{n,r}^d$ . By Wald’s identity and Lemma 1, we have for $0<p<\theta<1$ that

\begin{align*} \mathbb{E}(X)&=n\exp\Bigl\{pa\log n\left((\theta/p)-1-(\theta/p)\log(\theta/p)\right)+O(\log_+a\theta\log n)\Bigr\}\\ &=\exp\Bigl\{\log n(1-f_{\textrm{start}}(a,p,\theta)+o(1))\Bigr\}. \end{align*}

Consequently, if $f_{\textrm{start}}(a,p,\theta)>1$ , then by Markov’s inequality w.h.p. $X=0$ and no initially uninfected vertex of $\mathcal{P}$ ever becomes infected.

If on the other hand $f_{\textrm{start}}(a,p,\theta)<1$ , then let E denote the event that the ball of radius $r-\sqrt{d}$ around the origin contains at least $\theta a \log n$ initially infected vertices and that the ball of radius $\sqrt{d}$ around the origin contains at least one initially uninfected vertex of $\mathcal{P}$ . Then by Lemma 1 and standard properties of the Poisson point process, the probability of E is

\begin{align*}\mathbb{P}(E)&=\exp\left\{-f_{\textrm{start}}(a,p,\theta)\log n+o(\log n)\right\} \left(1-\exp\{-(1-p)\alpha_d (\sqrt{d})^d \}\right)\\&= \exp\left\{-f_{\textrm{start}}(a,p,\theta)\log n+o(\log n)\right\}.\end{align*}

By Lemma 2(ii) w.h.p. $N_E=n^{1-f_{\textrm{start}}+o(1)}$ . In particular w.h.p. the event $E(\textbf{x})$ occurs for some $\textbf{x}\in \Gamma$ . This implies that there exists an initially uninfected vertex $v\in B_{\sqrt{d}}(\textbf{x})\cap \mathcal{P}$ such that $B_r(v)\cap A_0\supseteq B_{r-\sqrt{d}}(\textbf{x})\cap A_0$ contains at least $\theta a \log n$ initially infected points of $\mathcal{P}$ . Thus v becomes infected in the first round of the bootstrap percolation process, and w.h.p. $A_0\neq A_1\subseteq A_{\infty}$ . This concludes the proof of the proposition.

Since $f_{\textrm{start}}(a,p,p)=0$ , it follows that $p\leq \theta_{\textrm{start}}\leq 1$ .

Proposition 2. For $a>1$ , $p<1$ , and $0<\theta<1$ fixed, set

\begin{align*} f_{\textrm{0$-$stop}}(a,\theta)\;:\!=\;a(1-\theta+\theta\log\theta). \end{align*}

(The reason for this choice of notation will become clear later.) Then, if $f_{\textrm{0$-$stop}}(a,\theta)<1$ , w.h.p. at least one initially uninfected vertex has degree less than $\theta a\log n$ in $G_{n,r}^d$ and consequently never becomes infected. On the other hand, if $f_{\textrm{0$-$stop}}(a,\theta)>1$ , then w.h.p. the minimum degree of $G_{n,r}^d$ is at least $\theta a \log n$ .

Proof. Write Y for the number of vertices which have fewer than $a\theta\log n$ neighbours in $G_{n,r}^d$ . Again, using Wald’s identity and Lemma 1 we have

\begin{align*} \mathbb{E}(Y)&=n\exp\left\{a\log n(\theta-1-\theta\log(\theta))+O(\log_+a\theta\log n)\right\}\\ &=\exp\left\{\log n(1-f_{\textrm{0$-$stop}}(a,\theta)+o(1))\right\}. \end{align*}

Thus, if $f_{\textrm{0$-$stop}}(a,\theta)>1$ , then $\mathbb{E}(Y)=o(1)$ , and by Markov’s inequality w.h.p. the minimum degree of $G_{n,r}^d$ is at least $\theta a \log n$ .

On the other hand, if $f_{\textrm{0$-$stop}}(a,\theta)<1$ , then let E be the event that the ball of radius $r+\sqrt{d}$ around the origin contains strictly fewer than $\theta a \log n$ vertices of $\mathcal{P}$ and that the ball of radius $\sqrt{d}$ around the origin contains at least one initially uninfected vertex of $\mathcal{P}$ . Then by Lemma 1 and standard properties of the Poisson point process, the probability of E is

\begin{align*} \mathbb{P}(E)&=\exp\left\{-f_{\textrm{0$-$stop}}(a,p,\theta)\log n+o(\log n)\right\} \left(1-\exp\left\{-(1-p)\alpha_d (\sqrt{d})^d \right\}\right)\\ &= \exp\left\{-f_{\textrm{0$-$stop}}(a,p,\theta)\log n+o(\log n)\right\}. \end{align*}

By Lemma 2(ii) w.h.p. $N_E=n^{1-f_{\textrm{0$-$stop}}+o(1)}$ . In particular, w.h.p. the event $E(\textbf{x})$ occurs for some $\textbf{x}\in \Gamma$ . This implies that there exists an initially uninfected vertex $v\in B_{\sqrt{d}}(\textbf{x})\cap \mathcal{P}$ such that $B_r(v)\subseteq B_{r+\sqrt{d}}(\textbf{x})$ contains strictly fewer than $\theta a \log n$ points of $\mathcal{P}$ . Thus v never becomes infected and w.h.p. $A_{\infty}\neq \mathcal{P}$ . This concludes the proof of the proposition.

A few comments are in order. First, if in Proposition 2 we have $f_{\textrm{0$-$stop}}(a,\theta)=1$ , then we cannot apply Lemma 1 directly, since the error term will dominate. However, in this case, $\mathbb{P}(Y>0)$ will tend to some constant that is neither 0 nor 1. An equivalent remark applies to Proposition 1. More precise results can be established in these special cases using the Stein–Chen method for Poisson approximation; however, we will not pursue such questions here. Second, when, say, $f_{\textrm{start}}(a,p,\theta)<1$ , not only does the infection start to spread somewhere, it in fact starts to spread in $n^{1-f_{\textrm{start}}(a,p,\theta)+o(1)}=n^{\alpha+o(1)}$ different places for some $\alpha >0$ , as established in the proof of Proposition 1 (more specifically the lower bound on $N_E$ ). Third, in Proposition 2 we have found one obstruction to full infection, but there may (and in fact will) be others.

3.1. Almost-percolation from a large local infection: the case $\theta<\frac{1+p}{2}$

Fix $a>1$ , and let $\pi {r}^2 =a \log n$ . In this subsection, our goal is to show that if $p, \theta$ are fixed and satisfy the growing condition

(2) \begin{align}\theta<\frac{1+p}{2},\end{align}

then w.h.p. any sufficiently large local infection spreads to almost all of $T_n$ . To state our formal result (Theorem 4), we must introduce two tilings of $[0, \sqrt{n}]^2$ . Let $K\in \mathbb{N}$ be a large constant to be specified later.

Let $p,\theta $ be fixed. Suppose $p,\theta$ satisfy (2). Then for any $\eta>0$ there exist constants $C_{\eta}>1$ sufficiently large and $\delta>0$ sufficiently small such that the following hold: let $\textbf{0}$ denote the origin in $\mathbb{R}^2$ , and let $R\geq C_{\eta}r$ be a real number. Then for any point $\textbf{x}$ at distance between $R-\delta r$ and $R+ \delta r$ of $\textbf{0}$ , the asymmetric lens $B_{R}(\textbf{0})\cap B_{r}(\textbf{x})$ has area at least

(3) \begin{align}\vert B_{R}(\textbf{0})\cap B_{r}(\textbf{x})\vert \geq \frac{\pi r^2}{2}(1-\eta).\end{align}

We can now specify our choice of K. Since $a, p, \theta$ are fixed and satisfy (2), there exists a constant $\eta>0$ such that

(4) \begin{align}\pi \theta< \frac{\pi}{2}(1+p)(1-2\eta) -\eta.\end{align}

Fix $\eta>0$ such that (4) is satisfied. Let $C_{\eta}$ and $\delta$ be such that (3) is satisfied. Now set $K=\lceil \max\left(4C_{\eta}, 1000/\eta, 1000/\delta\right)\rceil$ .

With K fixed (and with it our rough and fine tilings), we can now define tile colourings which we will use as discrete proxies for the spread of an infection in $T_n$ . We assign colours to the tiles of $\mathcal{R}$ and $\mathcal{F}$ as follows: a tile $T\in \mathcal{F}$ is coloured white if either it contains fewer than $(1-\eta)p\vert T\vert$ initially infected points at the start of the bootstrap percolation process, or it contains fewer than $(1-\eta)\vert T\vert $ points in total. Otherwise, we colour T red if all its points are infected by the end of the bootstrap percolation process, and blue if this is not the case. Furthermore, we colour a tile in $\mathcal{R}$ white if one of its subtiles in $\mathcal{F}$ is coloured white, red if all its subtiles in $\mathcal{F}$ are coloured red, and blue otherwise.

We will be interested in the interface between red and non-red tiles in $\mathcal{R}$ . We thus equip $\mathcal{R}$ with the natural square-grid graph structure by decreeing that two tiles in $\mathcal{R}$ are adjacent if they meet in a side. (Here we identify $[0, \sqrt{n}]^2$ with $\left(\mathbb{R}/\sqrt{n}\mathbb{Z}\right)^2$ in the natural way to ensure that, as is the case in the torus, the tiles in the rightmost column in $\mathcal{R}$ are adjacent to the corresponding tiles in the leftmost column, and similarly the tiles in the topmost row in $\mathcal{R}$ are adjacent to the corresponding tiles in the bottommost column.) By a red component in $\mathcal{R}$ , we mean a connected component of red tiles in the graph H thus defined on $\mathcal{R}$ .

We are now in a position to state the main result of this subsection.

In other words, once the growing condition is satisfied, any sufficiently large infection spreads to most of $T_n$ , leaving only $o(n^{1-\varepsilon})$ isolated islands of diameter $O(\log n)$ uninfected.

The proof of Theorem 4 relies on two main ingredients. First of all, we shall use (3) and the fine tiling to show that, in the absence of fine white tiles, an infection will spread radially outwards from a sufficiently large infected disc (this is the content of Lemma 3). Next, we shall use the Bollobás–Leader discrete isoperimetric inequality in the toroidal grid to show that any large component of rough red tiles has a large boundary. Combining these results with some probabilistic estimates showing that white tiles are few and far apart will then yield the final result.

In the first part of the proof, we shall use the following technical lemma, which follows from [Reference Falgas-Ravry and Walters20, Lemma 8].

Then all fine tiles that are wholly contained inside $B_{R+\delta r}(\textbf{x})\setminus B_{R-2r}(\textbf{x})$ are coloured red.

Proof. Any fine tile wholly contained inside $B_{R+\delta r}(\textbf{x})\setminus B_{R-2r}(\textbf{x})$ either is wholly contained inside $B_R(\textbf{x})\setminus B_{R-2r}(\textbf{x})$ (and hence coloured red), or, by our choice of K, is wholly contained inside $B_{R+\delta r}(\textbf{x})\setminus B_{R-\delta r}(\textbf{x})$ (and hence not coloured white).

It is thus enough to show that every vertex $\textbf{y} \in B_{R+\delta r}(\textbf{x})\setminus B_{R-\delta r}(\textbf{x})\cap \mathcal{P}$ is eventually infected by our bootstrap percolation process. Now by (3), the lens $L({\textbf{y}})\;:\!=\;B_{R}(\textbf{x})\cap B_r(\textbf{y})$ has area at least $\frac{\pi r^2}{2}(1-\eta)$ . Since this lens is contained inside the annulus $B_R(\textbf{x})\setminus B_{R-2r}(\textbf{x})$ , every fine tile wholly contained inside $L({\textbf{y}})$ is coloured red by Assumption (i). Furthermore, every other tile wholly contained inside the disc $B_r(\textbf{y})$ is not coloured white by Assumption (ii). We use this information, together with Proposition 3, to show that $\textbf{y}$ sees strictly more than $\theta \pi r^2$ infected points within distance at most r of itself—which in turn implies that $\textbf{y}$ must become infected before the end of the process, as required.

First of all, the boundary of $L({\textbf{y}})$ has length at most $2\pi r$ , whence by Proposition 3 it intersects at most $18 \pi K$ distinct fine tiles. It follows that $L({\textbf{y}})$ must wholly contain a collection of red fine tiles of combined area at least

\begin{align*} \vert L({\textbf{y}})\vert - 18 \pi K\frac{c^2r^2}{K^2}>\frac{\pi r^2}{2}(1-\eta) -\frac{\eta r^2}{2}, \end{align*}

where the inequality follows for n large enough from our lower bound on $\vert L({\textbf{y}})\vert$ , our choice of $K\geq 1000/\eta $ , and the fact that $c=1+o(1)$ .

Similarly, the boundary of $B_{r}(\textbf{y})$ has length $2\pi r$ , and thus, applying Proposition 3 as above, $B_{r}(\textbf{y})$ must wholly contain a collection of non-white fine tiles of combined area at least $\pi r^2 -\frac{\eta r^2}{2}$ . Given the definition of our colouring of fine tiles, it follows that $B_r(\textbf{y})$ contains at least

\begin{align*} \left(\frac{\pi r^2}{2}(1-\eta) -\frac{\eta r^2}{2}\right)(1-\eta) +\left(\frac{\pi r^2}{2}(1+\eta)\right)p(1-\eta)>\frac{\pi r^2}{2}(1+p)(1-2\eta) -\frac{\eta r^2}{2} \end{align*}

infected points, which by (4) is strictly more than $\theta \pi r^2$ . Thus $\textbf{y}$ is eventually infected by the bootstrap percolation process, and the lemma follows.

Lemma 3 implies that if a red rough tile is part of the vertex boundary of a connected component of red rough tiles in the graph H on $\mathcal{R}$ , then there must be a white rough tile in the vicinity.

We shall use Corollary 1 to show that if a connected component of red tiles in H has a large boundary, then we may find a large connected component of white tiles in a sufficiently large power of H. Recall that the tth power of H, denoted by $H^t$ , is the graph on the vertex set of H in which all pairs of distinct vertices lying at graph distance at most t in H are joined by an edge.

To make this argument formal, we need the standard notions of edge boundary and dual cycles. Given a subset $A\in \mathcal{R}$ , the edge boundary $\partial_e(A)$ is the collection of pairs $(T_1, T_2)$ such that $T_1\in A$ , $T_2\notin A$ , and $\{T_1,T_2\}$ is an edge of H. The dual $H^{\star}$ of the graph H is the graph whose vertices are the corners of rough tiles in $\mathcal{R}$ and whose edges are the sides of rough tiles in $\mathcal{R}$ . It can be shown (see e.g. [Reference Bollobás and Riordan14, Lemma 1, Chapter 1]) that the edge boundary of a connected component $\mathcal{C}$ in H corresponds to a union of cycles in the dual graph $H^{\star}$ .

We can now prove that to each cycle $\mathcal{C}^{\star}$ in the edge boundary of a red component C in H, we may associate a (large) connected component of white tiles in the seventh power $H^7$ of H.

Thus, if a red component in H has a large dual cycle in its boundary, there must exist a large white component in $H^8$ . On the other hand, as we now show, w.h.p. there are no large white components in $H^8$ . Set $k\;:\!=\;\lfloor \sqrt{n}/Kr\rfloor$ . Our auxiliary graph H on the set of rough tiles $\mathcal{R}$ is thus a $k\times k$ toroidal graph.

Proof. Part (i) of the lemma follows from Lemma 1 (applied to the $K^4$ fine subtiles of a rough tile) and Markov’s inequality. Using Part (i), the expected number of white rough tiles in H is at most $k^2n^{-\varepsilon}=O\left(n^{1-\varepsilon}/\log n\right)$ . Applying Markov’s inequality again, we obtain the second part of the lemma.

For the third part, observe that the graph $H^8$ has maximum degree less than $4^8$ , and that each tile is coloured white independently of all other tiles. Now it is well known (see e.g. [Reference Bollobás11, Problem 45]) that the number of connected subgraphs of order n containing a given vertex $v_0$ in a graph of maximum degree $\Delta$ is at most $(e\Delta)^n$ . Consequently, the expected number of connected subgraphs of white rough tiles of size $\ell>2/\varepsilon$ in $H^8$ is at most

\begin{align*}k^2(4^8e)^{\ell}n^{-\ell\varepsilon}=o(1), \end{align*}

whence Markov’s inequality tells us that w.h.p. no such connected subgraph exists. It follows that w.h.p. all connected components of white rough tiles in $H^8$ have size at most $2/\varepsilon$ in $H^8$ , as claimed.

Putting Lemmas 4 and 5 together, we have that w.h.p. there is no red component in H with a large dual cycle in its edge boundary. We now bring in the second main ingredient of the proof of Theorem 4, namely a discrete isoperimetric inequality in the toroidal grid due to Bollobás and Leader [Reference Bollobás and Leader13], in order to show that in such circumstances if there is a large red component $\mathcal{C}$ in H, then this component $\mathcal{C}$ is unique and all components in $H-\mathcal{C}$ are small.

The 2-dimensional case of the Bollobás–Leader edge-isoperimetric inequality for toroidal grids [Reference Bollobás and Leader13, Theorem 8] is as follows.

Proposition 4. (Bollobás--Leader edge-isoperimetric inequality.) Let A be a subset of $\mathcal{R}$ with $\vert A\vert \leq k^2/2$ . Then

\begin{align*} \vert \partial_e(A)\vert &\geq \min \left(4\sqrt{\vert A\vert }, 2k\right). \end{align*}

Proof. Let $N_0$ be fixed, and let n be sufficiently large so as to ensure that $2k>N_0$ . Let $\{\mathcal{C}_i: \ i \in I\}$ be the collection of connected components in $H[V(H)\setminus \mathcal{C}]$ . Note that each such component $\mathcal{C}_i$ sends an edge to $\mathcal{C}$ in H, and sends no edge to $\mathcal{C}_j$ for $j\neq i$ . For every $i_0\in I$ , consider the edge boundary of $\mathcal{C}_{i_0}$ . Since both $\mathcal{C}_{i_0}$ and its complement $\mathcal{C}\cup \bigcup_{i\in I\setminus\{i_0\}}\mathcal{C}_i$ induce connected subgraphs in H, the edge boundary of $\mathcal{C}_{i_0}$ (which is a subset of the edge boundary of $\mathcal{C}$ ) consists of a single dual cycle $\mathcal{C}^{\star}_{i_0}$ in $H^{\star}$ .

If $\vert \mathcal{C}_{i_0}\vert > k^2/2$ , then by Proposition 4 applied to the complement $\mathcal{C}\cup \bigcup_{i\in I\setminus\{i_0\}}\mathcal{C}_i$ of $\mathcal{C}_{i_0}$ , we have that this dual cycle $\mathcal{C}^{\star}_{i_0}$ has length at least

\begin{align*}\vert \partial_e (\mathcal{C}_{i_0})\vert \geq \min \left(4\sqrt{k^2-\vert \mathcal{C}_{i_0}\vert} , 2k\right)\geq \min\left(4\sqrt{\vert \mathcal{C}\vert}, 2k\right)>N_0,\end{align*}

by our assumptions that $\vert \mathcal{C}\vert \geq (N_0)^2$ and $2k>N_0$ . This contradicts the fact that every dual cycle in the edge boundary of $\mathcal{C}$ has length at most $N_0$ . Thus it must be the case that $\vert \mathcal{C}_{i_0}\vert \leq k^2/2$ .

Then, applying Proposition 4 to $\mathcal{C}_{i_0}$ itself, we have that the dual cycle $\mathcal{C}^{\star}_{i_0}$ has length at least

\begin{align*}\vert \partial_e (\mathcal{C}_{i_0})\vert \geq \min \left(4\sqrt{\vert \mathcal{C}_{i_0}\vert} , 2k\right).\end{align*}

Since by assumption every dual cycle in the edge boundary of $\mathcal{C}$ has length at most $N_0$ , and since $2k> N_0$ , it follows from the above that $\vert \mathcal{C}_{i_0}\vert \leq (N_0)^2/16<(N_0)^2$ , as required.

We are now ready to complete the proof of Theorem 4.

Proof of Theorem 4 . Let $\varepsilon>0$ be the constant whose existence is guaranteed by Lemma 5, let $N_0=\lceil 200/\varepsilon\rceil$ , and let $N={(N_0)}^2$ .

Now suppose that H contains a red component $\mathcal{C}$ of order $\vert \mathcal{C}\vert \geq N$ . By Lemma 5(iii), we know that w.h.p. all connected components of white rough tiles in $H^8$ have size at most $N_0/100$ . By Lemma 4, this in turn implies that w.h.p. all dual cycles in the edge boundary of $\mathcal{C}$ have length at most $N_0$ . This enables us to apply Lemma 6 and deduce that w.h.p. all connected components in $H-\mathcal{C}\;:\!=\;H[V(H)\setminus \mathcal{C}]$ have order strictly smaller than $N=(N_0)^2$ . In particular, $\mathcal{C}$ is w.h.p. unique, and therefore w.h.p. all other red components must have order strictly less than N.

It remains to bound the number of components in $H-\mathcal{C}$ . For this we again apply Lemma 4. For each connected component $\mathcal{C}'$ in $H-\mathcal{C}$ , we choose a pair of adjacent tiles $(T_0,T')$ with $T_0\in \mathcal{C}$ and $T'\in \mathcal{C}'$ . Lemma 4 then implies the existence of a rough white tile W at graph distance at most 3 from $T_0$ in H, and so at graph distance at most 4 from $\mathcal{C}'$ . Each such W can thus be associated with at most $4^4$ components $\mathcal{C}'$ . By Lemma 5(iii), w.h.p. there are at most $o(n^{1-\varepsilon})$ rough white tiles. Therefore w.h.p. there can be at most $o(n^{1-\varepsilon})$ components $\mathcal{C}'$ in $H-\mathcal{C}$ , each of which has order at most N. It follows that w.h.p.

\begin{align*} \vert C\vert \geq \vert \mathcal{R}\vert-o(n^{1-\varepsilon}), \end{align*}

i.e. that w.h.p. $\mathcal{C}$ is a giant red connected component covering all but $o(n^{1-\varepsilon})$ tiles in H, as claimed. This concludes the proof of Theorem 4.

3.2. Outbreaks stay local: the case $\theta>\frac{1+p}{2}$

Fix $a>1$ , and let $\pi {r}^2 =a \log n$ . In this subsection, our goal is to show that if $p, \theta$ are fixed and satisfy the non-growing condition

(5) \begin{align}\theta>\frac{1+p}{2},\end{align}

then w.h.p. any outbreak in $T_n\;:\!=\;T_n^2$ remains local. To state our formal result (Theorem 5), we must, as in the previous subsection, introduce two tilings of $[0,\sqrt{n}]^2$ . Let $K\in \mathbb{N}$ be a large constant to be specified later.

Let $p,\theta $ be fixed. Suppose $p,\theta$ satisfy (5). Then for any $\eta>0$ there exists a constant $C_{\eta}>1/\sqrt{2}$ sufficiently large so that the area of the lune $B_{r}((C_{\eta}r,0))\setminus B_{C_{\eta}r}(\textbf{0})$ is at most

(6) \begin{align}\vert B_{r}((C_{\eta}r,0))\setminus B_{C_{\eta}r}(\textbf{0})\vert \leq \frac{\pi r^2}{2}(1+\eta).\end{align}

We can now specify our choice of K. Since $a,p, \theta$ are fixed and satisfy (5), there exists a constant $\eta>0$ such that

(7) \begin{align}\pi \theta> \frac{\pi}{2}(1+p)(1+\eta)^2 +\eta.\end{align}

Fix $\eta>0$ such that (7) is satisfied. Let $C_{\eta}$ be such that (6) is satisfied. Now set $K=\lceil \max\left(2C_{\eta}, 10000/\eta\right)\rceil$ .

With K fixed (and with it our rough and fine tilings), we can now define tile colourings which we will use as discrete proxies for the spread of an infection in $T_n$ . We assign colours to the tiles of $\mathcal{R}$ and $\mathcal{F}$ as follows: a tile $T\in \mathcal{F}$ is coloured black if either it contains strictly more than $(1+\eta)p\vert T\vert$ points of $A_0$ , or it contains strictly more than $(1+\eta)\vert T\vert $ points of $\mathcal{P}$ . Otherwise, we colour T red if some of its initially uninfected points become infected at some stage in the bootstrap percolation process, and blue if this is not the case. Furthermore, we colour a tile in $\mathcal{R}$ black if one of its subtiles in $\mathcal{F}$ is coloured black, red if one of its subtiles in $\mathcal{F}$ is coloured red, and blue otherwise.

We equip $\mathcal{R}$ with the natural square-grid graph structure by decreeing that two tiles in $\mathcal{R}$ are adjacent if they meet in a side, and as in the previous subsection, we identify $[0,\sqrt{n}]^2$ with $\left(\mathbb{R}/\sqrt{n}\mathbb{Z}\right)^2$ in the natural way. We thus obtain an auxiliary toroidal grid-graph H on $\mathcal{R}$ . We can now state the main result of this subsection.

The key to Theorem 5 is the following lemma, showing that a non-black rough tile surrounded by non-black tiles will be coloured blue.

Proof. Let $\textbf{x}$ denote the centre of the tile T. We shall prove the stronger claim that no initially uninfected vertex in the ball $B_{cKr/\sqrt{2}}(\textbf{x})\supseteq T$ ever becomes infected.

Indeed, suppose $t\geq 0$ and no point in $B_{cKr/\sqrt{2}}(\textbf{x})\setminus A_0$ has yet become infected. Consider any such point v. Which infected points does v see within distance r of itself? In a worst-case scenario, every point in the lune $\textrm{Lune}(v)=B_r(v)\setminus B_{cKr/\sqrt{2}}(\textbf{x})$ has become infected. We show that even if this was the case, v does not become infected in the next round of the bootstrap percolation process.

Observe first of all that the length of the boundary $\partial\textrm{Lune}(v)$ of the lune $\textrm{Lune}(v)$ is at most $2\pi r$ , and thus $\partial\textrm{Lune}(v)$ meets at most $18\pi K$ tiles of $\mathcal{F}$ by Proposition 3. Similarly, the boundary of the asymmetric lens $\textrm{Lens}(v)=B_r(v)\cap B_{cKr/\sqrt{2}}(\textbf{x})$ has length at most $2\pi r$ and thus meets at most $18\pi K$ tiles of $\mathcal{F}$ .

Since both T and the eight tiles around it are not coloured black, each fine tile wholly contained in $\textrm{Lens}(v)$ contains at most $(1+\eta)p\frac{c^2r^2}{K^2}$ points of $A_0$ , and contains no other point of $A_t$ by our assumption. Furthermore, every other fine tile having non-empty intersection with $B_r(v)$ contains at most $(1+\eta)\frac{c^2r^2}{K^2}$ points of $\mathcal{P}$ in total, and thus at most that many points of $A_t$ .

By (6) and our choices of $\eta$ and K, we have that the area of $\textrm{Lune}(v)$ is at most $\frac{\pi r^2}{2}(1+\eta)$ (since the area of the lune is maximized if v lies on the circle of radius $cKr/\sqrt{2}$ about $\textbf{x}$ , and $cK/\sqrt{2}>C_{\eta}$ ). It follows that for n large enough the number of infected points of $A_t$ within distance r of v is at most

\begin{align*}\vert B_r(v)\cap A_t\vert &\leq (1+\eta)\vert \textrm{Lune}(v)\vert + (1+\eta)p(\pi r^2 -\vert \textrm{Lune}(v)\vert) +36\pi K(1+\eta)\frac{c^2r^2}{K^2}\\&< \pi r^2 \left(\frac{1+p}{2}\right)(1+\eta)^2 + \eta r^2< \theta \pi r^2.\end{align*}

Here, the first strict inequality follows from our bound on the area of $\textrm{Lune}(v)$ , the facts that $\eta\leq \pi$ and $c<2$ for n large enough, and from our choice of K ensuring that $144 (1+\pi)\pi /K< \eta$ . The second strict inequality follows from (7).

In particular, v sees strictly fewer than $\theta a \log n$ infected points from $A_t$ , and does not become infected in the next round of the bootstrap percolation process. Since $v\in B_{cKr/\sqrt{2}}(\textbf{x})\setminus A_0$ was arbitrary, it follows by induction on t that $B_{cKr/\sqrt{2}}(\textbf{x})\setminus A_0=B_{cKr/\sqrt{2}}(\textbf{x})\setminus A_{\infty}$ . Since the rough tile T is a subset of $B_{cKr/\sqrt{2}}(\textbf{x})$ and is not coloured black, it follows that T is coloured blue as claimed.

Similarly to Lemma 5, we now prove the following.

Proof. By Lemma 1 (applied to the $K^4$ fine subtiles of a rough tile) and Markov’s inequality, there exists a constant $\varepsilon=\varepsilon (a, \eta, K)>0$ such that the probability that a rough tile is coloured black is at most $n^{-\varepsilon}$ for all n sufficiently large. Thus the expected number of black rough tiles in H is at most $\left(\frac{\sqrt{n}}{Kr}\right)^2n^{-\varepsilon}=O\left(n^{1-\varepsilon}/\log n\right)$ . Applying Markov’s inequality again, we obtain the first part of the lemma.

For the second part, observe that the graph $H^7$ has maximum degree less than $4^7$ , and that each rough tile is coloured black independently of all other tiles. In particular, the expected number of paths of black rough tiles of length $\ell>1/\varepsilon$ in $H^7$ is at most

\begin{align*} \left(\frac{\sqrt{n}}{Kr}\right)^2 4^{7\ell} n^{-(\ell +1)\varepsilon}=O(n^{-\varepsilon})=o(1), \end{align*}

whence Markov’s inequality tells us that w.h.p. no such path exists. It follows that w.h.p. all connected components of black rough tiles in $H^7$ have diameter at most $1/\varepsilon$ , as claimed.

We can now prove Theorem 5.

3.3. Proof of Theorem 1

With our tiling results Theorems 4 and 5 in hand, we can prove the main results of this paper.

Proof of Theorem 1 (i). Suppose $(a,p, \theta)$ is fixed with $a>1$ and $(p,\theta)$ satisfying the growing condition (2). Then there exists $\eta=\eta(p, \theta)>0$ such that (4) is satisfied. We can then define $K=K(\eta)$ and the rough tiling $\mathcal{R}$ of $T_n$ as in Theorem 4. Let $N\in \mathbb{N}$ and $\varepsilon>0$ be constants such that the conclusions of Theorem 4 hold (note that our choice of these constants depends only on $a,p, \theta$ ). By Lemma 5 we may also ensure with our choice of $\varepsilon$ that the probability that a rough tile in $\mathcal{R}$ is coloured white is at most $n^{-\varepsilon}$ , provided n is taken sufficiently large.

Now we select a constant $C=C(a, p, \theta)$ sufficiently large so that any ball of radius Cr in $T_n$ wholly contains a connected component in H of at least N non-white rough tiles of $\mathcal{R}$ . This requires a little calculation. Set $M=\lceil\frac{2N}{\varepsilon}\rceil$ . Observe that there are at most n ways of choosing an $M \times M$ square grid of rough tiles in $\mathcal{R}$ . Taking a simple union bound, the probability that there are at least $\frac{2}{\varepsilon}N$ white rough tiles in such an $M\times M$ grid is at most

\begin{align*}2^{M^2} \left(n^{-\varepsilon}\right)^{\frac{2}{\varepsilon}N}=O(n^{-2N}).\end{align*}

By Markov’s inequality, it follows that w.h.p. every $M\times M$ grid of rough tiles in $\mathcal{R}$ contains fewer than $\frac{2}{\varepsilon}N$ white rough tiles. In particular, every such grid contains a column of $\frac{2}{\varepsilon}N>N$ non-white rough tiles.

We now take C sufficiently large so as to ensure that every ball of radius Cr wholly contains an $M\times M$ square grid of rough tiles. This is easily done: $C= 4MKc$ will certainly do, for instance. It follows that if we infect any ball B of radius Cr in $T_n$ , then, changing the colour of the non-white rough tiles wholly contained inside B to red, this yields w.h.p. a connected component of red rough tiles of order at least N in H. Applying Theorem 4, we obtain that all but $o(n^{1-\varepsilon})$ of the rough tiles from $\mathcal{R}$ are coloured red following the bootstrap percolation process started from the initially infected set $A_0\cup (B\cap \mathcal{P})$ .

By Lemma 1, w.h.p. every rough tile in $\mathcal{R}$ contains at most $O(\log n)$ vertices, so we deduce from the above that all but $O(n^{1-\varepsilon}\log n)=o(n)$ vertices of $\mathcal{P}$ eventually become infected.

This leaves only the ‘Furthermore’ part of Theorem 1(i) to establish. Consider a component of non-red rough tiles in $H^2$ . Such a component is a union of disjoint components of non-red rough tiles in H, connected by paths of length 2 in H where the middle tile $T_0$ in the path is red and the two other tiles are non-red and belong to distinct components. By Corollary 1, we know that there must be a white tile at distance at most 3 from $T_0$ . Much as in the proof of Theorem 4, it then follows that to the edge boundary in H of an $H^2$ -connected component of non-red tiles we may associate an $H^8$ -connected component of white tiles W. By Lemma 5, we know that w.h.p. all such components W have diameter at most $1/\varepsilon$ .

There are at most $\vert W\vert 4^3$ red tiles $T_0$ within graph distance 3 in H of a white tile in W, each red tile $T_0$ is the middle point of a path of length 2 in H between at most 4 distinct non-red components in H, and by Theorem 4 w.h.p. all non-red components in H have order at most N. It follows that all connected components of non-red tiles in $H^2$ have order at most $(4^{8})^{1/\varepsilon}4^3 4N$ .

Now since $K>1$ , to each connected component of forever-uninfected vertices in $G_{n,r}[\mathcal{P}\setminus A_0]$ is associated a collection of non-red rough tiles forming a (subset of a) connected component in $H^2$ . It follows that the Euclidean diameter in $T_n$ of such a component is bounded above by $(4^{8})^{1/\varepsilon}4^3 4N \sqrt{2Kcr}=O(\sqrt{\log n})$ , as claimed. This concludes the proof of Theorem 1(i).

Proof of Theorem 1 (ii). Suppose $(a,p, \theta)$ is fixed with $a>1$ and $(p,\theta)$ satisfying the non-growing condition (5). Then there exists $\eta=\eta(p, \theta)>0$ such that (7) is satisfied. We can then define $K=K(\eta)$ and the rough tiling $\mathcal{R}$ of $T_n$ as in Theorem 5. Let $\varepsilon>0$ be such that the conclusion of Theorem 5 holds (note that our choice of $\varepsilon$ depends only on $a,p, \theta$ ).

Let $C>1$ be fixed. Let B be an arbitrarily chosen ball of radius Cr in $T_n$ . By Proposition 3, B meets at most

\begin{align*}N= \left\lceil\frac{\pi (Cr)^2}{(Kcr)^2} + 9K(2\pi Cr)/r \right\rceil<100KC^2\end{align*}

tiles of $\mathcal{R}$ . Fully infect all points inside these at most N tiles and apply Theorem 5 to deduce that even if all points in $\mathcal{P}\cap B$ are infected, then w.h.p. all but $o(n^{1-\varepsilon})$ tiles of $\mathcal{R}$ are coloured blue.

By Lemma 1 and a union bound, w.h.p. every tile of $\mathcal{R}$ contains at most $O(\log n)$ points of $\mathcal{P}$ . Since the point-set $A_{\infty}\setminus (A_0\cup B)$ is contained inside the union of the non-blue tiles of $\mathcal{R}$ , it follows that $A_{\infty}\setminus (A_0\cup B)$ contains at most $o(n^{1-\varepsilon} \log n)=o(n)$ points of $\mathcal{P}$ .

This leaves only the ‘Furthermore’ part of Theorem 1(ii) to establish. We have shown in Theorem 5(ii) that w.h.p. all connected components of non-blue tiles in $H^2$ have order at most $100N^2/\varepsilon^2=O(1)$ . Since $K>2$ , the tiles containing points of a connected component in $G_{n,r}^2[A_{\infty}\setminus (A_0\cup B)]$ must form a connected component of non-blue tiles in $H^2$ . It immediately follows that each such connected component has Euclidean diameter $O(\sqrt{\log n})$ in $T_n$ . This concludes the proof of Theorem 1(ii).

Figure 2.

A lens and a lune.

3.4. Starting a sufficiently large local outbreak: proof of Theorem 2

With Theorem 1 in hand, we now turn our attention to the problem of determining when (for which triples $(a, p, \theta)$ ) a large local outbreak will occur w.h.p. in the Bradonjić–Saniee model for bootstrap percolation on random geometric graphs. We are unfortunately unable to answer this question rigorously, but we can relate it to the solution of an optimization problem which we conjecture gives the correct threshold for ‘large’ local outbreaks.

Definition 4. For $t\in \mathbb{R}_{\geq 0}$ , let $R_{\textrm{lens}}(t)$ denote the asymmetric lens $B_{t}(\textbf{0})\cap B_{1/\sqrt{\pi}}((t,0))$ . Also, let $R_{\textrm{lune}}(t)$ denote the lune $B_{1/\sqrt{\pi}} ((t,0))\setminus B_{t}(\textbf{0})$ (see Figure 2 for an illustration). Given functions $f,g: \ \mathbb{R}_{\geq 0}\rightarrow \mathbb{R}_{\geq 1}$ , we define the quantities

(8) \begin{align}I(f,g)(t)& := \int_{\textbf{x} \in R_{\textrm{lens}}(t)} \left(p f(\| \textbf{x}\|) +(1-p)g(\| \textbf{x}\|)\right)d\textbf{x} + \int_{\textbf{x} \in R_{\textrm{lune}}(t)}pf(\| \textbf{x}\|) d\textbf{x}, \\ Q(f,g)(t) & := \int_{\textbf{x} \in \mathbb{R}^2: \|\textbf{x}\|\leq t} p\left( f(\|\textbf{x}\|) -1 - f(\|\textbf{x}\|)\log [f(\|\textbf{x}\|)]\right) \notag \\& \qquad \qquad \qquad \quad + (1-p)\left(g(\|\textbf{x}\|) -1 - g(\|\textbf{x}\|)\log [g(\|\textbf{x}\|)] \right)d\textbf{x},\end{align}

and $q(f,g)\;:\!=\;\lim_{t\rightarrow \infty} Q(f,g)(t)$ , where $\|\cdot\|$ denotes the standard Euclidean $\ell_2$ -norm.

Note that for $f,g\geq 1$ , we have $f-1-f\log f \leq 0$ and $g-1-g\log g \leq 0$ . Thus Q(f, g) is a non-increasing function of t and either converges to a limit or goes to $-\infty$ .

The motivation for these quantities is as follows. We imagine an infection spreading from the origin $\textbf{0}$ . Around $\textbf{0}$ , at time $t=0$ , we see increased densities of both infected and uninfected points. It is natural to assume that these increased densities are radially symmetric. If so, we may specify them by the functions $f\ge 1$ and $g\ge 1$ , so that the intensities of (initially) infected and uninfected points at $\textbf{x}$ are given by $pf(\|\textbf{x}\|)$ and $(1-p)g(\| \textbf{x}\|)$ respectively. These functions must both decay to 1 as $\|\textbf{x}\|\to\infty$ , or else the probability of the associated configuration $\textbf{C}$ will be zero.

Now we consider the situation as the infection spreads. First we normalize so that the area of the neighbourhood of $\textbf{x}$ has area 1, instead of $a\log n$ . Next suppose that the infection has spread to radius t, i.e., to all of $B_t(\textbf{0})$ . Consider a point $\textbf{x}$ on the boundary of this disc; without loss of generality $\textbf{x}=(t,0)$ . Every point inside $R_{\textrm{lens}}(t)$ will now be infected as a result of the bootstrap percolation process, but in the lune $R_{\textrm{lune}}(t)$ , only those points that were initially infected will be infected. Summing these contributions and integrating, we see that I(f, g)(t) represents the (normalized) number of infections seen by $\textbf{x}$ ; if this exceeds $\theta$ , $\textbf{x}$ itself will be infected, and the infection will thus propagate radially outwards from $\textbf{0}$ .

Given f and g, and a configuration $\textbf{C}$ specified by f and g as above, what is the probability $p_{\textbf{C}}$ that $\textbf{C}$ actually occurs? For this, we turn to Lemma 1. Although this lemma only applies to finite unions of disjoint regions, the function q(f, t), derived from Lemma 1, represents the (normalized) logarithm of the sought probability $p_{\textbf{C}}$ . Maximizing q(f, t) over all admissible functions f and g, subject to the constraint that $I(f,g)(t)>\theta$ for all $t>0$ , yields an optimal pair (f, g), and if p and $\theta$ are such that the (un-normalized) associated probability $p_{\textbf{C}}$ exceeds $n^{-c}$ , for some $c<1$ , then such a configuration is bound to occur somewhere in $T_n$ . This is the content of Definition 5 below.

The use of the integral in (8) needs to be justified. For this, we use a tiling argument. Tiling the neighbourhood of (a truncated version of) an optimal configuration $\textbf{C}$ , we apply Lemma 1 to the disjoint union of finitely many tiles, to define a ‘discretized’ event E, based on $\textbf{C}$ , whose rigorously calculated probability $p_{\textbf{E}}$ is well approximated by $p_{\textbf{C}}$ , and whose existence rigorously guarantees that an infection will spread. This is achieved in Claims 1 and 2 below.

Definition 5. (Symmetric local growth threshold.) Let $Q_{\textrm{max}}= Q_{\textrm{max}}(p, \theta)$ denote the supremum of q(f,g) over all continuous functions $f,g: \ \mathbb{R}_{\geq 0}\rightarrow \mathbb{R}_{\geq 1}$ satisfying

\begin{align*}I(f,g)(t) > \theta \quad \forall t\in \mathbb{R}_{\geq 0}.\end{align*}

Furthermore, for $a>1$ and $p\in (0,1)$ fixed, let $\theta_{\textrm{local}}=\theta_{\textrm{local}}(a,p)$ be the supremum of all $\theta \leq 1$ such that

(9) \begin{align}Q_{\max}(p, \theta)> -1/a.\end{align}

Observe that $\theta_{\textrm{local}}$ depends only on the values of a and p, and that it is well-defined and greater than or equal to p, since $Q_{{\max}}(p,p)=0$ , as can be seen by taking f and g to be constant and equal to 1.

Proof of Theorem 2 . Since $\theta$ satisfies (1), it follows from the definitions of $\theta_{\textrm{local}}$ and $Q_{\textrm{max}}$ that for any fixed $T\in \mathbb{R}_{\geq 0}$ there exist functions $f,g: \mathbb{R}_{\geq 0}\rightarrow \mathbb{R}_{\geq 1}$ and a real $\varepsilon>0$ such that the following hold:

1. (i) for every $t\in [0,T]$ , $I(f,g)(t) > \theta+2\varepsilon$ ;

2. (ii) $Q(f,g)(T+2)> -1/a +2\varepsilon$ .

We use this information to construct for any constant $C>0$ a $(C+2)r$ -bounded event occurring w.h.p. and guaranteeing the existence of a ball of radius Cr that becomes wholly infected over the course of our bootstrap percolation process. As we note in Proposition 5 below, this implies that $\theta_{\textrm{local}}\leq (1+p)/2$ , and thus that for $\theta<\theta_{\textrm{local}}$ the growing condition (2) is satisfied. Combining this information with Theorem 1(i) then yields the desired almost percolation.

We now give the details. Pick $T=(C+2)/\sqrt{\pi}$ . Fix $\varepsilon>0$ and let $K>0$ be a sufficiently large positive real number to be specified later. Partition $\mathbb{R}^2$ into a fine grid of interior-disjoint $\frac{\sqrt{a\log n}}{K}\times \frac{\sqrt{a\log n}}{K}$ square tiles with axis-parallel sides. Let $\mathcal{F}$ be the finite family of tiles that are wholly contained inside the ball of radius $(C+2)r= T\sqrt{a\log n}$ about the origin. Note that $\vert \mathcal{F}\vert =O(1)$ . Let f, g be functions $f,g: \mathbb{R}_{\geq 0}\rightarrow \mathbb{R}_{\geq 1}$ such that Assumptions (i) and (ii) above are satisfied.

Let $\mathcal{P}_p$ and $\mathcal{P}_{1-p}$ be independent Poisson point processes on $B_{T\sqrt{a\log n}}(\textbf{0})$ with intensities p and $1-p$ respectively. Let E be the event that for every tile F in $\mathcal{F}$ , F contains

• at least $N_f(F)\;:\!=\;\int_{\textbf{x} \in F} p f(\| \textbf{x}\|/\sqrt{a\log n})d\textbf{x}$ points of $\mathcal{P}_p$ , and

• at least $N_g(F)\;:\!=\;\int_{\textbf{x} \in F} (1-p) g(\| \textbf{x}\|/\sqrt{a\log n})d\textbf{x}$ points of $\mathcal{P}_{1-p}$ .

Claim 1. For any $\varepsilon>0$ fixed, there exists $K_1>0$ such that picking $K\geq K_1$ ensures that

\begin{align*}\mathbb{P}(E)\geq e^{-c\log n +o(\log n)} \qquad \textrm{ for some fixed constant }c<1.\end{align*}

Proof. Set $M_1$ to be the area of a 2-dimensional ball of radius T. Since f, g are continuous functions from the compact set [0, T] to $\mathbb{R}_{\geq 1}$ , we have that f and g are bounded above by some $M_2>0$ on [0,T] and further that $\log f$ and $\log g$ are uniformly continuous over [0,T]. In particular, for every $\varepsilon>0$ there exists $K_1>0$ sufficiently large so that for all $K\geq K_1$ , and all $x,y\in [0,T]$ , $\vert x-y\vert \leq 2/K$ implies that both $\vert \log [f(x)]-\log[ f(y)]\vert$ and $\vert \log [g(x)]-\log[g(y)]\vert $ are less than $\varepsilon/M_1M_2$ .

For each tile $F\in \mathcal{F}$ , set $\rho_f(F)\;:\!=\; N_f(F)/\vert F\vert$ and $\rho_g(F)\;:\!=\; N_g(F)/\vert F\vert$ . By the consequence of uniform continuity observed above, picking $K\geq K_1$ ensures that

\begin{align*}f\left(\frac{\|\textbf{x}\|}{\sqrt{a\log n}}\right)\left(\log \left[f\left(\frac{\|\textbf{x}\|}{\sqrt{a\log n}}\right)\right]- \log \left[\rho_f(F)\right]\right)\geq -\varepsilon /M_1\end{align*}

for all $\textbf{x}\in F$ . Combining this with Lemma 1 (rescaled by a factor of p), the probability that F contains at least $N_f(F)$ points of $\mathcal{P}_p$ is

\begin{align*}\exp &\left\{ \left(\rho_f(F) -1- \rho_f(F)\log \left(\rho_f(F)\right) \right)p\vert F\vert +O(\log \log n) \right\}\\\geq &\exp \left\{ \int_{\textbf{x}\in F}p\left(f\left(\frac{\|\textbf{x}\|}{\sqrt{a\log n}}\right) -1- f\left(\frac{\|\textbf{x}\|}{\sqrt{a\log n}}\right)\log f\left(\frac{\|\textbf{x}\|}{\sqrt{a\log n}}\right) \right)d\textbf{x}\right\}\\\cdot &\exp\left\{- p\frac{\varepsilon }{M_1}\vert F\vert +O(\log \log n) \right\}.\end{align*}

One may obtain a similar expression for the probability that F contains at least $N_g(F)$ points of $\mathcal{P}_{1-p}$ , substituting $1-p$ for p and g for f.

Since $\{\mathcal{P}_p \cap F, \ F\in \mathcal{F}\}$ and $\{\mathcal{P}_{1-p} \cap F, \ F\in \mathcal{F}\}$ together form a collection of independent random variables, it follows that the probability that every tile $F\in \mathcal{F}$ contains at least $N_f(F)$ points of $\mathcal{P}_p $ and at least $N_g(F)$ points of $\mathcal{P}_{1-p}$ —in other words, the probability of E—is at least

\begin{align*}\mathbb{P}(E)&\geq \exp \left\{ \left(Q(f,g)(T) -\varepsilon\right)a\log n +O(\log \log n) \right\}, \end{align*}

which by Assumption (ii) is at least $e^{-(1-a\varepsilon)\log n +o(\log n)}$ , proving our claim with the constant $c=1-a\varepsilon$ .

Given a non-negative integer i, let $A_i=A_i(\mathcal{F})$ denote the collection of tiles of $\mathcal{F}$ that meet the annulus $B_{(i+1)\sqrt{a\log (n)}/K}(\textbf{0})\setminus B_{{i}\sqrt{a\log (n)}/K}(\textbf{0})$ . Furthermore, let $D_i=D_i(\mathcal{F})$ denote the union of the tiles of $\mathcal{F}$ that are wholly contained inside the disc $B_{{i}\sqrt{a\log (n)}/K}(\textbf{0})$ . Observe that both these tile families depend on $\mathcal{F}$ (and thus on our choice of K).

Claim 2. For every $\varepsilon>0$ fixed, there exists $K_2>0$ such that picking $K\geq K_2$ ensures that at least one of the following holds:

• the event E fails to occur;

• for every $i\leq KT-1$ , every tile $F\in A_i$ , and every vertex $\textbf{x}\in F$ , we have that

  \begin{align*} N_{\textbf{x}}\;:\!=\;\vert B_{r}(\textbf{x})\cap D_i\cap \mathcal{P}_{1-p}\vert + \vert B_{r}(\textbf{x})\cap \mathcal{P}_p\vert > \theta a \log n. \end{align*}

Proof. As in the previous claim, we note that the continuous functions f, g are bounded above on the compact set [0,T] by some $M_2>0$ .

Assume the event E occurs. Fix $i \leq KT-1$ , and $F \in A_i$ . Let $\textbf{x}\in F$ and set $t\;:\!=\; \|\textbf{x}\|/\sqrt{a \log n}$ . Denote by $S^1(\textbf{x})$ the collection of tiles of F wholly contained inside $D_i\cap B_{r}(\textbf{x})$ , and by $S^2(\textbf{x})$ the collection of tiles of F wholly contained inside $B_r(\textbf{x})$ . Since E occurs, we have

\begin{align*}N_{\textbf{x}}\geq \sum_{F\in S^2(\textbf{x})} N_f(F) +\sum_{F\in S^1(\textbf{x})}N_g(F).\end{align*}

Now since f, g are bounded above by $M_2$ , the expression on the right-hand side is at least

\begin{align*}I(f, g)(t)a\log n &- M_2 p\left(a\log n - \sum_{F\in S^2(\textbf{x})}\vert F\vert\right)\\&- M_2 (1-p)\left(\vert R_{\textrm{lens}}\vert a\log n - \sum_{F\in S^1(\textbf{x})}\vert F\vert\right).\end{align*}

It readily follows from an application of Proposition 3 that for any $\varepsilon>0$ , there exists $K_2>0$ such that picking $K\geq K_2$ ensures that the above is at least $(I(f,g) - \varepsilon)a\log n$ . Assumption (i) then tells us that

\begin{align*}N_{\textbf{x}}\geq (\theta+\varepsilon) a \log n, \end{align*}

proving our claim.

With Claims 1 and 2 in hand, the proof of Theorem 2 is now straightforward.

Consider $(a, p, \theta)$ satisfying $a>1$ and (1). As recorded in Proposition 5 below, this implies $\theta<(1+p)/2$ . Let $C=C(a, \theta, p)>0$ be a constant such that by Theorem1(i), the infection of a ball of radius Cr in $T_n$ leads w.h.p. to almost percolation in our bootstrap percolation process on $T_n$ . This then specifies our choice of $T=(C+2)/\sqrt{\pi}>0$ .

Let $K_1, K_2$ be the constants from Claims 1–2. Pick $K\geq \max(K_1, K_2)$ . As remarked in Section 2, by standard properties of Poisson point processes we may view the vertex set in the Bradonjić–Saniee model in the torus as being the union of a Poisson process $\mathcal{P}_p$ of initially infected points of intensity p with a Poisson process $\mathcal{P}_{1-p}$ of initially uninfected points of intensity $1-p$ . Partitioning the torus $T_n$ into a fine grid of interior-disjoint square tiles with side length $\sqrt{a \log n}/c'K$ , where $c'\geq 1$ is chosen to ensure that divisibility conditions are met, we can define a natural analogue E ^′ of our event E inside $T_n$ .

Clearly if E ^′ occurs, then by applying Claim 2 to $A_0,\ldots,A_{KT-1}$ , we see that all vertices inside a ball of radius Cr about the origin in $T_n$ become infected, which then leads to almost percolation. Since E ^′ is $(C+2)r$ -bounded and has probability $q=e^{-c\log n +o(\log n)}$ for some fixed constant $c<1$ (by Claim 1), it follows from Lemma 2(ii) that w.h.p. some translate of E ^′ occurs in $T_n$ . Thus, for $a>1$ fixed, w.h.p. we have almost percolation in the $(p, \theta)$ regime satisfying (1), as claimed.

We conclude this subsection by recording some trivial inequalities between $\theta_{\textrm{local}}$ and other quantities of interest, justifying the phase diagram we give in Figure 1.

Proposition 5. For all $a>1$ fixed and $p\in [0,1]$ , the following inequalities hold:

\begin{align*}p\leq \theta_{\textrm{local}} \leq \min \left(\frac{1+p}{2}, \theta_{\textrm{start}}\right).\end{align*}

3.5. Islands

Beyond the almost percolation guaranteed by Theorem 2, it is natural to ask when full percolation occurs in the Bradonjić–Saniee model. One obstacle for full percolation is the presence of initially uninfected vertices of degree strictly less than $\theta a \log n$ . Proposition 2 gives us the (implicit) $\theta$ threshold for the w.h.p. disappearance of such vertices. However there may be other, likelier, obstacles to full percolation, namely ‘islands’ of initially uninfected vertices with few initially infected vertices, surrounded by sparsely populated ‘lakes’ containing unusually few vertices.

Much as in the previous subsection, we are unable to rigorously determine the threshold for the w.h.p. disappearance of islands of uninfected vertices. We are, however, able to determine the threshold for the disappearance of symmetric islands, which is given by the solution of an explicit continuous optimization problem and can be determined explicitly using the method of Lagrange multipliers.

As the arguments involved are very similar to those in the previous section, we give only a minimal level of detail. The basic idea is quite simple: we look for a radially symmetric distribution of infected/non-infected point densities which guarantees that some island cannot be infected from the outside. To such a distribution we associate a local O(r)-bounded event, from which we can in turn derive a threshold for the w.h.p. disappearance of such islands—the proof essentially follows that of Theorem 2, mutatis mutandis.

To make this more precise, let us give analogues of Definition 4 tailored to the island (rather than local outbreak) setting.

Definition 6. Let $T>0$ be fixed. For $t\in [0,T]$ , write $R_{\textrm{inner}}(t)$ for the asymmetric lens $B_{T}(\textbf{0})\cap B_{1/\sqrt{\pi}}((t,0))$ and $R_{\textrm{outer}}(t)$ for the (possibly empty) lune $B_{1/\sqrt{\pi}}((t,0))\setminus B_{T}(\textbf{0})$ . A symmetric T-island distribution is a pair (f,g) of continuous functions $f,g: \ \mathbb{R}_{\geq 0}\rightarrow [0,1]$ such that for every $t\in [0,T]$ , the following holds:

(10) \begin{align} \int_{\textbf{x}\in R_{\textrm{inner}}(t)} pf(\|\textbf{x}\|) d\textbf{x} + \int_{\textbf{x}\in R_{\textrm{outer}}(t)} \left(pf(\|\textbf{x}\|)+(1-p)g(\|\textbf{x}\|)\right) d\textbf{x} < \theta. \end{align}

Given a symmetric T-island distribution (f, g), we define its weight q(f, g) as in (8) (just the equation, not the limit).

Definition 7. (Symmetric islands threshold.) For every $T\geq 0$ , the optimal T-island weight $q_{{\max}}(T)=q_{{\max}}(T)(p, \theta) $ is the supremum of the weight q(f,g) over all symmetric T-island distributions (f,g). The symmetric islands threshold $\theta_{\textrm{islands}}=\theta_{\textrm{islands}}(a,p)$ is then defined to be the supremum of the $\theta \leq 1$ such that

(11) \begin{align}\sup_{T\geq 0} q_{\textrm{max}}(T)>-1/a.\end{align}

We note that the quantity $\theta_{\textrm{islands}}$ can in principle be computed using Euler–Lagrange equations—see Appendix A. However, the solution will be implicit rather than explicit. Let us record here, however, the simple fact that

(12) \begin{align}\theta_{\textrm{islands}}\leq \frac{1+p}{2}.\end{align}

Indeed, let (a, p) and $\varepsilon>0$ be fixed. Pick a constant $T>0$ sufficiently large so that the area of $R_{\textrm{inner}}(T)$ is at least $\frac{1}{2}-\varepsilon$ . Then it is easily checked that taking the functions f, g to be identically 1 gives a symmetric T-island distribution (f, g) with weight $q(f,g)=0>-1/a$ for any $\theta> \frac{1+p}{2}+\varepsilon (1-p)$ . The inequality (12) follows immediately.

The content of Conjecture 3 is that the last obstruction to full percolation that will vanish as we decrease the infection threshold $\theta$ will correspond to the local distribution of initially infected/uninfected points that are well approximated by a symmetric T-island, for some $T=T(a,p)$ . Motivation for the conjectured circular symmetry comes from the isoperimetric inequality in the plane as well as probabilistic considerations: for an uninfected island configuration to remain both uninfected and likely to occur in $T_n^2$ , one expects it is best to minimize the length of its boundary, and to spread out unlikely low densities of points outside the island and of initially uninfected points inside the island as uniformly as possible.

Theorem 3 gives an upper bound on the values of $\theta$ for which full percolation may occur w.h.p. in the Bradonjić–Saniee model. While we are unable to prove a matching lower bound and thereby prove Conjecture 3, we note here that one can nevertheless prove some rigorous lower bounds on the threshold $\theta_{\textrm{percolation}}(a,p)$ below which percolation occurs w.h.p., which we believe refine the earlier simple bounds due to Bradonjić and Saniee [Reference Bradonjić and Saniee15, Theorem 2] (in both cases, the exact value of the threshold is given implicitly rather than explicitly, which makes a comparison difficult).

Theorems 1(ii) and 2 imply that once $\theta$ falls below $\theta_{\textrm{local}}$ , w.h.p. the only obstructions to full percolation are components of uninfected vertices of Euclidean diameter $O(\sqrt{\log n})$ in $T_n^2$ . Let us consider what point configurations make the existence of such components possible. Given a component of never-infected points of diameter $C\sqrt{\log n}$ , for some $C>0$ , consider a pair of uninfected points $\textbf{u}$ , $\textbf{v}$ from that component with $\|\textbf{u}-\textbf{v}\|=C\sqrt{\log n}$ . Then the whole component of never-infected points lies inside the lune L formed by the two discs of radius $C\sqrt{\log n}$ centred at $\textbf{u}$ and $\textbf{v}$ respectively. Since $\textbf{u}$ , $\textbf{v}$ do not become infected, it must be the case that the number of points in $B_r(\textbf{u})\setminus L$ plus the number of initially uninfected points in $B_r(\textbf{u})\cap L$ is less than $\theta a \log n$ , and a similar statement holds for $\textbf{v}$ . This implies that either $\left(B_r(\textbf{u})\cup B_r(\textbf{v})\right)\setminus L$ contains an abnormally low number of points from our Poisson point process, or that $\left(B_r(\textbf{u})\cup B_r(\textbf{v})\right)\cap L$ contains an abnormally low number of initially infected points. By performing a case analysis and some Lagrangian optimization, one can upper-bound the probability of such an event. Once this upper bound becomes $o(1/n)$ , one can then apply Markov’s inequality to show that such unlikely point configurations w.h.p. do not occur, and thus that we have w.h.p. entered the full percolation regime. However, we do not believe the bounds coming from this argument are optimal (since they will not match those from Conjecture 3) or particularly helpful, so we relegate a sketch of the aforementioned case analysis and optimization to Appendix B.

4.1. Technical remarks: uniform distribution and approximate densities

While the discussion that follows will be quite informal, let us set down here a few remarks on how it can be formalized. Let $C_1>C_2>0$ be fixed constants. Fix $c=c(C_1,C_2)>0$ . Let I be a fixed interval of length $\vert I\vert \in [C_1r, C_2r]$ on the circle. We say that a finite point-set $\mathcal{P}$ with $\vert \mathcal{P}\cap I\vert =x \vert I\vert $ is uniformly distributed on I if every subinterval J of I of length at least $c\sqrt{r}$ contains $\vert J\vert (x+o(1))$ points from $\mathcal{P}$ .

If $\mathcal{P}$ is the outcome of a Poisson process of intensity bounded away from 0 on the circle, then it is an easy consequence of Lemma 1 that conditional on $\vert \mathcal{P}\cap I\vert =x\vert I\vert $ , w.h.p. $\mathcal{P}$ is uniformly distributed on I (for a suitable choice of $c=c(C_1, C_2)$ ). In particular, the probability of seeing that many points in I is, up to a $(1+o(1))$ factor, the probability of seeing that many uniformly distributed points.

This remark, together with a partition of the circle into interval tiles of length $C_1r$ , for some suitably small constant $C_1$ , allows us to reason in terms of continuous point-density functions rather than discrete point-sets, as we do below.

To fully formalize some of our arguments, e.g. to rule out a family of obstructions by showing that the likeliest event in this family is unlikely to occur, one should also approximate the initially infected/uninfected point density inside each interval tile as a fraction $j/C_3$ , where $C_3$ is a sufficiently large constant and

\begin{align*}j=\min\left(\lceil C_3 \#\{\textrm{points in the interval}\}/C_1r\rceil, 100 C_3/C_1\right).\end{align*}

Doing so then allows us, when considering events supported on a bounded number of tiles, to take union bounds over a finite number of tile density configurations and simply apply Markov’s inequality; see e.g. the proof of [Reference Balister, Bollobás, Sarkar and Walters7, Lemma 5] for an example of this kind of argument.

4.2. Growing an infection

Our first observation is that if $f_{\textrm{start}}(a,p,\theta)<1$ , then, for some $\varepsilon$ , some vertex v (at position 0, say) will see at least $a(\theta+\varepsilon)\log n$ infected neighbours, rather than just $a\theta\log n$ . This follows from the continuity of the function $f_{\textrm{start}}$ . Using the notation $I_x=(\!-\!x,x)$ , we may also assume that both the infected and the uninfected vertices in $I_{100r}=(\!-\!100r,100r)$ are uniformly distributed on both $I_{100r}\setminus I_r$ and $I_r$ , so that any interval J of length $c\sqrt{\log n}$ inside $I_r$ contains $|J|(1-p)(1+o(1))$ initially uninfected vertices and $|J|(\theta+\varepsilon)(1+o(1))$ initially infected ones, while any such interval inside $I_{100r}\setminus I_r$ contains $|J|(1-p)(1+o(1))$ initially uninfected vertices and $|J|p(1+o(1))$ initially infected ones. (The densities $1-p$ , $\theta+\varepsilon$ , and p come from the colouring theorem for Poisson processes [Reference Kingman32], which implies in this case that the initially infected and uninfected points can be regarded as independent Poisson processes of intensities p and $1-p$ respectively. The uniform distribution assumption, for its part, holds w.h.p. as discussed in Section 4.1.)

One consequence of this is that not only does v become infected (if it was not already infected), but all vertices in the interval $(\!-\!\delta\log n,\delta\log n)$ become infected, for some $\delta=\delta(\varepsilon)$ . After the first round of new infections, the interval $I_{\delta\log n}$ contains $|I_{\delta\log n}|(1-p+\theta+\varepsilon)(1+o(1))$ vertices, all of which are infected; $I_r\setminus I_{\delta\log n}$ contains $|I_r\setminus I_{\delta\log n}|(1-p)(1+o(1))$ uninfected vertices and $|I_r\setminus I_{\delta\log n}|(\theta+\varepsilon)(1+o(1))$ infected ones; and w.h.p. $I_{100r}\setminus I_r$ contains infected and uninfected vertices with approximate densities p and $1-p$ respectively.

Now we show that w.h.p. the ‘infected interval’ $I_{\delta\log n}$ grows until it infects every vertex in $I_{100r}$ . For simplicity, we shall say that the interval $I_x$ is infected if every vertex within it is infected. Suppose that, after some rounds of the bootstrap process, $I_x$ is in fact infected. (Initially, we take $x=\delta\log n$ .) We examine the neighbours of the first uninfected vertex u to the right of $I_x$ , with a view to showing that u gets infected next, by virtue of having many infected neighbours in $I_x$ . An identical argument will apply on the left.

Assume first that $x\le r/2$ . Then w.h.p. u will have $N_1(x)(1+o(1))$ infected neighbours, where

\begin{align*}N_1(x)&=(\theta+\varepsilon)(2r-3x)+xp+2x(1-p+\theta+\varepsilon)\\&=2r\theta+\varepsilon(2r-x)+x(2-\theta-p)\\&>2r\theta=a\theta\log n,\end{align*}

so that u does indeed become infected w.h.p.

Next assume that $r/2<x\le r$ , and write $y=x-r/2$ . This time w.h.p. u will have $N_2(y)(1+o(1))$ infected neighbours, where

\begin{align*}N_2(y)&=(1-p+\theta+\varepsilon)r+\left(\frac{r}{2}-y\right)(\theta+\varepsilon)+\left(\frac{r}{2}+y\right)p\\&=\frac{(2-p+3\theta+3\varepsilon)r}{2}+y(p-\theta-\varepsilon)\\&>2r\theta=a\theta\log n.\end{align*}

Now since $N_2(y)$ is a linear function satisfying

\begin{align*}N_2(0)=\frac{(2-p+3\theta+3\varepsilon)r}{2}>\frac{(1+3\theta)r}{2}>2r\theta\end{align*}

and

\begin{align*}N_2\left(\frac{r}{2}\right)=\frac{(2+2\theta+2\varepsilon)r}{2}>2r\theta,\end{align*}

it follows that $N_2(y)>2r\theta$ and hence that u becomes infected w.h.p.

Finally we show that the infection spreads beyond $I_r$ , to at least the entire interval $I_{100r}$ . When $r<x\le 100r$ , u will have at least $(r+rp)(1+o(1))$ infected neighbours (this will be an underestimate if $x<2r$ ), and this exceeds $2r\theta$ when $2\theta<1+p$ . Accordingly, we name the inequality $2\theta<1+p$ (which is already familiar to us from Theorem 1) the global growth condition and display it for convenience:

\begin{align*}\boxed{\textbf{Global growth condition:}\ \ \theta<\frac{1+p}{2}.}\end{align*}

We also have the condition from Proposition 1 for the infection to start:

\begin{align*}\boxed{\textbf{Starting condition:}\ \ a(p-\theta+\theta\log(\theta/p))<1\ \ \textrm{or }\ \theta \lt p.}\end{align*}

Next, we describe the spread of the infection beyond $I_{100r}$ . As a consequence of Lemma 2(ii), if the starting condition is met, then the infection will actually start in $n^{\alpha+o(1)}$ sites, where $\alpha= 1-f_{\textrm{start}}(a,p,\theta)$ . If the global growth condition is also met, these local infections will grow on both sides from each such site, until one of them is met by a (left or right) blocking set, which we describe below.

4.3. Blocking sets

In this subsection, we assume that both the starting and the global growth conditions are satisfied. What can then stop an infection from spreading around the circle? We shall distinguish two possible obstructions: blocking sets (where initially uninfected vertices in an interval of length at least 2r stay uninfected) and islands (where initially uninfected vertices in an interval of length at most 2r stay uninfected). In this subsection, we deal with the former.

A clockwise, or right, blocking set consists of two contiguous intervals, both of length r. The left interval contains zr vertices, and the right interval contains xpr initially infected vertices, both sets of vertices being uniformly distributed within their respective intervals (note that as remarked in Section 4.1, uniform distribution occurs w.h.p. conditional on the sizes of the two vertex sets). Even if all the vertices in the left interval become infected, the infection will not spread to the right interval (or, more precisely, clockwise) as long as

(13) \begin{align}(z+xp)r<a\theta\log n=2r\theta,\end{align}

i.e. as long as $xp+z<2\theta$ . In other words, if this strict inequality is satisfied then the right interval in a right blocking set can only be infected ‘from the right’—the vertices in the left interval do not on their own suffice to spread the infection further to the right.

We wish to maximize the probability that such a right blocking set configuration occurs somewhere in the circle. Using Lemma 1, we see that the probability $q=q(x,z)$ of a blocking set with parameters x and z is given by

\begin{align*}q&=\exp\{r(z-1-z\log z)+pr(x-1-x\log x)+o(r)\}\\&=\exp\left\{\frac{a\log n}{2}\left((z-1-z\log z)+p(x-1-x\log x)+o(1)\right)\right\}.\end{align*}

Consequently, to maximize the probability that a blocking set occurs, we must maximize

\begin{align*}f(x,z)=z-1-z\log z+p(x-1-x\log x)\end{align*}

subject to the constraint

\begin{align*}g(x,z)=xp+z\leq 2\theta,\end{align*}

with p and $\theta$ fixed. Using the method of Lagrange multipliers, we see that f(x, z) is maximized when

\begin{align*}(x,z)=\left(\frac{2\theta}{1+p},\frac{2\theta}{1+p}\right),\end{align*}

and, since the growing condition is satisfied, we note that $x=z<1$ at the maximum. Substituting, the maximum $f_{\textrm{max}}$ of f(x, z) subject to $g(x,z)\leq 2\theta$ is given by

\begin{align*}f_{\textrm{max}}=2\theta-(1+p)-2\theta\log\left(\frac{2\theta}{1+p}\right),\end{align*}

so that the maximum of q(x, z) is

\begin{align*}q_{\textrm{max}}=\exp\left\{-a\log n\left(\frac{1+p}{2}-\theta+\theta\log\left(\frac{2\theta}{1+p}\right)+o(1)\right)\right\}.\end{align*}

We conclude that the expected number of blocking sets is $n^{\beta+o(1)}$ , where

\begin{align*}\beta=1-a\left(\frac{1+p}{2}-\theta+\theta\log\left(\frac{2\theta}{1+p}\right)\right).\end{align*}

Recall also that, as long as $\theta>p$ , the infection starts in $n^{\alpha+o(1)}$ places, where

\begin{align*}\alpha=1-f_{\textrm{start}}(a,p,\theta)=1-a(p-\theta+\theta\log(\theta/p)).\end{align*}

Now assume that the starting and growing conditions are satisfied, and consider the case $0<\alpha<\beta<1$ . Infections will start to spread in $n^{\alpha+o(1)}$ places, and these will be blocked by $n^{\beta+o(1)}\gg n^{\alpha+o(1)}$ blocking sets (a right blocking set stops infections spreading clockwise, and a left blocking set stops infections spreading anticlockwise). Accordingly, each of the $n^{\alpha+o(1)}$ growing infections will spread for distance $n^{1-\beta+o(1)}$ before being blocked in both the clockwise and the anticlockwise direction, so that the infections will cover $n^{1+\alpha-\beta+o(1)}=o(n)$ of the circle. We call this the regime of ‘polynomial growth’; in this regime, the spread of infection is largely contained.

Next, assume again that the starting and growing conditions are satisfied, but suppose that $0<\alpha/2<\beta<\alpha<1$ . The $n^{\alpha+o(1)}$ spreading infections will encounter $n^{\beta+o(1)}\ll n^{\alpha+o(1)}$ blocking sets, and since these blocking sets will usually be isolated, with spreading infections on each side, most of the circle will become infected. The only likely obstructions (save for the ‘islands’ to be described in the next subsection) are pairs of blocking sets (reading clockwise, a right blocking set followed by a left blocking set) with no growing infection between them.

To be slightly more precise, suppose there is some interval I of length at least r such that (a) every initially uninfected vertex in I stays uninfected, and (b) every vertex in the intervals of length r to the left and to the right of I become infected. Let v denote the leftmost uninfected vertex in I. Let zr denote the number of vertices in the interval of length r to the left of v, and xpr the number of initially infected vertices in the interval of length r to the right of v. Then x, z satisfy (13). Now, conditional on having zr vertices in the interval to the left of r and xpr initially infected vertices in the interval to the right of r, we know that w.h.p. these points are uniformly distributed on these intervals. Thus, up to a $(1+o(1))$ multiplicative factor, the probability of seeing such a point configuration is the probability of seeing a right blocking set with parameter (x, z), and hence is at most $n^{\beta +o(1)}$ . (Formally, one must also use approximate densities as sketched in Section 4.1 to partition the collection of all (x, z) into a finite collection of rational pairs, as well as the continuity of the functions f and q in order to show that the contribution from configurations with (x, z) close to $\left(\frac{2\theta}{1+p}, \frac{2\theta}{1+p}\right)$ dominates.)

There will be $n^{\beta}\cdot n^{\beta-\alpha+o(1)}=n^{2\beta-\alpha+o(1)}$ such pairs, typically separated by distance $n^{1+\alpha-2\beta+o(1)}$ , so that the entire circle except for regions of length totalling $n^{1-2\beta+\alpha+o(1)}=o(n)$ will become infected. We call this the regime of ‘polynomial obstructions’: when $2\beta>\alpha$ , blocking sets by themselves cannot prevent the spreading infections from covering most of the circle.

There are thus two thresholds: the first, separating the regime of polynomial growth from that of polynomial obstructions, occurring at $\alpha=\beta$ , and the second, separating the regime of polynomial obstructions from that of ‘logarithmic obstructions’ (caused by islands—see the subsection below), occurring at $\alpha=2\beta$ .

When finding these thresholds, we recall that they lie entirely inside the region $\theta\ge p$ , since $\alpha=1$ when $\theta\le p$ . For the first threshold, we have $\alpha>\beta$ exactly when

\begin{align*}\frac{1+p}{2}-\theta+\theta\log\left(\frac{2\theta}{1+p}\right)>p-\theta+\theta\log(\theta/p),\end{align*}

which yields the following expression for the threshold:

\begin{align*}\boxed{\textbf{First threshold condition:}\ \ \frac{1-p}{2}>\theta\log\left(\frac{1+p}{2p}\right).}\end{align*}

Note that this region contains the region $\theta\le p$ (as can be seen from the Taylor expansion of the right-hand side), and is independent of the choice of $a>1$ . For the second threshold, we have $\alpha>2\beta$ exactly when

\begin{align*}1-a(p-\theta+\theta\log(\theta/p))>2\left(1-a\left(\frac{1+p}{2}-\theta+\theta\log\left(\frac{2\theta}{1+p}\right)\right)\right),\end{align*}

which yields the following expression for the threshold:

\begin{align*}\boxed{\textbf{Second threshold condition:}\ \ a\left(1-\theta+\theta\log\left(\frac{4\theta p}{(1+p)^2}\right)\right)>1\ \ \textrm{or }\ \theta\lt p.}\end{align*}

This time, we need to include the additional condition $\theta<p$ .

4.4. Islands

Next assume that the starting, global growth, and first and second threshold conditions are all satisfied. What can then prevent full percolation? In this subsection, we sketch how the final obstructions for the infection to overcome are islands, i.e. intervals of length at most r in which no new infection is recorded.

Figure 3.

An island.

For $c\in [0,1]$ , a cr- island, illustrated in Figure 3, consists of five contiguous intervals whose lengths, from left to right, are cr, $(1-c)r$ , cr, $(1-c)r$ , and cr. Inside these intervals there are, from left to right, zcr vertices, $y(1-c)r$ vertices, xpcr initially infected vertices, $y(1-c)r$ vertices, and zcr vertices, all uniformly distributed within their respective intervals. We note that even if all the vertices in the four outermost intervals become infected, no vertices inside the middle interval will become infected, as long as

\begin{align*}cz+2y(1-c)+xpc<2\theta.\end{align*}

We wish to maximize the probability that such a set occurs.