# Monochromatic Edges in Complete Multipartite Hypergraphs
## 5 Proof of Theorem 3  
Assume that \(k\geqslant 2\). Let \(H\) be a balanced complete \(k\)-partite \((r+1)\)-uniform hypergraph with \(n\geqslant r+1\) vertices in each class, and let \(N=kn\). Let \(c\) be a red/blue/green coloring of \(H\) with the numbers of red, blue and green vertices of the \(i\)th class equal to \(r_{i},b_{i}\) and \(g_{i}\), respectively, and let \(R\), \(B\) and \(G\) be the total numbers of red, blue and green vertices, respectively. Let \(\triangle_{i^{\prime}}M(H,c,r,b)\) be the change in the number of monochromatic edges if a red vertex in the \(i\)th class is recolored into blue and a blue vertex in the \(i^{\prime}\)th class is recolored into red. The definitions are similar for other color combinations. The process will be called _swapping_, which results in a new coloring, say \(c^{\prime}\). As a result of the process, the number of red vertices in the \(i\)th class decreases by \(1\), and the number of red vertices in the \(i^{\prime}\)th class increases by \(1\), while the total number of red vertices remains the same. In other words, the coloring \(c^{\prime}\) has \(r_{i}-1\) and \(r_{i^{\prime}}+1\) red vertices in the \(i\)th and \(i^{\prime}\)th classes, respectively. Likewise, the coloring \(c^{\prime}\) has \(b_{i}+1\) and \(b_{i^{\prime}}-1\) blue vertices in the \(i\)th and \(i^{\prime}\)th classes, respectively. We can compute \(\triangle_{i^{\prime}}M(H,c,r,b)\) by comparing the numbers of monochromatic edges containing those vertices that underwent swapping before and after the swapping process. Thus,  
\[\triangle_{i^{\prime}}M(H,c,r,b) =\left[\binom{B-1}{r}-\binom{b_{i}}{r}\ +\ \binom{R-1}{r}-\binom{r_{i^{\prime}}}{r}\right]\] \[\ \ \ -\left[\binom{R-1}{r}-\binom{r_{i}-1}{r}\ +\ \binom{B-1}{r}- \binom{b_{i^{\prime}}-1}{r}\right]\] \[=\left[\binom{r_{i}-1}{r}\ +\ \binom{b_{i^{\prime}}-1}{r}\right]- \left[\binom{b_{i}}{r}\ +\ \binom{r_{i^{\prime}}}{r}\right].\]  
A _successful swapping_ is a swapping in such a way that the number of monochromatic edges is reduced, i.e., \(\triangle_{i^{\prime}}M(H,c,r,b)<0\). Note that if \(0<r_{i}<n\), \(<b_{i}<n\), \(r_{i^{\prime}}=n-1\) and \(b_{i^{\prime}}=1\), then  
\[\triangle_{i^{\prime}}M(H,c,r,b) =\left[\binom{r_{i}-1}{r}\ +\ \binom{b_{i^{\prime}}-1}{r}\right]- \left[\binom{b_{i}}{r}\ +\ \binom{r_{i^{\prime}}}{r}\right]\] \[=\left[\binom{r_{i}-1}{r}\ +\ \binom{1-1}{r}\right]-\left[\binom{b_{i }}{r}\ +\ \binom{n-1}{r}\right].\]  
Since \(r_{i}<n\), \(0<b_{i}\) and \(n-1\geqslant r\), we have that \(\triangle_{i^{\prime}}M(H,c,r,b)<0\). This implies that a swapping resulting in fewer polychromatic classes is always successful. Lemma 3: _If \(\triangle_{i^{\prime}}M(H,c,r,b)\leqslant 0\), then \(\triangle_{i^{\prime}}M(H,c^{\prime},r,b)\leqslant 0\)._The proof of this lemma is similar to that of Lemma 1. Lemma 3 means that if swapping can be carried out without increasing the number of monochromatic edges, another swapping in the same direction will be successful (if there is a red and blue vertices to be swapped). The process of successful swappings will terminate when the \(i\)th class has no red vertex or the \(i^{\prime}\)th class has no blue vertex. Lemma 4: _If \(\triangle_{ii^{\prime}}M(H,c,r,b)\geqslant 0\), then \(\triangle_{ii^{\prime}}M(H,c,b,r)\leqslant 0\)._  
The proof of this lemma is similar to that of Lemma 2. However, in contrast to Lemma 2, it is possible that the equality holds. Note that if \(c\) contains two classes, the \(i\)th and \(i^{\prime}\)th, such that both of them contain at least one red vertex and one blue vertex, then there are two directions of swapping as follows:  
1. Swapping a red vertex of the \(i\)th class with a blue vertex of the \(i^{\prime}\)th class;
2. Swapping a blue vertex of the \(i\)th class with a red vertex of the \(i^{\prime}\)th class. By Lemma 4, one of the two directions can be achieved without increasing the number of monochromatic edges.