# Are hypergraphs $H=(V,E)$ with $|E|=|V|$ $2$-colorable?

A hypergraph $$H=(V,E)$$ consists of a set $$V$$ and a collection of subsets $$E \subseteq {\cal P}(V)$$. A coloring is a map $$c: V\to \kappa$$, where $$\kappa \neq \emptyset$$ is a cardinal, such that for every $$e\in E$$ with $$|e|\geq 2$$ the restriction $$c|_e$$ is non-constant.

Question. Is every hypergraph $$H=(V,E)$$ with $$|V|\geq \omega$$ and $$|E| = |V|$$ and $$|e| = |V|$$ for all $$e\in E$$ $$2$$-colorable?

Motivation of question. If we take $$V= \omega$$ and $$E$$ to be the collection of computable subsets of $$\omega$$, then the resulting hypergraph is $$2$$-colorable - and there are even "balanced" colorings of $$\omega$$, also referred to as computationally random bitstreams.

• Surely an infinite complete graph is a counterexample... – lambda Dec 25 '19 at 21:17
• Surely all two subsets of a three set will help form a counterexample. Gerhard "Maybe The Subsets Are Bigger?" Paseman, 2019.12.25. – Gerhard Paseman Dec 26 '19 at 2:48
• Sorry - forgot to add the condition that all members of $E$ have cardinality $|V|$ – Dominic van der Zypen Dec 26 '19 at 8:37
• Equivalently and more clearly: Let $S$ be an infinite set, e.g. $[0,1]$. Let $R$ be a region of $S\times S$ such that every vertical line has at least as many points inside as outside $R$. Can we color the horizontal lines in $S\times S$ red and blue so that each vertical line has both red and blue points in $R$? – Matt F. Dec 26 '19 at 11:27
• Nice reformulation, thanks @MattF.! – Dominic van der Zypen Dec 26 '19 at 13:30

This is essentially done by the Bernstein set construction: if one has $$\kappa$$ many sets each of size $$\kappa$$, then order them into ordinal $$\kappa$$ and recursively choose 2 points from each, so that all these points are distinct. That is, we have $$x_\alpha,y_\alpha\in A_\alpha$$ with all $$x_\alpha,y_\alpha$$ distinct. At the end, color each $$x_\alpha$$ red, each $$y_\alpha$$ green.