# Chromatic number of the infinite Erdős–Hajnal shift-graph

For any set $$X$$, let $$[X]^2= \big\{\{x,y\}: x\neq y \in X\big\}$$. Let $$\kappa$$ be an infinite cardinal. Let $$G_\kappa = ([\kappa]^2, E_\kappa)$$ where $$E_\kappa = \big\{\{a,b\}\in \big[[\kappa]^2\big]^2: \max(a) = \min(b)\big\}$$.

In $$\newcommand{\ZFC}{{\sf (ZFC)}}\ZFC$$, is $$\chi(G_\kappa) = \kappa$$ for all infinite cardinals $$\kappa$$?

## 1 Answer

It is not true: $$\chi(G_{2^\kappa})\le \kappa$$.

Indeed, let $$\{A_i:i<2^\kappa\}\subset [\kappa]^\kappa$$ be independent, i.e. $$A_i\setminus A_j\ne \emptyset$$ for $$\{i,j\}\in [2^\kappa]^2.$$

Define $$f:[2^\kappa]^2\to \kappa$$ as follows: $$f(x)=\min(A_{\max x}\setminus A_{\min x})$$.

Then $$f$$ is a good coloring of $$G_{2^\kappa}$$.

• Wonderful, thanks Lajos! Do you happen to know how to construct a triangle-free graph on any infinite ordinal $\kappa$ with chromatic number $\kappa$? Mar 4 at 14:38
• @DominicvanderZypen: Erdős and Rado constructed such graphs in "P. Erdős, R. Rado: A construction of graphs without triangles having pre-assigned order and chromatic number, J. London Math. Soc. 35 (1960), 445--448 ( MR25 #3853; Zentralblatt 97,164.)" old.renyi.hu/~p_erdos/1960-01.pdf By the way, you can download all of the papers of Erdős from the homepage of the Renyi Institute. Mar 4 at 16:34
• And in fact, by the Erdős–Rado theorem, if $\kappa$ is an infinite cardinal, $\chi(G_\kappa)=\min\{\lambda:2^\lambda\ge\kappa\}$.
– bof
Mar 5 at 0:16
• @DominicvanderZypen I don't have time to look it up now, but if I remember right, the Erdős–Hajnal example of a $\kappa$-chromatic graph of order $\kappa$ (an infinite cardinal) has vertices $(a,b,c)$ where $a\lt b\lt c\lt\kappa$ and edges $\{(a,b,d),(c,e,f)\}$ where $a\lt b\lt c\lt d\lt e\lt f\lt\kappa$. I seem to recall that they call this a Specker graph.
– bof
Mar 5 at 0:21
• For showing that $\chi(G_\kappa)\le\lambda\implies\kappa\le2^\lambda$ the Erdős–Rado theorem is overkill. If $f:[\kappa]^2\to\lambda$ is a proper vertex coloring of $G_\kappa$ then we can define an injection $F:\kappa\to\mathcal P(\lambda)$ by setting $F(\alpha)=\{f(\{\beta,\alpha\}):\beta\lt\alpha\}$.
– bof
Mar 6 at 22:39