Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
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

2 Answers 2

up vote 9 down vote accepted

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.

share|improve this answer
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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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