# Two questions on infinite hypergraphs

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

• 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. Commented Nov 1, 2022 at 14:04
• @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! Commented Nov 1, 2022 at 14:23
• Oh, I see. Thanks for the clarification. Commented Nov 1, 2022 at 14:48

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

• 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 :) Commented Nov 8, 2022 at 8:35
• I think that you should definitely accept this one; my answer is just a link that was too long to be a comment. Commented Nov 8, 2022 at 10:10
• @domotorp Considering this as your permission, done! Commented Nov 8, 2022 at 13:11

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

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