## 3 Results in Dimension 2  
In this section, we present the 2-dimensional case and prove the following result [2, 5]. **Theorem 1**. : \(\frac{n}{2}\) _lions are not capable of cleaning a 2-dimensional grid of size \(n\). In other words, \(k_{2}(n)>\frac{n}{2}\)._  
In the following, the variable \(k\) always denotes the number of lions. As a first step we mention the following simple Lemma which holds because each lion can only clear one vertex within each step. The proof of Lemma 2 is slightly more involved. Observe that both, Lemma 1 and Lemma 2, hold for arbitrary graphs. **Lemma 1**. : _The number of cleared vertices cannot increase by more than \(k\) within one time step._  
**Lemma 2**. : _If there are at least \(2k\) boundary vertices in \(\mathcal{C}(t)\), then the amount of cleared vertices cannot increase in the following step._  
\[|\partial\mathcal{C}(t)|\geq 2k \Rightarrow |\mathcal{C}(t+1)|\leq|\mathcal{C}(t)|\]  
Figure 1: \(k=3\) lions try to decontaminate a 2-dimensional \(n\times n\)-grid, where \(n=4\). (In this illustration the vertices are cells, and edges exist between neighbor cells.) Proof. : We assume \(|\partial\mathcal{C}(t)|\geq 2k\) for arbitrary, but fixed \(t\). We define the set \(C_{1}:=\mathcal{C}(t)\setminus\partial\mathcal{C}(t)\). Let \(v\in\partial\mathcal{C}(t)\) be a boundary vertex with \(i\) non-cleared neighbors. If there are at least \(i\) lions located on \(v\) at time \(t\) and these lions move in such a way that they use every edge leading to a non-cleared neighbor, then \(v\) remains cleared. In this case, we say that \(v\) is _protected from recontamination by leaving lions_. For example the vertex \((0,0)\) is protected by a leaving lion in the first step (\(t=0\)) of Figure 1.  
We define the set \(C_{2}\) as the set of grid vertices which:  
* are occupied by a lion at time \(t+1\), or
* are belonging to \(\partial\mathcal{C}(t)\) and are protected from recontamination in the following step by leaving lions. Both numbers, the number of vertices occupied by a lion at time \(t+1\) as well as the number of vertices protected from recontamination by leaving lions, are at most \(k\). We conclude that \(|C_{2}|\leq 2k\). Using \(C(t+1)=C_{1}\cup C_{2}\), we obtain \(|C(t+1)|=|C_{1}\cup C_{2}|\leq|C_{1}|+|C_{2}|=|\mathcal{C}(t)|-|\partial \mathcal{C}(t)|+|C_{2}|\leq|\mathcal{C}(t)|\). Next, we will establish that every set \(C\subset V_{n}^{2}\) of approximately \(\frac{n^{2}}{2}\) cleared vertices has at least \(n\) boundary vertices. This isoperimetric inequality is by [PERSON] and [PERSON] [4]. For convenience, we include a direct proof in dimension \(2\). Its Lemma 3 and an analogue to Lemma 4 were also used by [PERSON] [7]. We introduce the _fall-down transformation_ ([PERSON] and [PERSON] [4] call those transformations compressions and [PERSON] [7] called it \"pushing\" process.) which enables us to concentrate on situations where the cleared vertices are spread in a monotone way, cf. Figure 2. The idea is to turn on a kind of gravity which tos all cleared vertices downward towards the \(0\)-level of a particular coordinate \(i\), and to execute this transformation for every coordinate \(i\in\{1,\ldots,d\}\). More formally, let \(C\subseteq[n]^{d}\) be an arbitrary subset of the grid-vertices. Let \(i\in\{1,\ldots,d\}\) be arbitrary, and let  
\[n_{i,C}(v_{1},\ldots,v_{i-1},v_{i+1},\ldots,v_{d}):=|\{(v_{1},\ldots,v_{i-1}, a,v_{i+1},\ldots,v_{d})\in C\mid a\in[n]\}|\]  
denote the number of vertices of \(C\) in the column over the vertex \((v_{1},\ldots,v_{i-1},0,v_{i+1},\ldots,v_{d})\). For simplicity, we will often omit the \(C\) in \(n_{i,C}(V)\). The _fall-down transformation with respect to coordinate \(i\)_ is defined by  
\[T_{i}(C):=\{(v_{1},\ldots,v_{d})\mid v_{i}<n_{i}(v_{1},\ldots,v_{i-1},v_{i+1}, \ldots,v_{d})\}\]  
Figure 2: The fall-down transformation does not increase the number of boundary cells (=vertices).