5
$\begingroup$

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$?

$\endgroup$

1 Answer 1

7
$\begingroup$

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}$.

$\endgroup$
5
  • $\begingroup$ Wonderful, thanks Lajos! Do you happen to know how to construct a triangle-free graph on any infinite ordinal $\kappa$ with chromatic number $\kappa$? $\endgroup$ Mar 4 at 14:38
  • 3
    $\begingroup$ @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. $\endgroup$ Mar 4 at 16:34
  • 1
    $\begingroup$ And in fact, by the Erdős–Rado theorem, if $\kappa$ is an infinite cardinal, $\chi(G_\kappa)=\min\{\lambda:2^\lambda\ge\kappa\}$. $\endgroup$
    – bof
    Mar 5 at 0:16
  • 1
    $\begingroup$ @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. $\endgroup$
    – bof
    Mar 5 at 0:21
  • $\begingroup$ 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\}$. $\endgroup$
    – bof
    Mar 6 at 22:39

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.