Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.


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

1 Answer 1

up vote 12 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|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] 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

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.