MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

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 2010 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 2010 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 2010 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 2010 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 2010 at 17:11
show 1 more comment

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 [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 2010 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 2010 at 11:28