# How to show that the chromatic number > aleph_0

Let $V =\{ f | \exists _{\alpha<\omega_1} ( f:\alpha \rightarrow \mathbb{N} \wedge f$ is $1-1) \}$. We define $E\subseteq [V]^2$, such that $\forall_{f,g\in V } (<f,g>\in E \longleftrightarrow ( f\subseteq g \vee g\subseteq f))$. We need to show that the chromatic number of $G=(V,E)$ is bigger than $\aleph_ 0$. It is obvious why it cannot be $<\aleph_0$, but I'm having trouble showing that it cant be $=\aleph_0$. Could anyone help?

• The unordered graph on an Aronszajn tree is of cardinality $\aleph_1$. – Eran Dec 5 '13 at 21:01
• @Eran What is the unordered graph on an Aronszajn tree? And what do Aronszajn trees have to do with this question? The partially ordered set $P=(V,\subseteq)$ is a tree, but it is not an Aronszajn tree. – bof Dec 6 '13 at 11:03

Consider any coloring $\varphi:V\to\omega$. Construct a strictly decreasing sequence $\langle X_n:n\lt\omega\rangle$ in $\mathcal P(\mathbb N)$ and a strictly increasing sequence $\langle f_n:n\lt\omega\rangle$ in $V$ so that for each $n\in\omega$ we have:

• $\text{range}(f_n)\subset X_n$,
• $|X_n\setminus\text{range}(f_n)|=\aleph_0$,
• either $\varphi(f_n)=n$, or else $\varphi(f)\ne n$ for all $f\in V$ such that $f_n\subseteq f,\text{range}(f)\subset X_n$, and $|X_n\setminus\text{range}(f)|=\aleph_0$.

[The last condition means that, whenever we can, we take $f_n$ to be a vertex of color $n$.]

Let $f=\bigcup_{n\lt\omega}f_n\in V$ and let $n=\varphi(f)$. Then $\varphi(f_n)=n=\varphi(f)$, showing that $\varphi$ is not a proper coloring of $G$.

[Note that $\text{range}(f)\subseteq X=\bigcap_{n\lt\omega}X_n$, and $X_n\setminus X$ is infinite for every $n$ as the $X_n$ are strictly decreasing.]

P.S. In other words, the partially ordered set $P=(V,\subseteq)$ has the partition property $P\rightarrow(2)_{\omega}^1$.
A similar argument shows that $P\rightarrow(\omega)_{\omega}^1$, which in turn implies (according to something I read somewhere) that $P\rightarrow(\alpha)_{\omega}^1$ for every ordinal $\alpha\lt\omega_1$. [Posets $P$ such that $P\rightarrow(\omega)_{\omega}^1$ are called non-special, see this answer.]

P.P.S. To prove $P\rightarrow(\omega+1)_{\omega}^1$ we proceed as before except that, instead of trying to choose $f_n$ of color $n$, we try to choose $f_n$ of color $c_n$ where $\langle c_n:n\lt\omega\rangle$ is an enumeration of $\omega$ with each element repeated infinitely often.

• Perhaps this will help somebody else checking that this works: note that $\text{range}(f)\subseteq X=\bigcap_{m<\omega}X_n$, and $X_n \setminus X$ is infinite for every $n$ as the $X_m$ are strictly decreasing. – Ben Barber Nov 29 '13 at 13:50

There is a beautiful argument going back to, I think, Galvin.

Assume that $F:V\to\omega$ is a good coloring. By transfinite recursion define $f_\alpha:\alpha\to\omega$ as follows. $f_0=\emptyset$. If $\alpha$ is limit, set $f_\alpha=\bigcup\{f_\beta:\beta<\alpha\}$. If $f_\alpha$ is given, let $f_{\alpha+1}$ be that extension of it to $\alpha+1$ for which $f_{\alpha+1}(\alpha)=F(f_\alpha)$ holds. Now one can show that each $f_\alpha$ is in $V$ and $f_{\beta}\subseteq f_\alpha$ for $\beta<\alpha$. But then $\bigcup\{f_\alpha:\alpha<\omega_1\}$ would be an injection $\omega_1\to\omega$, an impossibility.