## 3 Results in Dimension 2
The general _fall-down transformation_ is a concatenation of all such transformations,  
\[T:\mathcal{P}([n]^{d})\rightarrow\mathcal{P}([n]^{d}),\ \ \ T(C):=T_{1}\circ T_{2} \circ\ldots\circ T_{d}(C)\]  
Note that changing the order in this concatenation can alter the result but not the monotonicity of the result. A set \(C\subseteq[n]^{d}\) is said to be \(i\)_-monotone_, \(i\in\{1,\ldots,d\}\), if  
\[\forall(v_{1},\ldots,v_{i-1},v_{i},v_{i+1},\ldots,v_{d})\in C:v_{ i}>1\] \[\ \ \ \Rightarrow\ (v_{1},\ldots,v_{i-1},v_{i}-1,v_{i+1},\ldots,v_{ d})\in C\]  
The set \(C\) is _monotone_ if it is \(i\)-monotone for every \(i\in\{1,\ldots,d\}\). **Lemma 3**. : _The result of the fall-down transformation is monotone._  
Proof. : By definition it is clear that the result of each \(T_{i}\) is \(i\)-monotone. It remains to show that for every \(i,j\in\{1,\ldots,d\}\), \(i\
eq j\), and for every \(C\subseteq[n]^{d}\) which is \(j\)-monotone the transformed set \(T_{i}(C)\) is still \(j\)-monotone. To this end, let us assume that \(C\subseteq[n]^{d}\) is \(j\)-monotone, \(i\
eq j\). Let \(v=(v_{1},\ldots,v_{d})\in[n]^{d}\) be an arbitrary vertex satisfying \(v_{j}>0\). Then, we have  
Figure 1:0 Figure 1:1 Figure 1:2 Figure 1:3  
because the \(j\)-monotonicity of \(C\) implies that for every  
\((v_{1},\ldots,v_{i-1},a,v_{i+1},\ldots,v_{d})\in C\) also the vertex  
\((v_{1},\ldots,v_{i-1},a,v_{i+1},\ldots,v_{j-1},v_{j}-1,v_{j+1},\ldots,v_{d})\) belongs to \(C\). We want to prove  
Figure 1:4  
We assume that the preconditions are fulfilled. By (1) we can conclude  
Figure 1:5 Figure 1:6  
By definition of  
It contains \(n_{i}(v)=n_{i,T_{i}(C)}(v)=n_{i,C}(v)\) many vertices of \(T_{i}(C)\) and the same number of vertices of \(C\). It is not difficult to see that the number of boundary-vertices of \(T_{i}(C)\) in this column equals  
Figure 1:7  
where  
\[\chi_{1\leq n_{i}(v)\leq n-1}:=\left\{ \begin{array}{ll}1&\text{if }1\leq n_{i}(v) \leq n-1\\ 0&\text{otherwise}\end{array} \right.\]  
First, let us consider the case where this number equals zero. Then, either we have \(n_{i}(v)=0\) or we have \(n_{i}(v)=n\) and also \(n_{i}(w)=n\) for every \(w\in\mathcal{N}(v)\). In both cases the column of \(v\) does not contain any boundary vertices of \(C\) either. Now suppose the number does not equal zero, but still the maximum is attained by \(\chi_{1\leq n_{i}(v)\leq n-1}\). In this case the column of \(v\) is neither full nor empty, neither with respect to \(T_{i}(C)\) nor with respect to \(C\). Hence, there must also exist at least one boundary vertex of \(C\) in this column. Finally, suppose the maximum is attained by \(\max_{w\in\mathcal{N}(v)}n_{i}(v)-n_{i}(w)\). And let \(w\) be the neighbor vertex which maximizes \(n_{i}(v)-n_{i}(w)\). In this case we must have \(n_{i}(v)>n_{i}(w)\). The column of \(w\) contains exactly \(n_{i}(w)\) vertices of \(C\) and the column of \(v\) contains exactly \(n_{i}(v)\) vertices of \(C\). Thus, at least for \(n_{i}(v)-n_{i}(w)\) vertices of \(C\) in the \(v\)-column the corresponding neighbor in the \(w\)-column does not belong to \(C\). They are boundary vertices of \(C\). We have shown that for each column the number of boundary vertices of \(C\) cannot be less than the number of boundary vertices of \(T_{i}(C)\). This proves the claim. Now, we are ready to prove the following Lemma. **Lemma 5**. : _Any vertex set \(C\subset V_{n}^{2}\) satisfying \(\frac{n^{2}}{2}-\frac{n}{2}<|C|<\frac{n^{2}}{2}+\frac{n}{2}\) has at least \(n\) boundary vertices._  
Proof. : Due to Lemma 4 it suffices to prove the claim for monotone sets \(C\subset V_{n}^{2}\). Note that in the two-dimensional setting, \(n_{1}(j)\) denotes the number of vertices of \(C\) in the \(j\)-th row and \(n_{2}(i)\) denotes the number of vertices of \(C\) in the \(i\)-th column. Because of the monotonicity we have  
\[n_{1}(0)\geq n_{1}(1)\geq\ldots\geq n_{1}(n-1)\ \text{ and }\ n_{2}(0)\geq n_{2}(1)\geq\ldots\geq n_{2}(n-1)\]  
And clearly \(\sum_{j=0}^{n-1}n_{1}(j)=\sum_{i=0}^{n-1}n_{2}(i)=|C|\) holds.