34
$\begingroup$

Here is a question I asked myself years ago. Since it is not really in my field, I hope to find some (partial) answers here... Since it was unclear, I precise that I am looking for an answer in ZFC, so using the axiom of choice if needed.

The chromatic number of a graph $G$ is the minimal cardinal of a partition of $G$ into independant sets, i.e. sets all of whose connected components are trivial. This definition of independant sets suggests that a good analogue of them in the setting of topological spaces would be totally disconected sets. This motivate the following definition:

Definition. Define the chromatic number of a topological space $X$, denoted by $\chi(X)$, as the minimal cardinal of a partition of $X$ into totally disconnected sets.

My main question is the following:

Question. What is the chromatic number of $\mathbb{R}^n$?

Some remarks. If $X$ can be embedded in $Y$, then $\chi(X) \leqslant \chi(Y)$. We also have that $\chi(X \times Y) \leqslant \chi(X)\chi(Y)$, because if $(A_i)_{i \in I}$ and $(B_j)_{j \in J}$ are respective partitions of $X$ and $Y$ into totally disconnected sets, then $(A_i \times B_j)_{(i, j) \in I \times J}$ is so for $X \times Y$. We also have that $\chi(\mathbb{R}) = 2$, witnessed by the partition $\{\mathbb{Q}, \mathbb{I}\}$, where $\mathbb{I}$ denote the set of irrational numbers. So $\chi(\mathbb{R}^n) \leqslant 2^n$.

But we have better. Actually, $\chi(\mathbb{R}^2) \leqslant 3$, witnessed by the partition $\{\mathbb{Q}^2, (\mathbb{Q} \times \mathbb{I} \cup \mathbb{I}\times \mathbb{Q}), \mathbb{I}^2\}$ (where $\mathbb{Q} \times \mathbb{I} \cup \mathbb{I}\times \mathbb{Q}$ is totally disconnected because it embeds into $\mathbb{I}^2$ via $(x, y) \mapsto (x + y, x - y)$). So $\chi(\mathbb{R}^{2n}) \leqslant 3^n$ and $\chi(\mathbb{R}^{2n + 1}) \leqslant 2 \times 3^n$.

My conjecture is that $\chi(\mathbb{R}^n) = n + 1$. For the upper bound, I suspect that some partition of the form $\{A_0, \ldots A_n\}$ where $A_i$ is the set of elements of $\mathbb{R}^n$ having exactly $i$ rational coordinates could work, but I don't manage to prove anything. For the lower bound, I only have an intuition given by the following "image": if you consider $A \subseteq \mathbb{R}^n$ totally disconnected, then it sounds reasonable to think that there exists a set $B\subseteq \mathbb{R}^n$, homeomorphic to $\mathbb{R}^{n - 1}$, passing "between" the points of $A$; however, this is just an inutuition and I don't know if it is true. I suspect that some algebraic topology would be needed to prove that, but I have almost no experience in this field so I couldn't investigate more; I am not even able to show that $\chi(\mathbb{R}^n) > 2$ for some $n$.

An other possibility would be that $\chi(\mathbb{R}^n) = 2$ for every $n$, because of some "weird" colouring. What makes me suspect that is that if we replace "connected" by "arcwise connected" in the definition of the chromatic number, then it becomes easy to build a partition of $\mathbb{R}^n$ into two parts each of which having no non-trivial arcwise connected subset, by a diagonal argument using the axiom of choice. However, this proof uses the fact that there are exactly $\mathfrak{c}$ arcs $\gamma : [0, 1] \longrightarrow \mathbb{R}^n$. To do the same proof for connected sets, we would need the existence of a family of $\mathfrak{c}$ non-trivial connected subsets of $\mathbb{R}^n$ such that every non-trivial connected subset of $\mathbb{R}^n$ has a subset in this family, and I don't think that such a family exists (but I don't know).

In case where we manage to prove that $\chi(\mathbb{R}^n) = 2$ thanks to some construction using the axiom of choice, it would be interesting to investigate what happens (still supposing choice) if we impose some restriction on the complexity of the sets in the partition, for example to be Borel.

$\endgroup$
  • $\begingroup$ So, are you asking the question without choice? $\endgroup$ – Asaf Karagila Feb 5 '18 at 14:24
  • $\begingroup$ @AsafKaragila OP is interested in the answer both using and without using the axiom of choice, I believe. $\endgroup$ – Wojowu Feb 5 '18 at 14:25
  • 2
    $\begingroup$ @JānisLazovskis Your partition doesn't work: the curve with polar equation $r = \theta$ is entierly contained in the first part of your partition. $\endgroup$ – N. de Rancourt Feb 5 '18 at 14:46
  • 4
    $\begingroup$ @AsafKaragila That's what I tried to do in my formlation of the question, I never asked anything without choice, but simply suggested that choice could play a role. Do you think that there is something unclear that I should modify? Only the last paragraph mentions the idea of restricting to Borel partitions, do you think I should remove it? $\endgroup$ – N. de Rancourt Feb 5 '18 at 15:09
  • 4
    $\begingroup$ You might be interested in Engelking "Dimension Theory". For example Lemma 1.5.2 might give lower bounds on the number of subsets needed to decompose $\mathbb{R}^n$. $\endgroup$ – HenrikRüping Feb 5 '18 at 15:30
30
$\begingroup$

The chromatic number $\chi(X)$ of a topological space $X$ is related to the separation dimension $t(X)$ introduced and studied by Steinke.

The separation dimension $t(X)$ is defined inductively:

$\bullet$ $t(\emptyset)=-1$

$\bullet$ $t(X)=0$ for any space $X$ of cardinality $|X|=1$;

$\bullet$ if $|X|\ge 2$, then $t(X)\le n$ for some $n\in\mathbb N$ if for each subspace $M\subset X$ with $|M|\ge 2$ there exists a set $A\subset M$ such that $t(A)<n$ and $M\setminus A$ is disconnected;

$\bullet$ $t(X)=n$ for some integer $n\ge 0$ if $t(X)\le n$ and $t(X)\not\le n-1$.

It is easy to see that $t(X)=0$ if and only if the space $X$ is totally disconnected.

In Proposition 3.1 of his paper Steinke proved the following

Sum Theorem: For any subspaces $A,B$ of a topological space the union $A\cup B$ has separation dimension $t(A\cup B)\le t(A)+t(B)+1$.

This theorem implies that $t(X)+1\le\chi(X)$ for any topological space $X$.

On the other hand, by the classical Decomposition Theorem of Urysohn (this is Theorem 7.3.9 in Engelking's book "General Topology"), for a metrizable space $X$ of finite dimension $Ind(X)$ the number $Ind(X)+1$ is equal to the smallest cardinality of a partition of $X$ into subsets of large inductive dimension zero.

Since spaces of large inductive dimension zero are totally disconnected, this decomposition theorem implies that $\chi(X)\le Ind(X)+1$ for any metrizable space $X$. Therefore, for any metrizable space $X$ of finite large inductive dimension, we obtain the inequalities:

$$t(X)+1\le \chi(X)\le Ind(X)+1.$$

In Corollary on page 279 of his paper, Stainke proves that for each locally compact paracompact space $X$ we have the inequalities

$$dim(X)\le t(X)\le ind(X)\le Ind(X).$$

Since $dim(X)=ind(X)=Ind(X)$ for any separable metrizable space $X$, we finally conclude that

$$dim(X)=t(X)=ind(X)=Ind(X)\quad\mbox{and}\quad\chi(X)=\dim(X)+1$$

for any locally compact separable metrizable space $X$.

In particular, we obtain the following theorem answering the question of N. de Rancourt.

Theorem 1. For every $n\in\mathbb N$ the Euclidean space $\mathbb R^n$ has chromatic number $\chi(\mathbb R^n)=n+1.$

For general separable metrizable spaces, we have the following upper bound, which can be interesting for Set Theorists.

Theorem 2. Each separable metrizable space $X$ has chromatic number $\chi(X)\le\omega_1$.

Proof. Choose a family $(D_\alpha)_{\alpha\in\omega_1}$ of pairwise disjoint dense sets in the real line $\mathbb R$. For every countable ordinal $\alpha$ consider the set $Z_\alpha=\mathbb R\setminus\bigcup_{\alpha\le\beta<\omega_1}D_\beta$ and observe that $(Z_\alpha)_{\alpha\in\omega_1}$ is an increasing transfinite sequence of zero-dimensional subspaces of $\mathbb R$ such that $\bigcup_{\alpha\in\omega_1}Z_\alpha=\mathbb R$.

Taking into account that the cardinal $\omega_1$ has uncountable cofinality, we can show that $\{Z_\alpha^\omega\}_{\alpha<\omega_1}$ is a cover of $\mathbb R^\omega$ by $\omega_1$ many zero-dimensional subspaces, which yields the upper bound $\chi(\mathbb R^\omega)\le\omega_1$.

Since each separable metrizable space embeds into $\mathbb R^\omega$, we finally obtain the desired upper bound $\chi(X)\le\chi(\mathbb R^\omega)\le\omega_1$.

This upper bound is attained for the Hilbert cube.

Theorem 3. The Hilbert cube $\mathbb I^\omega=[0,1]^\omega$ has chromatic number $\chi(\mathbb I^\omega)=\omega_1$.

Proof. The upper bound $\chi(\mathbb I^\omega)\le\omega_1$ was proved in Theorem 2 and the lower bound $\chi(\mathbb I^\omega)>\omega$ was proved by Krasinkiewicz (see also this paper).

$\endgroup$
  • $\begingroup$ Just a remark about choice (to the OP and to those interested). The proof of Theorem 1 is without choice, modulo the blackbox theorems used (which I suspect one can get in a fairly choice free in the cases of interest); the second proof certainly utilizes some choice, since $\omega_1$ need not be regular. $\endgroup$ – Asaf Karagila Feb 5 '18 at 18:21
  • 3
    $\begingroup$ I suspect that Theorem 1 uses some weak forms of choice (like countable or dependent choice), but this acceptable (I hope). $\endgroup$ – Taras Banakh Feb 5 '18 at 19:06
  • 1
    $\begingroup$ That is impressive ! And does it also answer the question in the case of partition by borelian ? (i.e. does the decomposition theorem of Urysohn can produce decomposition in borelian subsets ?) $\endgroup$ – Simon Henry Feb 5 '18 at 21:14
  • 4
    $\begingroup$ @SimonHenry Yes. This follows from the fact that each zero-dimensional set is contained in a zero-dimensional $G_\delta$-set (and this fact follows from Lavrentev Theorem). So, the Urysohn decomposition theorem implies that each metrizable separable space $X$ of dimension $n$ can be covered by $n+1$ zero-dimensional $G_\delta$-sets. $\endgroup$ – Taras Banakh Feb 5 '18 at 21:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.