3
$\begingroup$

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

$\endgroup$
0

2 Answers 2

6
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Feb 22 at 22:20
  • 3
    $\begingroup$ 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. $\endgroup$
    – bof
    Feb 23 at 0:07
  • $\begingroup$ @bof that's a nice way to write it, thanks! I struggled to find a concise way to say what I wanted $\endgroup$ Feb 23 at 6:56
1
$\begingroup$

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

$\endgroup$

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.