If $H=(V,E)$ is a hypergraph and $\kappa$ is a cardinal,we say a map $c:V\to\kappa$ is a coloring if the restriction $c\restriction_e$ of $c$ to $e$ is non-constant whenever $e\in E$ and $|e|>1$. The smallest cardinal such that there is a coloring from $V$ to that cardinal is denoted by $\chi(H)$.

By $[\omega]^\omega$ we denote the set of infinite subsets of $\omega$.

Given $n\in\omega,n>1$ is there $E\subseteq[\omega]^\omega$ such that $\chi(\omega,E)=n$?


1 Answer 1


Yes. Partition $\omega$ into $n$ infinite sets $V_1,\dots,V_n$. Let $H=(\omega,E)$ where $E=\{e\in[\omega]^\omega:|\{i:e\cap V_i\ne\emptyset\}|\ge2\}$. Plainly $\chi(H)\le n$. Suppose the vertices of $H$ are colored with $m$ colors, $m\lt n$. For each $i$ choose an infinite monochromatic set $W_i\subseteq V_i$. By the pigeonhole principle, since $m\lt n$, for some $i\ne j$ the sets $W_i,W_j$ have the same color. Then $W_i\cup W_j\in E$ is monochromatic, showing that the coloring is not proper.


Your Answer

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

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