# monochromatic cycle-free colouring of the complete graph on R?

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.

• You should precise from the beginning that you are considering edge coloring. – Benoît Kloeckner Aug 17 '10 at 8:03
• (@Benoît Kloeckner: Il y a un défaut tragique de traduction précise pour "préciser"; ici on dirait "specify" ou "clarify".) – Tracy Hall Aug 17 '10 at 9:01
• 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? – Tracy Hall Aug 17 '10 at 9:20
• @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. – Jonathan Kariv Aug 17 '10 at 15:56
• @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. – Tracy Hall Aug 17 '10 at 17:11

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$.
• Thank you very much for this reference ! I am trying to read the beginning of this paper , 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 ! :-)  ams.org/bull/1943-49-06/S0002-9904-1943-07954-2/… – Nathann Cohen Aug 17 '10 at 10:29 • 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. – Joel David Hamkins Aug 17 '10 at 11:28 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. • 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? – Avshalom May 10 '15 at 10:22