## 4 Results on \(d\)-Dimensional Grids
### An upper bound
The strategy from Figure 5 can be generalized to grid graphs of arbitrary size and dimension. We sweep the grid \(G_{n}^{d}\) layer after layer. No vertex of \(L(r+1,n,d)\) is cleared before the last vertex of \(L(r,n,d)\) has been. Let us consider two consecutive layers \(L(r,n,d)\) and \(L(r+1,n,d)\), and let us assume that the former has been completely cleared, while the latter is still completely contaminated. Together they form a bipartite graph where every vertex has degree of at most \(d\). How many lions are needed to clear \(L(r+1,n,d)\) without recontamination? **Lemma 7**. : _Assume that the set \(\{v\in[n]^{d}\mid|v|\leq r\}\) is already cleared. At most \(|L(r,n,d)|+|L(r+1,n,d-1)|\) lions are needed to clear \(L(r+1,n,d)\) without recontamination, if \(r+1\leq(d-1)(n-1)\). In the remaining case, if \((d-1)(n-1)<r+1\leq d(n-1)\), we need only \(|L(r,n,d)|\) lions._  
Proof. : First, we notice that for every \((x_{1},\ldots,x_{d})\in L(r+1,n,d)\) with \(x_{d}\
eq 0\), \((x_{1},\ldots,x_{d}-1)\) lies in \(L(r,n,d)\). Furthermore, if there is an edge connecting \((x_{1},\ldots,x_{d})\in L(r,n,d)\) and \((y_{1},\ldots,y_{d})\in L(r+1,n,d)\), and \((y_{1},\ldots,y_{d})\
eq(x_{1},\ldots,x_{d}+1)\), then \(y_{d}=x_{d}\). Now, to clear \(L(r+1,n,d)\) we proceed as follows: Initially, we place one lion at each vertex of \(L(r,n,d)\). To do that, we obviously need \(|L(r,n,d)|\) lions. If \(r+1\leq(d-1)(n-1)\), in addition, for every \(y=(y_{1},\ldots,y_{d})\in L(r+1,n,d)\) with \(y_{d}=0\), we place one lion on a vertex \(x=(x_{1},\ldots,x_{d})\in L(r,n,d)\) with \(x_{d}=0\), so that there exists an edge \((x,y)\in E_{n}^{d}\). For that, \(|L(r+1,n,d-1)|\) lions are needed. The following algorithm shows that no further lion is necessary to clear \(L(r+1,n,d)\). In the first step, each one of the additional lions moves to its assigned vertex \(y=(y_{1},\ldots,y_{d-1},0)\). Now all vertices in \(L(r+1,n,d)\) of this form have been cleared. Because every vertex of \(L(r,n,d)\) is still occupied by a lion, no recontamination has occurred. Next, we move lions from \(L(r,n,d)\) to \(L(r+1,n,d)\) without causing any recontamination. Beginning with \(i=0\), we repeat the following action until \(i\) equals \(n-1\) or \(r\): Move every lion that is placed on a vertex of the form \((x_{1},\ldots,x_{d-1},i)\) to \((x_{1},\ldots,x_{d-1},i+1)\). After this loop, every vertex of \(L(r+1,n,d)\) is occupied, as follows from the remarks at the beginning of this proof. Moreover, no recontamination was possible during the loop, because every lion left his vertex via the only edge that led a contaminated vertex. Note that in the case of \(r+1>(d-1)(n-1)\) the layer \(L(r+1,n,d)\) does not contain any vertex \(v\) with \(v_{d}=0\). We can do the same as above with \(|L(r,n,d)|\) lions. No additional lions are needed. As a consequence, we obtain the following upper bounds. **Lemma 8**. : \[k_{d}(n) \leq |L(\lfloor\frac{d(n-1)}{2}\rfloor,n,d)|+|L(\lfloor\frac{d(n-1)}{2} \rfloor+1,n,d-1)|\] \[\leq 2|L(\lfloor\frac{d(n-1)}{2}\rfloor,n,d)|\]  
Proof. : From Lemma 7 we can conclude  
\[L(r,n,d)\ :=\ \{v\in[n]^{d}\ |\ |v|=r\}\]0 \[L(r,n,d)\ :=\ \{v\in[n]^{d}\ |\ |v|=r\}\]1  
The recursive formula for \(|L(r,n,d)|\) implies  
\[L(r,n,d)\ :=\ \{v\in[n]^{d}\ |\ |v|=r\}\]2  
We want to establish that \(\sum_{i=\max(0,r-n+1)}^{r+1}|L(i,n,d-1)|\) obtains its maximum for \(r=\lfloor\frac{d(n-1)}{2}\rfloor\). The above sum contains at most \(n+1\) consecutive elements of the sequence:  
\[L(r,n,d)\ :=\ \{v\in[n]^{d}\ |\ |v|=r\}\]3By Lemma 6 and its proof, we know that this sequence is monotonously increasing for \(i\leq\frac{(d-1)(n-1)}{2}\), monotonously decreasing for \(i\geq\frac{(d-1)(n-1)}{2}\) and symmetric with respect to \(i=\frac{(d-1)(n-1)}{2}\). Hence, the sum is maximized if \(n+1\) consecutive sequence indices are chosen as symmetrically as possible around \(\frac{(d-1)(n-1)}{2}\). If \(n+1\) is odd and \(d\) is odd, a maximum sum arises if \(r+1-\frac{n}{2}=\frac{(d-1)(n-1)}{2}\).