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

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

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

• Really all I'm saying without making it harder than it has to be is that there is a point $x_1$ with a unique colour in $\Bbb R$, so there is $x_2$ with a unique colour in $\Bbb R\setminus\{x_1\}$, so there is $x_3$ with a unique colour in $\Bbb R\setminus\{x_1,x_2\}$ and all those points have different colours. Feb 22 at 22:20
• More concisely, if an infinite $T_1$ space is coloured with finitely many colours, consider an infinite open set with a minimum number of colours, and delete a "uniquely coloured" point to get a contradiction.
– bof
Feb 23 at 0:07
• @bof that's a nice way to write it, thanks! I struggled to find a concise way to say what I wanted Feb 23 at 6:56

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