0
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ Surely an infinite complete graph is a counterexample... $\endgroup$
    – lambda
    Commented Dec 25, 2019 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$ Commented Dec 26, 2019 at 2:48
  • $\begingroup$ Sorry - forgot to add the condition that all members of $E$ have cardinality $|V|$ $\endgroup$ Commented Dec 26, 2019 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$
    – user44143
    Commented Dec 26, 2019 at 11:27
  • $\begingroup$ Nice reformulation, thanks @MattF.! $\endgroup$ Commented Dec 26, 2019 at 13:30

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Beautiful, Péter! $\endgroup$ Commented Dec 26, 2019 at 16:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .