The chromatic numbers of the Erdos-Hajnal graphs

Recall that a coloring $c:G\to \kappa$ of an (undirected) graph $(G,E)$ is said to be chromatic if $c(v_1)\ne 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\to \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 ,\mathrm{\perp })$, where $f\mathrm{\perp }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({\mathrm{\aleph }}_0)$ equals $2^{{\mathrm{\aleph }}_0}$;
• the chromatic number of $EH({\mathrm{\aleph }}_2)$ is bigger than ${\mathrm{\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 \to \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 $>{\mathrm{\aleph }}_1$.
If $E_{\omega }^{\lambda }$ admits a non-reflecting stationary subset, and ${\mu }^{{\mathrm{\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 \to \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_{\omega }^{\lambda }$ 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  $⟨C_{\delta }\mid \delta \in S⟩$. For all $\delta \in S$, let $\{{\delta }_n\mid n<\omega \}$ denote the increasing enumeration of $C_{\delta }$. Let ${\mathrm{\Gamma }}_{\delta }$ denote the collection of all sequences $⟨{\beta }_n\mid n<\omega ⟩$ 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 {|}^{{\mathrm{\aleph }}_0}\le \lambda =|F_{\delta }|$, we may fix a surjection $g_{\delta }:F_{\delta }\to {\mathrm{\Gamma }}_{\delta }$.
Finally, the set of edges of the constructed graph will be:
$$E:=\{\{({\beta }_{2m},{\beta }_{2m+1}),({\delta }_0,\gamma )\}\mid m<\omega ,\delta \in S,\gamma \in F_{\delta },g_{\delta }(\gamma )=⟨{\beta }_n\mid n<\omega ⟩\}.$$

Subclaim. $(G,E)$ is not countably chromatic.
Proof. Suppose not, as witnessed by some coloring $c:G\to \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 }^{\ast }<\lambda$. Denote $u^{\ast }:=u_{{\tau }^{\ast }}$.
Consider the club$$D:=\{\delta <\lambda \mid \mathrm{\forall }\tau <\delta \mathrm{\forall }n\in u^{\ast }\mathrm{\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 }^{\ast }$.
It follows that we may find a sequence $⟨{\beta }_n\mid n<\omega ⟩$ 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^{\ast }$, then $c({\beta }_{2n},{\beta }_{2n+1})=n$.

Pick $\gamma \in F_{\delta }$ such that $g_{\delta }(\gamma )=⟨{\beta }_n\mid n<\omega ⟩$. Then for all $n<\omega$, we have $\{({\beta }_{2n},{\beta }_{2n+1}),({\delta }_0,\gamma )\}\in E$, and hence $c({\delta }_0,\gamma )\ne c({\beta }_{2n},{\beta }_{2n+1})$. In particular, $$c({\delta }_0,\gamma )\in \omega \setminus u^{\ast }.$$
On the other hand, ${\tau }^{\ast }\le {\delta }_0<\gamma$, and so $c({\delta }_0,\gamma )\in u_{{\tau }^{\ast }}=u^{\ast }$. This is a contradiction. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◼"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fc.svg">}$

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

Note. if $i\notin 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\notin S$, we infer that $f(\beta )<i$, and so $(\alpha ,\beta )\in G_i$. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◼"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fc.svg">}$

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\notin S$, and a chromatic coloring $c:G_i\to \omega$, there exists a chromatic coloring $c^{\prime }:G_j\to \omega$ such that $c^{\prime }\upharpoonright G_i=c$, and $c^{\prime }[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$.

$▸$ The case $j=0$ is trivial. $◂$

$▸$ 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=\mathrm{\varnothing }$.
Now, build an ascending chain of chromatic colorings $\{c_k:G_k\to \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^{\prime }:=sup(e\cap k)$, and $j^{\prime }:=k$. Then $i^{\prime }<j^{\prime }<j$, and $i^{\prime }\notin S$, so by the induction hypothesis, we may pick a chromatic coloring $c_k:G_k\to \omega$ that extends $c_{i^{\prime }}$, and such that $c_k[G_k\setminus G_{i^{\prime }}]\subseteq u$.
• for $k\in \text{acc}(e)$, let $c_k:=\bigcup _{i^{\prime }<k}{c}_{i^{\prime }}$. Then $c_k$ is chromatic as the limit of chromatic colorings.

Finally, put $c^{\prime }:=\bigcup _{k<j}{c}_k$. Then $c^{\prime }$ has all the desired properties. $◂$

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

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

• $j(n):={\delta }_{(n^{\ast }+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)\notin S$.
So it follows from the induction hypothesis, that there exists an increasing chain of chromatic colorings  $\{c_n:G_{j(n)}\to \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^{\prime }:G_j\to \omega$ be some coloring that satisfies:

• $c^{\prime }\upharpoonright G_{\delta }=\bigcup _{n<\omega }{c}_n$;
• for every $\gamma \in F_{\delta }$, if $g_{\delta }(\gamma )=⟨{\beta }_n\mid n<\omega ⟩$, then $$c^{\prime }({\delta }_0,\gamma )\in u_0\setminus \{c({\beta }_{2m},{\beta }_{2m+1})\mid m<n^{\ast }\}.$$

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

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

• $f(\gamma )={\delta }^{\ast }$;
•  $g_{{\delta }^{\ast }}(\gamma )=⟨{\beta }_n\mid n<\omega ⟩$;
• $\{x,y\}=\{({\beta }_{2m},{\beta }_{2m+1}),({\delta }_0^{\ast },\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})\ne \delta$, because otherwise $j=\delta +1=f({\beta }_{2m+1})+1\le {\beta }_{2m+1}<{\delta }_{m+1}^{\ast }<{\delta }^{\ast }=f(\gamma )$, contradicting the fact that $({\delta }_0^{\ast },\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 }\ne \mathrm{\varnothing }$, we conclude that $f(\gamma )=\delta$, and $({\delta }_0^{\ast },\gamma )=({\delta }_0,\gamma )$.

Now, if $m<n^{\ast }$, then by the very choice of $c^{\prime }$, we have $$c^{\prime }({\delta }_0,\gamma )\in u_0\setminus \{c({\beta }_{2m},{\beta }_{2m+1})\}.$$

If $m\ge n^{\ast }$, then $n:=m-n^{\ast }$ 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^{\prime }({\beta }_{2m},{\beta }_{2m+1})\in u_{n+1}.$$
In particular, $$c^{\prime }({\beta }_{2m},{\beta }_{2m+1})\notin u_0.$$This concludes the last case. $◂$
This completes the proof of the main submclaim. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◼"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fc.svg">}$

It follows from the main subclaim that for every $i<\lambda$, the subgraph $(G_i,E\upharpoonright [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. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◼"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fc.svg">}$

Corollary. If $\lambda$ is a strong limit singular cardinal, and $EH({\lambda }^{+})$ is countably chromatic, then $0^{\mathrm{♯}}$ exists.
Proof. The covering lemma implies ${\lambda }^{{\mathrm{\aleph }}_0}\le {\lambda }^{+}$ and ${\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}}_{\lambda }$ for every strong limit singular cardinal $\lambda$. ${\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}}_{\lambda }$ implies that every stationary subset of ${\lambda }^{+}$ admits a non-reflecting stationary subset. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◼"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fc.svg">}$

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 \to ({\omega }_1{)}_{{\omega }_1,\omega }^{<\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\mathrm{\perp }g$, denote $$\mathrm{\Delta }(f,g):=min\{\gamma <\lambda \mid \text{dom}(f\cap g)\subseteq \gamma \}.$$ Let $\gamma :=sup\{\mathrm{\Delta }(f,g)\mid f,g\in \mathcal{F},f\mathrm{\perp }g\}$. As $|\mathcal{F}|<\text{cf}(\lambda )$, we get that $\gamma <\lambda$. Define $c:\mathcal{F}\to \omega$ by letting $c(f):=f(\gamma )$ for all $f\in \mathcal{F}$. Now, if $f,g\in \mathcal{F}$ and $f\mathrm{\perp }g$, then $f(\gamma )\ne g(\gamma )$ for all $\gamma \ge \mathrm{\Delta }(f,g)$ and hence $c$ is a chromatic coloring. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◼"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fc.svg">}$

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 \to \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{array}{ll}0,& \gamma <\alpha \\ g_{\gamma +1}(\alpha ),& \text{otherwise}\end{array}.$$Note that if $\{\alpha ,\beta \}\in E$, then $f_{\alpha }\mathrm{\perp }{f}_{\beta }$ (indeed, $\mathrm{\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)$. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◼"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fc.svg">}$

Corollary. The chromatic number of $EH({\mathrm{\aleph }}_1)$ is at least ${\mathrm{\aleph }}_1$. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◼"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fc.svg">}$

Fact. The chromatic number of $EH({\mathrm{\aleph }}_0)$ equals $2^{{\mathrm{\aleph }}_0}$.
Proof. Clearly, the chromatic number of $EH({\mathrm{\aleph }}_0)$ is $\le 2^{{\mathrm{\aleph }}_0}$. Next, fix an injection $\psi :[\omega {]}^{<\omega }\to \omega$. For every $X\subseteq \omega$, let $f_X:\omega \to \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\mathrm{\perp }{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^{{\mathrm{\aleph }}_0}$. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◼"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fc.svg">}$

Fact. Suppose that $\mathbb{T}:=⟨T,\le ⟩$ is an ${\mathrm{\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\to \omega$ is a chromatic coloring, then it is easy to construct an order-preserving function $o:T\to \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$. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◼"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fc.svg">}$

Trivia. Todorcevic proved that after Levy collapsing a supercompact to ${\omega }_2$, the following statement holds in the extension. If $⟨T,\le ⟩$ is a tree for which $G(T,\le )$ is not countably chromatic, then some subtree $T^{\prime }\in [T{]}^{{\mathrm{\aleph }}_1}$ already has the property that $G(T^{\prime },\le )$ is not countably chromatic.