Conflict-free coloring of $\mathbb{R}$ with the Euclidean topology

Question

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

Answer 1

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

Answer 2

The fact that $\chi_\text{cf}(\mathbb R,\tau)=\aleph_0$ can be generalized as follows. Given a hypergraph $H=(V,E)$ let's say that a set $S\subseteq V$ is a dense set (or a vertex cover) if $S\cap e\ne\varnothing$ for every nonempty edge $e\in E$, and let $d(H)$ be the minimum cardinality of a dense set.

Proposition. Let $H=(V,E)$ be a hypergraph. If $E$ is closed under arbitrary unions (in particular if $E$ is a topology) then $d(H)\le\chi_\text{cf}(H)\le d(H)+1$.

Proof. To see that $\chi_\text{cf}(H)\le d(H)+1$, if $S$ is a dense set, color each vertex in $S$ with a different color, and use another color for any remaining vertices.

To see that $d(H)\le\chi_\text{cf}(H)$, consider a conflict-free coloring $c$ of $H$; we shall construct a dense set $S$ in which no two vertices have the same color.

Define transfinite sequences of edges $e_\alpha\in E$ and sets $S_\alpha\subseteq V$ as follows. Suppose $e_\mu$ and $S_\mu$ have already been defined for $\mu\lt\alpha$. Let $e_\alpha$ be the union of all edges $e\in E$ such that $e\cap S_\mu=\varnothing$ for all $\mu\lt\alpha$, and let $S_\alpha$ be the set of all vertices $v\in e_\alpha$ such that the color $c(v)$ occurs only once in $e_\alpha$.

Note that, if $e_\alpha\ne\varnothing$, then $S_\alpha\ne\varnothing$ because $c$ is conflict-free. It follows that the sequence $\langle e_\alpha\rangle$ is strictly decreasing ($\alpha\lt\beta\implies e_\beta\subseteq e_\alpha\setminus S_\alpha$) until we arrive at $e_\lambda=\varnothing$ for some $\lambda$. Then $S=\bigcup_{\mu\lt\lambda}S_\mu$ is a dense set, and no two vertices in $S$ have the same color.

Corollary. Let $H=(V,E)$ be a hypergraph. If $E$ is closed under arbitrary unions and $d(H)\ge\aleph_0$ then $\chi_\text{cf}(H)=d(H)$.