7
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ The unordered graph on an Aronszajn tree is of cardinality $\aleph_1$. $\endgroup$
    – Eran
    Dec 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$
    – bof
    Dec 6, 2013 at 11:03

2 Answers 2

10
$\begingroup$

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.

$\endgroup$
1
  • 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$
    – Ben Barber
    Nov 29, 2013 at 13:50
6
$\begingroup$

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.

$\endgroup$

Your Answer

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

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