Chromatic number of the maximal chain hypergraph on ${\cal P}(\omega)$

Question

If $H=(V, E)$ is a hypergraph, the its chromatic number $\chi(H)$ is the smallest non-empty cardinal $\kappa$ such that there is a map $c:V \to \kappa$ such that for every $e\in E$ containing more than one point, the restriction $c|_e: e\to \kappa$ is non-constant.

A chain in ${\cal P}(\omega)$ is a set ${\cal C}\subseteq {\cal P}(\omega)$ such that for all $A, B\in {\cal C}$ at least one of $A\subseteq B, B\subseteq A$ holds. A standard application of Zorn's lemma shows that each chain is contained in a maximal chain.

Let $V=P(\omega)$, let $E$ be the collection of maximal chains in ${\cal P}(\omega)$, and consider $H=(V, E)$.

What is $\chi(H)$?

Answer 1

As noted in a comment-answer by te4, $\chi(H)=2$; a proper $2$-coloring is obtained by coloring the vertex $\varnothing$ (or the vertex $\omega$) red and all other vertices blue.

More generally, if the poset $(P,\le)$ has a maximal antichain consisting of a single element, and if $|P|\gt1$, then the hypergraph $(P,E)$, where $E$ is the set of all maximal chains in $(P,\le)$, has chromatic number $2$.

In view of this trivial answer, I suspect that the question was misstated. Perhaps you meant to ask about the maximal chains in the set of all nonempty proper subsets of $\omega$? In that case the chromatic number is still $2$ but the coloring is slightly less trivial. More generally:

Theorem. Suppose $h,k\lt\omega$. If $\{X\subseteq\omega:|X|=h\ \text{ or }\ |\omega\setminus X|=k\}\subseteq V\subseteq\mathcal P(\omega)$, and if $E$ is the set of all maximal chains in the poset $(V,\subseteq)$, then the hypergraph $H=(V,E)$ has chromatic number $\chi(H)=2$.

Proof. Plainly $\chi(H)\gt1$; we have to show that $H$ is $2$-colorable. Write $1=\sum_{n=1}^\infty a_n$ where $0\lt a_n\lt\frac1{2\max(h,k)}$ for all $n$. For $X\subseteq\omega$ let $m(X)=\sum_{n\in X}a_n$. I claim that every maximal chain $\mathcal C$ contains vertices $X$ and $Y$ with $m(X)\lt\frac12\lt m(Y)$.

Assume for a contradiction that $m(X)\ge\frac12$ for all $X\in\mathcal C$. Let $X_0=\bigcap\mathcal C$; then $m(X_0)\ge\frac12$, whence $|X_0|\gt h$. It follows that $X_0$ has a proper subset $X_0^\prime$ of cardinality $h$, and so $\mathcal C\cup\{X_0^\prime\}$ is a chain in $(V,\subseteq)$ properly extending $\mathcal C$, contradicting the maximality of $\mathcal C$.

Dually, assuming that $m(X)\le\frac12$ for all $X\in\mathcal C$, let $X_1=\bigcup\mathcal C$. Then $m(X_1)\le\frac12$, whence $|\omega\setminus X_1|\gt k$, etc.

Remark. This theorem does not apply to the hypergraph $H=(V,E)$ where $V=\{X\subseteq\omega:|X|=|\omega\setminus X|=\aleph_0\}$ and $E$ is the set of all maximal chains in $(V,\subseteq)$. In this case a different construction shows that $\chi(H)=2$.

Write $X\sim Y$ if $|X\triangle Y|\lt\aleph_0$. By the axiom of choice there is a map $f:V\to V$ such that $X\sim f(X)$ for all $X\in V$ and $f(X)=f(Y)$ whenever $X\sim Y$. Define $c:V\to\{0,1\}$ so that $c(X)\equiv|X\triangle f(X)|\pmod2$. Thus $c(X)\ne c(Y)$ whenever $|X\triangle Y|$ is odd.

Suppose $\mathcal C$ is a maximal chain. Choose $P,Q\in\mathcal C$ with $P\subsetneqq Q$ and choose $n\in Q\setminus P$. Let $R=\bigcup\{X\in\mathcal C:n\notin X\}$, so that $P\subseteq R\subseteq Q\setminus\{n\}$. Then $R\in V$, and $\mathcal C\cup\{R\}$ is a chain, so $R\in\mathcal C$. Likewise $R\cup\{n\}\in\mathcal C$, and $c(R)\ne c(R\cup\{n\})$.