# Minimum lethal sets in grids and tori under 3-neighbour bootstrap percolation

Fabricio Benevides, Jean-Claude Bermond, Hicham Lesfari, Nicolas Nisse

► To cite this version:

Fabricio Benevides, Jean-Claude Bermond, Hicham Lesfari, Nicolas Nisse. Minimum lethal sets in grids and tori under 3-neighbour bootstrap percolation. European Journal of Combinatorics, 2024, 119, pp.18. 10.1016/j.ejc.2023.103801. hal-04368240

HAL Id: hal-04368240

https://inria.hal.science/hal-04368240v1

Submitted on 31 Dec 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Minimum lethal sets in grids and tori under 3-neighbour bootstrap percolation*

Fabricio Benevides¹, Jean-Claude Bermond², Hicham Lesfari², and Nicolas Nisse²

¹Universidade Federal do Ceará, Fortaleza, Brazil

²Université Côte d'Azur, INRIA, CNRS, France

## Abstract

Let $r \ge 1$ be any non negative integer and let $G = (V, E)$ be any undirected graph in which a subset $D \subseteq V$ of vertices are initially *infected*. We consider the process in which, at every step, each non-infected vertex with at least $r$ infected neighbours becomes infected and an infected vertex never becomes non-infected. The problem consists in determining the minimum size $s_r(G)$ of an initially infected vertices set $D$ that eventually infects the whole graph $G$. This problem is closely related to cellular automata, to percolation problems and to the Game of Life studied by John Conway. Note that $s_1(G) = 1$ for any connected graph $G$. The case when $G$ is the $n \times n$ grid, $G_{n \times n}$, and $r=2$ is well known and appears in many puzzle books, in particular due to the elegant proof that shows that $s_2(G_{n \times n}) = n$ for all $n \in \mathbb{N}$. We study the cases of square grids, $G_{n \times n}$, and tori, $T_{n \times n}$, when $r \in \{3, 4\}$. We show that $s_3(G_{n \times n}) = \lceil \frac{n^2+2n+4}{3} \rceil$ for every $n$ even and that $\lceil \frac{n^2+2n}{3} \rceil \le s_3(G_{n \times n}) \le \lceil \frac{n^2+2n}{3} \rceil + 1$ for any $n$ odd. When $n$ is odd, we show that both bounds are reached, namely $s_3(G_{n \times n}) = \lceil \frac{n^2+2n}{3} \rceil$ if $n \equiv 5 \pmod 6$ or $n = 2^p - 1$ for any $p \in \mathbb{N}^*$, and $s_3(G_{n \times n}) = \lceil \frac{n^2+2n}{3} \rceil + 1$ if $n \in \{9, 13\}$. Finally, for all $n \in \mathbb{N}$, we give the exact expression of $s_3(T_{n \times n})$.

# 1 Introduction

Originally developed by von Neumann after a suggestion of Ulam, cellular automata are a dynamical system defined over graphs endowed with some homogeneous and local update rules. The notion of bootstrap percolation is an example of a cellular automaton which has been extensively investigated by mathematicians, physicists, computer scientists and sociologists, among others. For further applications to several other areas, we refer the reader to the survey article by Adler and Lev [AL03], and the references therein.

Several variants of classical bootstrap percolation on graphs have been considered. The particular model we are studying belongs to the class of *r-neighbour bootstrap processes* ($r \ge 1$). It was first introduced by Chalupa, Leath, and Reich [CLR79] as a monotone version of the Glauber dynamics in ferromagnetism.

Let $r \ge 1$ be a given integer and $G$ a finite graph whose vertices (usually called *sites* in the context of percolation) can be in one of two states: *healthy* or *infected*. An initial set of infected nodes is given. At any step, any healthy vertex with at least $r$ infected neighbours

<footnote>*This work has been supported by the French government through the UCA JEDI (ANR-15-IDEX-01) and EUR DS4H (ANR-17-EURE-004) Investments in the Future projects, by the SticAm-Sud project GALOP, and by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior – Brasil (CAPES) – Finance Code 001 and CNPq (Proc 315042/2021-4).</footnote>
becomes infected, while infected vertices remain infected forever. The parameter $r$ reflects at which extent sites *resist* to the infection spread. Note that the term *bootstrap percolation* is sometimes used with the implicit assumption that the initial set of vertices infected is random. In this paper we consider the same model but use a deterministic initial set.

An initial set of infected vertices is called *lethal* if at the end of the process all the vertices are infected. A problem widely considered in the literature consists in determining the minimum size of a lethal set denoted by $s_r(G)$. (Knowing this value, for example, plays certain starting role in the study of the probability for a random initial set to be lethal).

**Related work.** Lethal sets have been considered in the literature with various names according the domain of applications. In [CDP+11, DJR09], they are called irreversible $r$-conversion sets and infected vertices are called vertices in state 1. In the area of viral marketing, a lethal set is called a (perfect) target set and infected vertices are called active (see [CHY13, CHL+13]). In [FLL+04], lethal sets are called “irreversible dynamos (dynamic monopolies)” and infected vertices black or faulty (stemming from the distributed computing field). Note that non-irreversible dynamos have been widely investigated (see [Pel02]).

Computing exactly $s_r(G)$ is NP-hard ([CDP+11, Che09, DJR09] and the hardness result holds even when $r=2$ and $G$ has maximal degree $\Delta$, where $\Delta$ is a constant not depending on the size of $G$ (see [Che09]). The parameter $s_r(G)$ has been studied for several families of graphs including trees [CDP+11, DJR09, Rie12], $d$-dimensional grids [BB06, BP98, PS20], chordal graphs [BEPR19, CDP+11, CHL+13], hexagonal grids [ATZ11], honeycombs graphs [CHY13], hypercubes [BB06, MN18], expanders [COFKR14], random regular graphs [GS15].

**Cases of grids and tori.** In particular, the most known case is the square grids $G_{n \times n}$ with $r=2$ as it appears as a popular puzzle regularly in newspapers and is referenced in puzzles books [Win03, Bol06, LL11]. According to [Win03], the problem appeared for the first time in the Soviet magazine Kvant around 1986. The value $s_2(G_{n \times n}) = n$ can be proved with the elegant perimeter argument. Our interest to the problem was revived, in fact, due to a problem proposed in the french newspaper “Le Monde” (Problem 1141, entitled ”Le jeu de la viralité”, April 2020) in honor to John Conway (who just passed away). This leads us to study the problem of determining the value $s_3(G_{n \times n})$ (see examples for small grids in Figure 1. In addition to the formal proofs given later, the reader may verify that these sets, and all constructions throughout the paper, are actually lethal using the software Golly<fnref n="1" />). To the best of our knowledge this problem was considered first in [Pet97]. The result appears also in [BP98]. In [Pet97] it is proven that $\lfloor (n^2 + 2n)/3 \rfloor \le s_3(G_{n \times n}) \le (n^2 + 4n)/3 + O(1)$. The lower bound uses also the perimeter argument. In [Bol06] (Problem 65, pages 171-172) Bollobás gave the same lower bound for $n$ odd, but a slightly better one for $n$ even. He also proves that for $n \equiv 2 \pmod 6$ the lower bound is attained and in that case $s_3(G_{n \times n}) = (n^2 + 2n + 4)/3$ (see Figure 1(f) for $n=8$). The case of the grid was also considered in [DJR09] where they claim that $s_3(G_{n \times n}) \le n^2/3 + (7n+55)/12$, but the known lower bound of $(n^2 - 2n + 2)/3$ [Bol06, Pet97] is larger than their upper bound for $n$ large enough.

The problem for tori $T_{m \times n}$ was considered and solved in [Bol06, FLL+04, Pet97, Win03] for $r=2$, where $s_2(T_{m \times n}) = \lfloor \frac{n+m}{2} \rfloor - 1$. For the case $r=3$, it has been proved that $\lfloor (mn + 1) + 1 \rfloor \le s_3(T_{m \times n}) \le \max\{\lfloor m/3 \rfloor(n+1), \lfloor n/3 \rfloor(m+1)\}$ [FLL+04]. Finally, in [DJR09], exact expressions of $s_4(G_{m \times n})$ and $s_4(T_{m \times n})$ are given.

Other related problems have been considered in the literature like finding the size of a largest inclusion-minimal lethal set [Mor09, Rie10]. The speed of convergence was also considered in the square grid (see [BP13, BP15]).

<footnote n="1">¹http://golly.sourceforge.net/</footnote>
<figure><img src="image_2.png" /><figcaption>Figure 1: Some instances of minimum lethal sets in $G_{n \times n}$ when $r = 3$. The vertices are depicted as small squares. Initially infected (resp., not infected) vertices are red (resp., white).</figcaption></figure>

**Our contributions.** In this paper, we study the contamination process in square grids $G_{n \times n}$ and square tori $T_{n \times n}$. The tools developed here can be used to get results for non square grids and tori. In Section 2, we formally define the problem and recall the results obtained for $r = 2, 4$ and some known results for $r = 3$ that we use throughout the paper. Our main result is the following theorem that deals with an almost tight bound of $s_3(G_{n \times n})$.

**Theorem 1** Let $n \in \mathbb{N}^*$. Let $LB_n = \lfloor \frac{n^2+2n}{3} \rfloor$ if $n$ is odd and $LB_n = \lfloor \frac{n^2+2n+4}{3} \rfloor$ if $n$ is even.

* $s_3(G_{n \times n}) = LB_n$ if $n$ is even or if $n \equiv 5 \pmod{6}$ or if $n = 2^p - 1$;

* $LB_n \le s_3(G_{n \times n}) \le LB_n + 1$ if $n$ is odd;

* $s_3(G_{n \times n}) = LB_n + 1$ if $n \in \{9, 13\}$.

Section 3 is devoted to the proof of the first two items of Theorem 1. In Section 4, we prove the last item of Theorem 1. For the values $n = 9$ and $13$, we prove that the lower bound is not tight using a Linear Program. For $n = 9$, we also give a combinatorial proof. Then, Section 5 is devoted to settle the problem when $r = 3$ in tori:

**Theorem 2** For every $n \ge 3$, $s_3(T_{n \times n}) = \lfloor \frac{n^2+1}{3} \rfloor$.

We conclude in Section 6 by describing several open questions.

# 2 Preliminaries

## 2.1 Notations and Problem statement

Let $G = (V, E)$ be a graph. For a vertex $v \in V$, $N(v) = \{u \in V \mid \{u, v\} \in E\}$ is the neighbourhood of $v$ and $d(v) = |N(v)|$ is the degree of $v$.

The 2-dimensional (square) grid graph with $n$ rows and $n$ columns is denoted by $G_{n \times n}$. Its vertex set is defined by $V(G_{n \times n}) = \{(i, j) \mid 1 \le i \le n, 1 \le j \le n\}$. Two vertices $(i, j)$ and $(i', j')$ are adjacent if and only if $|i - i'| + |j - j'| = 1$. If $1 < i, j < n$, vertex $(i, j)$ has degree 4. The corners are the vertices with degree at most 2, that is, the vertices $(1, 1)$, $(1, n)$, $(n, 1)$ and $(n, n)$. The border $B$ is the set of vertices with degree at most 3.

For $n \ge 3$, let also $T_{n \times n}$ be the torus with vertex-set $\{(i, j) \mid i \in \mathbb{Z}_n \text{ and } j \in \mathbb{Z}_n\}$, where $\mathbb{Z}_n$ denotes the set of integers modulo $n$ denoted $0, 1, \dots, n - 1$. Vertex $(i, j)$ is adjacent to the 4 vertices $(i - 1, j)$, $(i + 1, j)$, $(i, j - 1)$ and $(i, j + 1)$.

Given a graph $G$ and a natural number $r \in \mathbb{N}^*$, we consider the following deterministic process (known as $r$-neighbour bootstrap percolation) that models the spread of an infection in $G$. Let $D_0 = D$ be a subset of initially *infected* vertices and for each step $t \ge 1$, let

$$D_t = D_{t-1} \cup \{v \in V : |N(v) \cap D_{t-1}| \ge r\}.$$
For a set $D \subset V(G)$, let $\langle D \rangle = \bigcup_{t=0}^{\infty} D_t$ be the closure of $D$, i.e., the set of eventually infected vertices in the process that was started from $D$. A configuration is a pair $(G, D)$ that consists of a graph $G$ together with the subset $D$ of its vertices that are initially infected. Abusing the notation, we call the size of the configuration as the size $|D|$ of the set $D$.

Any set $D \subseteq V$ is said *lethal* if $\langle D \rangle = V$. Similarly, a configuration $(G, D)$ is lethal if $D$ is a
lethal set. Let $s_r(G)$ be the minimum size of a lethal set in $G$. Since $\langle V \rangle = V$, $s_r(G)$ is always
well defined. A lethal set (resp. a lethal configuration) is *optimal* if it is of size $s_r(G)$. Note
that $s_1(G) = 1$ for every connected graph $G$.

The main goal of this paper is to investigate $s_3(G_{n \times n})$ and $s_3(T_{n \times n})$, i.e., focusing on square
grids and tori for $r = 3$. Let us first deal with the cases $r \in \{2, 4\}$.

## 2.2 Cases $r \in \{2, 4\}$

For completeness, we first precisely recall the known results when $r = 2$ and give exact results
in the case when $r = 4$.

The following result for the grid $G_{n \times n}$ and $r = 2$ can be considered as folklore and appeared
in many books with puzzles [Bol06, LL11, Win03]. The lower-bound is proved using an elegant
perimeter argument and an optimal lethal set is obtained by taking the $n$ vertices of the diagonal.

**Theorem 3 ([Bol06, LL11, Win03])** Let $n \ge 1$, then $s_2(G_{n \times n}) = n$.

The result for the torus can be found in Problem 66, page 173 in [Bol06] and in [FLL+04, Win03].

**Theorem 4 ([Bol06, FLL+04, Win03])** Let $n \ge 1$, then $s_2(T_{n \times n}) = n - 1$.

The case $r = 4$ was considered in [BP98] where it is only stated that $s_4(G_{n \times n}) \sim n^2/2$, and
has been completely solved in [DJR09].

**Proposition 5 ([DJR09])** For every $n \ge 3$, we have

* $s_4(G_{n \times n}) = \lfloor \frac{n^2+4n-4}{2} \rfloor$.

* $s_4(T_{n \times n}) = n \lfloor \frac{n+1}{2} \rfloor$.

## 2.3 Known results on $s_3(G_{n \times n})$ that are used throughout this paper

We first present two properties that we will use after.

**Property 6** When $r = 3$, every lethal set in $G_{n \times n}$ contains every corner.

**Proof.** Let $u$ be a corner of $G_{n \times n}$ and let $D$ be a lethal set. Since $u$ has degree at most 2 and requires at least 3 neighbours to be infected, then $u \in D$. ■

The next property states that, for every two adjacent vertices on the border, at least one must
be initially infected in order to eventually infect the whole grid.

**Property 7** Let $u, v$ be two adjacent vertices in $\mathcal{B}$ of $G_{n \times n}$ and let $D$ be a lethal set for $r = 3$, then $D \cap \{u, v\} \neq \emptyset$.

**Proof.** Let $D$ be a lethal set of $G_{n \times n}$. For purpose of contradiction, let us assume that there are two adjacent vertices $u$ and $v$ of the border (so they have degree at most 3) that are not in $D$. Then, the first vertex to be contaminated in $\{u, v\}$ would have at most two contaminated neighbours before being infected, a contradiction. ■
The following lower bound has been proved in [Bol06] using the perimeter argument and noting that, for $n$ even, there are four pairs of adjacent infected vertices in $\mathcal{B}$. In particular, the notation $LB_n$ defined below will be used throughout the paper. We provide for completeness a sketch of the proof.

**Theorem 8 (Problem 65, pages 171-172 in [Bol06])** Let $n \in \mathbb{N}^*$. It holds that:

$$s_3(G_{n \times n}) \geq LB_n = \begin{cases} \lfloor \frac{n^2+2n}{3} \rfloor & \text{if } n \text{ is odd,} \\ \lfloor \frac{n^2+2n+4}{3} \rfloor & \text{if } n \text{ is even.} \end{cases}$$

**Proof.** We rephrase the elegant perimeter's argument used in [Bol06]. Each vertex has a perimeter 4 and so the initial perimeter of a lethal set is at most $4|D|$. In the process of infection, each time a new vertex is infected, the perimeter decreases by at least 2 and the final perimeter is $4n$. Hence, we get $4|D| - 2(n^2 - |D|) \geq 4n$ and so $|D| \geq \frac{n^2+2n}{3}$. If $n$ is even, by Properties 6 and 7, there are on each side of the border $\mathcal{B}$ a pair of adjacent infected vertices. Therefore, the initial perimeter is at most $4|D| - 8$ and so we get $|D| \geq \frac{n^2+2n+4}{3}$. ■

This allows to prove the following corollary that we extensively use later.

**Corollary 9** Let $n \in \mathbb{N}$.

$$LB_{n+3} - LB_n = \begin{cases} 2n + 3 & \text{when } n \equiv 0, 4 \pmod{6} \\ 2n + 4 & \text{when } n \equiv 2 \pmod{6} \\ 2n + 6 & \text{when } n \equiv 5 \pmod{6} \\ 2n + 7 & \text{when } n \equiv 1, 3 \pmod{6} \end{cases} \\ \\ LB_{n+6} - LB_n = 4n + 16.$$

In [Bol06], Bollobás proved that the lower bound $LB_n$ is indeed reached in the case $n \equiv 2 \pmod{6}$ (see Figure 1(f) for $n = 8$). We rephrase his result as follows by specifying an extra property (useful later) of some optimal lethal sets.

**Theorem 10 ([Bol06])** Let $n \equiv 2 \pmod{6}$, then $s_3(G_{n \times n}) = LB_n = \frac{n^2+2n+4}{3}$. Furthermore, there exists an optimal lethal set of $G_{n \times n}$ containing the vertices $(1, n-1)$, $(2, n)$, $(n-1, 1)$, and $(n, 2)$.

# 3 Various constructions and optimal results

In this section, we present several ways to use (lethal or not) configurations for smaller grids in order to obtain new lethal configurations for larger grids. Each of the different tools that we propose allow us to prove Theorem 1 (but its last item that is proved in next Section).

## 3.1 From $n$ even to $n+3$ odd and optimality for $n \equiv 5 \pmod{6}$

**Proposition 11** Let $n$ be even. If $D$ is a lethal set in $G_{n \times n}$ containing the vertices $(1, n-1)$, $(2, n)$, $(n-1, 1)$, and $(n, 2)$, then there exists a lethal configuration $(G_{(n+3) \times (n+3)}, D')$ with size $|D'| = |D| + 2n + 4$.
<figure><img src="image_3.png" /><figcaption>Figure 2: Illustration of Proposition 11. The vertices are depicted as small squares (with most vertices inside $G_{n \times n}$ as well as their status omitted). Initially infected (resp., not infected) vertices of $D'$ are red (resp., white). Orange vertices are the ones that are initially infected in $D$ but not in $D'$.</figcaption></figure>

**Proof.** From the configuration $(G_{n \times n}, D)$, let $(G_{(n+3) \times (n+3)}, D')$ be the configuration defined as follows. The restriction of $D'$ to the subgrid $G_{n \times n}$ consisting of the first (topmost) $n$ rows and first (leftmost) $n$ columns of $G_{(n+3) \times (n+3)}$ will be the set $D$ minus the vertices $(1, n)$ and $(n, 1)$ (which belong to $D$ since $D$ is a lethal set in $G_{n \times n}$ and they are corners). Moreover, $D'$ contains the following infected vertices: $(1, n+1)$ and $(n+1, 1)$, plus the vertices $(n+2, 2j+2)$ for every $0 \le j \le n/2$ and $(n+3, 2j+1)$ for every $0 \le j \le n/2+1$. Symmetrically, $D'$ contains the vertices $(2j+2, n+2)$ for every $0 \le j \le n/2-1$ and $(2j+1, n+3)$ for every $0 \le j \le n/2$. See Figure 2 for an illustration. Hence, we have $2n+6$ infected vertices in the last (bottommost) 3 rows and last (rightmost) 3 columns. Overall, $|D'| = |D| + 2n+4$.

Now let us prove that $D'$ is a lethal set. The vertices $(1, n)$ and $(n, 1)$ will become infected at the first step because they have 3 infected neighbours initially. Therefore, every vertex of the subgrid $G_{n \times n}$ will become infected (as $D$ is a lethal set). At the first step, all the vertices of rows and columns $n+2$ and $n+3$ are also infected plus the vertices $(n+1, 2)$ and $(2, n+1)$. From these last two vertices the infection propagates along row $n+1$ and column $n+1$, until it reaches the vertex $(n+1, n+1)$. ■

By Corollary 9, we get:

**Corollary 12** Let $D$ be a lethal set for $G_{n \times n}$ such that $\{(1, n-1), (2, n), (n-1, 1), (n, 2)\} \subseteq D$. If $n \equiv 0 \text{ or } 4 \pmod 6$, then $s_3(G_{(n+3) \times (n+3)}) - LB_{n+3} \le |D| - LB_n + 1$. If $n \equiv 2 \pmod 6$, then $s_3(G_{(n+3) \times (n+3)}) - LB_{n+3} \le |D| - LB_n$.

**Theorem 13** Let $n \equiv 5 \pmod 6$. Then, $s_3(G_{n \times n}) = LB_n = \frac{n^2+2n+1}{3}$.

**Proof.** By Theorem 10, since $n-3 \equiv 2 \pmod 6$, $s_3(G_{(n-3) \times (n-3)}) = LB_{n-3}$. Moreover, there exists an optimal lethal configuration of $G_{(n-3) \times (n-3)}$ containing the vertices $(n-1, 1), (n, 2), (1, n-1), (2, n)$. The result follows from the Corollary 12. ■

## 3.2 From $n$ even to $n+6$ (even) and optimality for every $n$ even

**Proposition 14** Let $n$ be even. If $D$ is a lethal set in $G_{n \times n}$ such that $\{(1, n-1), (2, n), (n-1, 1), (n, 2)\} \subseteq D$, then there exists a lethal configuration $(G_{(n+6) \times (n+6)}, D'')$ with size $|D'| = |D| + 4n + 16$ and such that $\{(1, n+5), (2, n+6), (n+5, 1), (n+6, 2)\} \subseteq D''$.

**Proof.** From the configuration $(G_{n \times n}, D)$, we first construct the configuration $(G_{(n+3) \times (n+3)}, D')$ as in Proposition 11 and then the configuration $(G_{(n+6) \times (n+6)}, D'')$ as follows. The restriction
<figure><img src="image_4.png" /><figcaption>Figure 3: Illustration of Proposition 14. The vertices are depicted as small squares (with most vertices inside $G_{n \times n}$ as well as their status omitted). Initially infected (resp., not infected) vertices of $D''$ are red (resp., white). Orange vertices are the ones that are initially infected in $D$ but not in $D''$.</figcaption></figure>

of $D''$ to the subgrid $G_{n+3 \times n+3}$ consisting of the first (topmost) $n+3$ rows and first (leftmost) $n+3$ columns of $G_{(n+6) \times (n+6)}$ will be the set $D'$ minus the vertex $(n+3, 3)$. Then, $D''$ contains the following vertices: $(n+4, 2)$ and $(n+4, 4)$, $(n+5, 1)$ plus the vertices $(n+5, 2j+1)$ for every $2 \le j \le n/2+2$ (note that $(n+5, 3)$ is not infected) and the vertices $(n+6, 2j+2)$ for every $0 \le j \le n/2+2$. In addition, $D''$ contains the vertices $(2j+1, n+5)$ and $(2j+2, n+6)$ for every $0 \le j \le n/2+1$. Finally, $D''$ contains the two corners $(n+6, 1)$ and $(1, n+6)$. See Figures 3 for an illustration. Overall, $|D''| = |D'| + 2n + 12 = D + 4n + 16$.

Now let us prove that $D''$ is a lethal set. The vertices $(1, n)$ and $(n, 1)$ will become infected at the first step because they have 3 infected neighbours initially. Then, every vertex of the subgrid $G_{n \times n}$ will become infected (as $D$ is a lethal set). At the first step, all the vertices of columns $n+2, n+3, n+5$ and $n+6$ become infected except $(n+4, n+2)$, $(n+4, n+3)$ and all the vertices of rows $n+2, n+3, n+5$ and $n+6$ except $(n+2, 3)$, $(n+3, 3)$, $(n+5, 3)$, $(n+6, 3)$. Vertices $(n+1, 2)$, $(2, n+1)$, $(n+1, 2)$ and $(n+4, 5)$ are also infected at step 1. From the vertex $(2, n+1)$ the infection propagates along column $n+1$ until it reaches the vertex $(n+1, n+1)$ and then along row $n+1$ until it reaches vertex $(n+1, 4)$. Then vertices $(n+1, 3)$, $(n+2, 3)$, $(n+3, 3)$, $(n+4, 3)$, $(n+5, 3)$, $(n+6, 3)$ become infected. From the vertex $(n+4, 5)$ the infection propagates along row $n+4$ until it reaches the vertex $(n+4, n+4)$ and then along column $n+4$ until it reaches vertex $(1, n+4)$. See an example in Figure 4. ■

**Remark:** We can do the proof by deleting from $D'$ instead of vertex $(n+3, 3)$ any vertex $(n+3, 2j_0+1)$ with $1 \le j_0 \le n/2$. Then $D''$ should contain in row $n+4$ the infected vertices: $(n+4, 2j_0)$ and $(n+4, 2j_0+2)$ and in row $n+5$ all the vertices $(n+5, 2j+1)$ for every $0 \le j \le n/2+2$ except vertex $(n+5, 2j_0+1)$. That might be useful to diminish the propagation time.

**Theorem 15** Let $n$ be even. Then, $s_3(G_{n \times n}) = LB_n$. Moreover, there exists an optimal lethal set which contains the vertex $(2, 2)$.

**Proof.** The theorem is true for $n = 2, 4, 6$, in which cases, optimal grids can be constructed directly (for $n = 4$ and $6$, see Figure 1). Then, the theorem follows by induction on $n$ (even) using Proposition 14 and Corollary 9. The fact that all the grids contain the vertex $(2, 2)$ will be useful for the proof of the existence of optimal tori ($s_3(T_{n \times n}) = \lfloor \frac{n^2+1}{3} \rfloor$). ■

**Theorem 16** Let $n \equiv 1 \text{ or } 3 \pmod{6}$. Then, $s_3(G_{n \times n}) \le LB_n + 1$. Moreover, there exists a lethal set of size $LB_n + 1$ which contains the vertex $(2, 2)$.
<figure><img src="image_5.png" /><figcaption>Figure 4: Construction for $n = 30$. Here we start from the optimal grid $G_{6 \times 6}$ (depicted by a blue frame) obtained from the grid $G_{3 \times 3}$ (Theorem 21) and apply the construction recursively. In the left part, initially infected (resp., not infected) vertices are red (resp., white). In the right part, vertices infected at step 1 are in orange and those not infected at the end of step 1 are in white. To get optimal lethal sets for the grids with $n$ even we should also have the corners infected and to get almost optimal for the grids with $n$ odd we should also have the vertex $(n, 3)$ infected.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Figure 5: Illustration of the configuration $\mathcal{H}(G_{n \times n}, D)$.</figcaption></figure>

**Proof.** The theorem follows from Theorem 15 and Corollary 12. ■

<figure><img src="image_7.png" /></figure>

### 3.3 From $n$ to $2n + 1$ and optimality for $n = 2^p - 1$

We give now another tool which, while rather simple, allows us to identify a new class of grids (namely, $n = 2^p - 1$) with odd side where the lower bound is tight.

For any configuration $(G_{n \times n}, D)$, let $(G_{(2n+1) \times (2n+1)}, D') = \mathcal{H}(G_{n \times n}, D)$ be the configuration defined as follows. The restriction of $D'$ to each of the four connected components obtained from $G_{(2n+1) \times (2n+1)}$ by removing its central row and central column (i.e., the $(n+1)^{th}$ row and $(n+1)^{th}$ column) is equal to $D$. Finally, $D'$ also contains the vertex $(n+1, n+1)$. See Fig. 5 for an illustration.

**Lemma 17** If $(G_{n \times n}, D)$ is a lethal configuration, then $\mathcal{H}(G_{n \times n}, D)$ is a lethal configuration.

**Proof.** Since $D$ is a lethal set for $G_{n \times n}$, each of the component of $G_{(2n+1) \times (2n+1)}$ obtained by removing the central row and the central column will be infected independently. Finally, the
central row and central column will be infected using the fact that every other vertex and the central one $(n+1, n+1)$ are infected. ■

**Definition 18** Let $H_1$ be the configuration that consists of the grid $G_{1×1}$ whose single vertex is infected. For every $p > 1$, let $H_p = \mathcal{H}(H_{p-1})$.

**Proposition 19** For every $p \ge 1$, $H_p$ is an optimal lethal configuration for the grid $G_{2p-1×2p-1}$ with $\frac{4p-1}{3}$ vertices initially infected.

**Proof.** Since $H_1$ is clearly lethal, by induction on $p$ and Lemma 17, then $H_p$ is lethal for all $p$. Let $D_p$ be the lethal set of $H_p$, then $|D_p| = 4|D_{p-1}|+1$ and as $|D_1|=1$, we get $D_p = \frac{4p-1}{3}$. Finally, the optimality comes from Theorem 8 that states that for $n = 2^p - 1$, $LB_n = \frac{n(n+2)}{3} = \frac{4p-1}{3}$. ■

**Theorem 20** For every $p \in \mathbb{N}^*$, let $n = 2^p - 1$. Then, $s_3(G_{n×n}) = LB_n = \frac{n(n+2)}{3}$.

# 4 The lower bound is not always tight

In the case when $n$ is odd such that $n \equiv 1,3 \pmod 6$ and $n \ne 2^p - 1$, it remains to decide whether $s_3(G_{n×n})$ equals $LB_n$ or $LB_n+1$. The first two values which are undetermined yet are $n=9$ and $n=13$. For these values, we prove that the lower bound is not tight using a Linear Program. Finally, for $n=9$, we also give a long combinatorial proof.

## 4.1 Useful properties of lethal sets

First, let us present one useful properties that must be satisfied by any lethal set (or more precisely by the complement of any lethal set) of a grid.

**Property 21** Let $D$ be a lethal set of the grid $G_{n×n}$. Let $H = V \setminus D$. Then, $H$ induces an acyclic subgraph whose every connected component has at most one vertex on the border.

**Proof.** For purpose of contradiction, let us first assume that $H$ induces a subgraph containing a cycle $C$ and let $u$ be the first vertex of $C$ contaminated by $D$. Then, when $u$ becomes infected, it has at most two infected neighbours, a contradiction.

Similarly, if $H$ induces a subgraph that contains a path $P$ (with at least two vertices) whose ends are in the border, then the first vertex to be infected in $P$ would have at most 2 already infected neighbours, a contradiction. ■

## 4.2 Linear Program

We present a Mixed-Integer Linear Program (MILP) for computing $s_r(G)$ in any graph $G$. As initially described in section 2, we consider a *step* of the contamination process. That is, at every step, all non-infected vertices with at least $r$ infected neighbours become infected. The question addressed in this section is as follows:

**Instance**: A graph $G = (V, E)$, non-negative integers $r$ and $T$.

**Question**: What is the minimum number $s_r^T(G)$ of initially infected vertices such that the whole graph is contaminated in at most $T$ steps?
Note that, for every $k \in \mathbb{N}$: $s_r(G) \le k$ if and only if $s_r^{|V|-k}(G) \le k$.

We formulate the problem as the MILP below, which computes an optimal solution for $s_r^T(G)$. The main variables are the binary variables $c_{v,t}$ for $v \in V$ and $t \in \{1, ..., T\}$, defined as follows: $c_{v,t} = 1$ if the vertex $v$ is infected after the $t^{th}$ step of the contamination process and 0 otherwise.

We describe hereafter the different constraints (1-6) of the MILP, starting by the objective function:

(1) Minimize the number of initially infected vertices.

(2) After T steps, all the vertices are infected.

(3) An infected vertex remains infected.

(4) A non infected vertex with less than $r$ infected neighbors cannot become infected.

(5) Every vertex with a degree strictly smaller than $r$ must be initially infected (case for instance of the corners of a grid $G_{n \times n}$ when $r = 3$ (Property 6)).

(6) If two adjacent vertices have degree $r$, then at least one must be initially infected (case for instance of two adjacent vertices of the border of a grid $G_{n \times n}$ when $r = 3$, (Property 7)).

(7) If $D$ is a lethal set and $v \in D$ such that $|N(v) \cap D| \ge r$, then $D \setminus \{v\}$ is a lethal set.

$$ \text{Minimize} \quad \sum_{v \in V} c_{v,0} \qquad (1) $$

$$ \text{Subject to} \quad \sum_{v \in V} c_{v,T} = |V| \qquad (2) $$

$$ c_{v,t-1} \le c_{v,t} \qquad \forall v \in V, t \in \{1, ..., T\} \qquad (3) $$

$$ c_{v,t} \le c_{v,t-1} + \frac{1}{r} \sum_{w \in N(v)} c_{w,t-1} \qquad \forall v \in V, t \in \{1, ..., T\} \qquad (4) $$

$$ c_{v,0} = 1 \qquad \forall v \in V, d(v) < r \qquad (5) $$

$$ c_{u,0} + c_{v,0} \ge 1 \qquad \forall \{u, v\} \in E, d(u) = d(v) = r \qquad (6) $$

$$ c_{v,0} + \sum_{w \in S} c_{w,0} \le r \qquad \forall v \in V, d(v) \ge r, \forall S \subseteq N(v), |S| = r \qquad (7) $$

$$ c_{v,t} \in \{0, 1\} \qquad \forall v \in V, t \in \{1, ..., T\} \qquad (8) $$

We note that the above cuts were not sufficient to make the MILP terminate (in sufficiently reasonable time) for $G = G_{n \times n}$ except for some small values of $n$. Therefore, to speedup the search, we propose further optimization cuts which hold under certain conditions on $G$.

**Further cuts if $r \ge 3$ and $G = G_{n \times n}$**

Let $r \ge 3$. Consider the graph $G'$ obtained from $G$ by adding a new vertex $x$ adjacent to every vertex of the border of $G$. Let $H'$ be the subgraph induced by $H$ and $x$. By Property 21, if $D$ is a lethal set, then $H = V \setminus D$ is acyclic, and moreover, every connected component of $H$ has at most one vertex on the border. Note that $H$ satisfies both these properties if and only if $H'$ is acyclic.

We introduce the next constraints (9-14) to express this property.
First, let $c_{x,0} = 0$ be a new variable expressing that we consider the new vertex $x$ as non-infected. Then, we consider the binary variables $y_e$ for $e = \{u, v\} \in E(G')$, defined as follows: $y_e = 1$ if and only if $c_{u,0} = 0$ and $c_{v,0} = 0$ (i.e., $y_e = 1$ if and only if $e$ is an edge of $H'$).

$$y_e + c_{u,0} + c_{v,0} \geq 1 \quad \forall e = \{u, v\} \in E(G') \quad (9)$$

$$2y_e + c_{u,0} + c_{v,0} \leq 2 \quad \forall e = \{u, v\} \in E(G') \quad (10)$$

$$y_e \in \{0, 1\} \quad \forall e = \{u, v\} \in E(G') \quad (11)$$

Then, to ensure that $H'$ is acyclic, we leverage upon an efficient formulation usually used to design a Linear Program for computing the Maximum Average Degree of a graph in polynomial time. To this end, we consider the real non-negative variables $z_{e,u}$ and $z_{e,v}$ for every $e = \{u, v\} \in E(G')$. Intuitively, each edge induced by $H'$ distributes a potential of one from each of its end-vertices, and $H'$ is acyclic if and only if no vertex receives a potential of at least one.

$$z_{e,u} + z_{e,v} = y_e \quad \forall e = \{u, v\} \in E(G') \quad (12)$$

$$\sum_{\substack{e' = \{w, v\} \\ w \in N(v)}} z_{e',v} < 1 \quad \forall v \in V(G') \quad (13)$$

$$z_{e,u}, z_{e,v} \geq 0 \quad \forall e = \{u, v\} \in E(G') \quad (14)$$

**Further optimizations.** We also provided the MILP with lower and upper bounds on the expected solution. That is, we add constraints of the following form $LB \leq \sum_{v \in V} c_{v,0} \leq UB$ for some given integers $LB$ and $UB$. We note that the main purpose of the previous MILP is to determine whether the lower bound $LB_n$ is tight for the cases not covered by Theorem 1. Therefore, we added some specific constraints which reflect the properties of lethal sets of size $LB_n$. For instance, when $n = 1$ or 3 (mod 6), by Property 23 (proved in the next subsection) every such lethal set $D$ does not contain two adjacent vertices and a vertex in $V \setminus D$ cannot be surrounded by four vertices in $D$. In some cases, we also imposed some further restrictions (such as, in the case when $n$ is odd, that the vertices in the border of the grids are precisely characterized if we expect a lethal set of size $LB_n$) or explicitly implemented branch and bound algorithms where we specified the values of some vertices.

Overall, the MILP (these LPs) allowed us to obtain best known solutions for every $n$ up to 20 (but 19) and the solutions found helped us at the beginning of our research. So far, the case $n = 19$ is the smallest size that still resists to the MILP as it provided a solution with $LB_{19} + 1$ vertices initially contaminated, but was not able to terminate when requiring a solution with $LB_{19}$ vertices. This is in contrast with the case when $n = 13$, where the MILP terminates certifying that there are no solutions using $LB_{13}$ vertices initially contaminated. In summary, our experiments based on the MILP allowed us as such to show that $s_3(G_{n \times n}) = LB_n + 1$ for $n \in \{9, 13\}$ (Proposition 22); but the MILP does not terminate for $n = 19$.

**Proposition 22** $s_3(G_{n \times n}) = LB_n + 1$ if $n \in \{9, 13\}$.

**Proof.** The upper bounds come from Theorem 16. The fact that this is optimal results from the execution of the LP described in this section and that certified that no solutions with $LB_n$ vertices exist. ■
### 4.3 Combinatorial proof for $n = 9$

We now provide below an ad-hoc combinatorial proof that $s_3(G_{9 \times 9}) = LB_9 + 1$; but it seems quite tedious to generalize this proof already for $n = 13$. We first state a proposition which gives more properties of the vertices of $D$ and $V \setminus D$ when $n \equiv 1 \text{ or } 3 \pmod{6}$.

**Property 23** Let $n \equiv 1 \text{ or } 3 \pmod{6}$ and let $D$ be a lethal set of size $LB_n = (n^2+2n)/3$; then
a) there are no two adjacent vertices in $D$, and
b) a vertex in $V \setminus D$ cannot have 4 neighbours in $D$.

**Proof.** We reconsider the proof of Theorem 8 with a more careful analysis. If two vertices of $D$ are adjacent, their perimeter is 6 and not 8 and so the initial perimeter is at most $4|D| - 2$. So we get $4|D| - 2 - 2(n^2 - |D|) \ge 4n$ and so $|D| \ge (n^2 + 2n + 1)/3 > LB_n$ and that proves property a). If a vertex in $V \setminus D$ has 4 neighbours in $D$, then when this vertex is infected the perimeter decreases by 4 and not 2. So in that case we get $4|D| - 2(n^2 - |D|) - 2 \ge 4n$ and so $|D| \ge (n^2 + 2n + 1)/3 > LB_n$ and that proves property b). ■

**Proposition 24** We have $s_3(G_{9 \times 9}) = LB_9 + 1 = 34$.

**Proof.** The upper bounds come from Theorem 16. To prove the proposition, by Theorem 8, it is sufficient to show that there is no lethal set for $G_{9 \times 9}$ with 33 vertices.

Hence, for purpose of contradiction, let us assume that there exists a lethal set $D$ of size 33 in the grid $G_{9 \times 9}$. The basic idea of the proof is mainly to use Properties 7, 21 and 23 in order to progressively show that some vertices are forced to belong to $D$ (vertices in red in Figure 6) or to $V \setminus D$ (vertices in yellow in Figure 6). There are few cases to be considered.

By Property 7 and 23, $D \cap \mathcal{B} = \{(1,1), (1,3), (1,5), (1,7), (1,9), (3,9), (5,9), (7,9), (9,9), (9,7), (9,5), (9,3), (9,1), (7,1), (5,1), (3,1)\}$. Then by Property 23(a), $(2,3), (2,5), (2,7), (3,8), (5,8), (7,8), (8,7), (8,5), (8,3), (7,2), (5,2), (3,2)$ are not in $D$. Then, Property 21 implies that $(2,2) \in D$ (otherwise there will be the path $(1,2), (2,2), (2,1)$ in $V \setminus D$); similarly $(2,8), (8,2), (8,8) \in D$. So far, we may assume that $D$ contains the vertices described in red and does not contain the ones in yellow as shown in Figure 6(a).

Let us now prove two claims very useful for the proof.

**Claim 25** At least one vertex in each of the pairs $\{(2,4), (2,6)\}, \{(4,2), (6,2)\}, \{(4,8), (6,8)\}$ and $\{(8,4), (8,6)\}$ belongs to $D$.

*Proof of Claim.* Suppose it is not true and that for example $(2,4)$ and $(2,6)$ are in $V \setminus D$. Then there will be the path $(1,4), (2,4), (2,5), (2,6), (1,6)$ in $V \setminus D$, contradicting Property 21. ◇

**Claim 26** For each pair $\{(2,4), (4,2)\}, \{(6,2), (8,4)\}, \{(2,6), (4,8)\}$ and $\{(6,8), (8,6)\}$, the two vertices of this pair have the same status (either both in $D$ or both in $V \setminus D$).

*Proof of Claim.* For purpose of contradiction, let us assume by symmetry that $(2,4) \in D$ and $(4,2) \notin D$ (see Figure 6(b)). By Property 23(b), vertex $(3,3) \notin D$ (otherwise the vertex $(3,2)$ which belongs to $V \setminus D$ will have 4 neighbours in $D$). Then, Property 21 implies that vertex $(4,3) \in D$ (otherwise $V \setminus D$ would contain a 4-cycle). Moreover, by Claim 25, as $(4,2) \notin D$, then $(6,2) \in D$. Now, by Property 23(a), vertices $(3,4), (4,4), (5,3)$ and $(6,3)$ are not in $D$. Then, Property 21 implies $(5,4) \in D$ (since otherwise we will have in $V \setminus D$ the 8-cycle $(3,2), (3,3), (3,4), (4,4), (5,4), (5,3), (5,2), (4,2)$). Then, by Property 23(a), we have $(5,5), (6,4) \notin D$. Then, by Property 23(b) $(7,3) \notin D$ (since otherwise $(7,2)$ would be a vertex
<figure><img src="image_8.png" /><figcaption>Figure 6: Illustrations of Proposition 24 ($n = 9$). Red vertices are the one that are assumed to belong to the lethal set $D$ of size 33, yellow vertices are assumed to belong to $V \setminus D$ and white vertices are undetermined yet. Vertices (squares) surrounded by blue correspond to the hypotheses done in the different cases of the proof. Figure (a) is a configuration that is certain if $|D| = 33$. Figure (b) is the configuration obtained if $(2, 4) \in D$ and $(4, 2) \notin D$ and leads to a contradiction (Claim 26). Figure (c) corresponds to the first case and leads to a contradiction. Figure (d) corresponds to the second case. Figure (e) (resp., (f)) to the subcase $(6, 2) \in D$ (resp. $(6, 2) \notin D$) leading to a contradiction in both subcases.</figcaption></figure>

in $V \setminus D$ with four neighbours in $D$. Finally, Property 21 implies $(7, 4) \in D$ (otherwise $V \setminus D$ contains the 4-cycle ((7, 4), (7, 3), (6, 3), (6, 4))) and $(8, 4) \in D$ otherwise $V \setminus D$ contains a path from (4, 1) to (9, 4). But then, there are two adjacent vertices in $D$ namely (7, 4) and (8, 4), contradicting Property 23(a) (see Figure 6(b)). ◇

Now, let us come back to the partial configuration described in Figure 6(a). Recall that, red vertices are known to belong to $D$ and yellow vertices do not belong to $D$.

By Claim 25, at least one vertex in each of the pairs {(2, 4), (2, 6)} {(4, 2), (6, 2)}, {(4, 8), (6, 8)}
and $\{(8,4), (8,6)\}$ belongs to $D$. We consider two cases

* Case 1: all vertices (2, 4), (2, 6), (4, 2), (6, 2), (4, 8), (6, 8), (8, 4), (8, 6) belong to $D$ (see Figure 6(c)).

By Property 23(a), this implies that vertices (3, 4), (3, 6), (4, 7), (6, 7), (7, 6), (7, 4), (6, 3), (4, 3) are not in $D$. Then, vertices (3, 3), (3, 5), (3, 7), (5, 3), (5, 7), (7, 3), (7, 5), (7, 7) are not in $D$ by Property 23(b). But, then there exists a 16-cycle (3, 3), (3, 4), (3, 5), (3, 6), (3, 7), (4, 7), (5, 7), (6, 7), (7, 7), (7, 6), (7, 5), (7, 4), (7, 3), (6, 3), (5, 3), (4, 3) in $V \setminus D$, a contradiction.

* case 2: In at least one of the pairs $\{(2, 4), (2, 6)\}$ $\{(4, 2), (6, 2)\}$, $\{(4, 8), (6, 8)\}$ $\{(8, 4), (8, 6)\}$ one vertex belongs to $D$ and the other not. By symmetry suppose $(2, 4) \in D$ and $(2, 6) \notin D$.

By Claim 26, as $(2, 4) \in D$, then $(4, 2) \in D$. By Property 23(a) $(3, 4) \notin D$ and $(4, 3) \notin D$. By Claim 26, as $(2, 6) \notin D$, then $(4, 8) \notin D$. Hence, by Claim 25, $(6, 8) \in D$ and again by Claim 26, $(8, 6) \in D$. Moreover, by Property 23(a) $(6, 7)$ and $(7, 6)$ are not in $D$. Now, Property 21 implies $(3, 7) \in D$, since otherwise there would be a path from (1, 6) to (4, 9) in $V \setminus D$. Then, Property 23(a) implies that $(3, 6)$ and $(4, 7) \notin D$. Then, by Property 21, $(4, 6) \in D$ again to avoid a path from (1, 6) to (4, 9) in $V \setminus D$ and then, by Property 23(a) $(4, 5)$ and $(5, 6) \notin D$. Then, vertices $(3, 5)$ and $(5, 7)$ need to be in $D$ to avoid 4-cycle in $V \setminus D$. See Figure 6(d) for the configuration reached so far. There are two subcases to be considered.

- Case $(6, 2) \in D$ (see Figure 6(e)). By Claim 26, $(8, 4) \in D$ and so by Property 23(a), $(6, 3)$ and $(7, 4) \notin D$. Then, Property 23(b), $(7, 3) \notin D$ (otherwise $(8, 3)$ would have 4 neighbours in $D$). Then $(6, 4)$ must be in $D$ to avoid a 4-cycle in $V \setminus D$ and so, by Property 23(a), $(5, 4)$, $(6, 5) \notin D$ to avoid adjacent vertices in $D$. At this point, $D$ already contains 31 vertices. Then to avoid 4-cycles in $V \setminus D$ either $(4, 4) \in D$ or both $(3, 3)$ and $(5, 3) \in D$; similarly either $(6, 6) \in D$ or both $(5, 5)$ and $(7, 5) \in D$. Therefore, to get $|D| = 33$ we need to have $(4, 4) \in D$ and $(6, 6) \in D$ and the other vertices $(5, 3)$, $(5, 5)$, $(7, 5) \notin D$. But, then there is a 8-cycle in $V \setminus D$ $(5, 3), (5, 4), (5, 5), (6, 5), (7, 5), (7, 4), (7, 3), (6, 3)$), a contradiction.

- Case $(6, 2) \notin D$ (See Figure 6(f)). By Claim 26, $(8, 4) \notin D$. Hence $(7, 3) \in D$ to avoid a path from $(6, 1)$ to $(9, 4)$ in $V \setminus D$. Then, by Property 23(a), $(6, 3)$ and $(7, 4) \notin D$. Hence, $(5, 3)$, $(7, 5) \in D$ to avoid 4-cycles in $V \setminus D$, and $(6, 4) \in D$ to avoid a path from $(6, 1)$ to $(9, 4)$ in $V \setminus D$. Moreover, by Property 23(a), $(5, 4)$ and $(6, 5) \notin D$ to avoid adjacent vertices in $D$. There are already 32 vertices in $D$ and the single remaining (undetermined yet) vertex of $D$ is not sufficient to break all 4-cycles in $V \setminus D$, a contradiction.

<figure><img src="image_9.png" /></figure>

# 5 Tori

In this section, we focus on the square tori. We note that Property 21 proved for the grids holds for any graph. This property was used for tori in $[\text{FLL}^+04]$ to prove the following lower bound:

**Proposition 27** ([FLL$^+$04]) $s_3(T_{n \times n}) \ge \text{LBT}_n = \lfloor \frac{n^2+1}{3} \rfloor$.
<figure><img src="image_10.png" /><figcaption>Figure 7: Illustration of Theorem 28 and Theorem 29 for the torus $T_{n \times n}$. The vertices are depicted as small squares. Red squares are those of a lethal set $D$ of $G_{(n-1) \times (n-1)}$. Orange squares are deleted from $D$ and not infected in the torus. Blue vertices are extra infected vertices in the torus. In Figure 7(b) (resp. 7(d)), we start from the optimal grid $G_{4 \times 4}$ (resp. $G_{6 \times 6}$) and apply recursively the construction of proposition 14 (resp. plus proposition 11).</figcaption></figure>

An upper-bound of $\lfloor n/3 \rfloor(n+1)$ for $s_3(T_{n \times n})$ is also given in [FLL$^+$04]. Note that it differs from the lower bound by a factor of order $n$ (more precisely, $n/3-1$ if $n \equiv 0 \pmod 3$, $(2n-1)/3$ if $n \equiv 2 \pmod 3$ and $n$ if $n \equiv 1 \pmod 3$). Here, we determine the exact value of $s_3(T_{n \times n})$ for every $n \ge 3$, as given in Theorem 2.

**Theorem 28** If $n$ is odd, then $s_3(T_{n \times n}) = LBT_n$.

**Proof.** As $n$ is odd, $n-1$ is even. By Theorem 15, there exists a lethal configuration $(G_{(n-1) \times (n-1)}, D)$ of size $LB_{n-1}$ and such that $(2,2), \subseteq D$. We build a lethal configuration $(T_{n \times n}, D')$ as follows.

* Let $n \equiv 3 \pmod 6$. The restriction of $D'$ to the subgrid $G_{(n-1) \times (n-1)}$ consisting of the last (bottommost) $n-1$ rows and last (rightmost) $n-1$ columns of $G_{(n-1) \times (n-1)}$ will be the set $D$ minus the corners $(1, n)$. Moreover, $D'$ contains the vertex $(0, 0)$ (see Figure 7(a)). So, $|D'| = |D|$. We have $|D| = LB_{n-1} = \frac{(n-1)^2+2(n-1)+4}{3} = \frac{n^2+3}{3} = LBT_n$.

* Let $n \equiv 1, 5 \pmod 6$. The restriction of $D'$ to the subgrid $G_{(n-1) \times (n-1)}$ consisting of the last (bottommost) $n-1$ rows and last (rightmost) $n-1$ columns of $G_{(n-1) \times (n-1)}$ will be the set $D$ minus the three corners $(1, n)$, $(n, 1)$, $(1, 1)$ and vertex $(2, 2)$. Moreover, $D'$ contains the three vertices $(0, 1)$, $(1, 0)$ and $(2, 1)$ (see Figure 7(b)). So, $|D'| = |D| - 1$. We have $|D| = LB_{n-1} = \frac{(n-1)^2+2(n-1)+6}{3} = \frac{n^2+5}{3}$. So, $|D'| = \frac{n^2+2}{3} = LBT_n$.

We claim that $D'$ is lethal in both cases. For the first case, the infection reaches all the vertices of the subgrid $G_{(n-1) \times (n-1)}$ except $(1, n)$ as $D$ is a lethal set. Then, it propagates along line 0 till $(0, n)$ and so $(1, n)$ becomes infected and then the infection propagates along column 0. For the second case, the infection reaches all the vertices of the subgrid $G_{(n-1) \times (n-1)}$; indeed vertices $(1, 1)$, $(1, n)$, $(2, 2)$, $(2, 3)$, $(n, 1)$ are infected thanks to $(0, 1)$, $(1, 0)$, $(2, 1)$ and then vertex $(1, 2)$ becomes infected. Then the infection propagates along column 0 till $(n, 0)$ and so $(0, 0)$ becomes infected. Finally the infection propagates along line 0 till $(0, n)$. ■

**Theorem 29** If $n$ is even, then $s_3(T_{n \times n}) = LBT_n$.

**Proof.**
* Let $n \equiv 0 \pmod{6}$. So $n-1 \equiv 5 \pmod{6}$. By Theorem 16, there exists a lethal set $D$ in the grid $G_{(n-1)\times(n-1)}$ of size $LB_{n-1}$. We construct a lethal configuration $(T_{n\times n}, D')$ as follows. The restriction of $D'$ to the subgrid $G_{(n-1)\times(n-1)}$ consisting of the last (bottommost) $n-1$ rows and last (rightmost) $n-1$ columns of $G_{(n-1)\times(n-1)}$ will be the set $D$. Moreover, $D'$ contains the vertex $(0,0)$. (see Figure 7(c)). So, $|D'| = |D| + 1$. We have $|D| = LB_{n-1} = \frac{(n-1)^2+2(n-1)+1}{3} = \frac{n^2}{3}$. So, $|D'| = \frac{n^2+3}{3} = LBT_n$.

* Let $n \equiv 2, 4 \pmod{6}$. So $n-1 \equiv 1, 3 \pmod{6}$. By Theorem 16, there exists a lethal set $D$ in the grid $G_{(n-1)\times(n-1)}$ of size $LB_{n-1} + 1$ containing vertex $(2,2)$. We construct a lethal configuration $(T_{n\times n}, D')$ as follows. The restriction of $D'$ to the subgrid $G_{(n-1)\times(n-1)}$ consisting of the last (bottommost) $n-1$ rows and last (rightmost) $n-1$ columns of $G_{(n-1)\times(n-1)}$ will be the set $D$ minus the vertex $(2,2)$. Moreover, $D'$ contains the vertex $(0,0)$ (see Figure 7(d)). So, $|D'| = |D|$. We have $|D| = LB_{n-1} + 1 = \frac{(n-1)^2+2(n-1)}{3} + 1 = \frac{n^2+2}{3}$. So, $|D'| = |D| = \frac{n^2+2}{3} = LBT_n$.

Similarly to the case where $n$ is odd, we can check that $D'$ is lethal in both cases. ■

# 6 Further Work

The first open problem<fnref n="2" /> would be to completely settle the question of determining $s_3(G_{n\times n})$ (either $LB_n$ or $LB_n + 1$) for any undetermined $n$, i.e., for every odd $n > 13$ such that $n \not\equiv 5 \pmod{6}$ and $n \not\equiv 2^p - 1$. Note that the first undetermined value is $n = 19$ for which our Linear Program did not terminate. The next graph class to be considered would be $d$-dimensional grids for $d > 2$. Last but not least, it would be interesting to investigate further the question of the speed of the infection, i.e., determining optimal (in terms of size) lethal sets that infect the whole graph as fast (resp., as slow) as possible.

<footnote n="2">²Recently, the problem was solved in [DNR22]. In particular, the authors show that $s_3(G_{n\times n}) = LB_n + 1$ when $n$ is odd and not congruent to 5 (mod 6) or of the form $2^p - 1$ for $p \ge 1$.</footnote>
References

[AL03] Joan Adler and Uri Lev. Bootstrap percolation: visualizations and applications. *Brazilian Journal of Physics*, 33(3):641-644, 2003.

[ATZ11] Sarah Spence Adams, Denise Sakai Troxell, and S. Luke Zinnen. Dynamic monopolies and feedback vertex sets in hexagonal grids. *Computers Mathematics with Applications*, 62(11):4049-4057, 2011.

[BB06] József Balogh and Béla Bollobás. Bootstrap percolation on the hypercube. *Probability Theory and Related Fields*, 134(4):624-648, 2006.

[BEPR19] Stéphane Bessy, Stefan Ehard, Lucia Draque Penso, and Dieter Rautenbach. Dynamic monopolies for interval graphs with bounded thresholds. *Discrete Applied Mathematics*, 260:256-261, 2019.

[Bol06] Béla Bollobás. *The art of mathematics: Coffee time in Memphis*. Cambridge University Press, 2006.

[BP98] József Balogh and Gábor Pete. Random disease on the square grid. *Random Structures & Algorithms*, 13(3-4):409-422, 1998.

[BP13] Fabricio Benevides and Michał Przykucki. On slowly percolating sets of minimal size in bootstrap percolation. *The Electronic Journal of Combinatorics*, pages P46-P46, 2013.

[BP15] Fabricio Benevides and Michał Przykucki. Maximum percolation time in two-dimensional bootstrap percolation. *SIAM Journal on Discrete Mathematics*, 29(1):224-251, 2015.

[CDP$^{+}$11] Carmen C Centeno, Mitre C Dourado, Lucia Draque Penso, Dieter Rautenbach, and Jayme L Szwarcfiter. Irreversible conversion of graphs. *Theoretical Computer Science*, 412(29):3693-3700, 2011.

[Che09] Ning Chen. On the approximability of influence in social networks. *SIAM Journal on Discrete Mathematics*, 23(3):1400-1415, 2009.

[CHL$^{+}$13] Chun-Ying Chiang, Liang-Hao Huang, Bo-Jr Li, Jiaojiao Wu, and Hong-Gwa Yeh. Some results on the target set selection problem. *Journal of Combinatorial Optimization*, 25(4):702-715, 2013.

[CHY13] Chun-Ying Chiang, Liang-Hao Huang, and Hong-Gwa Yeh. Target set selection problem for honeycomb networks. *SIAM Journal on Discrete Mathematics*, 27(1):310-328, 2013.

[CLR79] John Chalupa, Paul L Leath, and Gary R Reich. Bootstrap percolation on a bethe lattice. *Journal of Physics C: Solid State Physics*, 12(1):L31, 1979.

[COFKR14] Amin Coja-Oghlan, Uriel Feige, Michael Krivelevich, and Daniel Reichman. Contagious sets in expanders. In *Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms*, pages 1953-1987. SIAM, 2014.

[DJR09] Paul A Dreyer Jr and Fred S Roberts. Irreversible k-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion. *Discrete Applied Mathematics*, 157(7):1615-1627, 2009.
[DNR22] Peter J Dukes, Jonathan A Noel, and Abel E Romer. Extremal bounds for three-neighbour bootstrap percolation in dimensions two and three. *arXiv preprint arXiv:2209.07594*, 2022.

[FLL$^{+}$04] Paola Flocchini, Elena Lodi, Fabrizio Luccio, Linda Pagli, and Nicola Santoro. Dynamic monopolies in tori. *Discrete applied mathematics*, 137(2):197–212, 2004.

[GS15] Alberto Guggiola and Guilhem Semerjian. Minimal contagious sets in random regular graphs. *Journal of Statistical Physics*, 158(2):300–358, 2015.

[LL11] Anany Levitin and Maria Levitin. *Algorithmic puzzles*. OUP USA, 2011.

[MN18] Natasha Morrison and Jonathan A Noel. Extremal bounds for bootstrap percolation in the hypercube. *Journal of Combinatorial Theory, Series A*, 156:61–84, 2018.

[Mor09] Robert Morris. Minimal percolating sets in bootstrap percolation. *The Electronic Journal of Combinatorics*, 16(1):Research Paper 2,20, 2009.

[Pel02] David Peleg. Local majorities, coalitions and monopolies in graphs: a review. *Theoretical Computer Science*, 282:231–257, 2002.

[Pet97] Gabor Pete. *Disease processes and bootstrap percolation*. PhD thesis, Thesis for diploma at the Bolyai Institute, Jzsef Attila University, Szeged, 1997.

[PS20] Michał Przykucki and Thomas Shelton. Smallest percolating sets in bootstrap percolation on grids. *The Electronic Journal of Combinatorics*, (P4.34), 2020.

[Rie10] Eric Riedl. Largest minimal percolating sets in hypercubes under 2-bootstrap percolation. *The Electronic Journal of Combinatorics*, 17(1), 2010.

[Rie12] Eric Riedl. Largest and smallest minimal percolating sets in trees. *The Electronic Journal of Combinatorics*, (P64), 2012.

[Win03] Peter Winkler. *Mathematical puzzles: a connoisseur's collection*. CRC Press, 2003.