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
    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
    Apr 21, 2021 at 12:28
  • 1
    $\begingroup$ Cool subquestion @LSpice and impressively quick answer Fedor!! $\endgroup$
    – Dominic van der Zypen
    Apr 21, 2021 at 12:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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