2
$\begingroup$

The De Bruijn–Erdős theorem states that when all finite subgraphs of a graph $G$ can be colored with $n$ colors, the same is true for the whole graph.

There is a natural notion of coloring for hypergraphs which is as follows. Let $H= (V, E)$ be a hypergraph, and let $\kappa\neq \emptyset$ be a cardinal. Then a map $c:V\to\kappa$ is said to be a (hypergraph) coloring if the restriction $c\restriction_e : e \to \kappa$ is non-constant whenever $e$ has more than $1$ element.

Is the following statement true?

Let $n>1$ be an integer, and let $H=(V,E)$ be a hypergraph such that for all finite $E_0\subseteq E$, the hypergraph $(V,E_0)$ can be colored with $n$ colors. Then $H$ can be colored with $n$ colors.

$\endgroup$

1 Answer 1

5
$\begingroup$

The space $X=\{1,\dots,n\}^V$ of all colorings (proper or not) of $H=(V,E)$ with $n$ colors is compact in the product topology. Given a finite set $F \subset E$, the set $K_{F}$ of proper colorings of $(V,F)$ is a closed set in $X$.

For any finite collection $F_1,\dots,F_k$ of finite subsets of $E$, the intersection $$\cap_{j=1}^k K_{F_j}=K_{\cup_{j=1}^k F_j}$$ is nonempty by the given hypothesis. Therefore, by compactness of $X$, the intersection $$\bigcap \{K_F : \, F \; \text{finite}, \; \, F \subset E \} $$ is nonempty, and any coloring in this intersection is a proper coloring of $H=(V,E)$.

$\endgroup$
1
  • $\begingroup$ Very cool - I would never have thought of applying compactness and Tikhonov here! $\endgroup$ Commented Oct 17, 2022 at 8:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.