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

Can you build a probabilistic scheme for colouring each edge (independently of all other edges) of the complete graph G on the positive integers such that the probability that G contains an infinite monochromatic complete subgraph is neither 0 nor 1?

share|cite|improve this question
The question has been answered, but I'm still confused. Isn't Ramsey's theorem exactly the statement that there is always a infinite monochromatic complete subgraph, so that the probability would be identically 1? – Tom Church Oct 28 '09 at 5:28
Well the infinite Ramsey theorem holds if you use only finitely many colours, but there is no such assumption here. Does that help? – Randomblue Oct 28 '09 at 10:29
up vote 8 down vote accepted

It seems like this would go against the Kolmogorov 0-1 law.. If we let Xi denote the coloring of all of the edges from i to integers larger than i, wouldn't the existence of an infinite monochromatic subgraph be a tail event?

share|cite|improve this answer
I didn't know the definition of a tail event, nor did I know Kolmogorow's 0-1 law. But yeah, it's seems you are right... Disappointing. – Randomblue Oct 27 '09 at 18: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.