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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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}$.

Improve this answer
$\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$
    – Dominic van der Zypen
    Commented 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$
    – Lajos Soukup
    Commented 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
    Commented 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
    Commented 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
    Commented Mar 6 at 22:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .