MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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.

share|cite|improve this question
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
up vote 14 down vote accepted

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$.

share|cite|improve this answer
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]… – 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.

share|cite|improve this answer
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
@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. – Ashutosh May 10 '15 at 21:28
@Ashutosh Question posted; looking forward to your answer! – Avshalom May 11 '15 at 12:44

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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