Welcome to MathOverflow

Question

8

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.

edited Aug 17 2010 at 9:18

Gjergji Zaimi
37.8k●2●75●151

asked Aug 17 2010 at 5:44

Jonathan Kariv
319●2●7

1

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

1

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

1

@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

Gjergji Zaimi · Accepted Answer · 2010-08-17 08:53:02Z UTC

12

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

answered Aug 17 2010 at 8:53

Gjergji Zaimi
37.8k●2●75●151

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

1

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

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.