3
$\begingroup$

A hypergraph $H=(V,E)$ consists of a set $V$ and $E\subseteq {\mathcal P}(V)$, that is, $E$ consists of subsets of $V$ of arbitrary size. Obviously, a graph is a special kind of hypergraph.

Let $H=(V,E)$ be a hypergraph and $\kappa\neq \emptyset$ be a cardinal. Then a map $c:V\to \kappa$ is said to be a coloring if for every $e\in E$ with $|e|\geq 2$ we have that the restriction $c\restriction_e$ is non-constant. The chromatic number $\chi(H)$ of $H$ is the smallest cardinal $\kappa$ such there is a colouring $c:V\to \kappa$.

Question. What is $\chi(\mathbb{R}, E)$ where $E$ consists of all uncountable Lebesgue-measurable sets?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
9
$\begingroup$

It is continuum. The coloring with continuum many colors is clear (all points may have different color). Assume that we have $\kappa<c$ colors. Consider the Cantor set $K$. All its subsets are Lebesgue measurable. If some color contains uncountably many points from $K$, it constitutes a monochromatic edge. So, each color contains at most $\omega$ points from $K$, and totally $|K|\leqslant w\cdot \kappa=\kappa$, a contradiction.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ What if one removes the measure-$0$ sets? $\endgroup$
    – LSpice
    Commented Apr 21, 2021 at 12:25
  • 4
    $\begingroup$ @LSpice then it changes dramatically: it is 2. Take a Hamel basis over $\mathbb{Q}$, denote by $f(x)$ a coordinate functional and use two colors: $\lfloor f(x)\rfloor$ is even or odd. $\endgroup$
    – Fedor Petrov
    Commented Apr 21, 2021 at 12:28
  • 1
    $\begingroup$ Cool subquestion @LSpice and impressively quick answer Fedor!! $\endgroup$
    – Dominic van der Zypen
    Commented Apr 21, 2021 at 12:30

You must log in to answer this question.

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