# Monochromatic Edges in Complete Multipartite Hypergraphs
## 5 Proof of Theorem 3
Moreover, by Lemma 3, we can continue swapping in the same direction until the \(i\)th class has no red vertex or the \(i^{\prime}\)th class has no blue vertex, and the number of monochromatic edges does not increase. Note that we obtain the same result when considering swapping relating to other color combinations. Hence, the coloring with the minimum number of monochromatic edges among colorings with a constant number of red, blue and green vertices is the coloring such that, for any two classes, they must have at most one color of vertices to be in common. We will list all these forms in Table 11.  
The first column illustrates the list of five canonical forms, and the second column describes the colors of vertices in each class. Suppose that \(r_{i}\leqslant b_{i^{\prime}}\). Let \(\triangle_{ii^{\prime}}M_{T}(H,c,r,b)\) be the change in the number of monochromatic edges if all red vertices in the \(i\)th class are recolored into blue and \(r_{i}\) blue vertices in the \(i^{\prime}\)th class are recolored into red. The process will be called _total swapping_, which results in a new coloring, say \(c^{\prime}\). We can compute \(\triangle_{ii^{\prime}}M_{T}(H,c,r,b)\) by summing the change in the number of monochromatic edges of the swappings. Thus,  
\[\triangle_{ii^{\prime}}M_{T}(H,c,r,b)=\sum_{k=0}^{r_{i}-1}\left[ \binom{r_{i}-1-k}{r}\ +\ \binom{b_{i^{\prime}}-1-k}{r}\right]-\left[\binom{b_{i}+k}{r}\ +\ \binom{r_{i^{ \prime}}+k}{r}\right]\] \[\qquad=\left[\binom{0}{r}+\binom{1}{r}+\cdots+\binom{r_{i}-1}{r} \right]+\left[\binom{b_{i^{\prime}}-r_{i}}{r}+\binom{b_{i^{\prime}}-r_{i}+1} {r}\right]+\cdots+\binom{b_{i^{\prime}}-1}{r}\right]\] \[\qquad-\left[\binom{b_{i}}{r}+\binom{b_{i}+1}{r}+\cdots+\binom{b _{i}+r_{i}-1}{r}\right]-\left[\binom{r_{i^{\prime}}}{r}+\binom{r_{i^{\prime}} +1}{r}+\cdots+\binom{r_{i^{\prime}}+r_{i}-1}{r}\right].\]  
A _successful total swapping_ is a total swapping in such a way that the number of monochromatic edges is reduced. \begin{table}
\begin{tabular}{c c} \hline \hline
**Canonical Forms** & **Descriptions** \\ \hline \(F_{1}\) & The first class contains three colors while the other classes \\  & are monochromatic. \\ \hline \(F_{2}\) & The first class contains a pair of colors while the other classes \\  & are monochromatic. \\ \hline \(F_{3}\) & The first and second classes contain different pairs colors while the other \\  & classes are monochromatic. \\ \hline \(F_{4}\) & The first, second and third classes contain different pairs colors while the \\  & other classes are monochromatic. \\ \hline \(F_{5}\) & All classes are monochromatic. \\ \hline \hline \end{tabular}
\end{table} 
Table 11: The five canonical forms for three colors. **Lemma 5**. : _Suppose that \(1\leqslant r_{i}\leqslant b_{i^{\prime}}\). Then, \(\triangle_{ii^{\prime}}M_{T}(H,c,r,b)\leqslant 0\) if \(c\) satisfies at least one of the following conditions:_  
1. \(b_{i^{\prime}}<r_{i}+b_{i^{\prime}}\)_;_
2. \(b_{i^{\prime}}<r_{i}+r_{i^{\prime}}\)_._  
Proof. : Suppose that \(1\leqslant r_{i}\leqslant b_{i^{\prime}}\). If \(b_{i^{\prime}}<r_{i}+b_{i}\), then  
\[\triangle_{ii^{\prime}}M_{T}(H,c,r,b)\] \[\leqslant\left[\binom{0}{r}+\binom{1}{r}+\cdots+\binom{r_{i}-1}{ r}\right]-\left[\binom{r_{i^{\prime}}}{r}+\binom{r_{i^{\prime}}+1}{r}+ \cdots+\binom{r_{i^{\prime}}+r_{i}-1}{r}\right]\leqslant 0.\]  
The equality holds only when \(b_{i}+r_{i}-1<r\) and \(r_{i^{\prime}}+r_{i}-1<r\), i.e., \(b_{i}+r_{i}<r+1\) and \(r_{i}+r_{i^{\prime}}<r+1\). If \(b_{i^{\prime}}<r_{i}+r_{i^{\prime}}\), then  
\[\triangle_{ii^{\prime}}M_{T}(H,c,r,b) \leqslant\left[\binom{0}{r}+\binom{1}{r}+\cdots+\binom{r_{i}-1}{ r}\right]-\left[\binom{b_{i}}{r}+\binom{b_{i}+1}{r}+\cdots+\binom{b_{i}+r_{i}-1}{ r}\right]\] \[\leqslant 0.\]  
The equality holds only when \(b_{i}+r_{i}-1<r\) and \(r_{i^{\prime}}+r_{i}-1<r\), i.e., \(b_{i}+r_{i}<r+1\) and \(r_{i}+r_{i^{\prime}}<r+1\).