For sets $A, B$ we write $B^A$ for the set of all functions $f:A\to B$.


Let $H = (V,E)$ be a [hypergraph](https://en.wikipedia.org/wiki/Hypergraph) such that $V,E\neq\varnothing$ and $|e| \geq 2$ for all $e\in E$. Let $\kappa>1$ be a cardinal, finite or infinite, and let $c:V\to \kappa$ be a map. By $\text{Mono}(H,c)$ we denote the set of mono-chromatic edges with respect to $c$, that is


$$\text{Mono}(H,c)=\{e\in E: c\restriction\_e \text{ is constant}\}.$$


Let ${\cal M}(H, \kappa) = \{\text{Mono}(H,c): c\in \kappa^V\}$, ordered by set inclusion.


**Question.** Do we necessarily have $\text{Min}({\cal M}(H, \kappa)) \neq \varnothing$?


**Notes.**


1. If $(P,\leq)$ is a partially ordered set, by $\text{Min}(P)$ we denote the set of minimal elements of $P$.
2. We have that $\varnothing$ is an **element** (the only element) of $\text{Min}({\cal M}(H, \kappa))$ if and only if $\kappa$ is at least the [hypergraph chromatic number](https://mathoverflow.net/questions/363267/chromatic-number-of-regular-linear-hypergraphs-on-omega) of $H=(V,E)$.



Minimizing the set of monochromatic edges
Let $H=(V,E)$ be a hypergraph, $\kappa$ a cardinal.


**Observation 1.** $\operatorname{Min}(\mathcal M(H,\kappa))\ne\emptyset$ if and only if $H$ has a maximal $\kappa$-colorable subhypergraph.


**Proof.** If $F\subseteq E$, then $(V,F)$ is a maximal $\kappa$-colorable subhypergraph of $H$ if and only if $E\setminus F$ is a minimal element of $\mathcal M(H,\kappa)$.


**Observation 2.** If $\kappa$ is infinite, then $\operatorname{Min}(\mathcal M(H,\kappa))\ne\emptyset$ if and only iff $H$ is $\kappa$-colorable. (Hence we get a simple example where $\operatorname{Min}(\mathcal M(H,\kappa))=\emptyset$ by taking $\kappa=\aleph\_0$ and $H=K\_{\aleph\_1}$, the complete graph on $\aleph\_1$ vertices.)


**Proof.** For the nontrivial direction, since $\kappa+1=\kappa$, we can always make another hyperedge non-monochromatic by creating a new color.


**Observation 3.** If $\kappa$ is finite and all hyperedges (elements of $E$) are finite, then $\operatorname{Min}(\mathcal M(H,\kappa))\ne\emptyset$.


**Proof.** By Observation 1, we have to prove that $H$ has a maximal $\kappa$-colorable subhypergraph. This follows from Zorn's lemma and the hypergraph version of the [De Bruijn–Erdős theorem](https://en.wikipedia.org/wiki/De_Bruijn%E2%80%93Erd%C5%91s_theorem_(graph_theory)), which says that for finite $\kappa$ a hypergraph with finite hyperedges is $\kappa$-colorable iff all of its finite subhypergraphs are $\kappa$-colorable.


**Observation 4.** If $1\lt\kappa\lt\aleph\_0$ and if $E$ is a nonprincipal ultrafilter on $V$, then $\operatorname{Min}(\mathcal M(H,\kappa))=\emptyset$.


**Proof.** Consider any coloring $c:V\to\kappa$. Since $E$ is an ultrafilter and $\kappa$ is finite, there is some $i\in\kappa$ such that $V\_i=\{v\in V:c(v)=i\}\in E$, whence $V\_i\in\operatorname{Mono}(H,c)$. Now we can make $V\_i$ non-monochromatic by changing the color of one vertex in $V\_i$; and this will not result in any previously non-monochromatic hyperedge becoming monochromatic, because each hyperedge has infinite intersection with $V\_i$. Therefore $\operatorname{Mono}(H,c)$ is not a minimal element of $\mathcal M(H,\kappa)$.


