7
$\begingroup$

The famous De Bruijn–Erdős theorem and its hypergraphs generalization states the following.

Theorem. Let $V$ be a set, and $E\subset2^V$ be a family of its subsets. Assume that every $e \in E$ is finite and that for some $k \in \mathbb{N}$, every finite sub-hypergraph of $H=(V,E)$ can be properly colored with $k$ colors. Then $H$ can also be properly colored with $k$ colors.

It looks like that the standard proof based on Tychonoff's theorem doesn't work when the edges are allowed to be infinite. So, I wonder if the following analogue of De Bruijn–Erdős theorem holds.

Let $V$ be a set, and $E\subset2^V$ be a family of its subsets. Assume that every $e \in E$ is countable. Moreover, assume that for some $k \in \mathbb{N}$ and for every countable $W \subset V$, the hypergraph $H(W)= (W,E(W))$ can be properly colored with $k$ colors, where $E(W) = \{e \in E: e \subset W\}$. Then $H=(V,E)$ can also be properly colored with $k$ colors.

Erdős and Hajnal proved in [EH] the following related result on families of bounded intersections.

Theorem. Let $V$ be a set, and $E\subset2^V$ be a family of its subsets. Assume that every $e \in E$ is countably infinite. Moreover, assume that there exists $m \in \mathbb{N}$ such that $|e_1\cap e_2|<m$ for all $e_1,e_2 \in E$. Then $H=(V,E)$ can be properly colored with $2$ colors.

Can this result be strengthened as follows to deal with all families of finite intersections?

Let $V$ be a set, and $E\subset2^V$ be a family of its subsets. Assume that every $e \in E$ is countably infinite, and that $e_1\cap e_2$ is finite for all $e_1,e_2 \in E$. Then $H=(V,E)$ can be properly colored with $2$ colors.

[EH] P. Erdős & A. Hajnal, On a property of families of sets, Acta Math. Academiae Scientiarum Hungarica, 12, 87–123 (1964).

$\endgroup$
3
  • $\begingroup$ There is something wrong with the statement of the second theorem. As written, it implies that all graphs, and all finite hypergraphs, are $2$-colourable, which is obviously nonsense. $\endgroup$ Commented Nov 1, 2022 at 14:04
  • $\begingroup$ @EmilJeřábek Somehow I thought that the set can be called 'countable' only if it is infinite, which is not true. I corrected the statements. Thanks! $\endgroup$ Commented Nov 1, 2022 at 14:23
  • $\begingroup$ Oh, I see. Thanks for the clarification. $\endgroup$ Commented Nov 1, 2022 at 14:48

2 Answers 2

5
$\begingroup$

The answer to the first question is also no, by a minor modification of the proof of the Elekes-Hoffmann result cited in the answer to the second question. In fact, we get the following:

Theorem There is a set $V$ of cardinality $2^{\aleph_0}$ and a collection $E$ of countably infinite subsets of $V$ such that, for every countable $W \subset V$, $H(W) = (W, E(W))$ is 2-colorable, but $H=(V,E)$ cannot be properly colored with countably many colors.

Proof Let $V$ be the collection of all functions of the form $f:\beta \rightarrow \omega$, where $\beta$ is a countable ordinal. For each such $f$, let $A_f$ be the set of all $n < \omega$ such that the preimage $f^{-1}(\{n\})$ is infinite. For each $n \in A_f$, let $e_{f,n} := \{f\} \cup \{f \restriction \alpha \mid \alpha \in f^{-1}(\{n\})\}$. Then let $E_f := \{e_{f,n} \mid n \in A_f\}$. Note that each element of $E_f$ is countably infinite and has a maximal element, namely $f$ itself. Finally, let $E := \bigcup_{f \in V} E_f$.

Let us first show that $H(W)$ is 2-colorable for every countable $W \subset V$. The point is that, for each such $W$, $E(W)$ is countable, since, by construction, $E(W) \subseteq \bigcup_{f \in W} E_f$, and each $E_f$ is countable. Therefore, one can enumerate both $W$ and $E(W)$ in order-type $\omega$ and use these enumerations to inductively define a coloring $c:W \rightarrow \{0,1\}$, diagonalizing against the elements of $E(W)$ to make sure none of them are monochromatic for $c$ (here we use the fact that every element of $E(W)$ is infinite).

We finally show that $H$ cannot be properly colored with countably many colors. Fix a function $c:V \rightarrow \omega$. We will show that it is not a proper coloring of $H$. Let us define a function $g:\omega_1 \rightarrow \omega$ by recursively specifying $g \restriction \beta$ for $\beta \leq \omega_1$. If $\beta \leq \omega_1$ is a limit ordinal and we have specified $g \restriction \alpha$ for all $\alpha < \beta$, then $g \restriction \beta = \bigcup_{\alpha < \beta} g \restriction \alpha$. For the successor step, suppose that we have constructed $g \restriction \beta$. To define $g \restriction (\beta + 1)$, we must define $g(\beta)$; do so by setting $g(\beta) = c(g \restriction \beta)$.

Let $A$ be the set of all $n < \omega$ such that $g^{-1}(\{n\})$ is unbounded in $\omega_1$, and let $\beta < \omega_1$ be large enough so that:

  • for all $\alpha < \omega_1$, if $g(\alpha) \notin A$, then $\alpha < \beta$; and
  • for all $n \in A$, $g^{-1}(\{n\}) \cap \beta$ is infinite.

Let $n = g(\beta)$, and let $f = g \restriction \beta$. By construction, we have $n = c(g \restriction \beta) = c(f)$. By the first bullet point above, we know that $n \in A$. By the second bullet point, we know that $f^{-1}(\{n\})$ is infinite, so $n \in A_f$ and $e_{f,n} = \{f\} \cup \{f \restriction \alpha \mid \alpha \in f^{-1}(\{n\})$ is in $E$. But for every $\alpha \in f^{-1}(\{n\})$, we have $c(f \restriction \alpha) = c(g \restriction \alpha) = g(\alpha) = n = c(f)$, so $e_{f,n}$ is monochromatic for $c$, showing that $c$ is not a proper coloring of $H$.

$\endgroup$
3
  • 1
    $\begingroup$ Thanks for such a detailed answer! Since I asked two questions in one post, I'm not sure it would be fair to accept either yours or @domotorp answer, but I upvoted both :) $\endgroup$ Commented Nov 8, 2022 at 8:35
  • $\begingroup$ I think that you should definitely accept this one; my answer is just a link that was too long to be a comment. $\endgroup$
    – domotorp
    Commented Nov 8, 2022 at 10:10
  • $\begingroup$ @domotorp Considering this as your permission, done! $\endgroup$ Commented Nov 8, 2022 at 13:11
5
$\begingroup$

To your second question, the answer is no, see problem 18.19 in P. Komjáth, V. Totik: Problems and Theorems in Classical Set Theory where they cite G. Elekes, G. Hoffmann: On the chromatic number of almost disjoint families of countable sets, Coll. Math. Soc. J. Bolyai, 10 Infinite and Finite Sets, Keszthely (Hungary), 1973, 397–402 as a source. (I have this latter book in my office, in case you want it.)

$\endgroup$
1
  • 1
    $\begingroup$ Thanks for the references, the first book is great! Next time I'd check it before posting some set-theory question here :) $\endgroup$ Commented Nov 8, 2022 at 8:35

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.