If $H=(V,E)$ is a hypergraph, and $\kappa \neq \emptyset$ is a cardinal, a map $c: V\to \kappa$ is said to be a coloring if the restriction $c|_e: e\to \kappa$ is non-constant whenever $e\in E$ and $e$ has at least $2$ elements. The least non-empty cardinal such that there is a coloring onto that cardinal is said to be the chromatic number of $H$.

Let $[\omega]^\omega$ denote the collection of infinite subsets of $\omega$. For $n\in \omega\setminus\{0,1\}$, let $${\cal E}_n =\{E\subseteq [\omega]^\omega: \chi(\omega, E) = n\}.$$

Question. For what values of $n$ does ${\cal E}_n$ have maximal elements with respect to $\subseteq$?


1 Answer 1


$\mathcal E_n$ has maximal elements for every $n\ge1$.

Let $V_1,\dots,V_n$ be pairwise disjoint infinite sets such that $V_1\cup\cdots\cup V_n=\omega$ and let $E=\{e\in[\omega]^\omega:e\not\subseteq V_i\text{ for all }i\in[n]\}$. Plainly $\chi(\omega,E)\le n$.

Let $c$ be any proper $n$-coloring of $(\omega,E)$. For each $i\in[n]$ there is some color $x_i$ which occurs infinitely often in $V_i$, and that color can not occur in $\omega\setminus V_i$. Thus the only proper $n$-colorings of $(\omega,E)$ are the obvious ones, where the color classes are the sets $V_i$. This shows that $\chi(\omega,E)=n$ and that $\chi(\omega,E')\gt n$ if $E\subsetneqq E'\subseteq[\omega]^\omega$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .