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.

  • 2
    $\begingroup$ Surely an infinite complete graph is a counterexample... $\endgroup$
    – lambda
    Dec 25 '19 at 21:17
  • 2
    $\begingroup$ Surely all two subsets of a three set will help form a counterexample. Gerhard "Maybe The Subsets Are Bigger?" Paseman, 2019.12.25. $\endgroup$ Dec 26 '19 at 2:48
  • $\begingroup$ Sorry - forgot to add the condition that all members of $E$ have cardinality $|V|$ $\endgroup$ Dec 26 '19 at 8:37
  • 2
    $\begingroup$ 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$? $\endgroup$
    – Matt F.
    Dec 26 '19 at 11:27
  • $\begingroup$ Nice reformulation, thanks @MattF.! $\endgroup$ 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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