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.

This entry was posted in Blog, Expository and tagged , , , . Bookmark the permalink.

13 Responses to The chromatic numbers of the Erdos-Hajnal graphs

  1. Pingback: Assaf Rinot: On incompactness for chromatic number of graphs | Set Theory Talks

  2. saf says:

    A PDF file with lecture notes for today’s talk on this subject, is available here.

  3. X.Shi says:

    Great talk. I really enjoyed it.
    1. In the last case of the main subclaim, I feel it might be simpler just staying with $j-1$, instead of using $\delta$ for $j-1$.
    2. I am not familiar with club guessing sequence. I’d like to ask you next week about how to get the $\beta$-sequence.

    • saf says:

      Thanks a lot, Shi!
      1. The choice of $\delta$ is to allow to fluently speak about $\{ \delta_n \mid n<\omega\}$. 2. Here is a proof of this form of club-guessing. Suppose $\lambda=\text{cf}(\lambda)>\aleph_1$, and $S\subseteq E^\lambda_\omega$ is stationary. For every $\delta\in S$, pick a cofinal subset $A_\delta\subseteq\delta$ of order-type $\omega$. Given a club $C\subseteq\lambda$, denote $$(C)_\delta:=\{ sup(C\cap\gamma)\mid \gamma\in A_\delta\ \&\ \gamma>\min(C)\}.$$ Notice that as $C$ is a club, we get that $(C)_\delta\subseteq C$. Notice also that if $\delta\in\text{acc}(C)$, then $(C)_\delta$ is a cofinal subset of $\delta$ of order-type $\omega$.

      We claim that there exists a club $C\subseteq\lambda$ for which $\{ (C)_\delta\mid \delta\in S\}$ guesses clubs. That is, for every club $D\subseteq\lambda$, there exists some $\delta\in\text{acc}(C)\cap S$ such that $(C)_\delta\subseteq D$.

      Suppose not. Then there exists a decreasing and continuous chain of clubs $\langle C_i\mid i<\omega_1\rangle$ such that $C_0=\lambda$, and $$(C_i)_\delta\nsubseteq C_{i+1}$$ for all $\delta\in\text{acc}(C_i)\cap S$.

      As $\{ C_i\mid i<\omega_1\}$ is a decreasing chain, for all $\gamma<\lambda$, the sequence of ordinals $\langle \sup(C_i\cap\gamma)\mid i<\omega_1\rangle$ is weakly decreasing, and hence must stabilize at some $i_\gamma<\omega_1$. Put $C:=\bigcap_{i<\omega_1}C_i$. Then $C$ is a club, so let us fix some $\delta\in\text{acc}(C)\cap S$. Let $i:=\sup_{\gamma\in A_\delta}i_\gamma$. Then $i<\omega_1$, and $\sup(C_i\cap\gamma)=\sup(C_{i+1}\cap\gamma)$ for all $\gamma\in A_\delta$. It follows that $\delta\in\text{acc}(C_i)\cap S$ and $(C_i)_\delta=(C_{i+1})_\delta\subseteq C_{i+1}$, contradicting the choice of $C_{i+1}$. $\blacksquare$

  4. Mirna Dzamonja says:

    I very much liked this post. The two last facts have slightly easier proofs, it seems:
    the chromatic number of $EH(2^{\aleph_0})$: we don’t need $\psi$, just let $f_X(n)$ be the n-th element in the increasing enumeration of $X$. For the special Aronszajn trees: if we use the original definition that an $\aleph_1$ tree is special if it is a union of countably many antichains then the fact is really obvious.

    • saf says:

      Thanks a LOT Mirna! This is a fun subject!
      You are of course right – the claim about special Aronszajn trees is obvious. It is just that I was always under the impression that the definition of “speciality” of trees stemmed as an order-oriented concept, rather than a graph-theoretic one.
      About the countable X’s – this surely works for a clever choice of a family of $X$’s. If I’d naively take $X_0:=(\omega\setminus2)\cup\{0\}$ and $X_1:=(\omega\setminus2)\cup\{1\}$, then the corresponding enumerating functions will not be $\perp$-adjacent.

  5. Literature says:

    You seem to be unaware of the fact that thirty years earlier in Theorem 8 of

    Todorčević, S. On a conjecture of R. Rado. J. London Math. Soc. (2) 27 (1983), no. 1, 1–8

    a stronger result is proved. You seem also unaware of the fact that the chromatic number of $EH(\omega_1)$ is bigger than $\aleph_1$.

    • saf says:

      Are these results comparable? Todorcevic’s conclusion is stronger in the sense that the incompact graph is moreover a tree. On the other hand, it appears that the incompactness there is restricted only to subgraphs of size $\le\aleph_1$, whereas here incompactness is witnessed on any small subgraph.

      The fact about $EH(\aleph_1)$ is mentioned as the third bullet in the above introduction.

  6. Literature says:

    Yes the results are comparable! Did you read the proof? Did you notice Claims 1 and 2? Did you notice that Claim 2 asserts that all subtrees of size $

    • saf says:

      I just read the proof, and agree that Theorem 8 is stronger.
      So, the existence of a nonreflecting stationary subset of $E^\lambda_\omega$ entails a nonspecial tree of size $\lambda$ all of which smaller subtrees are special.

  7. Monroe Eskew says:

    The claim of Stevo must be mistaken (although I can’t find this assertion in the linked paper). If there is an aleph_1 dense ideal on aleph_1 and CH holds, then there is a uniform ultrafilter on aleph_1 such that the ultrapower of aleph_0 has only aleph_1 many equivalence classes. This induces a graph coloring of EH(aleph_1) in aleph_1 colors. This is the same argument as Foreman gives for what his model satisfies about EH(aleph_2).

    • saf says:

      Thanks, Monroe! This is stated right after Question 8.3 in here. Indeed, the linked paper provides another result, namely, that $EH(\aleph_2)$ is uncountably chromatic. The post has been corrected accordingly.

Leave a Reply

Your email address will not be published. Required fields are marked *