Skip to main content
5 of 5
deleted 1 character in body
bof
  • 13.4k
  • 2
  • 43
  • 66

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

bof
  • 13.4k
  • 2
  • 43
  • 66