Monochromatic Edges in Complete Multipartite Hypergraphs
Consider the following problem. In a school with three classes containing $n$ students each, given that their genders are unknown, find the minimum possible number of triples of same-gender students not all of which are from the same class. Muaengwaeng asked this question and conjectured that the minimum scenario occurs when the classes are all boy, all girl and half-and-half. In this paper, we solve many generalizations of the problem including when the school has more than three classes, when triples are replaced by groups of larger sizes, when the classes are of different sizes, and when gender is replaced by other non-binary attributes.
\section{Introduction}
A \textit{hypergraph} is a pair $(V, E)$ where $V$ is a finite set of vertices and $E$ is a collection of subsets of $V$. Each subset in $E$ is called an \textit{edge}. An \textit{$r$-uniform} hypergraph contains only edges of size $r$ and if it contains all possible edges of size $r$, this $r$-uniform hypergraph is said to be \textit{complete}.

For decades, many researchers have been studying hypergraphs as a generalization of graphs and many theorems in graph theory have been extended to hypergraphs (see \cite{Frank}, \cite{Gyarfas}, \cite{Katona}, \cite{Keevash} and \cite{Mubayi}). Graph coloring which is a popular topic is also a part of those interesting extensions (see \cite{Berge} and \cite{Erdos}). Given a hypergraph, an \emph{$m$-coloring} is an assignment of a color to each vertex of the hypergraph from $m$ available colors. An edge is said to be \textit{monochromatic} if all vertices in it have the same color. Some later researches (see \cite{Bujt} and \cite{Cowen}) focused on \textit{proper coloring} and \textit{defective coloring} which involve colorings where monochromatic edges do not exist or exist only in some limited amount. The complexity of general hypergraphs has led to study  focusing on hypergraphs which have an orderly and symmetric structure, for example, $k$-partite hypergraphs.

A \textit{balanced $k$-partite $r$-uniform hypergraph} has $k$ vertex classes $V_1, V_2, … , V_k$ of the same size. There are two natural generalizations of $k$-partite graphs to hypergraphs. First, each edge is an $r$-subset of $\displaystyle\bigcup_{i=1}^{k}V_i$, all of whose vertices are from different classes. The second definition of edges is that each edge is an $r$-subset, not all of whose vertices are from the same class. In the paper, we will use the latter definition. 

The problem in the abstract can be restated in the language of hypergraphs as follows.
\begin{problem}
Which $2$-coloring minimizes the number of monochromatic edges of a balanced complete tripartite $3$-uniform hypergraph?
\end{problem}This question was asked by Muaengwaeng \cite{Muaeng}. Given that those two colors are red and blue, she conjectured that the minimum coloring occurs when those three classes are all blue, all red and half-and-half. In this paper, we solve many generalizations of Problem $1$. First, we study a balanced complete $k$-partite $r$-uniform hypergraph.  
\begin{theorem}\label{thm:1}
Let $n \geqslant r \geqslant 3$ and $k \geqslant 2$. The $2$-coloring minimizing the number of monochromatic edges of a balanced complete $k$-partite $r$-uniform hypergraph with $n$ vertices in each class is as follows:
\begin{enumerate}
	\item Color all vertices of the first $ \lfloor \frac{k}{2} \rfloor $ classes with red.
	\item Color all vertices of the last $ \lfloor \frac{k}{2} \rfloor $ classes with blue.
	\item If there is another class, color the vertices of that class such that the number of red and blue vertices are as equal as possible.
\end{enumerate}Moreover, this coloring is unique up to a permutation of colors and classes.
\end{theorem}
The case where $r=k=3$ was presented in a conference \cite{Boon} by the second author. The key idea is to calculate the change in the number of  monochromatic edges when a vertex is recolored. We use this to find the minimum coloring among those with a fixed number of red  vertices. Then we compare these minimum colorings.

The proof of Theorem $2$ gives a clue on how to prove a more general case when each class does not contain the same number of vertices.

\begin{theorem}\label{thm:2}
	For any unbalanced complete tripartite $3$-uniform hypergraph $H$ with the numbers of vertices of the first, second and third classes, $ n_1 \leqslant n_2 \leqslant n_3$ where $n_3 \geqslant 3$ and $n_1+n_2+n_3 = N$, a $2$-coloring minimizing the number of monochromatic edges of $H$ is as follows:
	\begin{enumerate} 
		\item If $n_1 + n_2 > n_3$, color all vertices in the second and third classes with blue and red, respectively, then and color $\left\lceil \frac{N^2-3N-n^2_1-2n_1n_3+3n_1+4n_3}{2(N-n_1)}\right\rceil-n_3$ vertices in the first class with red.
		\item If $n_1+n_2 \leqslant n_3$, then color all vertices in the first and second classes with red and color the third class with blue.
	\end{enumerate}Moreover, each coloring is unique up to a permutation of colors unless $(n_1,n_2,n_3)=(2,n,n+1)$ for $n \geqslant 2$ in which case there is another extremal coloring namely a coloring such that vertices in the third class are all red, all vertices in the second class are all blue and the first class has one red and one blue vertices.
\end{theorem}

The proof consists of two parts. First, by swapping a red vertex and a blue vertex in different classes, we conclude that a minimum coloring must be in one of the $12$ canonical  forms. Then we compares the numbers of monochromatic edges between the forms.

Finally, we study the number of monochromatic edges of balanced complete $k$-partite $r$-uniform hypergraphs except, this time, up to three colors will be available. The problem of minimizing the number of monochromatic edges gets more complicated as it is not a simple two-way comparison between red and blue. The results are divided upon the remainder of the number of vertex classes, $k$, divided by $3$. We are able to solve the cases $k\equiv 0,1 \ (\textrm{mod}\ 3)$.
\begin{theorem}\label{thm:3}
	Let $n \geqslant r \geqslant 3$ and $k \geqslant 3$. For any balanced complete $k$-partite $r$-uniform hypergraph, $H$, with $n$ vertices in each class, if $k\equiv 0\ (\textrm{mod}\ 3)$, the $3$-coloring minimizing the number of monochromatic edges of $H$ is as follows:
	\begin{enumerate} 
		\item Color all vertices of the first $\frac{k}{3}$ classes with red.
		\item Color all vertices of the next $\frac{k}{3}$ classes with blue.
		\item Color all vertices of the last $\frac{k}{3}$ classes with green.
	\end{enumerate} If $k\equiv 1 \ (\textrm{mod}\ 3)$, the $3$-coloring minimizing the number of monochromatic edges of $H$ is as follows:
	\begin{enumerate} 
		\item Color all vertices of the first $\left\lfloor\frac{k}{3}\right\rfloor$ classes with red.
		\item Color all vertices of the next $\left\lfloor\frac{k}{3}\right\rfloor$ classes with blue.
		\item Color all vertices of the next $\left\lfloor\frac{k}{3}\right\rfloor$ classes with green.
		\item Color all vertices of the last class such that the number of red, blue and green vertices are as equal as possible.
	\end{enumerate} Moreover, each coloring is unique up to a permutation of colors.
\end{theorem}
We use a similar idea to the proof of Theorem $3$, but we need to develop some new lemmas to construct the canonical forms of the colorings.
 
 The rest of this paper is organized as follows. In Section \ref{sec2}, we introduce some notations and useful properties that will be used throughout the paper. Later, we consider some straightforward cases. Sections \ref{sec:thm:1}, \ref{sec:thm:2} and \ref{sec:thm:3} are devoted to proving Theorems \ref{thm:1}, \ref{thm:2} and \ref{thm:3}, respectively. Finally, we conclude in Section \ref{sec:conclude} with a discussion of some open problems.

\section{Preliminaries}
First, we will introduce some notations that will be used throughout the paper. Later, we will mainly discuss some useful properties of binomial coefficients and some trivial cases of the problem.
\label{sec2}
\subsection{The number of monochromatic edges of a $2$-coloring of balanced complete $k$-partite $r$-uniform hypergraphs}
Let $H$ be a  balanced complete $k$-partite $(r+1)$-uniform hypergraph with $n$ vertices in each class. We consider $(r+1)$-uniform instead of $r$-uniform hypergraph for simple calculation. Let $c$ be a coloring of $H$ with $x_i$ red vertices in the $i^{th}$ class and let $X = x_1+x_2+\cdots +x_k$. Let $M(H,c)$ be the number of monochromatic edges of $H$ with coloring $c$. Then,
\begin{align*}
M(H,c) = \left[ { X \choose r+1}-\sum^{k}_{i=1}{x_i \choose r+1} \right] + \left[ { kn-X \choose r+1}-\sum^{k}_{i=1}{n-x_i \choose r+1} \right].
\end{align*}

This function is the main method to count the number of monochromatic edges. However, this function alone is not enough for comparing the numbers of monochromatic edges of all colorings. Let $\bigtriangleup_iM(H,c)$ be the change in the number of monochromatic edges when a blue vertex in the $i^{th}$ class is recolored (if possible). The change is equal to the difference between the number of monochromatic edges containing the vertex that will be recolored, before and after the recoloring. Then,
\begin{align*}
\bigtriangleup_iM(H,c)= \left[ {X \choose r} - {x_i \choose r}\right] - \left[ {kn-X-1 \choose r} - {n-x_i-1 \choose r}\right].
\end{align*}
We sometimes simply write $\bigtriangleup M(H,c)$ instead of $\bigtriangleup_iM(H,c)$ if the class of the color-changing vertex is clear.


\subsection{The number of monochromatic edges of a $2$-coloring of unbalanced complete tripartite $3$-uniform hypergraphs}
Let $H$ be an unbalanced complete tripartite $3$-uniform hypergraph with the numbers of vertices of the first, second and third classes equal to $n_1 \leqslant n_2 \leqslant n_3$, respectively, and let $N= n_1+n_2+n_3$. Let $c$ be the coloring of $H$ with the number of red vertices of the first, second and third classes equal to $x_1,x_2$ and $x_3$, respectively, and let $X=x_1+x_2+x_3$. Then, \begin{align*}
M(H,c)= \left[ { X \choose 3}-\sum^{3}_{i=1}{x_i \choose 3} \right] + \left[ { N-X \choose 3}-\sum^{3}_{i=1}{n_i-x_i \choose 3} \right],
\end{align*} and
\begin{align*}
\bigtriangleup_iM(H,c)= \left[ {X \choose 2} - {x_i \choose 2}\right] - \left[ {N-X-1 \choose 2} - {n_i-x_i-1 \choose 2}\right].
\end{align*}
\subsection{The number of monochromatic edges of a $3$-coloring of balanced complete $k$-partite $r$-uniform hypergraphs}
Let $H$ be a balanced complete $k$-partite $(r+1)$-uniform hypergraph with $n$ vertices in each class. Let $c$ be the $3$-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. Note that $ R= \sum^{k}_{i=1}{r_i}, B= \sum^{k}_{i=1}{b_i}$ and $ G= \sum^{k}_{i=1}{g_i}$. Moreover, $n= r_i+b_i+g_i$ for each $i = 1,2,\ldots,k$ and $kn = R+B+G$. Then, \begin{align*}
M(H,c)&= \left[ { R \choose r+1}-\sum^{k}_{i=1}{r_i \choose r+1} \right] + \left[ { B \choose r+1}-\sum^{k}_{i=1}{b_i \choose r+1} \right]+ \left[ { G \choose r+1}-\sum^{k}_{i=1}{g_i \choose r+1} \right].
\end{align*}

We write $\bigtriangleup_iM(H,c)$ for the change in the number of monochromatic edges when a blue vertex in the $i^{th}$ class is recolored to red (if possible). Then,
\begin{align*}
\bigtriangleup_iM(H,c) = \left[ {R \choose r} - {r_i \choose r}\right] - \left[ {B-1 \choose r} - {b_i-1 \choose r}\right].
\end{align*} The change can be calculated similarly for any recoloring with other color combinations.

\subsection{Properties of binomial coefficients}
We will additionally introduce some standard tools that will be applied throughout this paper.
\begin{proposition} For any non-negative integers $a,b,c$ and $d$ with $c \leqslant a \leqslant b \leqslant d$, if $a+b\leqslant c+d$, then ${a \choose r} + {b \choose r} \leqslant {c \choose r} + {d \choose r}$ for any positive integer $r$. Moreover, the equality holds if and only if $(a=c$ and $b=d)$ or $d<r$.
\end{proposition} 
Note that the inequality trivially holds when all upper indices of binomial coefficient terms are less than the lower index. This trivial condition will be found occasionally throughout our proofs of the main theorems.

\begin{proposition}
	For any non-negative integers $x_1, x_2 ,\ldots,x_n$ whose sum is constant and for any non-negative integer $r$, $ \sum_{i=1}^n{x_i\choose r}$ is smallest if and only if $x_1, x_2 ,\ldots,x_n$ are as equal as possible or $ max\{x_1,x_2,\ldots,x_n\}<r$ . 
\end{proposition}

\begin{proposition}
	For any non-negative integers $x_1, x_2 ,\ldots,x_n$ whose sum is constant and for any non-negative integer $r$, $ \sum_{i=1}^n{x_i\choose r}$ is largest if and only if all but one $x_i$ are zeros or $\sum_{i=1}^n x_i < r$.
\end{proposition}

Proposition $4$ is the main tool to compare binomial coefficients while Propositions $5$ and $6$ are generalizations of Proposition $4$ which we will apply to prove some trivial cases of the problems in the next subsections.

\subsection{Colorings of hypergraphs with the size of each class fewer than the size of an edge}
In our theorems, we assume that the size of each class must be at least the size of an edge, otherwise, an edge cannot be contained in a class and our hypergraphs are just complete hypergraphs. In this subsection, we will note that the problem is trivial when  $n<r$ and determine a coloring that have the minimum number of monochromatic edges. Let $H$ be a complete $r$-uniform hypergraphs $H$ and let $c$ be a coloring of $H$. Then,
\begin{align*}
M(H,c)={R \choose r} + {B \choose r}
\end{align*} if $c$ is a $2$-coloring with $R$ red and $B$ blue vertices, and
\begin{align*}
M(H,c)={R \choose r} + {B \choose r}+{G \choose r}
\end{align*} if $c$ is a $3$-coloring with $R$ red, $B$ blue and $G$ green vertices.

By Proposition $5$, $M(H,c)$ is smallest if $R$, $B$ (and $G$) are as equal as possible. Hence, a coloring such that the numbers of vertices of each color are as equal as possible has the minimum number of monochromatic edges.

\subsection{Colorings of hypergraphs with the number of classes fewer than or divisible by the number of colors}
In this subsection, we will consider colorings that the number of classes is fewer than or divisible by the number of colors and determine the colorings with the minimum number of monochromatic edges. We consider not only the colorings with $2$ or $3$ colors, but also $m$-colorings with $m$ greater than $3$.

First, we consider the hypergraphs with the number of classes fewer than the number of colors. There are no monochromatic edges of a fixed color only when all vertices of that color are contained in at most one class, or the number of vertices of that color is fewer than $r$. Hence, the colorings such that each color appears in at most one class, or appears on fewer than $r$ vertices, are the only colorings with no monochromatic edges. Such colorings exist when the number of classes is fewer than the number of colors.

The determination of the minimum coloring of the remaining case is straightforward from the Propositions $5$ and $6$.
\begin{proposition}
	Let $n \geqslant r$ and let $k$ be divisible by $m$. The $m$-coloring minimizing the number of monochromatic edges of a balanced complete $k$-partite $r$-uniform hypergraph with $n$ vertices in each class is the coloring with equal numbers of vertices of each color and no polychromatic class.
\end{proposition}
\begin{proof}
	
	Suppose that $ n \geqslant r$. Let $H$ be a balanced complete $k$-partite $r$-uniform hypergraph with $n$ vertices in each class and let $c$ be an $m$-coloring of $H$ such that $k$ is divisible by $m$. Let $x_{li}$ be the number of vertices with the $l^{th}$ color in the $i^{th}$ class and let $X_l$ be the total number of vertices with the $l^{th}$ color. Then,
	\begin{align*}
	M(H,c)&= \sum^{m}_{l=1} \left[ {X_l \choose r} - \sum^{k}_{i=1} {x_{li} \choose r} \right].
	\end{align*} We will show that the coloring $c^*$ with equal numbers of vertices of each color and no polychromatic class is the minimum coloring by directly comparing the numbers of monochromatic edges of $c$ and $c^*$. By Propositions $5$ and $6$,
	\begin{align*}
	M(H,c)&=\sum^{m}_{l=1} \left[ {X_l \choose r} - \sum^{k}_{i=1} {x_{li} \choose r} \right]\\
	&\geqslant m{\frac{1}{m} \sum_{l=1}^m X_l \choose r} - \sum^{k}_{i=1} {\sum^{m}_{l=1} x_{li} \choose r }\\
	&=m {\frac{kn}{m} \choose r} - \sum^{k}_{i=1} {n \choose r}=M(H,c^*).
	\end{align*}
	
	The equality holds only when ($X_i= \frac{kn}{m}$ for each $i$ and each class is monochromatic) or  $n<r$, but the latter is impossible. Hence, $c^*$ is the unique coloring with the minimum number of monochromatic edges.
\end{proof}

The proof in this subsection is a straightforward comparison due to the simplicity of color distribution. However, in other general cases, they are much more complicated.
\section{Proof of Theorem~\ref{thm:1}}
\label{sec:thm:1}


\begin{proof}[Proof of Theorem~\ref{thm:1}] Let $H$ be a  balanced complete $k$-partite $(r+1)$-uniform hypergraph with $n \geqslant r+1$ vertices in each class where $k \geqslant 2$ and $r \geqslant 2$. Let $c$ be a coloring of $H$ with $x_i$ red vertices in the $i^{th}$ class and let $X = x_1+x_2+\cdots+x_k.$ We may assume that $X\leqslant \lfloor \frac{kn}{2} \rfloor$ , otherwise, we relabel the names of the colors. Note that if $k$ is even, the proof is completed by Proposition $7$. However, we will not need to assume that $k$ is odd in the following proof.
	
	We will calculate $M(H,c)$ in a new manner by summing each change when a blue vertex is recolored into red one by one starting from the all blue hypergraph until we reach $c$. Let $c_0$ be the all blue coloring and let $c_j$ be the coloring after the $j^{th}$ change of $H$. Thus, 
	\begin{align*}
	M(H,c) = M(H,c_0) + \sum^{X-1}_{j=0} \bigtriangleup M(H,c_j)={kn \choose r+1}-k{n \choose r+1} +\sum^{X-1}_{j=0} \bigtriangleup M(H,c_j).
	\end{align*}
	
	 We suppose that the vertices in the first class of the all blue hypergraph will be recolored first to match the first class of $c$ and then continue to the next class. Note that $c_j$ has $j$ red vertices. Let the $i^{th}$ class be the class containing the blue vertex that will be recolored and $x$ be the number of red vertices in that class. Then, from Section $2.1$, 
	\begin{align*}
	\bigtriangleup M(H,c_j) &= \left[ {j \choose r} - {x \choose r}\right] - \left[ {kn-j-1 \choose r} - {n-x-1 \choose r}\right]\\
	&= \left[ {j \choose r} - {kn-j-1 \choose r}\right] - \left[ {x \choose r} - {n-x-1 \choose r}\right].
	\end{align*}
	
	Note that while each vertex in the changing class is being recolored, the term $x$ ascends from $0$ to $x_{i}-1$. Thus, \begin{align*}
	M(H,c) &={kn \choose r+1}-k{n \choose r+1} + \sum^{X-1}_{j=0} \bigtriangleup M(H,c_j)\\
	&= {kn \choose r+1}-k{n \choose r+1} + \sum^{X-1}_{j=0}\left[ {j \choose r} - {kn-j-1 \choose r}\right]- \sum^{k}_{i=1}\sum^{x_i-1}_{x=0}\left[ {x \choose r} - {n-x-1 \choose r}\right].
	\end{align*}
	
	In this way, if we consider only the colorings with $X$ red vertices, then the terms \[ {kn \choose r+1}-k{n \choose r+1} + \sum^{X-1}_{j=0}\left[ {j \choose r} - {kn-j-1 \choose r}\right] \] in the function $M(H,c)$ are constant. Only the term
	
	\[\sum^{k}_{i=1}\sum^{x_i-1}_{x=0}\left[ {x \choose r} - {n-x-1 \choose r}\right]\] is distinct and we denote this term by $S(x_1,x_2,\ldots,x_k)$. Hence, the coloring with maximum value of $S(x_1,x_2,\ldots,x_k)$ will have the minimum number of monochromatic edges.
	
	\begin{claim*}
		Among the colorings with a constant total number $X$ of red vertices, the coloring $c^*_X$ with the minimum number of polychromatic classes has the minimum number of monochromatic edges. Moreover, the minimum coloring is unique up to a permutation of classes.
	\end{claim*}
	\begin{proof} Consider a coloring with the number of red vertices in the $i^{th}$ class  equal to $x_i$ where $x_1 +x_2+\cdots+x_k = X$ and $x_1 \geqslant x_2 \geqslant \cdots\geqslant x_k$. Suppose that the coloring is not $c^*_X$. Therefore, there exist classes $l < m$ such that $x_l \neq n$ and $x_m \neq 0$. Next, we will compare the terms \[S(x_1, \ldots,x_l,\ldots,x_m,\ldots,x_k)\] and \[S(x_1, \ldots,x_l+1,\ldots,x_m-1,\ldots,x_k).\]
	which corresponds to swapping a red vertex from the $m^{th}$ class with a blue vertex from the $l^{th}$ class. Thus, since $x_l \geqslant x_m$,
	\begin{align*}S(x_1&, \ldots,x_l+1,\ldots,x_m-1,\ldots,x_k) - S(x_1, \ldots,x_l,\ldots,x_m,\ldots,x_k)\\ 
	&=\sum_{x=0}^{x_l + 1 -1}\left[ {x \choose r} - {n-x-1 \choose r}\right] + \sum_{x=0}^{x_m -1 -1}\left[ {x \choose r} - {n-x-1 \choose r}\right]\\
	&\;\;\;\;-\sum_{x=0}^{x_l-1}\left[ {x \choose r} - {n-x-1 \choose r}\right]-\sum_{x=0}^{x_m-1}\left[ {x \choose r} - {n-x-1 \choose r}\right]\\
	&= \left[{x_l \choose r} -{x_m-1 \choose r} \right] + \left[{n-x_m \choose r}-{n-x_l-1\choose r}\right] \geqslant 0.
	\end{align*}
	
	The equality holds only when all upper indices of the binomial coefficient terms are less than $r$. The swapping resulted in fewer or equal monochromatic edges. We will continue swapping as long as possible to reduce the number of polychromatic classes. The inequality is strict at some point since either $x_l$ will eventually equal to $n-1$ in which case $x_l=n-1 \geqslant r$, or $x_m$ will eventually equal to $1$ in which case $n-x_m=n-1 \geqslant r$. This implies that the original coloring has strictly more monochromatic edges than some coloring. Hence, $c^*_X$ is the unique coloring with the minimum number of monochromatic edges among those with $X$ red vertices.
	\end{proof}
	
	We have determined the minimum coloring for each value of $X$. Next, we will make comparisons between colorings with different values of $X$. We will show that $M(H,c^*_X) > M(H, c^*_{X+1})$ for all $X \leqslant \lfloor\frac{kn}{2}\rfloor -1$. Let $c^*_X$ be the minimum coloring with $X \leqslant \lfloor\frac{kn}{2}\rfloor-1$ red vertices. Suppose that the polychromatic class of $c^*_X$ is the $i^{th}$ class, but if $c^*_X$ has no polychromatic class, suppose the $i^{th}$ class is an all blue class. Observe that
	\begin{align*}
	M(H,c^*_{X+1})-M(H,c^*_X) &=\bigtriangleup_i M(H,c^*_X)\\
	&= \left[ {X \choose r} - {x_i \choose r}\right] - \left[ {kn-X-1 \choose r} - {n-x_i-1 \choose r}\right]\\
	&= \left[ {X \choose r} + {n-x_i-1 \choose r}\right] - \left[ {kn-X-1 \choose r} + {x_i \choose r}\right].
	\end{align*}
	The following proof will be divided into two cases according to the value of $x_i
	$.
	
	\textit{Case 1}: $\frac{n}{2} \leqslant x_i < n $.
	
	Thus, \begin{align*} X- (kn-X-1)=2\left(X+\frac{1}{2} -\frac{kn}{2}\right) \leqslant 2\left(\left\lfloor\frac{kn}{2}\right\rfloor-\frac{kn}{2}-\frac{1}{2}\right)< 0,
	\end{align*}and 
	\begin{align*}(n-x_i-1)-x_i = 2\left(\frac{n}{2}-x_i-\frac{1}{2}\right)< 0.
	\end{align*}
	Hence, $\bigtriangleup_i M(H,c^*_X) \leqslant 0$ but $\bigtriangleup_i M(H,c^*_X) \neq 0$ since one of the upper indices is at least $r$. Indeed, $kn-X-1 \geqslant \left\lceil\frac{kn}{2}\right\rceil \geqslant n > r$ because $k \geqslant 2$.
		
	\textit{Case 2}: $0 \leqslant x_i < \frac{n}{2}$.
	
	We will show that $\bigtriangleup_i M(H,c^*_X) < 0$ by Proposition 4. As in Case 1,  \[X- (kn-X-1)<0.\]
	Moreover, \begin{align*}(n-x_i-1)-x_i = 2\left(\frac{n}{2}-x_i-\frac{1}{2}\right)\geqslant 0.
	\end{align*} Suppose that there are $k^*$ red classes in $c^*_X$, i.e., $X = k^*n + x_i$. Since $X\leqslant \lfloor\frac{kn}{2}\rfloor-1$, we have $k^* \leqslant \frac{k-1}{2}$. Thus, \begin{align*}
	(X +n-x_i-1)-(x_i+kn-X-1)=2\left(k^*n - \frac{k-1}{2}n\right)\leqslant 0.
	\end{align*}\noindent Similarly, $kn-X-1>r$. Hence, by Proposition 4, $\bigtriangleup_i M(H,c^*_X) < 0.$
	
	By the two cases, $c^*_X$ contains strictly more monochromatic edges than $c^*_{X+1}$ does, given that $X \leqslant \lfloor\frac{kn}{2}\rfloor -1$. Consequently, we can conclude that the unique coloring with the minimum number of monochromatic edges among all minimum colorings $c^*_X$ is $c^*_{\lfloor\frac{kn}{2}\rfloor}$.
	
	Together with the claim, $c^*_{\lfloor\frac{kn}{2}\rfloor}$ is the unique coloring with the minimum number of monochromatic edges.\end{proof}

Note that, in the claim, we determine $c^*_X$ by means of determining the coloring with maximum $S(x_1,x_2,\ldots,x_k)$. On the contrary, we could determine the coloring with a constant number $X$ of red vertices that has the maximum number of monochromatic edges by showing conversely that the coloring with minimum $S(x_1,x_2,\ldots,x_k)$ is the coloring such that $x_1$, $x_2, \ldots, x_k$ are as equal as possible. However, this is out of our topic.
\section{Proof of Theorem~\ref{thm:2}}
\label{sec:thm:2}
 \begin{proof}[Proof of Theorem~\ref{thm:2}]
	Let $H$ be an unbalanced complete tripartite $3$-uniform hypergraph with the numbers of vertices of the first, second and third classes $ n_1 \leqslant n_2 \leqslant n_3$ and let $N=n_1+n_2+n_3$. Let $c$ be the coloring of $H$ with the number of red vertices of the first, second and third classes equal to $x_1,x_2$ and $x_3$, respectively, and let $X=x_1+x_2+x_3$.
	
	We divide the proof into two subsections according to the size of the smallest class. In the first subsection, a similar idea as in the proof of Theorem~\ref{thm:1} is extended to determine the minimum coloring when the number of vertices of each class is at least $3$. The second subsection is mainly about hypergraphs with some small classes.
	\subsection{Hypergraphs with $n_1 \geqslant 3$}
	Assume that $n_1 \geqslant 3$. Let $\bigtriangleup_{i{i'}} M(H,c)$ be the change in the number of monochromatic edges if a blue vertex in the $i^{th}$ class is recolored into red and a red vertex in the ${i'}^{th}$ class is recolored into blue. The process will be called \textit{swapping} which results in a new coloring, say $c'$. We compute $\bigtriangleup_{i{i'}} M(H,c)$ by comparing the number of monochromatic edges containing those vertices undergone swapping before and after swapping process. Thus,
	\begin{align*}
	\bigtriangleup_{i{i'}}M(H,c)&= \left[ {x_1+x_2+x_3-1 \choose 2}-{x_i \choose 2} + {N-x_1-x_2-x_3-1 \choose 2} - {n_{i'}-x_{i'}\choose 2} \right]\\
	&\;\;\;\;- \left[ {x_1+x_2+x_3-1 \choose 2}-{x_{i'}-1 \choose 2} + {N-x_1-x_2-x_3-1 \choose 2} - {n_i-x_i-1\choose 2} \right]\\
	&= \left[ {x_{i'}-1 \choose 2} + {n_i-x_i-1\choose 2} \right] - \left[ {x_i \choose 2} +  {n_{i'}-x_{i'}\choose 2} \right].
	\end{align*} A \textit{successful swapping} is a swapping in such a way that the number of monochromatic edges is reduced, i.e., $\bigtriangleup_{i{i'}} M(H,c) < 0$.
	\begin{lemma}
		If $\bigtriangleup_{i{i'}} M(H,c) \leqslant 0$, then $\bigtriangleup_{i{i'}} M(H,c') < 0$.
	\end{lemma}\begin{proof}
	 Observe that
\begin{align*}
	\bigtriangleup_{i{i'}}M(H,c')&= \left[ {(x_{i'}-1)-1 \choose 2} + {n_i-(x_i+1)-1\choose 2} \right] - \left[ {x_i+1 \choose 2} +  {n_{i'}-(x_{i'}-1)\choose 2} \right]\\
	&\leqslant \left[ {x_{i'}-1 \choose 2} + {n_i-x_i-1\choose 2} \right] - \left[ {x_i \choose 2} +  {n_{i'}-x_{i'}\choose 2} \right]=\bigtriangleup_{i{i'}} M(H,c) \leqslant 0.
	\end{align*}
	The equality holds only when ($x_{i'}-1<2$ and $n_i-x_i-1<2$) and ($x_i+1<2$ and $n_{i'}-x_{i'}+1<2$) and $\bigtriangleup_{i{i'}} M(H,c)=0$. Suppose that $\bigtriangleup_{i{i'}}M(H,c')=0$. We have that $x_i=0$ and $x_{i'}<3$. Thus, $n_i=n_i-x_i<3$ and $n_{i'}-2 \leqslant n_{i'} -x_{i'}<1 $, i.e., $n_{i'}<3$ which contradicts with $3 \leqslant n_1\leqslant n_2\leqslant n_3$. 
\end{proof}


Lemma 8 means that if a swapping can be done without increasing the number of monochromatic edges, another swapping in the same direction will be successful (if there are red and blue vertices to be swapped). The process of successful swappings will terminate when one of the two classes (or both) is monochromatic.
\begin{lemma}
	If $\bigtriangleup_{i{i'}} M(H,c) \geqslant 0$, then $\bigtriangleup_{{i'}i} M(H,c) < 0$.
\end{lemma}
\begin{proof}Observe that
	\begin{align*}
	\bigtriangleup_{{i'}i} M(H,c) &= \left[ {x_i-1 \choose 2} + {n_{i'}-x_{i'}-1\choose 2} \right] - \left[ {x_{i'} \choose 2} +  {n_i-x_i\choose 2} \right]\\
	&\leqslant \left[ {x_i \choose 2} + {n_{i'}-x_{i'}\choose 2} \right] - \left[ {x_{i'}-1 \choose 2} +  {n_i-x_i-1\choose 2} \right]\\
	&= -\bigtriangleup_{i{i'}} M(H,c) \leqslant 0.
	\end{align*}
	The equality holds only when ($x_i<2$ and $n_{i'}-x_{i'}<2$) and ($x_{i'}<2$ and $n_i-x_i<2$) and $\bigtriangleup_{i{i'}} M(H,c)=0$. Suppose that $\bigtriangleup_{{i'}i}M(H,c)=0$. We have that $x_i \leqslant 1$ and $x_{i'}\leqslant 1$. Thus, $n_i-1\leqslant =n_i-x_i<2$ and $n_{i'}-1\leqslant n_{i'} -x_{i'}<2 $, i.e., $n_i<3$ and $n_{i'}<3$ which contradicts with $3 \leqslant n_1\leqslant n_2\leqslant n_3$.
\end{proof}

Note that, for any coloring $c$, if $c$ contains two classes, the $i^{th}$ and ${i'}^{th}$, which are polychromatic, then a swapping can be done in two directions as follows.
\begin{enumerate}\item Swapping a red vertex of the $i^{th}$ class with a blue vertex of the ${i'}^{th}$ class.
	\item Swapping a blue vertex of the $i^{th}$ class with a red vertex of the ${i'}^{th}$ class.
\end{enumerate}
By Lemma 9, one of the two directions is successful. Moreover, by Lemma 8, we can continue swapping in the same direction until one of the two classes is monochromatic and get fewer monochromatic edges. Hence, the coloring with minimum number of monochromatic edges among colorings with constant number of red vertices, must have at most one polychromatic class. We will list all these forms in the following table which will be the candidates for the coloring with minimum number of monochromatic edges.
	\begin{center}
		\begin{tabular}{ |P{3cm}|P{3cm}|P{3cm}|P{3cm}|}
			\hline
			Canonical forms & $1^{st}$ Class  & $2^{nd}$ Class & $3^{rd}$ Class\\
			\hline
			$F_1$& polychromatic& blue&blue\\
			$F_2$& blue& polychromatic&blue\\
			$F_3$& blue& blue&polychromatic\\
			$F_4$& red&polychromatic&blue\\
			$F_5$& red&blue&polychromatic\\
			$F_6$& polychromatic&red&blue\\
			$F_7$& blue&red&polychromatic\\
			$F_8$& polychromatic&blue &red\\
			$F_9$& blue& polychromatic&red\\
			$F_{10}$& red& red&polychromatic\\
			$F_{11}$& red& polychromatic&red\\
			$F_{12}$& polychromatic& red&red\\
			\hline
		\end{tabular}
	\end{center}
	
	
	The first column illustrates the list of $12$ canonical forms and the remaining columns describe the colors of vertices in those classes. The terms \textit{red} and \textit{blue} mean all vertices in those classes are monochromatic of red and blue, respectively. On the other hand, \textit{polychromatic} means that this class is allowed to be polychromatic but it may be monochromatic. Note that a coloring can be considered to be in several canonical forms, for example, the all blue coloring is of the form $F_1$, $F_2$ or $F_3$.
	

	






	
	We may assume that $X \leqslant\lfloor\frac{N}{2}\rfloor$. Consequently, both $F_{11}$ and $F_{12}$ are out of our interest since the total numbers of red vertices, which are $n_1+x_2+n_3$ and $x_1+n_2+n_3$, respectively, exceed $\lfloor\frac{N}{2}\rfloor$ as shown:
	\begin{align*}
	n_1+x_2+n_3 = \frac{n_1+n_3+2x_2}{2}+\frac{n_1+n_3}{2} > \frac{n_2}{2} +\frac{n_1+n_3}{2} \geqslant  \left\lfloor\frac{n_1+n_2+n_3}{2}\right\rfloor
	\end{align*} and \begin{align*}
	x_1+n_2+n_3 = \frac{n_2+n_3+2x_1}{2}+\frac{n_2+n_3}{2} > \frac{n_1}{2} +\frac{n_2+n_3}{2} \geqslant  \left\lfloor\frac{n_1+n_2+n_3}{2}\right\rfloor.
	\end{align*}
	
	Next, we will focus on the possibility of $F_{10}$. If $c$ has total red vertices to be $X=n_1+n_2+x_3 \leqslant \lfloor\frac{n_1+n_2+n_3}{2}\rfloor $. Then, \begin{align*}
	n_1 + n_2 \leqslant 2\left(\left\lfloor\frac{n_1+n_2+n_3}{2}\right\rfloor-\frac{n_1+n_2}{2}\right)\leqslant 2\left(\frac{n_1+n_2+n_3}{2}-\frac{n_1+n_2}{2}\right)=n_3.
	\end{align*}
	
	The necessary condition of a coloring $c$ of a hypergraph $H$ to be in the form $F_{10}$ is that $n_1+n_2 \leqslant n_3$. Note that the condition $n_1+n_2 \leqslant n_3 $ is equivalent to $n_1+n_2 \leqslant \lfloor\frac{n_1+n_2+n_3}{2}\rfloor \leqslant n_3$ and we call a hypergraph with this condition \textit{type A}. On the other hand, the condition $n_1+n_2 > n_3 $ is equivalent to $n_3\leqslant \lfloor\frac{n_1+n_2+n_3}{2}\rfloor < n_1+n_2$ and we call a hypergraph with this condition \textit{type B}. Next, we will determine the minimum coloring among those colorings with constant number $X$ of red vertices or $c^*_X$ from the candidates $F_1$ to $F_9$ and $F_{10}$ will be considered only when $H$ is a type A hypergraph.
	
	As in the proof of Theorem~\ref{thm:1}, we calculate $M(H,c)$ by summing each change when a blue vertex is recolored into red one by one starting from the all blue hypergraph until we reach $c$. Let $c_0$ be the all blue coloring and let $c_j$ be the coloring after the $j^{th}$ change of $H$. Thus,
	\begin{align*}
	M(H,c) = M(H,c_0) + \sum^{X-1}_{j=0} \bigtriangleup M(H,c_j)= {N \choose 3}-\sum_{i=1}^3{n_i \choose 3}+\sum^{X-1}_{j=0} \bigtriangleup M(H,c_j).
	\end{align*}
	
	 We suppose that the vertices in the first class of the all blue hypergraph will be recolored first to match the first class of $c$ and then continue to the next class. Note that $c_j$ has $j$ red vertices. Let the $i^{th}$ class be the class containing the blue vertex that will be recolored and $x$ be the number of red vertices in that class. Then, from Section $2.2$, 
	 \begin{align*}
	 \bigtriangleup M(H,c_j) &= \left[ {j \choose 2} - {x \choose 2}\right] - \left[ {N-j-1 \choose r} - {n_i-x-1 \choose 2}\right]\\
	 &= \left[ {j \choose 2} - {N-j-1 \choose 2}\right] - \left[ {x \choose 2} - {n_i-x-1 \choose 2}\right].
	 \end{align*}
	 
	 Note that while each vertex in the changing class is being recolored, the term $x$ ascends from $0$ to $x_i-1$. Thus,
	 \begin{align*}
	 M(H,c) &= {N \choose 3}-\sum_{i=1}^3{n_i \choose 3}+\sum^{X-1}_{j=0} \bigtriangleup M(H,c_j)\\
	 &={N \choose 3}-\sum_{i=1}^3{n_i \choose 3}+\sum^{X-1}_{j=0}\left[ {j \choose 2} - {N-j-1 \choose 2}\right]- \sum^{3}_{i=1}\sum^{x_i-1}_{x=0}\left[ {x \choose 2} - {n_i-x-1 \choose 2}\right].
	 \end{align*}
	 
	 Similarly, if we consider only the coloring with $X$ red vertices, then the terms
	 \[{N \choose 3}-\sum_{i=1}^3{n_i \choose 3}+\sum^{X-1}_{j=0}\left[ {j \choose 2} - {N-j-1 \choose 2}\right]\] in the function $M(H,c)$ are constant. Only the term
	 \[\sum^{3}_{i=1}\sum^{x_i-1}_{x=0}\left[ {x \choose 2} - {n_i-x-1 \choose 2}\right]\] is distinct and we denote this term by $S(x_1,x_2,x_3)$. Hence, the coloring with maximum value of $S(x_1,x_2,x_3)$ will have the minimum number of monochromatic edges. Remark that if $x_i = n_i$, then the term $\sum^{x_i-1}_{x=0}\left[ {x \choose 2} - {n_i-x-1 \choose 2} \right]$ cancels itself out. Hence, $S(n_1,x_2,x_3)=S(0,x_2,x_3)$ and similarly when $x_2=n_2$ or $x_3=n_3$.
	 
	 Next, we will determine $c^*_X$ by considering and comparing only among possible canonical forms according to the value $X$ and type of $H$. We will divide into several cases.
	 
	 
	 \textit{Case 1}: $0 \leqslant X < n_1$.
	 \begin{center}
	 	\begin{tabular}{ |P{3cm}|P{1.5cm}|P{1.5cm}|P{1.5cm}|P{3cm}|  }
	 		\hline
	 		Possible forms & $x_1$  & $x_2$ & $x_3$ & $S(x_1,x_2,x_3)$\\
	 		\hline
	 		$F_1$& $X$& $0$&$0$&$S(X,0,0)$\\
	 		$F_2$& $0$& $X$&$0$&$S(0,X,0)$\\
	 		$F_3$& $0$& $0$&$X$&$S(0,0,X)$\\
	 		\hline
	 	\end{tabular}
	 \end{center}
	 
	 \noindent 
	 We will compare among colorings in the forms $F_1$, $F_2$ and $F_3$. Note that if $n_1=n_2$, $F_1$ and $F_2$ are the same. Similarly, if $n_1=n_2=n_3$, $F_1,F_2$ and $F_3$ are the same. Then,
	 \begin{align*}
	 S(0,X,0) = \sum_{j=0}^{X-1}\left[ {j \choose 2}-{n_2-j-1\choose 2} \right]\leqslant \sum_{j=0}^{X-1}\left[ {j \choose 2}-{n_1-j-1\choose 2} \right] = S(X,0,0).
	 \end{align*}
	 
	 \noindent The equality holds only when $n_1=n_2$ or $n_2-1<2$. Since $3 \leqslant n_2 \leqslant n_3$, we can conclude that a coloring in the form $F_1$ has fewer monochromatic edges than $F_2$ and similarly for $F_3$. Hence, $c^*_X$ is in the form $F_1$.
	 
	 \textit{Case 2}: $n_1 \leqslant X < \frac{n_1 + n_2}{2}$.
	 \begin{center}
	 	\begin{tabular}{ |P{3cm}|P{1.5cm}|P{1.5cm}|P{1.5cm}|P{3cm}|  }
	 		\hline
	 		Possible forms & $x_1$  & $x_2$ & $x_3$&$S(x_1,x_2,x_3)$\\
	 		\hline		
	 		$F_2$& $0$& $X$&$0$&$S(0,X,0)$\\
	 		$F_3$& $0$& $0$&$X$&$S(0,0,X)$\\
	 		$F_4$& $n_1$& $X-n_1$&$0$&$S(n_1,X-n_1,0)$\\
	 		$F_5$& $n_1$& $0$&$X-n_1$&$S(n_1,0,X-n_1)$\\
	 		\hline
	 	\end{tabular}
	 \end{center}
	 In this case, we must have that $n_1 < n_2$. Similarly to \textit{Case 1}, we have that $F_2$ has fewer number monochromatic edges than $F_3$. Next, we will compare between colorings in the forms $F_4$ and $F_5$. If $n_2=n_3$, then both forms are the same. Thus,
	 \begin{align*}
	 S(n_1,0,X-n_1) =S(0,0,X-n_1)\leqslant S(0,X-n_1,0)=S(n_1,X-n_1,0).
	 \end{align*}
	 The equality holds only when $n_2=n_3$ or $n_3-1<2$. Since $3\leqslant n_3$, we have that $F_4$ has fewer number monochromatic edges than $F_5$. Finally, we will compare between colorings in the forms $F_2$ and $F_4$. Note that $X-n_1 < \frac{n_1 + n_2}{2} - n_1 = n_2 - \frac{n_1 + n_2}{2} < n_2 -X $. Then, \begin{align*}
	 S(0,X,0)&=\sum_{j=0}^{X-1}\left[ {j \choose 2}-{n_2-j-1\choose 2} \right]\\
	 &=\sum_{j=0}^{(X-n_1)-1}\left[ {j \choose 2}-{n_2-j-1\choose 2} \right]+\left[{X-n_1 \choose 2} +{X-n_1 +1 \choose 2} +\cdots+ {X-1 \choose 2} \right]\\
	 &\;\;\;\;- \left[{n_2-X\choose2}+{n_2-X+1\choose2}+\cdots+{n_1+n_2-X-1\choose2}\right]\\
	 &\leqslant \sum_{j=0}^{(X-n_1)-1}\left[ {j \choose 2}-{n_2-j-1\choose 2} \right] = S(0,X-n_1,0) = S(n_1, X-n_1,0).
	 \end{align*}
	 The equality holds only when $n_1+n_2-X-1 <2$. Since $X< \frac{n_1 + n_2}{2}$, this occurs only when $n_1+n_2 \leqslant 3$, i.e., $n_1 \leqslant n_2 <3$. Since $3 \leqslant n_2$, we have that $F_4$ gives fewer number monochromatic edges than $F_2$ and $c^*_X$ is in the form $F_4$.
	 
	 \textit{Case 3}: $\frac{n_1 + n_2}{2} \leqslant X < n_2$.
	 \begin{center}
	 	\begin{tabular}{ |P{3cm}|P{1.5cm}|P{1.5cm}|P{1.5cm}|P{3cm}|  }
	 		\hline
	 		Possible forms & $x_1$  & $x_2$ & $x_3$&$S(x_1,x_2,x_3)$\\
	 		\hline		
	 		$F_2$& $0$& $X$&$0$&$S(0,X,0)$\\
	 		$F_3$& $0$& $0$&$X$&$S(0,0,X)$\\
	 		$F_4$& $n_1$& $X-n_1$&$0$&$S(n_1,X-n_1,0)$\\
	 		$F_5$& $n_1$& $0$&$X-n_1$&$S(n_1,0,X-n_1)$\\
	 		\hline
	 	\end{tabular}
	 \end{center}
	 Similarly, we must have $n_1 < n_2$ in this case. The comparisons between $F_2$ and $F_3$ and between $F_4$ and $F_5$ are similar to the previous case. Note that $X-n_1 \geqslant \frac{n_1 + n_2}{2} - n_1 = n_2 - \frac{n_1 + n_2}{2} \geqslant n_2 -X $. Next, we will show the comparison between $F_2$ and $F_4$ which gives a contrary result as shown:\begin{align*}
	 S(0,X,0)&=\sum_{j=0}^{X-1}\left[ {j \choose 2}-{n_2-j-1\choose 2} \right]\\
	 &=\sum_{j=0}^{(X-n_1)-1}\left[ {j \choose 2}-{n_2-j-1\choose 2} \right]+\left[{X-n_1 \choose 2} +{X-n_1 +1 \choose 2} +\cdots+ {X-1 \choose 2} \right]\\
	 &\;\;\;\;- \left[{n_2-X\choose2}+{n_2-X+1\choose2}+\cdots+{n_1+n_2-X-1\choose2}\right]\\
	 &\geqslant \sum_{j=0}^{(X-n_1)-1}\left[ {j \choose 2}-{n_2-j-1\choose 2} \right] = S(0,X-n_1,0) = S(n_1, X-n_1,0).
	 \end{align*}
	 The equality holds only when $X=\frac{n_1+n_2}{2}$ or $X-1<2$. Since $\frac{n_1 + n_2}{2} \leqslant X < n_2$ and $n_1<n_2$, the condition that $X<3$ occurs only when $n_1=1$ and $n_2=2$ or $3$. Since $3 \leqslant n_1$, we have that $F_2$ gives fewer number monochromatic edges than $F_4$ and $c^*_X$ is in the form $F_2$ when $X>\frac{n_1+n_2}{2}$. If $X=\frac{n_1+n_2}{2}$, both forms give the same number of monochromatic edges.
	 
	 From now on, the cases will be divided by whether the hypergraph is of type A or B.
	 
	 \textit{Case 4A}: $n_2 \leqslant X < n_1+n_2$ and $H$ is a type A hypergraph.
	 \begin{center}
	 	\begin{tabular}{ |P{3cm}|P{1.5cm}|P{1.5cm}|P{1.5cm}|P{3cm}|  }
	 		\hline
	 		Possible forms & $x_1$  & $x_2$ & $x_3$&$S(x_1,x_2,x_3)$\\
	 		\hline		
	 		$F_3$& $0$& $0$&$X$&$S(0,0,X)$\\
	 		$F_4$& $n_1$& $X-n_1$&$0$&$S(n_1,X-n_1,0)$\\
	 		$F_5$& $n_1$& $0$&$X-n_1$&$S(n_1,0,X-n_1)$\\
	 		$F_6$& $X-n_2$& $n_2$&$0$&$S(X-n_2,n_2,0)$\\
	 		$F_7$& $0$& $n_2$&$X-n_2$&$S(0,n_2,X-n_2)$\\
	 		\hline
	 	\end{tabular}
	 \end{center}
	 Similarly to \textit{Case 2}, we have that $F_4$ has fewer number monochromatic edges than $F_5$. Next, we will compare between colorings in the forms $F_6$ and $F_7$. If $n_1=n_2=n_3$, then the forms $F_4, F_5, F_6$ and $F_7$ are the same. Thus,
	 \begin{align*}
	 S(0,n_2,X-n_2) =S(0,0,X-n_2) \leqslant S(X-n_2,0,0)=S(X-n_2,n_2,0).
	 \end{align*}
	 The equality holds only when $n_1=n_3$ or $n_3-1<2$. Since $n_3 \geqslant 3$, we have that $F_6$ has fewer number monochromatic edges than $F_7$. Next, we will compare between colorings in the forms $F_4$ and $F_6$. If $n_1=n_2$, then both forms are the same. Suppose that $n_1<n_2$. Thus, since $X< n_1+n_2$,
	 \begin{align*}
	 S(n_1, X-n_1,0) &= S(0,X-n_1,0
	 \\&= \left[{0 \choose 2} + {1 \choose 2} +\cdots+{X-n_2-1 \choose 2}\right]\\
	 &\;\;\;\;- \left[{n_1+n_2-X \choose 2} + {n_1+n_2-X+1 \choose 2} + \cdots + {n_1 -1 \choose 2}\right]\\
	 &\;\;\;\;+ \left[{X-n_2 \choose 2} + {X-n_2+1 \choose 2} +\cdots+{X-n_1-1 \choose 2}\right]\\
	 &\;\;\;\;- \left[{n_1\choose 2} + {n_1+1 \choose 2} + \cdots + {n_2-1 \choose 2}\right]\\
	 &\leqslant \left[{0 \choose 2} + {1 \choose 2} +\cdots+{X-n_2-1 \choose 2}\right]\\
	 &\;\;\;\;- \left[{n_1+n_2-X \choose 2} + {n_1+n_2-X+1 \choose 2} + \cdots + {n_1 -1 \choose 2}\right]\\
	 &= S(X-n_2,0,0) = S(X-n_2,n_2,0).
	 \end{align*}
	 The equality holds only when $n_2-1<2$. Since $ n_2\geqslant 3$, we have that $F_6$ has fewer number monochromatic edges than $F_4$. Finally, we will compare between colorings in the forms $F_3$ and $F_6$. Then, since $n_2 \leqslant X < n_1+n_2 \leqslant n_3$, \allowdisplaybreaks
	 
	 \begin{align*}
	 S(0,0,X) &=\left[{0 \choose 2} + {1 \choose 2} +\cdots+{X-1 \choose 2}\right]- \left[{n_3-X \choose 2} + {n_3-X+1 \choose 2} + \cdots + {n_3 -1 \choose 2}\right]\\
	 &\leqslant\left[{0 \choose 2} + {1 \choose 2} +\cdots+{X-1 \choose 2}\right]- \left[{n_3-X \choose 2} + {n_3-X+1 \choose 2} + \cdots + {n_3 -1 \choose 2}\right]\\
	 &\;\;\;\;- \left[{X-n_2 \choose 2} + {X-n_2+1 \choose 2} +\cdots+{X-1 \choose 2}\right]\\
	 &\;\;\;\;+ \left[{n_3-n_2\choose 2} + {n_3+n_2+1 \choose 2} + \cdots + {n_3-1 \choose 2}\right]\\
	 &\;\;\;\;- \left[{n_1+n_2-X \choose 2} + {n_1+n_2-X+1 \choose 2} +\cdots+{n_3-X-1 \choose 2}\right]\\
	 &\;\;\;\;+ \left[{n_1\choose 2} + {n_1+1 \choose 2} + \cdots + {n_3-n_2-1 \choose 2}\right]\\
	 &= \left[{0 \choose 2} + {1 \choose 2} +\cdots+{X-n_2-1 \choose 2}\right]\\ 
	 &\;\;\;\;- \left[{n_1+n_2-X \choose 2} + {n_1+n_2-X+1 \choose 2} + \cdots + {n_1 -1 \choose 2}\right]\\
	 &= \sum_{j=0}^{(X-n_2)-1}\left[ {j \choose 2}-{n_1-j-1\choose 2} \right]= S(X-n_2,0,0) = S(X-n_2,n_2,0).
	 \end{align*}
	 The equality holds only when $n_3-1<2$. Since $n_3 \geqslant 3$,  $F_6$ gives fewer number monochromatic edges than $F_3$ and $c^*_X$ is in the form $F_6$.
	 
	 \textit{Case 5A}: $n_1+n_2 \leqslant X \leqslant \lfloor{\frac{N}{2}}\rfloor$ and $H$ is a type A hypergraph.
	 \begin{center}
	 	\begin{tabular}{ |P{3cm}|P{1.5cm}|P{1.5cm}|P{2cm}|P{4cm}|  }
	 		\hline
	 		Possible forms & $x_1$  & $x_2$ & $x_3$&$S(x_1,x_2,x_3)$\\
	 		\hline		
	 		$F_3$& $0$& $0$&$X$&$S(0,0,X)$\\
	 		$F_{10}$& $n_1$& $n_2$&$X-n_1-n_2$&$S(n_1,n_2,X-n_1-n_2)$\\
	 		\hline
	 	\end{tabular}
	 \end{center}
	 Note that this is only the case that we will consider $F_{10}$. We only compare  between colorings in the forms $F_3$ and $F_{10}$. Then, since $X \leqslant \lfloor{\frac{n_1+n_2+n_3}{2}}\rfloor$,
	 \begin{align*}
	 S(0,0,X)&= \left[{0 \choose 2} + {1 \choose 2} +\cdots+{X-1 \choose 2}\right]- \left[{n_3-X \choose 2} + {n_3-X+1 \choose 2} +\cdots+{n_3-1 \choose 2}\right]\\
	 &= \left[{0 \choose 2} + {1 \choose 2} +\cdots+{X-n_1-n_2-1 \choose 2}\right]\\
	 &\;\;\;\;- \left[{n_1+n_2+n_3-X \choose 2} + {n_1+n_2+n_3-X+1 \choose 2} + \cdots + {n_3 -1 \choose 2}\right]\\
	 &\;\;\;\;+ \left[{X-n_1-n_2\choose2}+{X-n_1-n_2+1\choose2}+\cdots+{X-1\choose2}\right]\\
	 &\;\;\;\;-\left[{n_3-X\choose2}+{n_3-X+1\choose2}+\cdots+{n_1+n_2+n_3-X-1\choose2}\right]\\
	 &\leqslant \left[{0 \choose 2} + {1 \choose 2} +\cdots+{X-n_1-n_2-1 \choose 2}\right]\\ 
	 &\;\;\;\;- \left[{n_1+n_2+n_3-X \choose 2} + {n_1+n_2+n_3-X+1 \choose 2} + \cdots + {n_3 -1 \choose 2}\right]\\
	 &= S(0,0,X-n_1-n_2) = S(n_1,n_2,X-n_1-n_2).
	 \end{align*}
	 The equality holds only when $X=\frac{N}{2}$ or $N-X-1<2$. Since $X \leqslant \lfloor{\frac{N}{2}}\rfloor$, the condition that $N-X<3$ occurs only when $N \leqslant 4$. This is impossible because $n_3 \geqslant 3$. If $X= \frac{N}{2}$, then both forms have the same number of monochromatic edges. However, if we relabel the names of the colors, then both forms are the same. Hence, $F_{10}$ gives fewer number monochromatic edges than $F_3$ and $c^*_X$ is in the form $F_{10}$. Next, we will focus on the other cases of type B hypergraphs.
	 
	 \textit{Case 4B}: $n_2 \leqslant X < n_3$ and $H$ is a type B hypergraph.
	 \begin{center}
	 	\begin{tabular}{ |P{3cm}|P{1.5cm}|P{1.5cm}|P{1.5cm}|P{3cm}|  }
	 		\hline
	 		Possible canonical forms & $x_1$  & $x_2$ & $x_3$&$S(x_1,x_2,x_3)$\\
	 		\hline		
	 		$F_3$& $0$& $0$&$X$&$S(0,0,X)$\\
	 		$F_4$& $n_1$& $X-n_1$&$0$&$S(n_1,X-n_1,0)$\\
	 		$F_5$& $n_1$& $0$&$X-n_1$&$S(n_1,0,X-n_1)$\\
	 		$F_6$& $X-n_2$& $n_2$&$0$&$S(X-n_2,n_2,0)$\\
	 		$F_7$& $0$& $n_2$&$X-n_2$&$S(0,n_2,X-n_2)$\\
	 		\hline
	 	\end{tabular}
	 \end{center}
	 Similarly to \textit{Case 4A}, $F_4$ and $F_6$ have fewer monochromatic edges than $F_5$ and $F_7$, respectively, and $F_6$ has fewer monochromatic edges than $F_4$. Next, we have to compare between $F_3$ and $F_6$ to determine that which form $c^*_X$ is. Due to complexity of the comparison, we will conclude that $c^*_X$ is in the form $F_3$ or $F_6$.
	 
	 \textit{Case 5B}: $n_3 \leqslant X \leqslant \lfloor{\frac{n_1+n_2+n_3}{2}}\rfloor $ and $H$ is a type B hypergraph.
	 \begin{center}
	 	\begin{tabular}{ |P{3cm}|P{1.5cm}|P{1.5cm}|P{1.5cm}|P{3cm}|  }
	 		\hline
	 		Possible canonical forms & $x_1$  & $x_2$ & $x_3$&$S(x_1,x_2,x_3)$\\
	 		\hline		
	 		$F_4$& $n_1$& $X-n_1$&$0$&$S(n_1,X-n_1,0)$\\
	 		$F_5$& $n_1$& $0$&$X-n_1$&$S(n_1,0,X-n_1)$\\
	 		$F_6$& $X-n_2$& $n_2$&$0$&$S(X-n_2,n_2,0)$\\
	 		$F_7$& $0$& $n_2$&$X-n_2$&$S(0,n_2,X-n_2)$\\
	 		$F_8$& $X-n_3$& $0$&$n_3$&$S(X-n_3,0,n_3)$\\
	 		$F_9$& $0$& $X-n_3$&$n_3$&$S(0,X-n_3,n_3)$\\
	 		\hline
	 	\end{tabular}
	 \end{center}
	 Similarly to \textit{Case 4A}, $F_4$ and $F_6$ have fewer monochromatic edges than $F_5$ and $F_7$, respectively, and $F_6$ has fewer monochromatic edges than $F_4$. Next, we will compare between colorings in the forms $F_8$ and $F_9$. If $n_1=n_2$, then both forms are the same. Thus, \begin{align*} S(0,X-n_3,n_3) =S(0,X-n_3,0)=S(X-n_3,0,0)==S(X-n_3, 0,n_3).
	 \end{align*}
	 The equality holds only when $n_1=n_2$ or $n_2-1 <2$. Since $3 \leqslant n_2$, we have that $F_8$ gives fewer number monochromatic edges than $F_9$. Finally, we will compare between colorings in the forms $F_6$ and $F_8$. If $n_2=n_3$, then both forms are the same. We may suppose that $n_2<n_3$. Thus, since $X \leqslant \lfloor{\frac{N}{2}}\rfloor $, 
	 
	 \begin{align*}
	 S(X-n_2, n_2,0)&= S(X-n_2,0,0)\\
	 &= \left[{0 \choose 2} + {1 \choose 2} +\cdots+{X-n_3-1 \choose 2}\right]\\
	 &\;\;\;\;+ \left[{X-n_3 \choose 2} + {X-n_3+1 \choose 2} +\cdots+{X-n_2-1 \choose 2}\right]\\
	 &\;\;\;\;- \left[{n_1+n_2 -X\choose 2} + {n_1+n_2-X+1 \choose 2} + \cdots + 
	{n_1+n_3-X-1 \choose 2}\right]\\
	&\;\;\;\;- \left[{n_1+n_3-X \choose 2} + {n_1+n_3-X+1 \choose 2} + \cdots + {n_1 -1 \choose 2}\right]\\
	 &\leqslant \left[{0 \choose 2} + {1 \choose 2} +\cdots+{X-n_3-1 \choose 2}\right]\\
	 &- \left[{n_1+n_3-X \choose 2} + {n_1+n_3-X+1 \choose 2} + \cdots + {n_1 -1 \choose 2}\right]\\
	 &= S(X-n_3,0,0) = S(X-n_3,0,n_3).
	 \end{align*}
	 The equality holds only when $X=\frac{N}{2}$ or $n_1+n_3-X-1<2$. First, if $X=\frac{N}{2}$, then both forms have the same number of monochromatic edges. However, if we relabel the names of the colors, then both forms are the same. We will focus on the condition of $n_1+n_3-X<3$ where $3 \leqslant n_1 \leqslant n_2<n_3\leqslant X < \frac{N}{2}$ and $n_1+n_2>n_3$. Suppose that $n_1+n_3-X<3$.
	 
	 If $N$ is even, then $3 > n_1+n_2-X \geqslant n_1+n_3-\left(\frac{N}{2}-1\right)=\frac{n_1+n_3-n_2}{2}+1$. Thus, $n_1+n_3-n_2 <4$. Since $1 \leqslant n_3-n_2$, we have that $n_1<3$ which contradicts with $3\leqslant n_1$.
	 
	 If $N$ is odd, then $3 > n_1+n_2-X \geqslant n_1+n_3-\left(\frac{N-1}{2}\right)=\frac{n_1+n_3-n_2+1}{2}$. Thus, $n_1+n_3-n_2 <5$. Since $1 \leqslant n_3-n_2$, we have that $n_1<4$. Consequently, it is only possible when $n_1=3$. Note that $n_2 < n_3$ and $n_1 + n_2=3+n_2 > n_3$. For $N = 3+n_2+n_3$ to be odd, $n_2$ and $n_3$ must have the same parity. Thus, $n_3=n_2+2$ and $5>n_1+n_3-n_2=3+n_2+2-n_2=5$, which is a contradiction.
	 
	 Now, we have that $n_1+n_3-X \geqslant 3$. Hence, $F_8$ gives fewer number monochromatic edges than $F_6$ and $c^*_X$ is in the form $F_8$.
	 
	 To sum up, we have already determined (as shown in the table below) the canonical forms $c^*_X$ that has minimum number of monochromatic edges for each condition of hypergraphs and range of the number of red vertices $X$.
	 \begin{center}
	 	\begin{tabular}{ |P{1cm}|P{3.5cm}|P{1.7cm}|P{1cm}|P{3.5cm}|P{1.7cm}|  }
	 		\hline
	 		\multicolumn{6}{|c|}{List of best canonical forms} \\
	 		\hline
	 		\multicolumn{3}{|c|}{Type A Hypergraphs $n_1+n_2 \leqslant n_3$} & \multicolumn{3}{|c|}{Type B Hypergraphs $n_1+n_2>n_3$} \\
	 		\hline
	 		Cases&Number of red vertices & Canonical form&Cases &Number of red vertices&Canonical form\\
	 		\hline
	 		$1$&$0 \leqslant X < n_1$&   $F_1$&$1$&$0 \leqslant X < n_1$  &$F_1$\\
	 		$2$&$n_1 \leqslant X < \frac{n_1+n_2}{2}$   &$F_4$&$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$&$3$&$X = \frac{n_1+n_2}{2}$ &$F_2$ or $ F_4$\\
	 		$ $&$\frac{n_1+n_2}{2} < X < n_2$& $F_2$&$ $&$\frac{n_1+n_2}{2} < X < n_2$ &$F_2$\\
	 		$4A$&$n_2 \leqslant X < n_1 +n_2$&  $F_6$&$4B$&$n_2 \leqslant X <n_3$&$F_3$ or $F_6$\\
	 		$5A$&$n_1 + n_2 \leqslant X \leqslant \lfloor{\frac{N}{2}}\rfloor$&$F_{10}$&$5B$&$n_3 \leqslant X \leqslant \lfloor{\frac{N}{2}}\rfloor$ &   $F_8$\\
	 		
	 		\hline
	 	\end{tabular}
	 \end{center}
	 
	 Note that, in \textit{Case 3}, $c^*_X$ is only in the form $F_2$ when $\frac{n_1+n_2}{2} < X < n_2$. However, if $X=\frac{n_1+n_2}{2}$, then $F_2$ and $F_4$ give the same number of monochromatic edges. Moreover, in \textit{Case 4B}, we have not compared the colorings in the form $F_3$ and $F_6$. The uniqueness of $c^*_X$ of the other cases will be also considered. We can see that the inequalities in some cases are equal when the sizes of some parts are equal which means that those canonical forms are equivalent. For example, in \textit{Case 1}, if $n_2=n_3$, $F_2$ is equivalent to $F_3$. The remaining inequalities are equal when $X$ is equal to some certain value, for example, in \textit{Case 5A} and \textit{Case 5B} when $X = \frac{N}{2}$; the colorings in the forms $F_3$ and $F_{10}$ are isomorphic up to a permutation of the name of colors and so are colorings in the forms $F_6$ and $F_8$ in \textit{Case 5B}.
	 
	 Hence, apart from \textit{Case 3} where $X=\frac{n_1+n_2}{2}$ and \textit{Case 4B}, a coloring with red vertices in the form, according to the previous table, has fewer monochromatic edges than other colorings with the same amount of red vertices and the uniqueness follows.
	 
	 Next, we will make comparisons between colorings with different values of $X$. We will show that any $c^*_X$ with $X\leqslant \lfloor{\frac{N}{2}}\rfloor -1$ has strictly more monochromatic edges than some colorings. We, hence, would like to show that $M(H,c^*_{X+1})-M(H,c^*_{X}) < 0$ for each $0 \leqslant X < \lfloor{\frac{N}{2}}\rfloor-1$. Note that, if $c^*_X$ and $c^*_{X+1}$ are in the same canonical form, we will consider $\displaystyle \bigtriangleup M(H,c^*_X)$ instead. Again, we will divide into several cases conforming to the value of $X$ and the type of $H$.
	 
	 \textit{Case 1}: $0 \leqslant X < n_1$.
	 
	 We have that $c^*_X$ is in the form $F_1$ with $x_1 = X$, $x_2 =0$ and $x_3=0$. Then,\begin{align*} \bigtriangleup_1M(H,c^*_X)= \left[ {X \choose 2} - {X \choose 2}\right] - \left[ {N-X-1 \choose 2} - {n_1-X-1 \choose 2}\right]\leqslant 0.
	 \end{align*}
	 The equality holds only when $N-X-1<2$, which is impossible.
	 
	 \textit{Case 2}: $n_1 \leqslant X < \frac{n_1 + n_2}{2}$.
	 
	 We have that $c^*_X$ is in the form $F_4$ with $x_1 = n_1$, $x_2 =X-n_1$ and $x_3=0$. Then, \begin{align*}
	 \bigtriangleup_2M(H,c^*_X)= \left[ {X \choose 2}+{n_1+n_2-X-1 \choose 2}\right]-\left[ {X-n_1 \choose 2} +  {N-X-1 \choose 2}  \right].
	 \end{align*} 
	 We will show that $\bigtriangleup_2M(H,c^*_X)<0$ by Proposition 4. We have $X + (n_1+n_2-X-1) = n_1+n_2 -1 \leqslant n_3 +n_2 -1 =(X - n_1) +(N-X-1)$,
	 $X-n_1 < X$ and $n_1+n_2-X-1 < N -X -1$. Since $2 \leqslant N-X-1$, we have that $\displaystyle \bigtriangleup_2M(H,c^*_X)<0$.
	 
	 \textit{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 $\bigtriangleup_2M(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 $\bigtriangleup_2M(H,c^*_X) < 0$ similarly as in \textit{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 \begin{align*}
	 \bigtriangleup_2M(H,c^*_X) = \left[ {X \choose 2} - {X \choose 2}\right] - \left[ {N-X-1 \choose 2} - {n_2-X-1 \choose 2}\right]\leqslant 0.
	 \end{align*}
	 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.
	 
	 \textit{Case 4A}: $n_2 \leqslant X < n_1+n_2$ and $H$ is a type A hypergraph.
	 
	 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, \begin{align*}
	 \bigtriangleup_1M(H,c^*_X) =\left[{X\choose 2}+{n_1+n_2-X-1 \choose2} \right] -\left[ {X-n_2 \choose2}+{N-X-1\choose 2} \right].
	 \end{align*}
	 We will show that $\displaystyle \bigtriangleup_1M(H,c^*_X)<0$ by Proposition 4. 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 $\displaystyle \bigtriangleup_1M(H,c^*_X)<0$.
	 
	 \textit{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, \begin{align*}
	 \bigtriangleup_3M(H,c^*_X)=\left[{X\choose 2} - {X-n_1-n_2 \choose2}\right] - \left[{N-X-1\choose 2} - {N-X-1 \choose2}\right] \geqslant 0.
	 \end{align*}
	 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.
	 
	 \textit{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 $\bigtriangleup_3M(H,c^*_X) < 0$ for $F_3$ and $\bigtriangleup_1M(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 \begin{align*}
	 \bigtriangleup_3M(H,c^*_X) = \left[ {X \choose 2} - {X \choose 2}\right] - \left[ {N-X-1 \choose 2} - {n_3-X-1 \choose 2}\right]\leqslant 0.
	 \end{align*}
	 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 \begin{align*}
	 \bigtriangleup_1M(H,c^*_X) = \left[{X \choose 2} +{n_1 +n_2-X-1\choose 2} \right]-\left[{N-X-1 \choose 2} + {X-n_2 \choose 2}\right].
	 \end{align*}
	 We will show that $\displaystyle \bigtriangleup_1M(H,c^*_X) < 0$ by Proposition 4. 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 $\displaystyle \bigtriangleup_1M(H,c^*_X) < 0$.
	 
	 \textit{Case 5B}: $n_3 \leqslant X \leqslant \lfloor{\frac{N}{2}}\rfloor $ and $H$ is a type B hypergraph.
	 
	 We have that $c^*_X$ is in the form $F_{8}$ with $x_1 = X-n_3$, $x_2=0$ and $x_3 = n_3$. Then, \begin{align*}
	 \bigtriangleup_1M(H,c^*_X)&=\left[{X\choose 2} - {X-n_3 \choose2}\right] - \left[{N-X-1\choose 2} - {n_1-(X-n_3)-1 \choose2}\right]\\
	 &= \frac{n_1^2+2n_1n_3+2X(N-n_1)-3n_1+3N-N^2-4n_3}{2}.
	 \end{align*}
	 Since we cannot apply any lemmas to $\bigtriangleup_1M(H,c^*_X)$, we expand the binomial coefficient terms and see when  $\displaystyle \bigtriangleup_1M(H,c^*_X)$ is fewer than $0$. Consequently, $\displaystyle \bigtriangleup_1M(H,c^*_X) < 0$ if and only if \[X< \left \lceil\frac{N^2-3N-n_1^2-2n_1n_3+3n_1+4n_3}{2(N-n_1)}\right\rceil.\]
	 
	 Write $X'$ for $\left\lceil\frac{N^2-3N-n_1^2-2n_1n_3+3n_1+4n_3}{2(N-n_1)}\right\rceil$. We have that the $c^*_{X'}$ has the minimum number of monochromatic edges among all colorings in the form $F_8$ and we will show that $X'\leqslant\frac{N}{2}$.
	 \begin{align*}
	 X'=\left\lceil\frac{N^2-3N-n_1^2-2n_1n_3+3n_1+4n_3}{2(N-n_1)}\right\rceil
	 \leqslant \frac{N^2 -Nn_1- 2n_3+2n_3}{2(N-n_1)}= \frac{N}{2}.
	 \end{align*}
	 
	 Hence, we have shown all the comparisons between colorings and we can conclude that:
	 \begin{enumerate}
	 	\item If $H$ is a type A hypergraph, then the coloring with $n_1 + n_2$ red vertices in the form $F_{10}$ has the minimum number of monochromatic edges.
	 	\item If $H$ is a type B hypergraph, then the coloring with $X'$ red vertices in the form $F_8$ has the minimum number of monochromatic edges.
	 \end{enumerate}
	 We have already proved that those minimum colorings are the unique colorings that has the minimum number of monochromatic edges among colorings with the same red vertices. Furthermore, we have shown that $\bigtriangleup M(H,c^*_X)$ is fewer than zero when $X$ is fewer than $n_1+n_2$ in a type A hypergraph and when $X$ is less than $X'$ in a type B hypergraph. Hence, those minimum colorings are the unique colorings that has minimum number of monochromatic edges among all colorings.
	\subsection{Hypergraphs with $n_1 < 3$ or $n_2 < 3$}
	In this subsection, we will prove the remaining cases which are unbalance complete tripartite hypergraphs with some classes smaller than $3$. These cases are easy and straightforward but contain fuzzy details. First, we will consider an unbalanced complete tripartite $3$-uniform hypergraphs with $n_1 \leqslant n_2 < n_3 \geqslant 3$. There are three possibilities for these hypergraphs:
	
	\textit{Case i}: $n_1 = n_2 =1$ and $n_3 \geqslant 3$.
	
	Since we have that the first two classes are smaller than $3$, no edge can be contained in the first two classes. Thus, 
	\[M(H,c)={X\choose 3}+{N-X\choose 3}-{x_3 \choose 3}-{n_3-x_3\choose3}.\]
	We have that $M(H,c) \geqslant 0$. Suppose that $M(H,c)=0$. Since $X \geqslant x_3$ and $N-X \geqslant n_3-x_3$, we have that ${X\choose 3}={x_3 \choose 3}$ and ${N-X\choose 3}={n_3-x_3\choose3}$.  Since $N=n_1+n_2+n_3=1+1+n_3\geqslant 5$, at least $3$ vertices are colored the same say red, i.e., $X\geqslant 3$. Then, $X=x_3$ which implies that $N-X=n_3+2-X>n_3-x_3$. Consequently, $3 > N-X = n_3+2-x_3$, i.e., $n_3=x_3$. This means that $c$ is a coloring such that the third class contains all red vertices and no blue vertex and the first two classes are all blue. Hence, we have already determined the minimum coloring and showed that it is unique up to a permutation of colors and classes.





	
	
	\textit{Case ii}: $n_1=1, n_2 =2$ and $n_3 \geqslant 3$.
	
	Again, no edge can be contained in the first two classes. Thus, 
	\[M(H,c)={X\choose 3}+{N-X\choose 3}-{x_3 \choose 3}-{n_3-x_3\choose3}.\]
	We will show that $M(H,c) \geqslant 1$. We have that $X \geqslant x_3$ and $N-X \geqslant n_3-x_3$. Since $N=n_1+n_2+n_3=1+1+n_3\geqslant 6$, at least $3$ vertices are colored the same say red, i.e., $X\geqslant 3$. If $X>x_3$, then $M(H,c)>0$. Suppose that $X=x_3$. Then, $N-X=n_3+3-x_3>n_3-x_3 \geqslant 3$. Hence, $M(H,c)>0$. Next, suppose that $M(H,c)=1$. If $X>x_3$, then
	\begin{align*}
	1\leqslant {X-1 \choose 2} \leqslant{X\choose 3}-{x_3\choose 3}\leqslant{X\choose 3}+{N-X\choose 3}-{x_3 \choose 3}-{n_3-x_3\choose3}= M(H,c). 
	\end{align*}
	This implies that $X=3$ and so $N-X \geqslant 3$, moreover, ${N-X\choose 3}={n_3-x_3\choose3}$. Hence, $N-X=n_3-x_3$. Now, we have $N-3=N-X=n_3-x_3=N-3-x_3$, i.e., $x_3=0$. This means $c$ is a coloring such that the third class contains no red vertices and the first two classes are all red.
	
	Suppose that $X=x_3$. Then,
	\begin{align*}
	1=M(H,c)={X\choose 3}+{N-X\choose 3}-{x_3 \choose 3}-{n_3-x_3\choose3}={n_3-x_3+3\choose 3}-{n_3-x_3\choose3}. 
	\end{align*} It is only possible when $n_3-x_3=0$ or $c$ is a coloring such that the third class contains all red vertices and no blue vertex and the first two classes are all blue. Note that if we relabel the names of colors, then both colorings are the same. Hence, we have already determined the minimum coloring and showed that it is unique up to a permutation of colors and classes.





	
	\textit{Case iii}: $n_1=2, n_2 =2$ and $n_3 \geqslant 3$.
	
	Similarly, no edges can be contained in the first two classes. Thus, 
	\[M(H,c)={X\choose 3}+{N-X\choose 3}-{x_3 \choose 3}-{n_3-x_3\choose3}.\]
	We will show that $M(H,c) \geqslant 4$. We have that $X \geqslant x_3$ and $N-X \geqslant n_3-x_3$. If there is a color, say red, such that all vertices of that color are only in the third class, then, we have $X=x_3$ and $N-X=n_3+4-x_3\geqslant 4$. Thus,
	\begin{align*}
	M(H,c)&= {N-X\choose 3}-{N-X-4\choose3}\\
	&={N-X-1 \choose 2}+{N-X-2 \choose 2}+{N-X-3 \choose 2}+{N-X-4 \choose 2}\\
	&\geqslant {3 \choose 2}+{2 \choose 2} = 4.
	\end{align*} The equality holds only when $N-X=4$, i.e., $n_3=x_3$. Hence, if $M(H,c)=4$, then $c$ is a colorings such that the third class contains all red vertices but no blue vertex and the first two classes are all blue.
	
	Suppose that there is no color such that all vertices of that color are only in the third class, i.e., $X>x_3$ and $N-X>n_3-x_3$. Since $N=n_1+n_2+n_3=2+2+n_3\geqslant 7$, at least $4$ vertices are colored the same say red, i.e., $X\geqslant 4$. If $X \geqslant 5$, then
	\begin{align*}
	M(H,c)\geqslant {X\choose 3}-{x_3\choose3}\geqslant {X\choose 3}-{X-1\choose3}={X-1 \choose 2} \geqslant {4 \choose 2} = 6.
	\end{align*}
	If $X=4$, then $N-X \geqslant 3$ and
	\begin{align*}
	M(H,c)\geqslant {X\choose 3}-{x_3\choose3} + 1\geqslant {X\choose 3}-{X-1\choose3}+1={X-1 \choose 2}+1= 4.
	\end{align*}
	The equality holds only when $N-X =3$ and $x_3=X-1$, i.e., $N=7$ and $x_3=3$. This means that $n_3=3$. Hence, if $M(H,c)=4$, then $c$ is a coloring of $H$ which has $7$ vertices such that the third class is all red, the second class is all blue and the first class has one red and one blue vertices. This implies that when $n_3=3$, minimum colorings are not unique.





	
















	





	
	Finally, the last class is a hypergraph such that only the first class is smaller than $3$.
	
	\textit{Case iv}: $n_1<3$ and $3 \leqslant n_2 \leqslant n_3$.
	
	Fortunately, this case conforms to almost all cases in the previous subsection since we assume that $n_2 \geqslant 3$. However, there are two points that we use the fact that $n_1\geqslant 3$. The first one is in the last part of \textit{Case 3} where we compare and determine which form of $F_2$ and $F_4$ has fewer monochromatic edges. Since we do not have that $n_1\geqslant 3$, it is possible that both forms have the same number of monochromatic edges. This is not problematic because both of them have strictly more monochromatic edges than some coloring according to the next comparisons. The next case is in the last part of \textit{Case 5B} where we compare and determine which form of $F_6$ and $F_8$ has fewer monochromatic edges. Again, since we do not have that $n_1\geqslant 3$, we may have that $n_1+n_3-X<3$ where $n_2<n_3\leqslant X < \frac{n_1+n_2+n_3}{2}$ and $n_1+n_2>n_3$. If this condition occurs, we will have that $F_6$ and $F_8$ have the same number of monochromatic edges. Since $n_1<3$, the condition is possible only when ($N$ is even and $n_1<3$) or ($N$ is odd and $n_1 \leqslant 3$).
	
	Suppose that $N$ is even. If $n_1=1$, then we have that $n_3 < n_1+n_2 = n_2+1$. Since $n_2<n_3$, there is no choice for $n_3$. If $n_1=2$, then we have that $n_3 < n_1+n_2= n_2+2$. Since $n_2<n_3$, $n_3=n_2+1$. However, for $N$ to be even, $n_2$ and $n_3$ must have different parity, which is impossible.
	
	Suppose that $N$ is odd. Again, it is impossible for $n_1=1$. Since $n_1<3$, we have $n_1=2$. Similarly, $n_3=n_2+1$ and $N=n_1+n_2+n_3=2+n_2+n_2+1=2(n_2+1)+1$ which is odd. Consequently, the condition is possible only here and $F_6$ and $F_8$ have the same number of monochromatic edges. Hence, if $H$ is a hypergraph with $n_1=2$ and $ 3\leqslant n_2=n_3-1$, then there are only two colorings (each unique up to a permutation of colors and classes) that have minimum number of monochromatic which are colorings with $X=\lfloor{\frac{N}{2}}\rfloor$ in the form $F_6$ and $F_8$.











	
	Now, we have determined the minimum colorings of all unbalanced complete tripartite $3$-uniform hypergraphs. 
\end{proof}





\section{Proof of Theorem~\ref{thm:3}}
\label{sec:thm:3}
\begin{proof}[Proof of Theorem~\ref{thm: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 $\bigtriangleup_{i{i'}} 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'}^{th}$ class is recolored into red. The definitions are similar for other colors combinations. The process will be called a \textit{swapping} which results in a new coloring, say $c'$. 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'}^{th}$ class increases by $1$ while the total number of red vertices remains the same. In other words, the coloring $c'$ has $r_i - 1$ and $r_{i'}+1$ red vertices in the $i^{th}$ and ${i'}^{th}$ classes, respectively. Likewise, the coloring $c'$ has $b_i+1$ and $b_{i'}-1$ blue vertices in the $i^{th}$ and ${i'}^{th}$ classes, respectively.

We can compute $\bigtriangleup_{i{i'}} M(H,c,r,b)$ by comparing the numbers of monochromatic edges containing those vertices undergone swapping before and after the swapping process. Thus,
\begin{align*}
\bigtriangleup_{i{i'}}M(H,c,r,b)&= \left[ {B-1 \choose r}-{b_i \choose r} + {R-1 \choose r}- {r_{i'}\choose r} \right]\\ &\;\;\;\;- \left[ {R-1 \choose r}-{r_i-1 \choose r} + {B-1 \choose r} - {b_{i'}-1\choose r} \right]\\
&= \left[ {r_i-1 \choose r} + {b_{i'}-1\choose r} \right] - \left[ {b_i \choose r} +  {r_{i'}\choose r} \right].
\end{align*}
A \textit{successful swapping} is a swapping in such a way that the number of monochromatic edges is reduced, i.e., $\bigtriangleup_{i{i'}} M(H,c,r,b) < 0$. Note that if $0<r_i<n$, $<b_i<n$, $r_{i'}=n-1$ and $b_{i'}=1$, then
\begin{align*}
\bigtriangleup_{i{i'}}M(H,c,r,b)&= \left[ {r_i-1 \choose r} + {b_{i'}-1\choose r} \right] - \left[ {b_i \choose r} +  {r_{i'}\choose r} \right]\\
&=\left[ {r_i-1 \choose r} + {1-1\choose r} \right] - \left[ {b_i \choose r} +  {n-1\choose r} \right].
\end{align*} Since $r_i<n$, $0<b_i$ and $n-1 \geqslant r$, we have that $\bigtriangleup_{i{i'}}M(H,c,r,b)<0$. This implies that a swapping resulting in fewer polychromatic classes is always successful.

\begin{lemma} If $\bigtriangleup_{i{i'}} M(H,c,\text{r},\text{b}) \leqslant 0$, then $\bigtriangleup_{i{i'}} M(H,c',\text{r},\text{b}) \leqslant 0$. \end{lemma}

The proof of this lemma is similar to that of Lemma 8. Lemma 10 means that if a swapping can be done 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'}^{th}$ class has no blue vertex.
\begin{lemma}
	If $\bigtriangleup_{i{i'}} M(H,c,\text{r},\text{b}) \geqslant 0$, then $\bigtriangleup_{i{i'}} M(H,c,\text{b},\text{r}) \leqslant 0$.
\end{lemma}
The proof of this lemma is similar to that of Lemma 9. However, in contrast to Lemma $9$, it is possible that the equality holds. Note that if $c$ contains two classes, the $i^{th}$ and ${i'}^{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:
\begin{enumerate}\item Swapping a red vertex of the $i^{th}$ class with a blue vertex of the ${i'}^{th}$ class.
	\item Swapping a blue vertex of the $i^{th}$ class with a red vertex of the ${i'}^{th}$ class.
\end{enumerate}
By Lemma 11, one of the two directions can be achieved without increasing the number of monochromatic edges. Moreover, by Lemma 10, we can continue swapping in the same direction until the $i^{th}$ class has no red vertex or the ${i'}^{th}$ class has no blue vertex and the number of monochromatic edges does not increase. Note that we get the same result when considering a swapping relating to other color combinations. Hence, the coloring with minimum number of monochromatic edges among colorings with 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 the following table.
\begin{center}
	\begin{tabular}{ |P{3cm}|P{10cm}| }
		\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
	\end{tabular}
\end{center}


The first column illustrates the list of $5$ canonical forms and the second column describes the colors of vertices in each class.

Suppose that $r_i \leqslant b_{i'}$. Let $\bigtriangleup_{i{i'}} 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'}^{th}$ class are recolored into red. The process will be called \textit{total swapping} which results in a new coloring, say $c'$. We can compute $\bigtriangleup_{i{i'}} M_T(H,c,r,b)$ by summing the change in the number of monochromatic edges of the swappings. Thus,
\begin{align*}
\bigtriangleup_{i{i'}} &M_T(H,c,r,b)= \sum_{k=0}^{r_i-1}\left[ {r_i-1-k \choose r} + {b_{i'}-1-k\choose r} \right] - \left[ {b_i+k\choose r} +  {r_{i'}+k\choose r} \right]\\
&=\left[{0 \choose r}+{1 \choose r}+\cdots+{r_i-1 \choose r}\right]+\left[{b_{i'}-r_i \choose r}+{b_{i'}-r_i+1 \choose r}+\cdots+{b_{i'}-1 \choose r}\right] \\
&\;\;\;\;-\left[{b_i \choose r}+{b_i+1 \choose r}+\cdots+{b_i+r_i-1 \choose r}\right]-\left[{r_{i'} \choose r}+{r_{i'}+1 \choose r}+\cdots+{r_{i'}+r_i-1 \choose r}\right].
\end{align*}
 A \textit{successful total swapping} is a total swapping in such a way that the number of monochromatic edges is reduced.
\begin{lemma}
	Suppose that $1 \leqslant r_i \leqslant b_{i'}$. Then, $\bigtriangleup_{i{i'}} M_T(H,c,r,b)\leqslant0$  if $c$ satisfies at least one of the following conditions:
	\begin{enumerate}
		\item $b_{i'} < r_i+b_i$.
		\item $b_{i'} < r_i+r_{i'}$.
	\end{enumerate}
\end{lemma}
\begin{proof}
	Suppose that $ 1 \leqslant r_i \leqslant b_{i'}$. If $b_{i'} < r_i+b_i$, then \begin{align*}
	\bigtriangleup_{i{i'}} &M_T(H,c,r,b)\\
	&\leqslant\left[{0 \choose r}+{1 \choose r}+\cdots+{r_i-1 \choose r}\right]-\left[{r_{i'} \choose r}+{r_{i'}+1 \choose r}+\cdots+{r_{i'}+r_i-1 \choose r}\right]\leqslant 0.
	\end{align*}The equality holds only when $b_i+r_i-1<r$ and $r_{i'}+r_i-1<r$, i.e., $b_i+r_i<r+1$ and $r_i+r_{i'}<r+1$. If $b_{i'} < r_i+r_{i'}$, then \begin{align*}
	\bigtriangleup_{i{i'}} M_T(H,c,r,b)& \leqslant\left[{0 \choose r}+{1 \choose r}+\cdots+{r_i-1 \choose r}\right]-\left[{b_i \choose r}+{b_i+1 \choose r}+\cdots+{b_i+r_i-1 \choose r}\right]\\
	&\leqslant 0.
	\end{align*}The equality holds only when $b_i+r_i-1<r$ and $r_{i'}+r_i-1<r$, i.e., $b_i+r_i<r+1$ and $r_i+r_{i'}<r+1$.
\end{proof}

Note that if we consider a class with only two colors say $r_i+b_i=n \geqslant r+1$, then $\bigtriangleup_{i{i'}} M_T(H,c,r,b)$ is strictly less than zero in both cases. We will use Lemma $12$ to get more information from the canonical forms. From this point, the term \textit{quadruple} refers to a collection of $4$ values which are the numbers of vertices of any pair of colors in any pair of classes, e.g. $(r_i,b_i,r_{i'},b_{i'})$. Consequently, in each coloring in the forms any canonical forms, all quadruples contain at least one zero. Suppose that $c$ contains the $i^{th}$ and ${i'}^{th}$ classes such that they have a color in common but the $i^{th}$ class contains a color that the ${i'}^{th}$ class does not, say we focus on $(r_i\neq 0,b_i\neq 0,r_{i'} =0,b_{i'}\neq 0)$. If $c$ is a minimum coloring with $r_i+b_i=n$, then we can conclude by Lemma $12$ that
\begin{enumerate}
	\item if $r_i \leqslant b_{i'}$, then $b_{i'} \geqslant r_i+b_i$ and $b_{i'} \geqslant r_i  +r_{i'}=r_i$, and
	\item if $r_i \geqslant b_{i'}$, then $r_i \geqslant b_i + b_{i'}$ and $r_i \geqslant r_{i'}+b_{i'}=b_{i'} $.
\end{enumerate} We will call these \textit{quadruple conditions}.

Next, we will focus on the possibility of $F_4$. Suppose that $c$ is the coloring that has minimum number of monochromatic edges which is in the form $F_4$ such that, WLOG, the first class has $g_1 \neq 0$ green and $r_1 \neq 0$ red vertices, the second class has $g_2 \neq 0$ green and $b_2 \neq 0$ blue vertices and the third class has $r_3 \neq 0$ red and $b_3 \neq 0$ blue vertices, where $g_1$ is the maximum among those values. We will apply quadruple conditions to the quadruple $(g_1,b_1=0,g_2,b_2)$. Since $g_1 \geqslant b_2$ and $g_2+b_2=n$, $n = g_2 + b_2 \leqslant g_1 = n - r_1 < n$, which is a contradiction. Hence, an minimum coloring cannot be in the form $F_4$ and this form will be out of our interest. Consequently, we will search for the minimum colorings only from $F_1, F_2, F_3$ and $F_5$. 

We will divide this into $2$ cases upon the remainder of the number $k$ of vertex classes divided by $3$. For simplicity, we define a \textit{type i} hypergraph to be a hypergraph with $k\equiv i \ (\textrm{mod}\ 3)$ classes for $i=0,1,2$. We will consider a type 0 hypergraph first.

\textit{Case 0}: $H$ is a type 0 hypergraph.

Since the number of classes is divisible by the number of colors, it is done by Proposition 7.

\textit{Case 1}: $H$ is a type 1 hypergraph.


\textit{Case 1.1}: The coloring $c$ is in the form $F_3$.

In this case, our aim is to show that all colorings in the form $F_3$ have more monochromatic edges than some coloring in the form $F_2$. We have that $c$ has two classes that are polychromatic, say the first class contains green and red vertices and the second class contains green and blue vertices, while the rest classes are monochromatic. The number of vertices of each color and the number of monochromatic classes of each color are shown in the table below.
\begin{center}
	\begin{tabular}{ |P{1.3cm}|P{1.4cm}|P{1.4cm}|P{1.4cm}|P{1.4cm}|P{1.4cm}|P{1.4cm}|   }
		\hline
		\multicolumn{4}{|c|}{Polychromatic Classes} & \multicolumn{3}{|c|}{Monochromatic Classes} \\
		\hline
		Classes&Red vertices & Blue vertices&Green vertices &Red classes &Blue classes&Green classes\\
		\hline
		$1$&$r_1 \neq 0$&   $0$&$g_1 \neq 0$&$k_r$  &$k_b$&$k_g$\\
		$2$&$0$   &$b_2 \neq 0$&$g_2 \neq 0$&$ $&   $ $&   $ $\\
		
		\hline
	\end{tabular}
\end{center}

We will show that the coloring such that $k_r$, $k_b$ and $k_g$ are as equal as possible has smaller number of monochromatic edges than the coloring those of which are not. WLOG, suppose that $c$ has $k_g$ green classes and $k_r$ red classes such that $k_g - k_r \geqslant 2$. We will recolor all vertices in a green class into red and get a new coloring $c'$. Thus,
\begin{align*}
M(H,c)&= { nk_r+ r_1 \choose r+1}+ { nk_b+ b_2 \choose r+1}+ { nk_g+ g_1+g_2 \choose r+1}\\
&\;\;\;\;-{r_1 \choose r+1}-{b_2 \choose r+1}-{g_1 \choose r+1}-{g_2 \choose r+1} -(k-2){n \choose r+1}
\end{align*}and
\begin{align*}
M(H,c')&= { n(k_r+1)+ r_1 \choose r+1}+ { nk_b+ b_2 \choose r+1}+ { n(k_g-1)+ g_1+g_2 \choose r+1}\\
&\;\;\;\;-{r_1 \choose r+1}-{b_2 \choose r+1}-{g_1 \choose r+1}-{g_2 \choose r+1} -(k-2){n \choose r+1}.
\end{align*}Then,
\begin{align*}
M(H,c')-M(H,c)&= \left[ { n(k_r+1)+ r_1 \choose r+1}+ { n(k_g-1)+ g_1+g_2 \choose r+1}\right]\\&\;\;\;\;-\left[{ nk_r+ r_1 \choose r+1}+ { nk_g+ g_1+g_2 \choose r+1}\right].
\end{align*} We will show that $M(H,c')-M(H,c) < 0$ by Proposition 4. We have $\left[n(k_r+1)+ r_1\right]+\left[n(k_g-1)+ g_1+g_2\right] = \left[nk_r+ r_1\right]+ \left[nk_g+ g_1+g_2\right]$, $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')-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 \ (\textrm{mod}\ 3)$, colorings such that $k_r$, $k_b$ and $k_g$ are as equal as possible must have one of these conditions:
\begin{enumerate}
	\item $k_r+1=k_b=k_g$,
	\item $k_r=k_b+1=k_g$,
	\item $k_r=k_b=k_g+1$.
\end{enumerate}

We will show that a coloring with the last condition has more number of 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 class. WLOG, we will recolor all vertices in a red class into green and get a new coloring $c'$ with condition (1). Then,
\begin{align*}
M(H,c)&= { nk_r+ r_1 \choose r+1}+ { nk_b+ b_2 \choose r+1}+ { nk_g+ g_1+g_2 \choose r+1}\\
&\;\;\;\;-{r_1 \choose r+1}-{b_2 \choose r+1}-{g_1 \choose r+1}-{g_2 \choose r+1} -(k-2){n \choose r+1}
\end{align*}and
\begin{align*}
M(H,c')&= { n(k_r-1)+ r_1 \choose r+1}+ { nk_b+ b_2 \choose r+1}+ { n(k_g+1)+ g_1+g_2 \choose r+1}\\
&\;\;\;\;-{r_1 \choose r+1}-{b_2 \choose r+1}-{g_1 \choose r+1}-{g_2 \choose r+1} -(k-2){n \choose r+1}.
\end{align*}Then,
\begin{align*}
M(H,c')-M(H,c)&= \left[ { n(k_r-1)+ r_1 \choose r+1}+ { n(k_g+1)+ g_1+g_2 \choose r+1}\right]\\&\;\;\;\;-\left[{ nk_r+ r_1 \choose r+1}+ { nk_g+ g_1+g_2 \choose r+1}\right].
\end{align*} We will show that $M(H,c')-M(H,c) < 0$ by Proposition $4$. We have $\left[n(k_r-1)+ r_1\right]+\left[n(k_g+1)+ g_1+g_2\right] =\left[ nk_r+ r_1\right]+ \left[nk_g+ g_1+g_2\right]$. 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')-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. Then,
\begin{align*}
\bigtriangleup_1M(H,c)
= \left[ {nk_r+r_1 \choose r}- {nk_g+g_1+g_2-1 \choose r} \right] + \left[{g_1-1 \choose r} -{r_1 \choose r} \right].
\end{align*} We have $nk_r+r_1 = n(k_g-1)+r_1 < nk_g < nk_g+g_1+g_2-1$ and $g_1-1<g_1+g_2 \leqslant r_1$. Since $nk_g+g_1+g_2-1>r$,  we have that  $\bigtriangleup_1M(H,c) < 0$. This is true for any arbitrary value of $r_1 > 0$. Hence, we will recolor a green vertex into red until the first class is a red class which is a coloring in the form $F_2$ and get fewer number of monochromatic edges. Consequently, we can conclude that $c$ has more monochromatic edges than a coloring in the form $F_2$.

\textit{Case 1.2}: The coloring $c$ is in the form $F_5$.

In this case, our aim is to show that all colorings in the form $F_5$ have more monochromatic edges than some coloring in the form $F_2$. We have that all classes of $c$ are monochromatic with $k_r$, $k_b$ and $k_g$ red, blue and green classes, respectively. We can show that the coloring that $k_r$, $k_b$ and $k_g$ are as equal as possible has smaller number of monochromatic edges similarly as in \textit{Case 1.1}. Since $k\equiv 1 \ (\textrm{mod}\ 3)$, colorings that $k_r$, $k_b$ and $k_g$ are as equal as possible must have one of these conditions:
\begin{enumerate}
	\item $k_r-1=k_b=k_g$,
	\item $k_r=k_b-1=k_g$,
	\item $k_r=k_b=k_g-1$.
\end{enumerate}

By symmetry, suppose that $c$ is a coloring such that $k_r-1=k_b=k_g$. We will show that if a red vertex in a red class, say the first class, is recolored into green, the number of monochromatic edges will decrease. The new coloring is not in the form $F_5$ but in the form $F_2$ instead. Then, 
\begin{align*}
\bigtriangleup_1M(H,c)
= \left[ {nk_g \choose r}+{n-1 \choose r} \right] - \left[ {nk_r-1 \choose r} +{0 \choose r} \right].
\end{align*} we will show that $\bigtriangleup_1M(H,c) < 0$ by Proposition $4$. We have $nk_g+ (n-1)= n(k_g+1) -1 = (nk_r-1)+0$ and $0 < n-1 < nk_g <nk_r-1$. Since $nk_r-1>r$, we have that $\bigtriangleup_1M(H,c) < 0$. Consequently, we can conclude that $c$ has more monochromatic edges than a coloring in the form $F_2$.

\textit{Case 1.3}: The coloring $c$ is in the form $F_2$.

In this case, our aim is to show that all colorings in the form $F_2$ have more monochromatic edges than some coloring in the form $F_1$. We have that $c$ has a class that is polychromatic, WLOG, say the first class contains red and blue vertices while the rest classes are monochromatic. Note that the number of vertices of each color and the number of monochromatic classes of each color are shown in the table below.
\begin{center}
	\begin{tabular}{ |P{1.3cm}|P{1.4cm}|P{1.4cm}|P{1.4cm}|P{1.4cm}|P{1.4cm}|P{1.4cm}|   }
		\hline
		\multicolumn{4}{|c|}{Polychromatic Classes} & \multicolumn{3}{|c|}{Monochromatic Classes} \\
		\hline
		Classes&Red vertices & Blue vertices&Green vertices &Red classes &Blue classes&Green classes\\
		\hline
		$1$&$r_1 \neq 0$&   $b_1 \neq 0$&$0$&$k_r$  &$k_b$&$k_g$\\
		\hline
	\end{tabular}
\end{center} We can show that the coloring such that $k_r$, $k_b$ and $k_g$ are as equal as possible has smaller number of monochromatic edges similarly as in \textit{Case 1.1}. Hence, we will focus on a coloring that $k_r$, $k_b$ and $k_g$ are as equal as possible. Since $(k-1)\equiv 0 \ (\textrm{mod}\ 3)$, colorings such that $k_r$, $k_b$ and $k_g$ are as equal as possible must have $k_r=k_b=k_g$.

Suppose that $c$ is a coloring such that $k_r=k_b=k_g$. By symmetry, suppose that $r_1 > 1$. We will show that if a red vertex in the first class is recolored into green, the number of monochromatic edges will decrease. The new coloring is not in the form $F_2$ but in the form $F_1$ instead. Then, 
\begin{align*}
\bigtriangleup_1M(H,c) &= \left[ {nk_g \choose r} - {0 \choose r}\right] - \left[ {nk_r+r_1-1 \choose r} - {r_1-1 \choose r}\right]\\
&= \left[ {nk_g \choose r}+{r_1-1 \choose r} \right] - \left[ {nk_r +r_1-1 \choose r} +{0 \choose r} \right].
\end{align*} We will show that $\bigtriangleup_1M(H,c) < 0$ by Proposition $4$. We have $nk_g+ (r_1-1)= (nk_r +r_1 -1)+0$ and $0 < r_1-1 < nk_g <nk_r+r_1-1$. Since $nk_r+r_1-1>r$, we have that $\bigtriangleup_1M(H,c) < 0$. Consequently, we can conclude that $c$ has more monochromatic edges than a coloring in the form $F_1$.

\textit{Case 1.4}: The coloring $c$ is in the form $F_1$.

In this case, our aim is to show that a coloring in the form $F_1$ such that the numbers of red, blue and green vertices are as equal as possible has the minimum number of monochromatic edges. We have that $c$ has a class that is polychromatic, WLOG, say the first class contains red, blue and green vertices while the rest classes are monochromatic. Note that the number of vertices of each color and the number of monochromatic classes of each color are shown in the table below.
\begin{center}
	\begin{tabular}{ |P{1.3cm}|P{1.4cm}|P{1.4cm}|P{1.4cm}|P{1.4cm}|P{1.4cm}|P{1.4cm}|   }
		\hline
		\multicolumn{4}{|c|}{Polychromatic Classes} & \multicolumn{3}{|c|}{Monochromatic Classes} \\
		\hline
		Classes&Red vertices & Blue vertices&Green vertices &Red classes &Blue classes&Green classes\\
		\hline
		$1$&$r_1 \neq 0$&   $b_1 \neq 0$&$g_1 \neq 0$&$k_r$  &$k_b$&$k_g$\\
		\hline
	\end{tabular}
\end{center} We can show that the coloring that $k_r$, $k_b$ and $k_g$ are as equal as possible has smaller number of monochromatic edges similarly as in \textit{Case 1.1}. Since $(k-1)\equiv 0 \ (\textrm{mod}\ 3)$, colorings such that $k_r$, $k_b$ and $k_g$ are as equal as possible must have $k_r=k_b=k_g$.

Suppose that $c$ is a coloring such that $k_r=k_b=k_g$. We will show that if we recolor the vertices in such a way that $r_1, b_1$ and $g_1$ are as equal as possible then the number of monochromatic edges will decrease. WLOG, assume that $r_1-g_1 \geqslant 2$. We will show that if a red vertex in the first class is recolored into green, the number of monochromatic edges will decrease. Then, 
\begin{align*}
\bigtriangleup_1M(H,c) &= \left[ {nk_g +g_1 \choose r} - {g_1 \choose r}\right] - \left[ {nk_r+r_1-1 \choose r} - {r_1-1 \choose r}\right]\\
&= \left[ {nk_g +g_1 \choose r}+{r_1-1 \choose r} \right] - \left[ {nk_r +r_1-1 \choose r} +{g_1 \choose r} \right].
\end{align*} We will show that $\bigtriangleup_1M(H,c) < 0$ by Proposition $4$. We have $(nk_g+g_1)+ (r_1-1)= (nk_r +r_1 -1)+g_1$ and $g_1 < r_1-1 < nk_g+g_1 <nk_r+r_1-1$. Since $nk_r+r_1-1>r$, we have that $\bigtriangleup_1M(H,c) < 0$. Consequently, we can conclude that $c$ is not a minimum coloring.

To sum up, we have proved that all colorings in the forms $F_2, F_3$ and $F_5$ have strictly more number of monochromatic edges than some coloring in the form $F_1$. Moreover, a coloring in the form $F_1$ where the numbers of red, blue and green vertices in the first class are not as equal as possible has strictly more monochromatic edges than the coloring $c^*$ where the numbers of red, blue and green classes are as equal as possible and the number of red, blue and green vertices in the first class are as equal as possible. Hence, this is the minimum coloring and it is unique up to a permutation of colors and classes.
\end{proof}

\section{Concluding remarks}
\label{sec:conclude}
In this paper, we considered $2$-colorings of balanced complete $k$-partite $r$-uniform hypergraphs and determined which one has the minimum number of monochromatic edges. The proof may give a clue for further generalization to an unbalanced hypergraph with arbitrary sizes of classes. We observed that the minimum coloring can only be in certain forms which are called canonical forms of the colorings. We studied the canonical forms of $2$-colorings of unbalanced complete tripartite $3$-uniform hypergraphs. Finally, we continued to determine the extermal $3$-coloring of balanced complete $k$-partite $r$-uniform hypergraphs when $k \equiv 0,1 \mod{3}$.

In Theorem \ref{thm:2}, we determined the minimum coloring for unbalanced $3$-uniform hypergraphs. In the proof, almost all comparisons have been done without expanding the binomial coefficient terms and they also hold if we try to generalize the proof to $r$-uniform hypergraphs with arbitrary $r \leqslant n_1$. However, in the \textit{Case 5B}, it cannot be done without expanding those binomial coefficient terms where, in this case, we expand with $r+1=3$ as the lower index. Hence, the proof works only for $3$-uniform hypergraphs. We believe that the minimum coloring for $r$-uniform hypergraphs with arbitrary $r \leqslant n_1$ differs from those in Theorem \ref{thm:2}.


Another generalized case is unbalanced complete hypergraphs with several vertex classes ($k>3$). The problem seems to be much more complicated because Theorem \ref{thm:2} demonstrates that the extremal coloring varies depending on the relationship among the sizes of the vertex classes.
\begin{problem}
	What is the minimum $2$-coloring of an unbalanced complete $k$-partite $r$-uniform hypergraph?
\end{problem}
We have determined the extermal $3$-coloring of balanced complete $k$-partite $r$-uniform hypergraphs only for $k\equiv 0,1 \mod{3}$. 
\begin{problem}
What is the minimum $3$-coloring of a balanced complete $k$-partite $r$-uniform hypergraph where $k\equiv 2 \mod{3}$?
\end{problem}

For $k \equiv 2 \mod{3}$, if we apply the same ideas as in the proof of Theorem \ref{thm:3}, we can conclude that the minimum coloring is in the form $F_3$ instead of $F_1$. However, the comparisons between colorings in the form $F_3$ are rather challenging and we believe that they require some further comparison tools. One might expect the minimum coloring to have approximately $\frac{\abs{V(H)}}{3}$ vertices in each color as in Theorem $4$. However, this is not the case, for example, when the number of vertices in each class is much greater than $k$.

For $m>3$, we have studied only some trivial cases for $m$-colorings of the hypergraphs in Section $2.6$.
\begin{problem}
	What is the minimum $m$-coloring of a balanced complete $k$-partite $r$-uniform hypergraph ?
\end{problem}
This is a generalization of the hypergraphs in Problem $15$ which is extremely complex as we believe that the minimum coloring varies depending on the relationship between number of colors and the number of classes. However, the proof of Theorem \ref{thm:3} might be useful to determine the minimum $m$-coloring of balanced complete $k$-partite $r$-uniform hypergraphs with $k\equiv 1 \mod{m}$, and we speculate that it would be in the form similar to the coloring in the form $F_1$.

Finally, there is another natural definition of $k$-partite hypergraphs where each edge is an $r$-subset containing vertices from different classes. 

\begin{problem}
	With the above definition of $k$-partite hypergraphs, what is the minimum coloring of a balanced complete $k$-partite $r$-uniform hypergraph?
\end{problem}


2021-07-21T02:18:35.000
2107
2107.09450
en
https://arxiv.org/abs/2107.09450
Consider the following problem. In a school with three classes containing $n$ students each, given that their genders are unknown, find the minimum possible number of triples of same-gender students not all of which are from the same class. Muaengwaeng asked this question and conjectured that the minimum scenario occurs when the classes are all boy, all girl and half-and-half. In this paper, we solve many generalizations of the problem including when the school has more than three classes, when triples are replaced by groups of larger sizes, when the classes are of different sizes, and when gender is replaced by other non-binary attributes.
Combinatorics (math.CO)
Monochromatic Edges in Complete Multipartite Hypergraphs
Qwen/Qwen-72B
1. YES
2. YES