Competing deterministic growth models in two dimensions

Janko Gravner
Department of Mathematics

University of California

Davis, CA 95616

<EMAIL_ADDRESS>
David Sivakoff
Departments of Statistics and Mathematics

The Ohio State University

Columbus, OH 43210, USA

<EMAIL_ADDRESS>
###### Abstract

We consider three-state cellular automata in two dimensions in which two
colored states, blue and red, compete for control of the empty background,
starting from low initial densities $p$ and $q$. When the dynamics of both
colored types are one-dimensional, the dynamics has three distinct phases,
characterized by a power relationship between $p$ and $q$: two in which one of
the colors is prevalent, and one when the colored types block each other and
leave most of the space forever empty. When one of the colors spread in two
dimensions and the other in one dimension, we also establish a power relation
between $p$ and $q$ that characterizes which of the two colors eventually
controls most of the space.

##  1 Introduction

Competing growth models were introduced in the probabilistic literature in the
1990s as a class of deterministic cellular automata called threshold voter
models [GG], and as multiple-type first passage percolation dynamics [HP1,
HP2]. The latter processes have been explored further in [Hof, SS, CS, FS1,
FS2]. In these models, two types of particles compete for space using simple
infection rules, which may not be the same for both types; for example, one of
the types may spread faster or require “activation.” Such models are
intrinsically non-monotone, which poses a challenge in rigorous analysis.
Another competition between two types of particles, introduced in [GM], is
when one of the types is inert and simply provides a random environment — a
field of obstacles — in which the other type tries to spread. See [GH, GHS,
Gho] for recent progress on such dynamics. In the context of the present work,
these obstacles undergo degenerate, zero-dimensional, growth. By contrast,
[GG] studies cases when the types both spread in two dimensions (with
sufficient regularity). It is thus natural to consider the remaining
possibility whereby the two growths have different non-zero dimensions and we
investigate such competing growth models on the planar lattice; the two types
may in addition have different range and spread at different speeds. Our
motivation comes from the earlier work on models that combine one- and two-
dimensional growth features [BGSW]. Recent physical literature also includes
experiments and mathematical models of crystal growth that may vary the
dimensionality depending on nucleation conditions [YLG+] and in particular
features competition between one-dimensional crystals growing in different
directions [CLY+, YLG+], which warrants further mathematical investigation of
such dynamics.

In our model, each vertex of ${\mathbb{Z}}^{2}$ is independently initially

(1.1) $\begin{cases}\text{blue}&\text{with probability }p\\\
\text{red}&\text{with probability }q\\\ \text{empty}&\text{with probability
}1-p-q.\end{cases}$

Let $\mathcal{B}\subset{\mathbb{Z}}\times\\{0\\}$ and
${\mathcal{R}}\subset{\mathbb{Z}}^{2}$ be finite subsets of the lattice, and
fix an update interval for red $r>0$. At times $t\in\\{1,2,3,\ldots\\}$, every
empty vertex $x\in{\mathbb{Z}}^{2}$ that has a blue neighbor in
$x+\mathcal{B}$ becomes blue. At times $t\in\\{r,2r,3r,\ldots\\}$, every empty
vertex $x\in{\mathbb{Z}}^{2}$ that has a red neighbor in $x+{\mathcal{R}}$
becomes red. Ties are decided according to independent fair coin flips. In
this way, our model is a competition between two deterministic first-passage
processes, where blue spreads via its neighborhood at speed $1$, and red
spreads via its neighborhood at speed $1/r$.

We denote the resulting configuration at time $t\in[0,\infty)$ by $\xi_{t}$.
As every site in ${\mathbb{Z}}^{2}$ changes state at most once, we may define
the final configuration $\xi_{\infty}$, in which every site has its final
state. Properties of this random configuration are of our primary interest.

Our first result is on competing one-dimensional processes, resembling the
dynamics in [CLY+], in which red grows vertically with range $\rho$ and blue
grows horizontally with range $\tau$.

Figure 1: Illustration of Corollary 1.2 when $\rho=\tau=1$: final
configurations on an $800\times 800$ torus when $p=0.001$, $q=0.001$ (left)
and $q=0.02$ (right).

######  Theorem 1.1.

Assume that ${\mathcal{R}}=\\{0\\}\times([-\rho,\rho]\cap{\mathbb{Z}})$ and
$\mathcal{B}=([-\tau,\tau]\cap{\mathbb{Z}})\times\\{0\\}$, with
$\rho,\tau\in{\mathbb{Z}}_{\geq 1}$. If $q=ap^{\gamma}$ where
$\gamma=\frac{1}{\tau}+\frac{\rho}{\rho+1}$, then

$0<\liminf_{p\to 0}\mathbb{P}(0\text{ is eventually blue})\leq\limsup_{p\to
0}\mathbb{P}(0\text{ is eventually blue})<1.$

Moreover, the $\limsup$ tends to $0$ as $a\to\infty$ and the $\liminf$ tends
to $1$ as $a\to 0$.

We conclude that, as $q$ increases compared to $p$, the dynamics can be in
three distinct phases, dominated by blue, neither, or red. For example, when
$\rho=\tau=1$, the three phases occur when $q\ll p^{3/2}$, $p^{3/2}\ll q\ll
p^{2/3}$ and $q\gg p^{2/3}$. See Figure 1 for an illustration.

######  Corollary 1.2.

Assume the same setting as in the above Theorem 1.1, and additionally denote
$\gamma^{\prime}=\frac{1}{\rho}+\frac{\tau}{\tau+1}$. Then
$\gamma\gamma^{\prime}>1$ and

  * •

if $q\ll p^{\gamma}$, $\mathbb{P}(0\text{ is eventually blue})\to 1$;

  * •

if $p^{\gamma}\ll q\ll p^{1/\gamma^{\prime}}$, $\mathbb{P}(0\text{ remains
empty for all time})\to 1$; and

  * •

if $p^{1/\gamma^{\prime}}\ll q$, $\mathbb{P}(0\text{ is eventually red})\to
1$.

Our second result addresses competition between a two-dimensional red growth
with range $\rho$ and a one-dimensional blue one. To strengthen the second
part of the theorem, we show that the blue type still wins in the appropriate
regime even if it only spreads leftward, with the smallest possible range $1$.
See Figure 2 for an illustration.

Figure 2: Illustration of Theorem 1.3 when $\rho=2$ and
$\mathcal{B}=\\{e_{1}\\}$: final configurations on $800\times 800$ torus when
$p=0.04$, $q=0.0001$ (left) and $q=0.001$ (right).

######  Theorem 1.3.

(1) Assume that ${\mathcal{R}}=\\{x\in{\mathbb{Z}}^{2}:||x||_{1}\leq\rho\\}$
for some $\rho\in{\mathbb{Z}}_{\geq 1}$. If $e_{1}\in\mathcal{B}$ and $p,q$
are not both zero, then a.s. every site in ${\mathbb{Z}}^{2}$ is eventually
nonempty.

In (2) and (3) below, assume that $q=ap^{1+\rho/(\rho+1)}$.

(2) Suppose first that
$\mathcal{B}=([-\tau,\tau]\cap{\mathbb{Z}})\times\\{0\\}$, with
$\tau\in{\mathbb{Z}}_{\geq 1}$. Then for every $a>0$,

$\limsup_{p\to 0}\mathbb{P}(0\text{ is eventually blue})<1$

and tends to $0$ as $a\to\infty$.

(3) Suppose next that $\mathcal{B}=\\{e_{1}\\}$. Then for every $a>0$,

$\liminf_{p\to 0}\mathbb{P}(0\text{ is eventually blue})>0$

and tends to $1$ as $a\to 0$.

We give the very simple proof of the first statement right away.

###### Proof of (1).

Let $A=\inf\\{a\geq 0:(a,0)\text{ is nonempty in the final configuration}\\}$.
As at least one of $p$ and $q$ is nonzero, $P(A<\infty)=1$. If $a>0$ is
finite, then on the event $\\{A=a\\}$ there is a finite time $t$ at which
$(a,0)$ is colored, which causes $(a-1,0)$ to be colored by time $t+(1\vee
r)$. This implies that $\\{A<\infty\\}=\\{A=0\\}$. ∎

The proof of part (2) of Theorem 1.3 is relatively straightforward, and the
key lemma is proved in Section 2. The most substantial effort is devoted to
proving part (3) of Theorem 1.3. This involves a multiscale argument, whose
essential ingredients are already necessary for the nearest neighbor case
$\rho=1$. To make the presentation more readable, we therefore assume $\rho=1$
until Section 4. The bulk of the argument is in Section 3, and in Section 4 we
explain the modifications necessary for the general case. We also complete the
proofs of Theorem 1.1 and Corollary 1.2 in Section 4. In Section 5 we conclude
with a discussion of open problems and extensions to multicolor dynamics.

##  2 Red wins

In this section, we prove the following lemma, which implies part (2) of
Theorem 1.3.

######  Lemma 2.1.

Assume that ${\mathcal{R}}=\\{\pm e_{1},\pm e_{2}\\}$, $r>0$ is arbitrary, and
$\mathcal{B}=([-\tau,\tau]\cap{\mathbb{Z}})\times\\{0\\}$, with
$\tau\in{\mathbb{Z}}_{\geq 1}$. If $q=ap^{3/2}$, then

$\liminf_{p\to 0}\mathbb{P}(0\text{ is eventually red})>0$

for every $a>0$ and tends to $1$ as $a\to\infty$.

###### Proof.

To gain independence between red and blue vertices, we construct the initial
configuration in two stages. First, mark each site independently as red with
probability $q$. Next, mark each site independently potentially blue with
probability $p^{\prime}=\frac{p}{1-q}$. To realize the initial state (1.1),
label each site marked red as red, label each site that is not red but
potentially blue as blue, and label each remaining site empty.

$A+1$$2A+1$$(0,0)$$(B,0)$$(B+A,0)$$(-B,0)$$(-(B+A),0)$ Figure 3: Assuming
$r=\tau=1$, the origin becomes red if there are integers $A$ and $B$ so that,
initially, there is a red site in the rectangle $[0,B]\times[0,A]$ (grey), no
blue site in the outlined $(2A+1)\times(A+1)$ rectangle centered horizontally
around that red site, and also no blue site in the interval on the $x$ axis
from $(-(B+A),0)$ to $(B+A,0)$.

We define the following two events for a constant $\epsilon>0$ and small
enough $p$:

(2.1) $\displaystyle G$ $\displaystyle=\\{\text{there is no potentially blue
site in }[-\epsilon\tau r/p,\epsilon\tau r/p]\times\\{0\\}\\},\quad\text{and}$
$\displaystyle H$ $\displaystyle=\\{\text{there is a red site
$(x,y)\in[0,\epsilon/2p]\times[0,\epsilon/\sqrt{p}]$ and}$
$\displaystyle\qquad\text{ no potentially blue site in $[x-2\epsilon\tau
r/\sqrt{p},x+2\epsilon\tau r/\sqrt{p}]\times[0,\epsilon/\sqrt{p}]$}\\}.$

Observe that on the event $G\cap H$, the origin becomes red because the red
site at $(x,y)$ causes $(x,0)$ to become red by time $\epsilon\tau
r/\sqrt{p}$, before blue can interfere, and this red growth propagates to the
origin in additional time at most $\epsilon\tau r/2p$, before the closest blue
could reach the origin. See Figure 3.

Fix $\delta>0$. Choose $\epsilon$ small enough that $3\epsilon\tau r<\delta$
and $6\epsilon^{2}\tau r<\delta$, so that for small enough $p$ (and $q$), we
have $\mathbb{P}(G^{c})<\delta$ and

$\displaystyle\mathbb{P}(\text{there exists a potentially blue site in
$[-2\epsilon\tau r/\sqrt{p},2\epsilon\tau
r/\sqrt{p}]\times[0,\epsilon/\sqrt{p}]$})$
$\displaystyle\leq\frac{5\epsilon^{2}\tau r}{p}p^{\prime}\leq
6\epsilon^{2}\tau r<\delta.$

Then,

$\mathbb{P}(\text{there is no red site in
}[0,\epsilon/2p]\times[0,\epsilon/\sqrt{p}])\leq(1-q)^{\epsilon^{2}/3p^{3/2}}\leq\exp(-\epsilon^{2}a/3).$

It follows by independence between red sites and potentially blue sites that

$\mathbb{P}(H)\geq(1-\delta)(1-\exp(-\epsilon^{2}a/3)).$

Since $G$ and $H$ are positively correlated, for every $a>0$ and all
sufficiently small $p$ we have

$\mathbb{P}(0\text{ is eventually red})\geq\mathbb{P}(G\cap
H)\geq(1-\delta)^{2}(1-\exp(-\epsilon^{2}a/3))>0.$

This proves the first claim of the lemma. The second claim follows by taking
$a$ sufficiently large such that $\exp(-\epsilon^{2}a/3)<\delta$. ∎

##  3 Blue wins

We prove in this section the lower bound on the probability that the origin is
eventually blue when $\mathcal{B}=\\{e_{1}\\}$ and ${\mathcal{R}}=\\{\pm
e_{1},\pm e_{2}\\}$. Observe that we have monotonicity in the red
configurations, meaning that adding red sites at any time results in more
sites being colored red and fewer sites colored blue at later times.
Therefore, without loss of generality, we can assume that $r\leq 1$.

For blue to win, it is sufficient that the following conditions hold:

  1. 1.

there is an initially blue vertex in $[0,C/p]\times\\{0\\}$; and

  2. 2.

no vertex in $[-C/p,C/p]\times\\{0\\}$ is colored red by time $C/p$.

Condition 1 is easy to guarantee by choosing $C$ large. Condition 2 is much
more subtle. We will construct a blocking configuration of initially blue
sites, whose eventual growth will intercept any red sites below its center,
thus preventing red from reaching the $x$-axis from below. By symmetry, a
similar structure will also stop red from above.

###  3.1 A continuous comparison process

We describe here a process in continuous time and space, for which we show
that blue can slow the vertical progression of red. In this process, we let
$\widetilde{R}_{t}\subset{\mathbb{R}}^{2}$ denote the set of red points at
time $t\in[0,\infty)$, and let $\widetilde{B}\subset{\mathbb{R}}^{2}$ be the
set of blue points, which will not change in time in the comparison process.
Red points will grow vertically at infinite speed, and horizontally at speed
$1/\alpha$ with $\alpha\in(0,\infty)$, but cannot pass through blue sites, and
must grow around them. More precisely, for $z,z^{\prime}\in{\mathbb{R}}^{2}$,
let $\Gamma(z,z^{\prime})$ denote the set of paths in ${\mathbb{R}}^{2}$ that
start at $z$, end at $z^{\prime}$, and move only horizontally or vertically.
That is, each path in $\Gamma(z,z^{\prime})$ consists of line segments
connecting consecutive points in $z=z_{0},z_{1},\ldots,z_{n}=z^{\prime}$ for
some $n$ and such that $z_{i}-z_{i-1}$ has exactly one coordinate equal to
$0$. The length of a path $\gamma=(z_{0},\ldots,z_{n})\in\Gamma(z,z^{\prime})$
is $\mathrm{Len}(\gamma):=\alpha\sum_{i=1}^{n}|x_{i}-x_{i-1}|$, where
$z_{i}=(x_{i},y_{i})$, so $\mathrm{Len}(\gamma)$ is $\alpha$ times the total
horizontal displacement along $\gamma$. Then, given the sets
$\widetilde{R}_{0}$ and $\widetilde{B}$, the set of red points at time $t$ is

$\widetilde{R}_{t}=\\{z\in{\mathbb{R}}^{2}:\inf\\{\mathrm{Len}(\gamma):\gamma\in\Gamma(z,z^{\prime}),z^{\prime}\in\widetilde{R}_{0},\gamma\cap\widetilde{B}=\emptyset\\}\leq
t\\}.$

We now describe the initial sets $\widetilde{R}_{0}$ and $\widetilde{B}$.
Since red grows vertically at infinite speed, the vertical displacements
between points in these sets will be immaterial, so we choose unit spacing.
For $f,g,h\in(0,\infty)$ and integer $m\geq 1$, let

$\widetilde{R}_{0}=[0,f]\times\\{0\\},$

and

$\widetilde{B}=\bigcup_{k=1}^{m}\Big{\\{}[(k-1)g-kh,kg-
kh]\times\\{k\\}\Big{\\}}.$

Note that $\widetilde{B}$ consists of $m$ horizontal intervals of length $g$.
We want the horizontal extent of $\widetilde{B}$ to exceed that of
$\widetilde{R}_{0}$ by $h$ on either side, so we require

(3.1) $m(g-h)=f+h.$

With this choice, observe that $\widetilde{R}_{t}$ contains points with
arbitrarily large (positive) second coordinate only after time $\alpha h$.
This follows because the horizontal overlap between successive blue intervals
is $h$, and the overhang beyond $[0,f]$ is also $h$. So red “escapes” blue
after this time, and the horizontal extent of $\widetilde{R}_{\alpha h}$ is
$[-h,f+h]$.

$f$$h$$h^{\prime}$$f^{\prime}$$g$$g^{\prime}$$\widetilde{B}$$\widetilde{B}^{\prime}$
Figure 4: The comparison process with $\alpha=1$ and $m=3$, and so
$\lambda=5/4$. The overhangs of length $h$ and $h^{\prime}$ are framed by
black rectangles. The dashed line illustrates one shortest path on which red
can break through the bottom configuration $\widetilde{B}$ of blue sites. Once
that happens, we assume that the entire interval of length $f^{\prime}$ is
painted red, and then the red can proceed to break through the next, larger,
configuration of blue sites, which is the appropriately translated
configuration $\widetilde{B}^{\prime}$.

In the discrete dynamics, we will have a sequence of configurations of blue
sites, and each configuration is intended to slow the vertical progress of red
by some amount. To obtain a lower bound on how much blue can slow the progress
of red, when red first reaches a blue configuration, we stop the growth of
blue sites in that configuration, but allow blue to continue to spread in
configurations above, which red has not reached up to that time. Therefore, in
our continuous comparison process, we put a second configuration of blue above
the first to further impede the vertical progress of red, which has had the
advantage of being able to “grow” for an additional time $\alpha h$ before red
is first able to reach these blue sites, but now must block an interval of red
with horizontal extent of length $f+2h$. To quantify this situation, with
$f^{\prime},g^{\prime},h^{\prime}>0$ and $m$ as above, we shift back to the
origin (to the right by $h$ and vertically so that red lies on the $x$-axis)
to obtain the new initial coloring,

(3.2) ${}\widetilde{R}^{\prime}_{0}=[0,f^{\prime}]\times\\{0\\}$

and

(3.3)
$\widetilde{B}^{\prime}=\bigcup_{k=1}^{m}\Big{\\{}[(k-1)g^{\prime}-kh^{\prime},kg^{\prime}-kh^{\prime}]\times\\{k\\}\Big{\\}}.$

We have the additional consistency equations,

(3.4) $m(g^{\prime}-h^{\prime})=f^{\prime}+h^{\prime},\qquad
f^{\prime}=f+2h,\qquad g^{\prime}=g+\alpha h.$

In matrix form, these are

$\begin{pmatrix}f^{\prime}\\\ g^{\prime}\end{pmatrix}=A\begin{pmatrix}f\\\
g\end{pmatrix}$

where

$A=\begin{pmatrix}1-\frac{2}{m+1}&\frac{2m}{m+1}\\\
\frac{-\alpha}{m+1}&\frac{m+\alpha m+1}{m+1}\end{pmatrix}.$

The matrix $A$ has eigenvalues $1$ and $\lambda=\frac{m+\alpha m-1}{m+1}$, and
we want $\lambda>1$, so we choose $m>2/\alpha$. The eigenvector corresponding
to eigenvalue $\frac{m+\alpha m-1}{m+1}$ is $(1,\frac{\alpha}{2})$, so if we
assume $g=\frac{\alpha}{2}f$, then

$h=\frac{(\frac{m\alpha}{2}-1)f}{m+1}>0$

and

$(f^{\prime},g^{\prime},h^{\prime})=\lambda(f,g,h).$

See Figure 4 for an illustrative example.

In our discrete system, to make the existence of a blocking configuration of
blue sites likely we will need larger intervals at each level wherein
existence of initially blue sites guarantee a configuration resembling
$\widetilde{B}^{\prime}$ will exist at an appropriate time in the growth
process. To identify these intervals, we imagine what happens if red grows at
a slower speed than $1/\alpha$, and take $\overline{\alpha}>\alpha$. Then
$\widetilde{R}_{t}$ will first pass the configuration $\widetilde{B}$ only
after time $\overline{\alpha}h>\alpha h$, so the blue in the next
configuration has additional time $(\overline{\alpha}-\alpha)h$ to grow,
relative to the faster-moving red. Therefore,
$\bar{g}^{\prime}=g^{\prime}+(\overline{\alpha}-\alpha)h$ is the length of
each blue interval in the second configuration of blue for the slower-moving
red. We can translate to the right the right endpoint of each blue interval
from $\widetilde{B}^{\prime}$ by up to $(\overline{\alpha}-\alpha)h$ and still
blue will have sufficient time to cover the original intervals.

###  3.2 Discrete blocking configuration

To make the connection with the discrete system, we construct layers in which
blue sites will dominate the blue intervals in the continuous configurations
at the appropriate times. In each discrete layer, we will increase the
horizontal dimension by a factor $\mu^{2}>1$ and decrease the vertical
dimension by the factor $1/\mu<1$. Since the continuous process indicates that
each layer grows horizontally by a factor $\lambda$ from the previous layer,
we take $\mu^{2}=\lambda$, so the area of each region increases by the factor
$\mu=\sqrt{\lambda}>1$. The first layer has height $m/\sqrt{p}$, which is
subdivided into $m$ sublayers of height $1/\sqrt{p}$. Each subsequent layer
will have height $(1/\mu)$ times the height of the previous layer, rounded up
to the next integer multiple of $m$. Within the $k$th layer, each of the $m$
sublayers will contain a blue point within a rectangle with dimensions
$(1/\sqrt{\lambda^{k}p})\times(\lambda^{k}C/\sqrt{p})$ centered at certain
points. The construction will be such that the probability that every such
rectangle (for every $k\geq 0$) contains at least one initially blue point
tends to $1$ as $C\to\infty$ for all small $p$.

Construction of the blocking configuration centered at $(0,0)$ begins by
choosing $\alpha<\overline{\alpha}<r$ with $\alpha<1$, fixing $m>2/\alpha$ and
defining a sequence $(f_{\ell},g_{\ell},h_{\ell})_{\ell\geq 0}$ for the
continuum dynamics with $f_{0}=1$, $g_{0}=\frac{\alpha}{2}$ and
$h_{0}=\frac{(\frac{m\alpha}{2}-1)}{m+1}$ so that

$(f_{\ell+1},g_{\ell+1},h_{\ell+1})=\lambda(f_{\ell},g_{\ell},h_{\ell}).$

We also define $S_{0}=0$ and $S_{\ell+1}=S_{\ell}-h_{\ell}$ for $\ell\geq 1$
to account for the artificial shift to the origin in our frame of reference in
the continuous dynamics at (3.3).

For $u\in{\mathbb{R}}$, we define the rescaled $u$ to be
$\lceil\frac{1}{\sqrt{p}}u\rceil$, and analogously for vectors
$u\in{\mathbb{R}}^{d}$ and for the dimensions of rectangles. We assume that
red starts from a single point at rescaled $(0,-\frac{g_{1}}{\alpha})$. The
shift downward by $g_{1}/\alpha$ is to allow time for blue to grow
horizontally by at least $g_{1}$ at the time red reaches the $x$-axis and is
contained in the rescaled interval $[0,f_{0}]\times\\{0\\}$ to initialize the
continuous growth comparison. Note that for this initialization step, we
assume that red propagates vertically and horizontally at speed $1/\alpha$.
After this initialization step, we assume that red propagates vertically at
infinite speed, as it does in the continuous comparison process.

We now translate the continuous blocking construction into a discrete one by
identifying boxes through which horizontal lines of blue sites will appear by
the appropriate times, assuming there are initially blue sites nearby the
right edges of these lines. These boxes are divided into layers of $m$ boxes
each. The $0$th layer of boxes have lower-left endpoints at rescaled
$x$-coordinates $(k-1)g_{0}-kh_{0}$ for $k=1,\ldots,m$; they have width
rescaled $g_{0}$; they have height rescaled $1$; and they are stacked
disjointly and adjacently above the $x$-axis. Each subsequent layer is stacked
disjointly above the previous layer and adjacent to it. The lower-left
endpoints of the boxes in the $\ell$th layer are at rescaled
$(k-1)g_{\ell}-kh_{\ell}+S_{\ell}$ for $k=1,\ldots,m$; they have width
rescaled $g_{\ell}$; they have height rescaled $1/\lambda^{\ell/2}$; and they
are stacked disjointly and adjacently.

Figure 5: An example of a layer with $m=3$ in which all boxes (outlined in
blue) are successful: there is a blue site in each of the $m$ shaded
activation regions.

We call the $k$th box in the $\ell$th layer successful if there is at least
one blue site initially in the box immediately to its right with the same
rescaled height $1/\lambda^{\ell/2}$ and rescaled width
$(\overline{\alpha}-\alpha)h_{\ell-1}$. We call these boxes the activation
regions corresponding to the $k$th box in the $\ell$th layer. We call the
$k$th box in the $0$th layer successful if there is a blue site initially in
the activation region immediately to its right with rescaled height $1$ and
rescaled width $\frac{1}{2}(\overline{\alpha}-\alpha)$. We say the entire
blocking configuration centered at $(0,0)$ is successful if every box in every
layer is successful. See Figure 5.

Let

$\displaystyle{\mathcal{C}}(x_{0},y_{0})$
$\displaystyle:=(x_{0},y_{0})+\\{(x,y):y\leq-|x|\\}$
$\displaystyle{\mathcal{C}}^{\prime}(x_{0},y_{0})$
$\displaystyle:=(x_{0},y_{0})+\\{(x,y):y\geq|x|\\}$

denote the downward and upward affine cones with peak at $(x_{0},y_{0})$.

######  Lemma 3.1.

If the blocking configuration centered at $(0,0)$ is successful and initially
red sites are confined to the rescaled affine cone
${\mathcal{C}}(0,-g_{1}/\alpha)$, then every box in the construction contains
a horizontal line spanning the box that is colored blue before the first time
that red enters the smallest horizontal strip containing the box. Moreover,
the static initial configuration of blue, which consists only of the line
segments crossing each box in the blocking configuration and does not grow,
also prevents red from reaching the smallest horizontal strip containing the
boxes in layer $\ell$ before time
$\frac{1}{\sqrt{p}}\left[g_{\ell}+(\overline{\alpha}-\alpha)h_{\ell-1}\right]$.

###### Proof.

By monotonicity, we may assume that every point in the affine cone is
initially red. For the initialization step, observe that it takes time
$\frac{1}{\sqrt{p}}\left[g_{0}+\frac{1}{2}(\overline{\alpha}-\alpha)\right]=\frac{\overline{\alpha}}{2\sqrt{p}}$
for blue to grow across the boxes in layer $0$. Meanwhile, it takes time

$\frac{g_{1}r}{\alpha\sqrt{p}}>\frac{r}{2\sqrt{p}}>\frac{\overline{\alpha}}{2\sqrt{p}}$

for red to first reach the $x$-axis, which it first does at the origin. This
verifies the base case for our induction argument. At the time at which red
first reaches the $x$-axis, we can assume the dynamics proceeds from the
single red point at the origin and the blue configuration at this time, which
we can compare to the continuous dynamics.

For the induction step, we assume that the time it takes for red to first
reach layer $\ell$ from this initial configuration is at least
$\frac{g_{\ell}}{\sqrt{p}}$, and the points in layer $\ell$ that are first
colored red are contained in the rescaled interval
$[S_{\ell},S_{\ell}+f_{\ell}]$. To compute the time for red to reach the
$(\ell+1)$st layer in the discrete dynamics, we compare with the continuous
dynamics where red grows at speed $1/\overline{\alpha}$ within layer $\ell$.
In these dynamics, the time for red to pass the $\ell$th layer is
$\overline{\alpha}h_{\ell}$, so the time for red to reach the $(\ell+1)$st
layer in the discrete dynamics is at least

$\frac{1}{\sqrt{p}}[g_{\ell}+\overline{\alpha}h_{\ell}]=\frac{1}{\sqrt{p}}\left[g_{\ell+1}+(\overline{\alpha}-\alpha)h_{\ell}\right],$

which is an upper bound on the time for blue to horizontally cross the boxes
in layer $\ell+1$. This allows comparison with the continuous dynamics to
proceed in layer $\ell+1$, and completes the induction. ∎

The blocking configuration centered at $(x,y)\in{\mathbb{Z}}^{2}$ is defined
by shifting the blocking configuration centered at $(0,0)$ by $(x,y)$, and as
above, a blocking configuration is successful if every box in every layer is
successful. We also define the transposed blocking configuration centered at
$(x,y)\in{\mathbb{Z}}^{2}$ by reflecting the blocking configuration centered
at $(0,0)$ over the $x$-axis, then shifting by $(x,y)$. Again, a transposed
blocking configuration is successful if every box in every layer is
successful.

The next lemma confirms that a collection of successful blocking
configurations will not be interfered with by the growth of red sites,
provided red sites are restricted to a certain region. Because blue sites
expand in time, the red dynamics are not additive, but an additive dynamics
can be used for comparison.

######  Lemma 3.2.

Let $x_{1},x_{2},\ldots,x_{K}\in{\mathbb{R}}$. Suppose that for every
$k=1,\ldots,K$, the blocking configuration centered at rescaled $(x_{k},0)$ is
successful, and that the initially red points are confined to the union of
rescaled affine cones

$\bigcup_{k=1}^{K}{\mathcal{C}}(x_{k},-g_{1}/\alpha).$

Then every box in every blocking configuration contains a horizontal line
spanning the box that is colored blue before the first time that red enters
the smallest horizontal strip containing the box.

###### Proof.

Lemma 3.1 says that if red starts from rescaled
${\mathcal{C}}(x_{k},-g_{1}/\alpha)$ and the blocking configuration centered
at rescaled $(x_{k},0)$ is successful, then the dynamic blue environment
achieves a configuration in which each box of the blocking configuration is
crossed by a blue line before it comes in contact with red. This implies that
we may assume that these blue line segments are present at time $0$ and blue
is static thereafter.

To see that this is still true when we introduce multiple red cones and blue
blocking configurations, we proceed inductively on the layer $\ell$. Clearly,
the first time that red reaches the $x$-axis is still strictly larger than
$\frac{\overline{\alpha}}{2\sqrt{p}}$, which is an upper bound on the time
that it takes for blue to cross the boxes in layer $0$. Therefore, we may
assume that these boxes are crossed by blue initially, and blue does not grow
within the smallest horizontal strip containing layer $0$. Now, we assume the
statement holds through layer $\ell$, so all boxes in these layers are assumed
to be crossed by blue initially, and that blue does not grow within the half-
plane containing layers $0$ through $\ell$ and the initially red points. Then,
until the first time red exits this half-plane, the red dynamics are additive,
since they proceed according to a first-passage percolation process on a
subset of ${\mathbb{Z}}^{2}$. Therefore, by Lemma 3.1, the time it takes for
red to first reach layer $\ell+1$ is at least
$\frac{1}{\sqrt{p}}\left[g_{\ell+1}+(\overline{\alpha}-\alpha)h_{\ell}\right]$,
which is an upper bound on the time for blue to cross layer $\ell+1$. This
completes the induction. ∎

######  Lemma 3.3.

Let $\sigma=\frac{2m\sqrt{\lambda}}{\sqrt{\lambda}-1}$ and let
$x_{1},x_{2},\ldots,x_{K}\in{\mathbb{R}}$. Suppose that for every
$k=1,\ldots,K$, the blocking configuration centered at rescaled
$(x_{k},-\sigma)$ is successful, and that the initially red points are
confined to the union of rescaled affine cones

$\bigcup_{k=1}^{K}{\mathcal{C}}(x_{k},-\sigma-g_{1}/\alpha).$

Then there are no red points on the $x$-axis through time $C/p$.

###### Proof.

By Lemmas 3.1 and 3.2, blue sites will cross the boxes in layer $\ell$ of the
successful blocking configurations centered at rescaled
$(x_{1},-\sigma),\ldots,(x_{K},-\sigma)$ before red first enters the smallest
horizontal strip containing layer $\ell$. Since blue spreads at speed $1$, it
therefore takes time at least
$\frac{g_{\ell}}{\sqrt{p}}=\frac{g_{0}\lambda^{\ell}}{\sqrt{p}}$ for red to
reach layer $\ell$. Therefore, if $\ell\geq\frac{\log(1/p)}{\log\lambda}$,
then for small $p$ the time for red to reach layer $\ell$ is at least $C/p$;
choose $\ell$ to be the smallest such integer. The total height of the
blocking configuration centered at $(0,0)$ through layer $\ell$ is at most

$m\sum_{k=0}^{\ell}\left\lceil\frac{1}{\lambda^{k/2}\sqrt{p}}\right\rceil\leq
m(\ell+1)+m\sum_{k=0}^{\infty}\frac{1}{\lambda^{k/2}\sqrt{p}}=m(\ell+1)+\frac{m\sqrt{\lambda}}{(\sqrt{\lambda}-1)\sqrt{p}}\leq\frac{\sigma}{\sqrt{p}}$

for small $p$, by our choice of $\sigma$. Thus, shifting the blocking
configuration down by rescaled $\sigma$ puts the $\ell$th layer below the
$x$-axis, and prevents red from reaching the $x$-axis by time $C/\sqrt{p}$. ∎

Figure 6: Protection of the origin from red occupation, as described in Lemma
3.4. Red is initially confined to the area shaded red. The blue rectangles are
the first two layers of each successful blocking configuration: each contains
a blue site in its activation region and is horizontally traversed by a blue
line by the time it contains a red site. The closest vertical lines containing
red points are at distance on the order $1/p$ from the $y$-axis, while the
vertices of the cones are at distance on the order $1/\sqrt{p}$ from the
$x$-axis.

We now state our final protection lemma, which is illustrated in Figure 6.

######  Lemma 3.4.

Let $\sigma=\frac{2m\sqrt{\lambda}}{\sqrt{\lambda}-1}$ and let
$x_{1},x_{2},\ldots,x_{K}\in{\mathbb{R}}$ and
$x_{1}^{\prime},\ldots,x_{K^{\prime}}^{\prime}\in{\mathbb{R}}$. Suppose that
for every $k=1,\ldots,K$, the blocking configuration centered at rescaled
$(x_{k},-\sigma)$ is successful, and for every $k=1,\ldots,K^{\prime}$, the
transposed blocking configuration centered at rescaled
$(x_{k}^{\prime},\sigma)$ is successful, and all initially red points are
either in the union of rescaled affine cones,

$\bigcup_{k=1}^{K}{\mathcal{C}}(x_{k},-\sigma-
g_{1}/\alpha)\cup\bigcup_{k=1}^{K^{\prime}}{\mathcal{C}}^{\prime}(x_{k}^{\prime},\sigma+g_{1}/\alpha),$

or in the complement of a vertical strip around the origin,

$\left([-3C/(rp),3C/(rp)]\times{\mathbb{Z}}\right)^{c}.$

Then there are no red points in $[-C/p,C/p]\times\\{0\\}$ at time $C/p$.

###### Proof.

If we only allow red points initially in the union of rescaled affine cones,
then Lemma 3.3 and the observation that the red points above and below the
$x$-axis do not interact by time $C/p$ implies that there are no red points
anywhere on the $x$-axis by time $C/p$. Now observe that by a standard speed-
of-light argument, the state of a vertex $(x,0)$ for $x\in[-C/p,C/p]$ at time
$C/p$ depends only on the initial colors of sites within distance
$C(\frac{1}{r}+1)/p\leq 2C/(rp)$. Therefore, allowing red (or blue) points
outside of the strip $[-3C/(rp),3C/(rp)]\times{\mathbb{Z}}$ will not change
the states of the vertices in $[-C/p,C/p]\times\\{0\\}$ at time $C/p$. ∎

Lemma 3.4 describes a region that needs to be void of initially red sites to
protect the origin from red occupation up to time on the order $1/p$. This
region will be random — dependent on the initial configuration of blue sites —
and we proceed to show that it is unlikely to be too large.

For every $k\in{\mathbb{Z}}$, we define $I_{k}$ to be the indicator of the
event that there is a successful blocking configuration at rescaled
$(k,-\sigma)$, with $\sigma$ as defined in Lemma 3.3. Then, for each
$k\in{\mathbb{Z}}$, we define $Z_{k}=\inf\\{\ell\geq 0:I_{k+\ell}=1\\}$ to be
the (rescaled) distance from $k$ to the next successful blocking site to its
right.

######  Lemma 3.5.

Let $B>0$. Assume the initial probability of a vertex being blue is $Bp$. Then
there exists a large enough $B$ such that

$\sup_{0<p\leq 1/B}{\mathbb{E}}Z_{0}<\infty.$

###### Proof.

For $z\in{\mathbb{Z}}$, let $P_{z}=\mathbb{P}\left(Z_{0}\geq z\right)$ be the
probability that there are $z$ consecutive $0$s starting at $0$:
$I_{0}=I_{1}=\cdots=I_{z-1}=0$. For $\ell\geq 0$, let $A_{\ell}$ be the event
that the $\ell$th layer of the blocking configuration centered at
$(0,-\sigma)$ is not successful, and each layer $\ell^{\prime}<\ell$ is
successful. Partitioning according to these events, we have for $z\geq 1$,

(3.5)
$P_{z}=\sum_{\ell=0}^{\infty}\mathbb{P}\left(A_{\ell}\right)\mathbb{P}\left(Z_{0}\geq
z|A_{\ell}\right)\leq\sum_{\ell=0}^{\infty}\mathbb{P}\left(A_{\ell}\right)\mathbb{P}\left(Z_{0}\geq
z-\lceil D\lambda^{\ell}\rceil\right)$

where $D$ is a constant such that
$D\lambda^{\ell}>(\overline{\alpha}-\alpha)h_{\ell-1}$ for every $\ell\geq 1$.
The last inequality follows because on the event $A_{\ell}$, the layers in the
blocking constructions strictly above layer $\ell$ remain unaffected by the
conditioning, and the layer $\ell^{\prime}\leq\ell$ has activation regions
with rescaled width at most
$\lceil(\overline{\alpha}-\alpha)h_{\ell-1}\rceil$. Therefore, we have that
$I_{k},I_{k+1},\ldots$ are independent of $A_{\ell}$ whenever
$k\geq\lceil(\overline{\alpha}-\alpha)h_{\ell-1}\rceil$.

The event $A_{\ell}$ implies that there is a box in the $\ell$th layer of the
blocking configuration centered at $(0,-\sigma)$ that is not successful. By a
union bound on the $m$ activation regions in the $\ell$th layer, for $\ell\geq
1$ this probability is at most

$\mathbb{P}\left(A_{\ell}\right)\leq
m(1-Bp)^{\lambda^{-\ell/2}\cdot(\overline{\alpha}-\alpha)h_{\ell-1}/p}\leq
m\exp\left[-B\delta\lambda^{\ell/2}\right],$

for a small enough constant $\delta>0$. By possibly decreasing $\delta$, we
have

(3.6) $\mathbb{P}\left(A_{\ell}\right)\leq
m\exp\left[-B\delta\lambda^{\ell/2}\right]$

for all $\ell\geq 0$. Combining inequalities (3.5) and (3.6) gives

(3.7) $P_{z}\leq
m\sum_{\ell=0}^{\infty}\exp\left[-B\delta\lambda^{\ell/2}\right]P_{z-\lceil
D\lambda^{\ell}\rceil}.$

We now claim that we can choose $B$ sufficiently large so that $P_{z}\leq
2^{-\sqrt{z}}$ for all $z\geq 0$. Clearly, for $z\leq 0$ we have
$P_{z}=1=2^{0}$, and we proceed by induction. By (3.7) and the induction
hypothesis, we have

(3.8) $\displaystyle P_{z}$ $\displaystyle\leq
m\sum_{\ell=0}^{\infty}\exp\left[-B\delta\lambda^{\ell/2}\right]2^{-\sqrt{\max(z-2D\lambda^{\ell},0)}}$
$\displaystyle\leq
m\sum_{\ell=0}^{\infty}\exp\left[-B\delta\lambda^{\ell/2}\right]2^{-\sqrt{z}+\sqrt{2D\lambda^{\ell}}}$
$\displaystyle=2^{-\sqrt{z}}\cdot
m\sum_{\ell=0}^{\infty}\exp\left[-\lambda^{\ell/2}\left(B\delta-\sqrt{2D}\log
2\right)\right].$

The series in the last line converges for large enough $B$, and decreases to
$0$ as $B\to\infty$, so we choose $B$ such that the series is smaller than
$1/m$, which justifies the induction step, and proves the claim. It follows
that ${\mathbb{E}}Z_{0}=\sum_{z\geq 1}P_{z}\leq\sum_{z\geq 1}2^{-\sqrt{z}}$
for all $p\in(0,1/B]$. ∎

The next lemma provides the key step in the proof of Theorem 1.3. Due to the
rescaling, the size of the red-free area will have the area of the set $F$,
defined below, multiplied by $1/p$.

######  Lemma 3.6.

Assume the probability of a vertex being initially blue is $Bp$ and $B$ is
chosen as in Lemma 3.5. Let
$\mathcal{I}=\\{k\in{\mathbb{Z}}:I_{k}=1,-3C/(r\sqrt{p})\leq k\leq
3C/(r\sqrt{p})\\}$ and let

$F=\left(\bigcup_{k\in\mathcal{I}}{\mathcal{C}}(k,-\sigma-
g_{1}/\alpha)\right)^{c}\cap([-3C/(r\sqrt{p}),3C/(r\sqrt{p})]\times(-\infty,0]).$

For any $\epsilon>0$, we can choose either $C>0$ sufficiently small (depending
on $w$) or $w$ sufficiently large (depending on $C$) so that

$\mathbb{P}\left(\mathrm{Area}(F)\geq w/\sqrt{p}\right)<\epsilon$

for all sufficiently small $p>0$.

###### Proof.

Observe that for $k\geq 1$, the region below the $x$-axis, above the cones
${\mathcal{C}}(0,-\sigma-g_{1}/\alpha)$ and ${\mathcal{C}}(k,-\sigma-
g_{1}/\alpha)$, and between the lines $x=0$ and $x=k$ has area

$k(\sigma+g_{1}/\alpha)+k^{2}/2\leq Dk^{2}$

for a constant $D>0$. Moreover, if $I_{0}=I_{1}=\ldots=I_{k-1}=0$, then
$\sum_{j=0}^{k-1}Z_{j}\geq\frac{1}{2}k^{2}$. By decomposing the sequence
$(I_{k})$ into gaps between successive $1$s, we conclude that on the event
$\mathrm{Area}(F)<\infty$, we have

$\mathrm{Area}(F)\leq 2D\sum_{|k|\leq 3C/(r\sqrt{p})}Z_{k}.$

Noting that the area of $F$ is finite if, say, $Z_{0}\leq C/\sqrt{p}$, the
conclusion now follows from Lemma 3.5 and Markov’s inequality. ∎

###  3.3 Proof of Theorem 1.3 for $\rho=1$

###### Proof of parts (2) and (3) of Theorem 1.3 when $\rho=1$.

Lemma 2.1 implies part (2). To prove part (3), we may replace $p$ by $Bp$,
where the constant $B$ is chosen in Lemma 3.5. Fix an $\epsilon>0$, and choose
$w=w(\epsilon,C)$ such that the area of the region $F$ defined in Lemma 3.6
satisfies

$\mathbb{P}(\mathrm{Area}(F)\geq w/\sqrt{p})<\epsilon.$

Let $H=\\{\mathrm{Area}(F)\geq w/\sqrt{p}\\}$ be the event above, and let
$H^{\prime}$ be the same event after the entire initial configuration has been
reflected across the $x$-axis, so that
$\mathbb{P}(H^{\prime})=\mathbb{P}(H)<\epsilon.$ Let $F^{\prime}$ be the
region specified in the reflected event $H^{\prime}$, which is the region
protected by transposed blocking configurations in the analogous strip above
the $x$-axis. Then, on the event $(H\cup H^{\prime})^{c}$, if the rescaled
region $F\cup F^{\prime}$ is devoid of red points, then the conditions of
Lemma 3.4 are met, so there will be no red points in $[-C/p,C/p]\times\\{0\\}$
at time $C/p$. Therefore,

(3.9) $\displaystyle\mathbb{P}(0\text{ is not eventually blue})$
$\displaystyle\leq\mathbb{P}(H\cup H^{\prime})$
$\displaystyle\quad+\mathbb{P}(\\{\text{there is a red point in rescaled
}F\cup F^{\prime}\\}\cap(H\cup H^{\prime})^{c})$
$\displaystyle\quad+\mathbb{P}(\text{there is no blue point in
}(0,C/p]\times\\{0\\})$ $\displaystyle\leq 2\epsilon+q(2w/p^{3/2})+e^{-BC}$
$\displaystyle=2\epsilon+2awB^{3/2}+e^{-BC}$ $\displaystyle<4\epsilon$

by first choosing $C$ large, which along with $\epsilon$ determines $w$, then
choosing $a$ sufficiently small. This completes the proof of (2) in the case
where $a\to 0$.

Now, fix $a>0$ and replace $p$ by $(B+1)p$. We will make a sprinkling
argument, so we first assume that sites are occupied by blue with probability
$Bp$ or red with probability $q=a((B+1)p)^{3/2}$. Choose
$w<1/(8a(B+1)^{3/2})$, and let $H$ and $H^{\prime}$ be the same events as
above. Choose $C>0$ sufficiently small so that $\mathbb{P}_{Bp}\left(H\cup
H^{\prime}\right)<1/4$. Now, independently of everything, we add initially
blue points with probability $p$ along the $x$-axis. Then, we have

(3.10) $\displaystyle\mathbb{P}_{(B+1)p}\left(\text{0 is eventually
blue}\right)\geq$ $\displaystyle\quad\left(1-\mathbb{P}_{Bp}\left(H\cup
H^{\prime}\right)-\mathbb{P}_{Bp}\left(\\{\text{there is a red point in
rescaled }F\cup F^{\prime}\\}\cap(H\cup H^{\prime})^{c}\right)\right)\times$
$\displaystyle\qquad\mathbb{P}_{p}\left(\text{there is a blue point in
}(0,C/p]\times\\{0\\}\right)$ $\displaystyle\geq(1/2)(1-e^{-C})>0$

for all small enough $p$. This completes the proof of the statement (2) for
arbitrary fixed $a$. ∎

##  4 Larger range for red

In this section, we provide the necessary modification of our arguments to
prove Theorems 1.3 and 1.1 in full generality.

###### Proof of Theorem 1.3.

To prove the statement (2), we need an analog of Lemma 2.1. Now, in order to
stop red from growing, blue must form a horizontal strip of $\rho$ neighboring
lines, which red cannot jump over. The vertical scale is now
$p^{-\rho/(\rho+1)}$, and the new version of the event $H$ is

$\displaystyle H$ $\displaystyle=\\{\text{there is an initially red site
}(x,y)\in[0,\epsilon/2p]\times[0,\epsilon/p^{\rho/(\rho+1)}]\text{ and}$
$\displaystyle\qquad\text{there is no set of }\rho\text{ neighboring
horizontal lines in }$ $\displaystyle\qquad[x-2\epsilon\tau
r/p^{\rho/(1+\rho)},x+2\epsilon\tau
r/p^{\rho/(1+\rho)}]\times[0,\epsilon/p^{\rho/(1+\rho)}]$
$\displaystyle\qquad\text{such that each contains a potentially blue
point}\\}.$

Let $G$ be defined as in (2.1). It follows that the event $G\cap H$ implies
that the origin is eventually red, and if $H_{1}=\\{\text{there is an
initially red site in
}[0,\epsilon/2p]\times[0,\epsilon/p^{\rho/(\rho+1)}]\\}$, then

$P(H^{c}\mid H_{1})\leq\epsilon p^{-\rho/(\rho+1)}\left(4\epsilon\tau
rp^{-\rho/(\rho+1)}p\right)^{\rho}=(4\tau r)^{\rho}\epsilon^{\rho+1}.$

The rest of the proof is analogous to that of Lemma 2.1.

For the statement (3), the proof proceeds along the lines of the $\rho=1$
case. The blocking construction is the same, with the following modified
definition of a successful box. A box is now called successful if its
activation region has $\rho$ neighboring rows, each of which contains at least
one blue site. We need to replace Lemma 3.5 with a bound on
${\mathbb{E}}Z_{0}$ for the gaps between consecutive blocking structures for
the range-$\rho$ process, and we do so below. The rest of the proof is the
same.

Assume we have a box with width $w$ and height $h$, where $wBp<1$. The
probability that such a box is unsuccessful is bounded above by

$(1-c(wBp)^{\rho})^{h}\leq\exp(-cB^{\rho}hw^{\rho}p^{\rho}),$

for a small enough $c>0$. Therefore, the upper bound for probability
$\mathbb{P}(A_{\ell})$ in the proof of Lemma 3.5 is now for all $\ell\geq 0$

$\displaystyle\mathbb{P}\left(A_{\ell}\right)$ $\displaystyle\leq
m\exp\left[-cB^{\rho}\lambda^{-\ell/2}p^{-\rho/(\rho+1)}(\overline{\alpha}-\alpha)^{\rho}h_{\ell-1}^{\rho}p^{-\rho^{2}/(\rho+1)}\cdot
p^{\rho}\right]$ $\displaystyle\leq
m\exp\left[-B^{\rho}\delta\lambda^{(\rho-1/2)\ell}\right],$

for a small enough $\delta>0$. It follows that (3.6) holds for all $\rho\geq
1$, so the computation (3.8) holds as well. (In fact, we can get exponential
instead of stretched exponential tail bounds for $\rho\geq 2$.) ∎

###### Proof of Theorem 1.1.

Since it makes no difference at our level of precision, we assume also that
blue and red grow at the same rates, so $r=1$. We first prove the lower bound.
For blue to reach the origin, it is sufficient for there to be an initially
blue point in $[0,\delta/p]\times\\{0\\}$ and for no $\tau$ consecutive red
points to reach this segment of the $x$-axis by time $\delta/(\tau p)$. To
stop red from above, we subdivide the region ${\mathbb{Z}}\times[0,N]$ into
$N\times N$ disjoint, adjacent boxes. We call a box successful if it contains
$\rho$ consecutive rows each with at least one initially blue point.

$N$$N$$C(\ell+1)N$ Figure 7: Protection from red in the proof of the lower
bound in Theorem 1.1, with $\rho=\tau=3$, $Z_{k}=3$. All initially red sites
(circled) in the shaded box are covered by the red lines, no three of which
are neighboring. The three initially blue sites (also circled) therefore
generate the blue neighboring lines before the red from above the box can
interfere with them.

For $k\in{\mathbb{Z}}$, we define $I_{k}$ to be the indicator of the event
that the $k$th box is successful. Then, for each $k\in{\mathbb{Z}}$, we define
$Z_{k}=\inf\\{\ell\geq 0:I_{k+\ell}=1\\}$ to be the number of boxes from the
$k$th box to the next successful box to its right. We choose $N$ just large
enough so that $EI_{k}\geq 1/2$, so $N\asymp(1/p)^{\rho/(\rho+1)}$. Then,
since boxes are successful independently, it follows that
$E(Z_{k}^{\tau+1})=E(Z_{1}^{\tau+1})<\infty$ for all $k$, so by Markov’s
inequality, for any $\epsilon>0$ we can find $C$ so that

(4.1) $\mathbb{P}\left(\sum_{k=1}^{\delta/{Np}}(Z_{k})^{\tau+1}\geq
C\delta/(Np)\right)<\epsilon.$

We define the region, $F$, above the $x$-axis, which is unprotected by
successful blue boxes, as follows. For each interval $[k,k+\ell]$ such that
$I_{k}=I_{k+\ell}=1$ and $I_{k+1}=\cdots=I_{k+\ell-1}=0$, we include in $F$
the rectangular region with dimensions $(\ell+1)N\times C(\ell+1)N$ that
shares lower left corner with the $k$th box and lower right corner with the
$(k+\ell)$th box. The constant $C$ here is chosen sufficiently large so that
the blue lines growing from the successful boxes at $k$ and $k+\ell$ will fill
the gap between them before any red starting above the rectangular region can
reach height $N$. See Figure 7. For one such region, the probability that it
contains $\tau$ neighboring vertical lines, each containing at least one
initially red point, is bounded above by $C(\ell N)^{\tau+1}q^{\tau}$. If

$\sum_{k=1}^{\delta/{Np}}(Z_{k})^{\tau+1}<C\delta/(Np),$

then the probability that any such rectangle in $F$ has this property is at
most $C\delta N^{\tau+1}q^{\tau}/(Np)\leq C\delta a^{\tau}$. For large $a$,
this can be made small by choosing $\delta$ small enough. The interval
$[0,\delta/p]\times\\{0\\}$ is protected from below by an analogous
construction with positive probability, Therefore, the origin will be
eventually blue with positive probability. This shows that the $\liminf$ in
the statement is positive for every $a>0$. By taking $\delta$ large, the
probability that there is a blue point in $[0,\delta/p]\times\\{0\\}$ can be
made close to $1$, then by taking $a$ sufficiently small, this interval will
be protected from above and below with probability close to $1$. This shows
that the $\liminf$ tends to $1$ as $a\to 0$.

We now sketch the proof of the upper bound on the $\limsup$ in the statement
of the theorem, which is again analogous to the proof of Lemma 2.1. For
$x\in{\mathbb{Z}}$, define the events

(4.2) $\displaystyle G$ $\displaystyle=\\{\text{there is no potentially blue
site in }[-\epsilon\tau/p,\epsilon\tau/p]\times\\{0\\}\\},\quad\text{and}$
$\displaystyle H(x)$ $\displaystyle=\\{\text{the $\tau$ consecutive vertical
lines $[x,x+\tau-1]\times[0,\epsilon/p^{\rho/(1+\rho)}]$}$ each contain an
initially red site and there is no set of $\rho$ neighboring horizontal lines
in
$[x-2\epsilon\tau/p^{\rho/(1+\rho)},x+2\epsilon\tau/p^{\rho/(1+\rho)}]\times[0,\epsilon/p^{\rho/(1+\rho)}]$
$\displaystyle\qquad\text{such that each contains a potentially blue
point}\\}.$

Now define

(4.3) $H^{+}=\bigcup_{x\in[0,\epsilon/2p]}H(x),\quad\text{ and }\quad
H^{-}=\bigcup_{x\in[-\epsilon/2p,0]}H(x).$

If $H(x)$ occurs, the $\tau$ consecutive vertical lines will eventually
produce $\tau$ consecutive red sites on the $x$-axis, which cannot be crossed
by blue. Therefore, on the event $G\cap H^{+}\cap H^{-}$, the origin never
becomes blue. For any fixed $\epsilon>0$, the probability that there exist
$\tau$ consecutive vertical lines in
$[0,\epsilon/2p]\times[0,\epsilon/p^{\rho/(1+\rho)}]$ and $\tau$ consecutive
vertical lines in $[-\epsilon/2p,0]\times[0,\epsilon/p^{\rho/(1+\rho)}]$, each
with an initially red site, is bounded away from $0$ for any $a>0$, and tends
to $1$ as $a\to\infty$. Moreover, conditional on this event, the probability
of $G\cap H^{+}\cap H^{-}$ is also bounded away from $0$ for small enough
$\epsilon$, and tends to $1$ as $\epsilon\to 0$. ∎

###### Proof of Corollary 1.2.

First, we check that $\gamma^{\prime}\gamma>1$.

$\displaystyle\gamma^{\prime}\gamma$
$\displaystyle=\left(\frac{1}{\rho}+\frac{\tau}{\tau+1}\right)\left(\frac{1}{\tau}+\frac{\rho}{\rho+1}\right)$
$\displaystyle=1+\frac{1}{\rho\tau}+\frac{1}{(\rho+1)(\tau+1)}>1.$

Then by Theorem 1.1, when $q\gg p^{\gamma}$, the origin is eventually blue
with probability tending to $0$. Reversing the roles of blue and red and
exchanging $\rho$ and $\tau$, Theorem 1.1 implies that when $p\gg
q^{\gamma^{\prime}}$, the origin is eventually red with probability tending to
$0$, and the corollary follows. ∎

##  5 Extensions and open problems

We begin with a natural question on a more precise form of our main two
theorems.

######  Open problem 5.1.

Are the $\liminf$ and $\limsup$ in Theorem 1.1 and Theorem 1.3 equal, i.e.,
does the limit exist?

Processes with three (or more) colors are a natural generalization. Here, we
will merely touch on them, with a result and open problems on two basic cases.
The third color will be green, and the initial densities of the blue, red, and
green colors will be $p_{b}$, $p_{r}$, and $p_{g}$. Also, we will assume that
$r=1$ and that the neighborhood for the green growth is
${\mathcal{G}}\subset{\mathbb{Z}}^{2}$. Then, an empty vertex that has a
colored neighbor in $x+\mathcal{B}$, $x+{\mathcal{R}}$, or $x+{\mathcal{G}}$
at time $t$ changes to the corresponding color at time $t+1$, with ambiguities
resolved at random.

First consider the case when red and blue colors undergo one-dimensional
nearest neighbor growth in orthogonal directions, as in Corollary 1.2 with
$\rho=\tau=1$, $\mathcal{B}=\\{\pm e_{1}\\}$, ${\mathcal{R}}=\\{\pm e_{2}\\}$;
whereas green undergoes two-dimensional nearest-neighbor growth,
${\mathcal{G}}=\\{\pm e_{1},\pm e_{2}\\}$. We also assume that $p_{b}=p_{r}=p$
and $p_{g}=q$ are small. See Figure 8 (left).

Figure 8: Two cases of three color dynamics, with one-dimensional growth by
blue and red and two-dimensional growth by green. Left: $\mathcal{B}=\\{\pm
e_{1}\\}$, ${\mathcal{R}}=\\{\pm e_{2}\\}$, ${\mathcal{G}}=\\{\pm e_{1},\pm
e_{2}\\}$, $p_{b}=p_{r}=0.001$, $p_{g}=0.002$. Right:
$\mathcal{B}=\\{e_{1}\\}$, ${\mathcal{R}}=\\{e_{2}\\}$, ${\mathcal{G}}=\\{\pm
e_{1},\pm e_{2}\\}$, $p_{b}=p_{r}=0.001$, $p_{g}=0.00001$.

######  Theorem 5.2.

If $p\ll q$, then $\mathbb{P}(\text{\rm the origin is eventually green})\to
1$, while if $p\gg q$, then $\mathbb{P}(\text{\rm the origin remains
empty})\to 1$.

###### Proof.

We denote by $B_{n}$ the $n\times n$ box centered at the origin.

The first statement is easy to prove. Indeed, let $n=n(p)$ be such that
$n^{2}p\to 0$ while $n^{2}q\to\infty$ and let $G$ be the event that $B_{n}$
contains an initially green site, while $B_{2n}$ initially contains neither a
red nor a blue site. Then clearly $\mathbb{P}(G)\to 1$ but on $G$ the origin
becomes green by time $n$.

For the converse, by Corollary 1.2 with $\tau=\rho=1$, it suffices to show
that the origin is not eventually green with high probability. We now assume
$n=n(p)$ is such that $n^{2}p\to 1$ while $n^{2}q\to 0$. Partition the lattice
into $n\times n$ boxes with the origin in the center of one of them. Call a
box a red fence if it contains an initially red site and no initially blue
sites and there are no initially blue sites in any of the neighboring four
boxes (i.e., those that share an edge). Define a blue fence analogously. We
say that a blue line crosses a box if it connects the left and right sides of
the box.

Observe that a red fence will never be crossed by a blue line. Observe also
that a box is a red fence with probability bounded away from $0$, and that
boxes at distance at least 3 from each other are red fences independently. It
follows that the probability that the box centered at the origin is the left
endpoint of an interval of $m$ boxes, none of which is a red fence, is at most
$\exp(-\alpha m)$, where $\alpha>0$.

Assume now that $q=0$. Then, as it cannot have a boundary site with a
horizontal and a vertical neighbor inside, every connected component of
forever empty sites is a rectangle, bounded on the top and bottom by
horizontal intervals of blue sites and on the left and right by vertical
intervals of red sites. Let $R$ be such connected component of the origin with
dimensions $A\times B$.

Assume that the horizontal dimension is maximal: $A\geq B$. Then there is a
row of at least $\lfloor A/n\rfloor-2$ boxes, none of which is a red fence,
that intersects the blue boundary of $R$ but not the red boundary. Then

$P(A\geq B,A\geq mn)\leq\sum_{k\geq m-2}2k^{4}e^{-\alpha k}$

and then

$P(\max(A,B)\geq mn)\leq\sum_{k\geq m-2}4k^{4}e^{-\alpha k}.$

It follows that

$P(\max(A,B)\leq mn)\to 1$

as $m\to\infty$. By the same argument, if $T$ is the time when all sites on
the outer edges of $R$ reach their final state,

$P(T\leq mn)\to 1$

as $m\to\infty$.

Figure 9:  Three color dynamics with one-dimensional growth by blue and two-
dimensional growth by red and green, with $\mathcal{B}=\\{e_{1}\\}$,
${\mathcal{R}}={\mathcal{G}}=\\{\pm e_{1},\pm e_{2}\\}$, $p_{b}=0.02$,
$p_{r}=p_{g}=0.001$.

We now remove the assumption that $q=0$, and define the configuration in two
stages: start by deciding on the red and blue sites, then independently on
potentially green sites with probability $q/(1-2p)$, and then finally define
the green sites as those that are potentially green but not blue or red. It
then follows by the speed-of-light argument that

$\displaystyle\mathbb{P}(\text{the origin is forever not green})\geq$
$\displaystyle\qquad\mathbb{P}(\text{there are no potentially green sites in
the $2mn\times 2mn$ box around the origin})$
$\displaystyle\qquad\times\mathbb{P}(\max(A,B)\leq mn,T\leq mn).$

Fix $\epsilon>0$, and choose $m$ large so that the second factor is at least
$1-\epsilon$ for all sufficiently small $p$. Then for this choice of $m$, the
first factor tends to $1$ as $p\to 0$. This completes the proof. ∎

######  Open problem 5.3.

Assume the setting of Theorem 5.2, but now $q=cp$, for a fixed number $c$.
Does the limit

$\lim_{p\to 0}\mathbb{P}(\text{the origin is eventually green})$

exist?

We also ask what happens when red and blue grow in only one direction. The
argument for Theorem 5.2 breaks down in this case, since the connected
components of empty sites when $p_{g}=0$ are no longer rectangles. See Figure
8 (right).

######  Open problem 5.4.

Assume the setting of Theorem 5.2 except that $\mathcal{B}=\\{e_{1}\\}$ and
${\mathcal{R}}=\\{e_{2}\\}$. What relationship between $p$ and $q$ results in
$\mathbb{P}(\text{the origin is eventually green})\to 1$?

One way to attack the first two open problems would be to try to define a
limiting continuum object to which final configurations converge when suitably
scaled as $p\to 0$. This seems to be a substantial challenge; we end with
another question in this vein that might be more accessible. Assume now that
$\mathcal{B}=\\{e_{1}\\}$, ${\mathcal{R}}={\mathcal{G}}=\\{\pm e_{1},\pm
e_{2}\\}$, $p_{r}=p_{g}=p$ and $q=p^{\gamma}$ with $\gamma>3/2$. Observe that
Theorem 1.3 implies that the density of blue sites in the final configuration
vanishes as $p\to 0$. Thus, the red and green sites divide the space in a sort
of “dynamic Voronoi tessellation” (by contrast to the “static” one discussed
in [GG] when $q=0$). See Figure 9.

######  Open problem 5.5.

Does this final configuration, scaled by $1/\sqrt{p}$, converge to a random
two-coloring of ${\mathbb{R}}^{2}$?

## Acknowledgments

JG was partially supported by the Slovenian Research Agency research program
P1-0285 and Simons Foundation Award #709425. DS was partially supported by the
NSF TRIPODS grant CCF–1740761.

## References

  * [BGSW] D. Blanquicett, J. Gravner, D. Sivakoff, L. Wilson, Two-dimensional supercritical growth dynamics with one-dimensional nucleation, arXiv:2305.04378 (2023).
  * [CLY+] Y. Cheng, C. Lu, B. Yang, X. Tao, J. Wang, G. Ye, One-dimensional crystal growth model on a square lattice substrate, Physics Letters A 380 (2016), 2989–2992.
  * [CS] E. Candellero, A. Stauffer, First passage percolation in a hostile environment is not monotone, arXiv:2110.05821 (2021).
  * [FS1] T. Finn, A. Stauffer, Non-equilibrium multi-scale analysis and coexistence in competing first passage percolation, Journal of the European Mathematical Society 26 (2022), 1313–1363.
  * [FS2] T. Finn, A. Stauffer. Coexistence in competing first passage percolation with conversion, Annals of Applied Probability (2022), 4459–4480.
  * [Gho] A. Ghosh, Polluted $\mathcal{U}$-bootstrap percolation, Ph. D. Thesis, 2022, The Ohio State University ProQuest Dissertation Publishing, 30360081.
  * [GG] J. Gravner, D. Griffeath, Multitype threshold voter model and convergence to Poisson-Voronoi tessellation, Annals of Applied Probability 7 (1997), 615–647.
  * [GH] J. Gravner, A. Holroyd, Polluted bootstrap percolation with threshold 2 in all dimension, Probability Theory and Related Fields 175 (2019), 467–486.
  * [GHS] J. Gravner, A. Holroyd, D. Sivakoff, Polluted bootstrap percolation in three dimensions, Annals of Applied Probability 31 (2021) 218–246.
  * [GM] J. Gravner, E. McDonald, Bootstrap percolation in a polluted environment, Journal of Statistical Physics 87 (1997), 915–927.
  * [HP1] O. Häggatröm, R. Pemantle, First passage percolation and a model for competing spatial growth, Journal of Applied Probability 35 (1998), 683–692.
  * [HP2] O. Häggatröm, R. Pemantle, Absence of mutual unbounded growth for almost all parameter values in the two-type Richardson model, Stochastic Processes and Their Applications 90 (2000), 207–222.
  * [Hof] C. Hoffman, Coexistence for Richardson type competing spatial growth models, Annals of Applied Probability 15 (2005), 739–747.
  * [SS] V. Sidoravicius, A. Stauffer, Multi-particle diffusion limited aggregation, Inventiones Mathematicae 218 (2019), 491–571.
  * [YLG+] X. Ye, Y. Liu, Q. Guo, Q. Han, C. Ge, S. Cui, L. Zhang, X. Tao, 1D versus 2D cocrystals growth via microspacing in-air sublimation, Nature Communications 10, 761 (2019), 1–10. https://doi.org/10.1038/s41467-019-08712-1