Conflict-Free Coloring – Conflict-Free Coloring of $\mathbb{R}$ with the Euclidean Topology

gn.general-topologygraph theorygraph-coloringsinfinite-combinatorics

A hypergraph $H =(V, E)$ consists of a set $V$ and a set $E \subseteq {\cal P}(V)$ of subsets of $V$. A hypergraph coloring is a map $c: V\to \kappa$, where $\kappa \neq \emptyset$ is a cardinal and the restriction $c\restriction_e: e \to \kappa$ is non-constant whenever $e$ has more than $1$ element. The chromatic number $\chi(H)$ is the least cardinal $\kappa \neq \emptyset$ such that there is a coloring $c: V \to \kappa$.

The map $c:V\to \kappa$ is said to be a conflict-free if every (non-empty) edge $e\in E$ contains at least one vertex $v$ of a color unique in $e$, or more formally, if there is $v\in e$ such that $$e \;\cap\; \bigl(c^{-1}(\{c(v)\})\bigr) = \{v\}.$$ The conflict-free chromatic number $\chi_{\text{cf}}(H)$ is the least cardinal $\kappa \neq \emptyset$ such that there is a conflict-free coloring $c: V \to \kappa$.

(Conflict-free colorings were motivated by a frequency assignment problem in cellular networks, see the introduction of Pach and Tardos – Conflict-free colorings of graphs and hypergraphs.)

Of course, every conflict-free coloring is a coloring in the "traditional" sense, so $\chi(H) \leq \chi_{\text{cf}}(H)$.

Let $\tau$ be the Euclidean topology on $\mathbb{R}$. The chromatic number $\chi(\mathbb{R}, \tau)$ equals $2$ (see Chromatic number of a connected Hausdorff space).

Question. What is $\chi_{\text{cf}}(\mathbb{R},\tau)$?

Best Answer

By colouring every element of $\Bbb Q$ with a unique colour and every element of $\Bbb R\setminus\Bbb Q$ with the same colour (different from all the colours used so far), we see that $\chi_\mathrm{cf}(\Bbb R)\leq\aleph_0$.

But in fact $\aleph_0$ is a lower bound in any reasonable space.

Lemma 1: Let $X$ be a $T_1$ space with at least three points. Then $\chi_{\mathrm{cf}}(X)>2$.

Proof: Suppose for a contradiction $\chi_{\mathrm{cf}}(X)=2$ as witnessed by $c\colon X\to 2$. Let $x\in X$ be such that $c(x)\neq c(x')$ for all $x'\in X\setminus\{x\}$. But now we have that $X\setminus\{x\}$ is a monochromatic open set in $X$ with at least two points, a contradiction.

Lemma 2: Let $X$ be an infinite $T_1$ space. Then $\chi_{\mathrm{cf}}(X)\geq\aleph_0$.

Proof: Suppose for a contradiction $\chi_{\mathrm{cf}}(X)=n$ as witnessed by $c\colon X\to n$. Let $x_1\in X$ be such that $c(x)\neq c(x')$ for all $x'\in X\setminus\{x_1\}$. Now $c\upharpoonright X\setminus\{x_1\}$ witnesses that $\chi_{\mathrm{cf}}(X\setminus\{x_1\})\leq n-1$. Proceed inductively to find $x_1,\ldots,x_{n-2}$ so that $c\upharpoonright X\setminus\{x_1,\ldots,x_{n-2}\}$ witnesses that the latter space has conflict-free chromatic number at most $2$, which contradicts Lemma 1.

In conclusion $\chi_{\mathrm{cf}}(\Bbb R)=\aleph_0$.

Related Question