1
$\begingroup$

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$?

$\endgroup$

1 Answer 1

3
$\begingroup$

$\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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.