12
$\begingroup$

Hi

So there is an edge-colouring of a complete graph on R (the reals), with countably many colours that as no monochromatic triangle. To find it map R to (0,1) write the numbers in binary and if 2 numbers differ 1st in the kth digit use colour k.

Now this colouring has cycles of length 4. (1/4, 3/4, 1/3, 2/3 for example). You can get rid of cycles of length 4 by considering the 1st 2 binarary digits in which 2 numbers differ (and of course seperate colours if they only differ in 1 digit). Anyway my question is can we avoid cycles completely? i.e. does there exist a colouring of the complete graph on R such that there is no monochromatic cycle.

$\endgroup$
6
  • 1
    $\begingroup$ You should precise from the beginning that you are considering edge coloring. $\endgroup$ Aug 17, 2010 at 8:03
  • $\begingroup$ (@Benoît Kloeckner: Il y a un défaut tragique de traduction précise pour "préciser"; ici on dirait "specify" ou "clarify".) $\endgroup$
    – Tracy Hall
    Aug 17, 2010 at 9:01
  • 1
    $\begingroup$ If the color of an edge comes from the pair of first binary differences, wouldn't (1/5, 4/5, 1/6, 5/6) give a monochromatic 4-cycle? Or did I misunderstand your construction? $\endgroup$
    – Tracy Hall
    Aug 17, 2010 at 9:20
  • $\begingroup$ @Tracy: The 1st construction I gave has no 3 cycles but as you say does have 4-cycles. The question was weather there is a "better" colouring which does not have any cycles. $\endgroup$ Aug 17, 2010 at 15:56
  • 1
    $\begingroup$ @Jonathan: I was talking about the second, supposedly 4-cycle-free construction. The 4-cycle (1/5, 4/5, 1/6, 5/6) alternates between binary expansions starting .00 and .11, and so as I understood your edge-coloring each step would be colored {1,2}: a monochromatic 4-cycle. This seems to be a fundamental problem with the approach: if there is some pair of numbers $p$ and $q$ such that the rule coloring the edge from $p$ to $q$ depends on only the first digits (or neglects any digit at all), then changing a neglected digit of $p$ and a neglected digit of $q$ yields a monochromatic 4-cycle. $\endgroup$
    – Tracy Hall
    Aug 17, 2010 at 17:11

2 Answers 2

14
$\begingroup$

Turns out that the existence of such a coloring is equivalent to the continuum hypothesis. This was proved by Erdos and Kakutani in 1943 in the paper "On non-denumerable graphs". They prove:

A complete graph of cardinal number $m$ (that is, the cardinal number of the vertices is $m$) can be split up into a countable number of trees if and only if $m\le \aleph_1$.

$\endgroup$
2
  • $\begingroup$ Thank you very much for this reference ! I am trying to read the beginning of this paper [1], and I am stuck somewhere though. They are splitting all the intervals according to some notion of "length" (the $G_n$), then taking the union of all of them. Well, I do not get why there are not as many $G_n$ as $\omega_1$ :-/ Or does it mean that an initial section of a well ordered set of power $\omega_1$ is of cardinal at most $\omega_0 ? If you think some reading may be fitting in this case.. Thanks ! :-) [1] ams.org/bull/1943-49-06/S0002-9904-1943-07954-2/… $\endgroup$ Aug 17, 2010 at 10:29
  • 1
    $\begingroup$ Nathann, every initial segment of the ordinal $\omega_1$ is countable, if this is what you are asking. This is because $\omega_1$ is the smallest uncountable ordinal, by definition. $\endgroup$ Aug 17, 2010 at 11:28
4
$\begingroup$

Let me add to the above answer by noting that a stronger result holds and that, in the absence of the Continuum Hypothesis, the problems with the attempted construction of a 4-cycle-free coloring are unavoidable.

To fix notation, if $X$ is a set, $[X]^2$ is the set of 2-element subsets of $X$. We show that any coloring $c:[\omega_2]^2 \rightarrow \omega$ has a monochromatic 4-cycle. This will also give a shorter proof of the negative direction of the Erdos-Kakutani result mentioned above.

Fix $c:[\omega_2]^2 \rightarrow \omega$. For each $\omega_1 \leq \gamma < \omega_2$, find $n_\gamma < \omega$ such that $A^\gamma_{n_\gamma} := \{\alpha < \gamma \mid c(\{\alpha, \gamma\}) = n_\gamma\}$ is uncountable. Find a stationary $S \subseteq \omega_2$ and an $n^* < \omega$ such that, for all $\gamma \in S$, $n_\gamma = n^*$. For each $\gamma \in S$, let $\alpha_\gamma = \min(A^\gamma_{n^*})$, and let $\beta_\gamma = \min(A^\gamma_{n^*} \setminus (\alpha_\gamma + 1))$. By Fodor's Lemma, we can find $\alpha^* < \beta^* < \omega_2$ and a stationary $T \subseteq S$ such that, for all $\gamma \in T$, $(\alpha_\gamma, \beta_\gamma) = (\alpha^*, \beta^*)$. Fix $\gamma < \delta$, both in $T$. Then $c(\{\alpha^*, \gamma\}) = c(\{\gamma, \beta^*\}) = c(\{\beta^*, \delta\}) = c(\{\delta, \alpha^*\}) = n^*$, giving us a monochromatic 4-cycle.

$\endgroup$
3
  • 1
    $\begingroup$ Erdos and Kakutani ask at the end of that beautiful 1943 paper whether if CH fails, and the sets $M_n$ consist of rationally independent numbers, then $\bigcup M_n$ has inner measure 0. Was this ever answered? $\endgroup$
    – Avshalom
    May 10, 2015 at 10:22
  • $\begingroup$ @Avshalom This looks true to me. If you ask this as a separate question I will try to check the details and write an answer. $\endgroup$
    – Ashutosh
    May 10, 2015 at 21:28
  • $\begingroup$ @Ashutosh Question posted; looking forward to your answer! $\endgroup$
    – Avshalom
    May 11, 2015 at 12:44

Your Answer

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

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