5
$\begingroup$

Let $X$ be a Polish space and let $G\in\mathbf{\Sigma}^1_1(X^2)$ be a graph on $X$, that is an irreflexive and symmetric relation on $X$.

Given a cardinal $\kappa$ we say that $G$ has chromatic number $\kappa$, in symbols $\chi(G)=\kappa$, if there is a function $\varphi\colon X\to Y$ for some Polish space $Y$ such that $|\varphi(X)|=\kappa$ and for every $y\in\varphi(X)$, we have that $\varphi^{-1}(y)$ is $G$-independent, meaning that $G\cap(\varphi^{-1}(y))^2=\varnothing$, and $\kappa$ is the least cardinal with this property. We say that $G$ has Borel chromatic number $\kappa$, in symbols $\chi_B(G)=\kappa$ if we additionally require $\varphi$ to be Borel (of course the fact that $Y$ is Polish is completely irrelevant in the definition of $\chi(G)$ and I'm only phrasing it this way to define $\chi_B(G)$ analogously).

Question: Does $\mathsf{ZFC}$ prove that $\chi(G)\in\{1,2,\ldots,\aleph_0,2^{\aleph_0}\}$? Of course the answer is positive under $\mathsf{CH}$ but that is hardly interesting.

Remarks:

  • If $\mathsf{CH}$ fails and there are no regularity assumption on $G$ then there are trivial counterexamples, fix $A\subseteq\Bbb R$ with $|A|=\aleph_1$ and let $G=A^2\setminus\Delta_\Bbb R$. Then $\chi(G)=\aleph_1$ but $G$ is not analytic.
  • The same question for $\chi_B(G)$ (or even for Baire measurable colourings) has a positive answer by the Kechris-Solecki-Todorcevic $G_0$-dichotomy.
  • $\chi(G)$ and $\chi_B(G)$ can be wildly different, there are examples with $\chi(G)=2$ ($G$ can even be taken to be acyclic) and $\chi_B(G)=2^{\aleph_0}$.
$\endgroup$
0

1 Answer 1

6
$\begingroup$

There is a counterexample due to Todorcevic. See Proposition 9.2 in Kechris, Solecki, Todorcevic, Borel Chromatic Numbers, Advances in Mathematics, Vol. 141, Issue 1, 1999, Pages 1-44

$\endgroup$

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.