## 4 Results on \(d\)-Dimensional Grids
### A lower bound  
Now, that we found an upper bound on \(k_{d}(n)\) in terms of the size of the middle layer, we want to prove that \(L:=|L(\lfloor\frac{(n-1)d}{2}\rfloor,n,d)|\) also determines a lower bound. The proof is based on a result by [PERSON] and [PERSON] [PERSON] and [PERSON] (2000) which uses the following _simplicial order_ on \([n]^{d}\). For every two vertices \(v,w\in[n]^{d}\) we have  
\[v<w :\Leftrightarrow |v|<|w|\ \vee\] \[(|v|=|w|\wedge\exists j\in[n]:\ (v_{j}>w_{j}\wedge\forall i<j:v_{i}=w_{ i}))\]  
Let \(v^{1}:=0:=(0,\ldots,0)\), \(v^{2}:=(1,0,\ldots,0)\), \(v^{3}:=(0,1,0,\ldots,0)\), \(\ldots\) denote the vertices in simplicial order. And for every \(i\in\{1,\ldots,n^{d}\}\) let \(A_{i}:=\{v^{1},\ldots,v^{i}\}\) be the set of the first \(i\) vertices with respect to the simplicial order. Then, \(|\partial A_{i}|\) denotes the number of boundary vertices of \(A_{i}\). With this notation we can formulate the following important kind of isoperimetric inequality. **Lemma 9**. : _For every given size \(m\in\{1,\ldots,n^{d}\}\) the set \(A_{m}\) attains the minimum number of boundary vertices, i.e._  
\[\forall C\subseteq[n]^{d}:\ \ |C|=m\ \Rightarrow\ |\partial C|\geq|\partial A_{m}|\]  
Proof. : For every \(A\subseteq[n]^{d}\) and every \(r\in\{1,\ldots,n(d-1)\}\) one defines the _closed neighborhood_ of \(A\) as  
\[\mathcal{N}(A) := \{v\in[n]^{d}\mid\exists w\in A:\ |v-w|\leq 1\}\]  
Then, Theorem 8 in [PERSON] and [PERSON] (2000) states that every \(C\subseteq[n]^{d}\) of \(m:=|C|\) vertices satisfies \(|\mathcal{N}(C)|\geq|\mathcal{N}(A_{m})|\). This can be translated into our Lemma 9 as follows:  
\[|\partial C|=|\mathcal{N}(\overline{C})|-|\overline{C}|=|\mathcal{N}( \overline{C})|-|\overline{A_{m}}|\geq|\mathcal{N}(\overline{A_{m}})|-| \overline{A_{m}}|=|\partial A_{m}|\]  
Now we can prove a lower bound in terms of the middle layer. **Lemma 10**. : \(k_{d}(n)\geq\lfloor\frac{1}{6}L\rfloor\)_._Proof. : Let us consider the paths of \(k_{d}(n)\) lions successfully cleaning the grid. By Lemma 1, the number of cleared vertices increases by at most \(k_{d}(n)\) within each step. Consequently, there must be some moment \(t\) such that \(\frac{n^{d}}{2}-k_{d}(n)\leq|\mathcal{C}(t)|\leq\frac{n^{d}}{2}\) and \(|\mathcal{C}(t+1)|>|\mathcal{C}(t)|\). Thanks to Lemma 2, we obtain  
\[k_{d}(n)\geq\frac{1}{2}|\partial\mathcal{C}(t)|.\]  
Thus we have to lower bound the number of boundary vertices of a subset of the grid with size \(|\mathcal{C}(t)|\). By Lemma 9, the fewest boundary vertices for such a set are obtained by the set \(A_{|\mathcal{C}(t)|}\). Thus, \(k_{d}(n)\geq\frac{1}{2}|\partial A_{|\mathcal{C}(t)|}|\). Let us assume there exist \(n,d\) such that \(k_{d}(n)<\lfloor\frac{1}{6}L\rfloor\). Then both nodes \(v^{\lceil\frac{n^{d}}{2}\rceil-k_{d}(n)}\) and \(v^{\lfloor\frac{n^{d}}{2}\rfloor}\) are contained in the middle layer, \(L(\lfloor\frac{(n-1)d}{2}\rfloor,n,d)\). We want to estimate the number of boundary vertices of \(A_{|\mathcal{C}(t)|}\) contained in the middle layer. Let us first consider the situation for the set \(A_{\lfloor\frac{n^{d}}{2}\rfloor}\), which contains half the number of all grid vertices. If \((n-1)d\) is even, half of the vertices of the middle layer are contained in \(A_{\lfloor\frac{n^{d}}{2}\rfloor}\). If \((n-1)d\) is odd, \(A_{\lfloor\frac{n^{d}}{2}\rfloor}\) contains all vertices of the middle layer and no vertex of the neighboring layer with distance \(\lceil\frac{(n-1)d}{2}\rceil\) from the origin. In both cases, there are at least \(\lfloor\frac{1}{2}L\rfloor\) boundary vertices of \(A_{\lfloor\frac{n^{d}}{2}\rfloor}\) in the middle layer of the grid. Since \(\frac{n^{d}}{2}-k_{d}(n)\leq|\mathcal{C}(t)|\leq\frac{n^{d}}{2}\) and \(k_{d}(n)<\lfloor\frac{L}{6}\rfloor\), the sets \(A_{\lfloor\frac{n^{d}}{2}\rfloor}\) and \(A_{|\mathcal{C}(t)|}\) differ in at most \(k_{d}(n)\) middle layer vertices. We conclude that \(A_{|\mathcal{C}(t)|}\) contains at least \(\lfloor\frac{1}{2}L\rfloor-k_{d}(n)\) boundary vertices in the middle layer.