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?

  • $\begingroup$ 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? $\endgroup$ – Tom Church Oct 28 '09 at 5:28
  • $\begingroup$ Well the infinite Ramsey theorem holds if you use only finitely many colours, but there is no such assumption here. Does that help? $\endgroup$ – Randomblue Oct 28 '09 at 10:29

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?

  • $\begingroup$ 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. $\endgroup$ – Randomblue Oct 27 '09 at 18:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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