The chromatic numbers of the Erdos-Hajnal graphs

Recall that a coloring $c:G\rightarrow\kappa$ of an (undirected) graph $(G,E)$ is said to be chromatic if $c(v_1)\neq c(v_2)$ whenever $\{v_1,v_2\}\in E$. Then, the chromatic number of a graph $(G,E)$ is the least cardinal $\kappa$ for which there exists a chromatic coloring $c:G\rightarrow\kappa$.
Motivated by a paper I found yesterday in the arXiv, this post will be dedicated to exemplifying incompactness properties of the chromatic number measure. More specifically, we shall give a construction of Shelah, of a graph of size $\lambda$ such that all of its subgraphs of size $<\lambda$ are countably chromatic, while the graph itself is not.

Before stating and proving Shelah’s theorem, we mention a somewhat simpler (yet, canonical) test-case. To every cardinal $\lambda$, one associates the Erdos-Hajnal graph $EH(\lambda)=({}^\lambda\omega,\bot)$, where $f\bot g$ stands for the set $\{ \alpha<\lambda\mid f(\alpha)=g(\alpha)\}$ being bounded in $\lambda$. Here is a list of fairly simple observations:

• if $\lambda$ is a regular cardinal, then any subgraph of $EH(\lambda)$ of size $<\lambda$ is countably chromatic;
• the chromatic number of $EH(\aleph_0)$ equals $2^{\aleph_0}$;
• the chromatic number of $EH(\aleph_2)$ is bigger than $\aleph_0$;
• if $(G,E)$ is a graph of size $\lambda$ such that every subgraph of size $<\lambda$ is countably chromatic, then the chromatic number of $EH(\lambda)$ is $\ge$ the chromatic number of $(G,E)$. This shows that $EH(\lambda)$ is a canonical witness to incompactness of this sort, whenever exists.
• why did I write “whenever exists” in the previous item? well, for instance, if $\lambda$ is a measurable cardinal, then every function $f:\lambda\rightarrow\omega$ is fixed on a measure one set, and hence $EH(\text{measurable})$ is countably chromatic!

Update (November, 2015): See the interesting discussion in the comments below.

Now, on to the theorem.

Theorem (Shelah, 2012).  Suppose that $\lambda$ is a regular cardinal $>\aleph_1$.
If $E^{\lambda}_\omega$ admits a non-reflecting stationary subset, and $\mu^{\aleph_0}\le\lambda$ for all $\mu<\lambda$, then there exists a graph $(G,E)$ of size $\lambda$ such that any of its subgraphs of size $<\lambda$ is countably chromatic, while $(G,E)$ is not countably chromatic.
In particular, the above assumptions entails that $EH(\lambda)$ is not countably chromatic.
Proof. Fix a regressive surjection $f:\lambda\rightarrow\lambda$ such that the preimage of every singleton is cofinal in $\lambda$. Denote $F_\delta:=\{\gamma<\lambda\mid f(\gamma)=\delta\}$.  Let $S\subseteq E^{\lambda}_\omega$ be a non-reflecting stationary subset, and put $T:=f^{-1}[S]$.
As the underlying set of our graph, we take: $$G:=\{ (\alpha,\beta)\in \lambda\times T\mid  \alpha<f(\beta)\}.$$

Next, we fix a club guessing sequence  $\langle C_\delta\mid\delta\in S\rangle$. For all $\delta\in S$, let $\{ \delta_n\mid n<\omega\}$ denote the increasing enumeration of $C_\delta$. Let $\Gamma_\delta$ denote the collection of all sequences $\langle \beta_n\mid n<\omega\rangle$ that satisfies for all $n<\omega$:

• $(\beta_{2n},\beta_{2n+1})\in G$;
• $\delta_n<\beta_{2n}<\beta_{2n+1}<\delta_{n+1}$.

As $|\delta|^{\aleph_0}\le\lambda=|F_\delta|$, we may fix a surjection $g_\delta:F_\delta\rightarrow\Gamma_\delta$.
Finally, the set of edges of the constructed graph will be:
$$E:=\left\{\{(\beta_{2m},\beta_{2m+1}),(\delta_0,\gamma)\}\mid m<\omega, \delta\in S, \gamma\in F_\delta, g_\delta(\gamma)=\langle\beta_n\mid n<\omega\rangle\right\}.$$

Subclaim. $(G,E)$ is not countably chromatic.
Proof. Suppose not, as witnessed by some coloring $c:G\rightarrow\omega$. For each $\tau<\lambda$, let $u_\tau:=\{ c(\alpha,\beta)\mid (\alpha,\beta)\in G, \alpha\ge\tau\}$. Then $\{ u_\tau\mid \tau<\lambda\}$ is a descending chain, and since $\text{cf}(\lambda)>\omega$, the chain must stabilize at some $\tau^*<\lambda$. Denote $u^*:=u_{\tau^*}$.
Consider the club$$D:=\{ \delta<\lambda\mid \forall\tau<\delta\forall n\in u^*\exists(\alpha,\beta)\in G\text{ with }\tau<\alpha<\beta<\delta\text{ s.t. }c(\alpha,\beta)=n\}.$$
Pick $\delta\in S$ such that $C_\delta\subseteq D\setminus\tau^*$.
It follows that we may find a sequence $\langle \beta_n\mid n<\omega\rangle$ such that for all $n<\omega$:

• $(\beta_{2n},\beta_{2n+1})\in G$;
• $\delta_n<\beta_{2n}<\beta_{2n+1}<\delta_{n+1}$;
• if $n\in u^*$, then $c(\beta_{2n},\beta_{2n+1})=n$.

Pick $\gamma\in F_\delta$ such that $g_\delta(\gamma)=\langle \beta_n\mid n<\omega\rangle$. Then for all $n<\omega$, we have $\{(\beta_{2n},\beta_{2n+1}),(\delta_0,\gamma)\}\in E$, and hence $c(\delta_0,\gamma)\neq c(\beta_{2n},\beta_{2n+1})$. In particular, $$c(\delta_0,\gamma)\in\omega\setminus u^*.$$
On the other hand, $\tau^*\le\delta_0<\gamma$, and so $c(\delta_0,\gamma)\in u_{\tau^*}=u^*$. This is a contradiction. $\blacksquare$

Write $G=\bigcup_{i<\lambda}G_i$, where $G_i:=\{ (\alpha,\beta)\in G \mid f(\beta)<i\}$.

Note. if $i\not\in S$, then $G_{i+1}=G_i$.
Proof. If $(\alpha,\beta)\in G_{i+1}$, then $\beta\in T$ and $f(\beta)<i+1$. As $f(\beta)\in S$, while $i\not\in S$, we infer that $f(\beta)<i$, and so $(\alpha,\beta)\in G_i$. $\blacksquare$

Note also that if $(\alpha,\beta)\in G$, then $(\alpha,\beta)\in G_\beta\setminus G_{\alpha+1}$.

Main subclaim. Suppose that $u$ is an infinite subset of $\omega$.
Then, for every $i\le j<\lambda$ with $i\not\in S$, and a chromatic coloring $c:G_i\rightarrow\omega$, there exists a chromatic coloring $c’:G_j\rightarrow\omega$ such that $c’\restriction G_i=c$, and $c'[G_j\setminus G_i]\subseteq u$.
Proof. Given $u\in[\omega]^\omega$, let $\{ u_n\mid  n<\omega\}$ be some partition of $u$ into mutually-disjoint infinite sets. We now prove the claim by induction on $j<\lambda$.

$\blacktriangleright$ The case $j=0$ is trivial. $\blacktriangleleft$

$\blacktriangleright$ If $j$ is a limit non-zero ordinal, let us pick a club $e$ in $j$ such that $\min(e)=i$. As $S$ is non-reflecting, we may moreover assume that  $e\cap S=\emptyset$.
Now, build an ascending chain of chromatic colorings $\{ c_k:G_k\rightarrow\omega\mid k\in e\}$ by induction on $k\in e$:

• for $k=\min(e)$, let $c_k:=c$;
• for $k\in\text{nacc}(e)$, let $i’:=\sup(e\cap k)$, and $j’:=k$. Then $i'<j'<j$, and $i’\not\in S$, so by the induction hypothesis, we may pick a chromatic coloring $c_k:G_k\rightarrow\omega$ that extends $c_{i’}$, and such that $c_k[G_k\setminus G_{i’}]\subseteq u$.
• for $k\in\text{acc}(e)$, let $c_k:=\bigcup_{i'<k}c_{i’}$. Then $c_k$ is chromatic as the limit of chromatic colorings.

Finally, put $c’:=\bigcup_{k<j}c_k$. Then $c’$ has all the desired properties. $\blacktriangleleft$

$\blacktriangleright$ If $j$ is a successor ordinal, and $j-1\not\in S$, then $G_j=G_{j-1}$, and so we may appeal to the induction hypothesis for $j-1$. $\blacktriangleleft$

$\blacktriangleright$ If $j$ is a successor ordinal, and $j-1\in S$, let us denote $\delta:=j-1$. Since $i\le\delta$ and $i\not\in S$, we get that $i<\delta$, so let us fix a large enough $n^*<\omega$ so that $\delta_{n^*}\ge i$.
Let

• $j(n):=\delta_{(n^*+n)}+1$ for all $n<\omega$;
• $i(0):=i$, and $i({n+1}):=j(n)$ for all $n<\omega$.

Note that for all $n<\omega$, we have $i\le i(n)<j(n)<j$ and $i(n)\not\in S$.
So it follows from the induction hypothesis, that there exists an increasing chain of chromatic colorings  $\{ c_n:G_{j(n)}\rightarrow\omega\mid n<\omega\}$ that extends $c$, and such that $c_{n}[G_{j(n)}\setminus G_{i(n)}]\subseteq u_{n}$, for all $n<\omega$. Note that $\text{dom}(\bigcup_{n<\omega}c_n)=G_\delta$.
Finally, let $c’:G_j\rightarrow \omega$ be some coloring that satisfies:

• $c’\restriction G_\delta=\bigcup_{n<\omega}c_n$;
• for every $\gamma\in F_\delta$, if $g_\delta(\gamma)=\langle \beta_n\mid n<\omega\rangle$, then $$c'(\delta_0,\gamma)\in u_0\setminus\{ c(\beta_{2m},\beta_{2m+1})\mid m<n^*\}.$$

We need to verify that $c’$ is chromatic.
For this, fix $x,y\in G_j$ such that $\{x,y\}\in E$, and let us verify that $c'(x)\neq c'(y)$.
Of course, we may assume that $\{ x,y\}\setminus G_\delta\not=\emptyset$, because otherwise $\{ x,y\}\subseteq\text{dom}(c_n)$ for some $n<\omega$.

Next, by the definition of $E$, there exists $\delta^*\in S$, $m<\omega$, and $\gamma<\lambda$ such that:

• $f(\gamma)=\delta^*$;
•  $g_{\delta^*}(\gamma)=\langle\beta_n\mid n<\omega\rangle$;
• $\{ x,y\}=\{ (\beta_{2m},\beta_{2m+1}) , (\delta^*_0,\gamma) \}$.

As $(\beta_{2m},\beta_{2m+1})\in G_j$, we know that $f(\beta_{2m+1})\le\delta$. In addition, $f(\beta_{2m+1})\neq\delta$, because otherwise $j=\delta+1=f(\beta_{2m+1})+1\le\beta_{2m+1}<\delta^*_{m+1}<\delta^*=f(\gamma)$, contradicting the fact that $(\delta^*_0,\gamma)\in G_j$.

So $f(\beta_{2m+1})<\delta$, that is $(\beta_{2m},\beta_{2m+1})\in G_\delta$, and since $\{x,y\}\setminus G_\delta\neq\emptyset$, we conclude that $f(\gamma)=\delta$, and $(\delta^*_0,\gamma)=(\delta_0,\gamma)$.

Now, if $m<n^*$, then by the very choice of $c’$, we have $$c'(\delta_0,\gamma)\in u_0\setminus \{c(\beta_{2m},\beta_{2m+1})\}.$$

If $m\ge n^*$, then $n:=m-n^*$ is a natural number, and so $$\delta_m<\beta_{2m}<\beta_{2m+1}<\delta_{m+1}$$ entails
$$i(n+1)=j(n)=\delta_m+1\le\beta_{2m}<\beta_{2m+1}<\delta_{m+1}<j(n+1).$$
Since $(\beta_{2m},\beta_{2m+1})\in G$, we get that $i(n+1)\le \beta_{2m}<f(\beta_{2m+1})$. Since $f$ is regressive, we get that $f(\beta_{2m+1})<\beta_{2m+1}<j(n+1)$. Altogether, $$(\beta_{2m},\beta_{2m+1})\in G_{j(n+1)}\setminus G_{i(n+1)},$$ and hence $$c'(\beta_{2m},\beta_{2m+1})\in u_{n+1}.$$
In particular, $$c'(\beta_{2m},\beta_{2m+1})\not\in u_0.$$This concludes the last case. $\blacktriangleleft$
This completes the proof of the main submclaim. $\blacksquare$

It follows from the main subclaim that for every $i<\lambda$, the subgraph $(G_i,E\restriction [G_i]^2)$ is countably chromatic. As $\lambda$ is regular, this in particular entails that every subgraph of $(G,E)$ of size $<\lambda$ is countably chromatic. $\blacksquare$

Corollary. If $\lambda$ is a strong limit singular cardinal, and $EH(\lambda^+)$ is countably chromatic, then $0^\sharp$ exists.
Proof. The covering lemma implies $\lambda^{\aleph_0}\le\lambda^+$ and $\square_\lambda$ for every strong limit singular cardinal $\lambda$. $\square_\lambda$ implies that every stationary subset of $\lambda^+$ admits a non-reflecting stationary subset. $\blacksquare$

The preceding is of no surprise, as previously Todorcevic proved that if $\lambda$ is an infinite cardinal and $EH(\lambda)$ is countably chromatic, then $\lambda\rightarrow(\omega_1)^{<\omega}_{\omega_1,\omega}$.

We conclude this post by providing proofs to several easy facts (some of which were mentioned in the introduction).

Fact. if $\lambda$ is a regular cardinal, then any subgraph of $EH(\lambda)$ of size $<\lambda$ is countably chromatic.
Proof. Suppose that $\lambda$ is a regular cardinal, and $\mathcal F$ is a family of less than $\lambda$ many functions from $\lambda$ to $\omega$. For $f,g\in\mathcal F$ such that $f\bot g$, denote $$\Delta(f,g):=\min\{ \gamma<\lambda\mid \text{dom}(f\cap g)\subseteq\gamma\}.$$ Let $\gamma:=\sup\{ \Delta(f,g)\mid f,g\in\mathcal F, f\bot g\}$. As $|\mathcal F|<\text{cf}(\lambda)$, we get that $\gamma<\lambda$. Define $c:\mathcal F\rightarrow\omega$ by letting $c(f):=f(\gamma)$ for all $f\in\mathcal F$. Now, if $f,g\in\mathcal F$ and $f\bot g$, then $f(\gamma)\neq g(\gamma)$ for all $\gamma\ge\Delta(f,g)$ and hence $c$ is a chromatic coloring. $\blacksquare$

Fact. If $(G,E)$ is a graph  of size $\lambda$ such that every subgraph of size $<\lambda$ is countably chromatic, then the chromatic number of $EH(\lambda)$ is $\ge$ the chromatic number of $(G,E)$.
Proof. Without loss of generality, $G=\lambda$. For every $\gamma<\lambda$, let $c_\gamma:\gamma\rightarrow\omega\setminus\{0\}$ exemplify that $(\gamma,E\cap[\gamma]^2)$ is countably chromatic.
Next, for all $\alpha<\lambda$, define $f_\alpha\in{}^\lambda\omega$ by letting for all $\gamma<\lambda$:$$f_\alpha(\gamma):=\begin{cases}0,&\gamma<\alpha\\g_{\gamma+1}(\alpha),&\text{otherwise}\end{cases}.$$Note that if $\{\alpha,\beta\}\in E$, then $f_\alpha\bot f_\beta$ (indeed, $\Delta(f_\alpha,f_\beta)\le\min\{\alpha,\beta\}$). So, $\alpha\mapsto f_\alpha$ is a graph homomorphism, and the chromatic number of $EH(\lambda)$ is $\ge$ the one of $(G,E)$. $\blacksquare$

Corollary. The chromatic number of $EH(\aleph_1)$ is at least $\aleph_1$. $\blacksquare$

Fact. The chromatic number of $EH(\aleph_0)$ equals $2^{\aleph_0}$.
Proof. Clearly, the chromatic number of $EH(\aleph_0)$ is $\le2^{\aleph_0}$. Next, fix an injection $\psi:[\omega]^{<\omega}\rightarrow\omega$. For every $X\subseteq\omega$, let $f_X:\omega\rightarrow\omega$ be the function defined by $f_X(n):=\psi(X\cap n)$, for all $n<\omega$. Notice that if $X,Y$ are distinct infinite subsets of $\omega$, then $f_X\bot f_Y$. It follows that any chromatic coloring of $EH(\omega)$ must be injective over $\{ f_X\mid X\in[\omega]^\omega\}$, and hence the chromatic number of $EH(\omega)$ equals $2^{\aleph_0}$. $\blacksquare$

Fact. Suppose that $\mathbb T:=\langle T,\le\rangle$ is an $\aleph_1$-tree. Let $G(\mathbb T)$ denote the comparability graph of $\mathbb T$. If $G(\mathbb T)$ is countably chromatic, then $T$ is a special Aronszajn tree.
Proof. Recall that $G(\mathbb T)=(T,E)$, where $E=\{ \{x,y\}\in[T]^2\mid x\le y\text{ or }y\le x\}$. Now, if $C\subseteq T$ is a chain, then any chromatic coloring of $G(\mathbb T)$ must be injective over $C$. In particular, if $G(\mathbb T)$ is countably chromatic, then $\mathbb T$ is Aronszajn. Moreover, if $c:T\rightarrow\omega$ is a chromatic coloring, then it is easy to construct an order-preserving function $o:T\rightarrow\mathbb Q$. Simply define $o$ for all $x\in T$ by induction on $c(x)$, while insuring that $o[c^{-1}\{n\}]$ is finite for all $n<\omega$. $\blacksquare$

Trivia. Todorcevic proved that after Levy collapsing a supercompact to $\omega_2$, the following statement holds in the extension. If $\langle T,\le\rangle$ is a tree for which $G(T,\le)$ is not countably chromatic, then some subtree $T’\in[T]^{\aleph_1}$ already has the property that $G(T’,\le)$ is not countably chromatic.