# Monochromatic Edges in Complete Multipartite Hypergraphs
## 5 Proof of Theorem 3
Thus,  
\[M(H,c) =\binom{nk_{r}+r_{1}}{r+1}+\binom{nk_{b}+b_{2}}{r+1}+\binom{nk_{g} +g_{1}+g_{2}}{r+1}\] \[\quad-\binom{r_{1}}{r+1}-\binom{b_{2}}{r+1}-\binom{g_{1}}{r+1}- \binom{g_{2}}{r+1}-(k-2)\binom{n}{r+1}\]  
and  
\[M(H,c^{\prime}) =\binom{n(k_{r}+1)+r_{1}}{r+1}+\binom{nk_{b}+b_{2}}{r+1}+\binom{n (k_{g}-1)+g_{1}+g_{2}}{r+1}\] \[\quad-\binom{r_{1}}{r+1}-\binom{b_{2}}{r+1}-\binom{g_{1}}{r+1}- \binom{g_{2}}{r+1}-(k-2)\binom{n}{r+1}.\]  
Then,  
\[M(H,c^{\prime})-M(H,c) =\left[\binom{n(k_{r}+1)+r_{1}}{r+1}+\binom{n(k_{g}-1)+g_{1}+g_{2} }{r+1}\right]\] \[\triangle_{ii^{\prime}}M_{T}(H,c,r,b)\]0  
We will show that \(M(H,c^{\prime})-M(H,c)<0\) by Proposition 1. We have \([n(k_{r}+1)+r_{1}]+\left[n(k_{g}-1)+g_{1}+g_{2}\right]=[nk_{r}+r_{1}]+[nk_{g} +g_{1}+g_{2}]\), \(nk_{r}+r_{1}<n(k_{r}+1)+r_{1}\leqslant n(k_{g}-1)+r_{1}<nk_{g}+g_{1}+g_{2}\) and \(nk_{r}+r_{1}<n(k_{r}+1)+g_{1}+g_{2}\leqslant n(k_{g}-1)+g_{1}+g_{2}<nk_{g}+g_{ 1}+g_{2}\). Since \(nk_{g}+g_{1}+g_{2}>r+1\), we have that \(M(H,c^{\prime})-M(H,c)<0\). Note that we only use the fact that \(r_{1}<n\) and \(g_{1}+g_{2}>0\). Since \((k-2)\equiv 2\pmod{3}\), colorings such that \(k_{r}\), \(k_{b}\) and \(k_{g}\) are as equal as possible must have one of these conditions:  
1. \(k_{r}+1=k_{b}=k_{g}\);
2. \(k_{r}=k_{b}+1=k_{g}\);
3. \(k_{r}=k_{b}=k_{g}+1\). We will show that a coloring with the last condition has more monochromatic edges than a coloring with either of the first two conditions (with the same polychromatic classes). Suppose that \(c\) is a coloring such that \(k_{r}=k_{b}=k_{g}+1\). We consider \((g_{1},r_{1},g_{2},0)\) of \(c\). Since \(g_{1}+r_{1}=n\), if \(g_{2}\geqslant r_{1}\), then \(g_{2}\geqslant r_{1}+g_{1}\). This leads to a contradiction since \(n=r_{1}+g_{1}\leqslant g_{2}=n-b_{2}<n\). Hence, \(g_{2}<r_{1}\) and consequently \(g_{1}+g_{2}\leqslant r_{1}\) by quadruple conditions. Next, we will increase the number of green classes. Without loss of \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Number of Red Classes** & **Number of Blue Classes** & **Number of Green Classes** \\ \hline \(k_{r}\) & \(k_{b}\) & \(k_{g}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 13: The number of monochromatic classes of each color. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Polychromatic Classes** & **Number of Red Vertices** & **Number of Blue Vertices** & **Number of Green Vertices** \\ \hline
1 & \(r_{1}\
eq 0\) & 0 & \(g_{1}\
eq 0\) \\
2 & 0 & \(b_{2}\
eq 0\) & \(g_{2}\
eq 0\) \\ \hline \hline \end{tabular}
\end{table} 
Table 12: The number of vertices of each color for the first two classes. generality, we will recolor all vertices in a red class into green and obtain a new coloring \(c^{\prime}\) with Condition (1). Then,  
\[M(H,c) =\binom{nk_{r}+r_{1}}{r+1}+\binom{nk_{b}+b_{2}}{r+1}+\binom{nk_{g}+g _{1}+g_{2}}{r+1}\] \[\quad-\binom{r_{1}}{r+1}-\binom{b_{2}}{r+1}-\binom{g_{1}}{r+1}- \binom{g_{2}}{r+1}-(k-2)\binom{n}{r+1}\]  
and  
\[M(H,c^{\prime}) =\binom{n(k_{r}-1)+r_{1}}{r+1}+\binom{nk_{b}+b_{2}}{r+1}+\binom{n( k_{g}+1)+g_{1}+g_{2}}{r+1}\] \[\quad-\binom{r_{1}}{r+1}-\binom{b_{2}}{r+1}-\binom{g_{1}}{r+1}- \binom{g_{2}}{r+1}-(k-2)\binom{n}{r+1}.\]  
Then,  
\[M(H,c^{\prime})-M(H,c) =\bigg{[}\binom{n(k_{r}-1)+r_{1}}{r+1}+\binom{n(k_{g}+1)+g_{1}+g _{2}}{r+1}\bigg{]}\] \[\quad-\bigg{[}\binom{nk_{r}+r_{1}}{r+1}+\binom{nk_{g}+g_{1}+g_{2} }{r+1}\bigg{]}.\]  
We will show that \(M(H,c^{\prime})-M(H,c)<0\) by Proposition 1. We have \([n(k_{r}-1)+r_{1}]+[n(k_{g}+1)+g_{1}+g_{2}]=[nk_{r}+r_{1}]+[nk_{g}+g_{1}+g_{2}]\). Since \(g_{1}+g_{2}\leqslant r_{1}\), then \(nk_{g}+g_{1}+g_{2}\leqslant nk_{g}+r_{1}=n(k_{r}-1)+r_{1}<nk_{r}+r_{1}\) and \(nk_{g}+g_{1}+g_{2}<n(k_{g}+1)+g_{1}+g_{2}\leqslant n(k_{g}+1)+r_{1}=nk_{r}+r_ {1}\). Since \(nk_{g}+g_{1}+g_{2}>r+1\), we have that \(M(H,c^{\prime})-M(H,c)<0\). Finally, we will consider a coloring with condition (1) or (2). By symmetry, assume that \(c\) is a coloring with \(k_{r}+1=k_{b}=k_{g}\). We will recolor a green vertex in the first class of \(c\) into red.