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?
-
$\begingroup$ The unordered graph on an Aronszajn tree is of cardinality $\aleph_1$. $\endgroup$– EranDec 5, 2013 at 21:01
-
$\begingroup$ @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. $\endgroup$– bofDec 6, 2013 at 11:03
2 Answers
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.
-
2$\begingroup$ 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. $\endgroup$ Nov 29, 2013 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.