# Monochromatic Edges in Complete Multipartite Hypergraphs
Case 3: \(\frac{n_{1}+n_{2}}{2}\leqslant X<n_{2}\). We have that \(c_{X}^{*}\) is in the form \(F_{2}\) or \(F_{4}\). We will show that \(\triangle_{2}M(H,c_{X}^{*})<0\) for both forms. If \(X=\frac{n_{1}+n_{2}}{2}\) and \(c_{X}^{*}\) is in the form \(F_{4}\) with \(x_{1}=n_{1}\), \(x_{2}=X-n_{1}\) and \(x_{3}=0\), then \(\triangle_{2}M(H,c_{X}^{*})<0\) similarly as in Case 2. If \(\frac{n_{1}+n_{2}}{2}\leqslant X<n_{2}\) and \(c_{X}^{*}\) is in the form \(F_{2}\) with \(x_{1}=0\), \(x_{2}=X\) and \(x_{3}=0\), then  
\[\triangle_{2}M(H,c_{X}^{*})=\left[\binom{X}{2}-\binom{X}{2}\right]-\left[ \binom{N-X\ -\ 1}{2}-\binom{n_{2}-X\ -\ 1}{2}\right]\leqslant 0.\]  
The equality holds only when \(N-X\ -\ 1<2\), which is impossible. Again, from this point, the cases will be divided by whether the hypergraph is of type A or B. Case 4A: \(n_{2}\leqslant X<n_{1}+n_{2}\) and \(H\) is a type A hypergraph. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Cases** & **Number of Red Vertices** & **Canonical Form** \\ \hline
1 & \(0\leqslant X<n_{1}\) & \(F_{1}\) \\
2 & \(n_{1}\leqslant X<\frac{n_{1}+n_{2}}{2}\) & \(F_{4}\) \\
3 & \(X=\frac{n_{1}+n_{2}}{2}\) & \(F_{2}\) or \(F_{4}\) \\  & \(\frac{n_{1}+n_{2}}{2}<X<n_{2}\) & \(F_{2}\) \\
4\(B\) & \(n_{2}\leqslant X<n_{3}\) & \(F_{3}\) or \(F_{6}\) \\
5\(B\) & \(n_{3}\leqslant X\leqslant\lfloor\frac{N}{2}\rfloor\) & \(F_{8}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 10: List of best canonical forms for Type B hypergraphs \(n_{1}+n_{2}>n_{3}\). We have that \(c_{X}^{*}\) is in the form \(F_{6}\) with \(x_{1}=X-n_{2}\), \(x_{2}=n_{2}\) and \(x_{3}=0\). Then,  
\[\triangle_{1}M(H,c_{X}^{*})=\bigg{[}\binom{X}{2}+\binom{n_{1}+n_{2}-X\ -\ 1}{2} \bigg{]}-\bigg{[}\binom{X-n_{2}}{2}+\binom{N-X\ -\ 1}{2}\bigg{]}.\]  
We will show that \(\triangle_{1}M(H,c_{X}^{*})<0\) by Proposition 1. We have \(X+(n_{1}+n_{2}-X\ -\ 1)=n_{1}+n_{2}-1\leqslant n_{1}+n_{3}-1=(X-n_{2})+(N-X\ -\ 1)\), \(X-n_{2}<X\) and \(n_{1}+n_{2}-X\ -\ 1<N-X\ -\ 1\). Since \(2\leqslant N-X\ -\ 1\), we have that \(\triangle_{1}M(H,c_{X}^{*})<0\). Case 5A: \(n_{1}+n_{2}\leqslant X\leqslant\lfloor\frac{N}{2}\rfloor\) and \(H\) is a type A hypergraph. We have that \(c_{X}^{*}\) is in the form \(F_{10}\) with \(x_{1}=n_{1}\), \(x_{2}=n_{2}\) and \(x_{3}=X-n_{1}-n_{2}\). Then,  
\[\triangle_{3}M(H,c_{X}^{*})=\bigg{[}\binom{X}{2}-\binom{X-n_{1}-n_{2}}{2} \bigg{]}-\bigg{[}\binom{N-X\ -\ 1}{2}-\binom{N-X\ -\ 1}{2}\bigg{]}\geqslant 0.\]  
The equality holds only when \(X<2\), which is impossible. This yields a contrary result: The number of monochromatic edges increases when the number of red vertices increases. Hence, \(F_{10}\) gives the minimum number of monochromatic edges when \(X=n_{1}+n_{2}\) instead. Next, we will consider the last two cases of type B hypergraphs. Case 4B: \(n_{2}\leqslant X<n_{3}\) and \(H\) is a type B hypergraph. We have that \(c_{X}^{*}\) is in the form \(F_{3}\) or \(F_{6}\). We will show that \(\triangle_{3}M(H,c_{X}^{*})<0\) for \(F_{3}\) and \(\triangle_{1}M(H,c_{X}^{*})<0\) for \(F_{6}\). If \(c_{X}^{*}\) is in the form \(F_{3}\) with \(x_{1}=0\), \(x_{2}=0\) and \(x_{3}=X\), then  
\[\triangle_{3}M(H,c_{X}^{*})=\bigg{[}\binom{X}{2}-\binom{X}{2}\bigg{]}-\bigg{[} \binom{N-X\ -\ 1}{2}-\binom{n_{3}-X\ -\ 1}{2}\bigg{]}\leqslant 0.\]  
Note that the inequality is equal when \(N-X\ -\ 1<2\), which is impossible. Next, if \(c_{X}^{*}\) is in the form \(F_{6}\) with \(x_{1}=X-n_{2}\), \(x_{2}=n_{2}\) and \(x_{3}=0\), then  
\[\triangle_{1}M(H,c_{X}^{*})=\bigg{[}\binom{X}{2}+\binom{n_{1}+n_{2}-X\ -\ 1}{2} \bigg{]}-\bigg{[}\binom{N-X\ -\ 1}{2}\bigg{]}\ +\ \binom{X-n_{2}}{2}\bigg{]}.\]  
We will show that \(\triangle_{1}M(H,c_{X}^{*})<0\) by Proposition 1. We have \(X+(n_{1}+n_{2}-X\ -\ 1)=n_{1}+n_{2}-1\leqslant n_{1}+n_{3}-1=(N-X\ -\ 1)+(X-n_{2})\), \(X>X-n_{2}\) and \(n_{1}+n_{2}-X\ -\ 1<N-X\ -\ 1\). Since \(2\leqslant N-X\ -\ 1\), we have that \(\triangle_{1}M(H,c_{X}^{*})<0\). Case 5B: \(n_{3}\leqslant X\leqslant\lfloor\frac{N}{2}\rfloor\) and \(H\) is a type B hypergraph.