6
$\begingroup$

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?

$\endgroup$
2
  • $\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, 2009 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, 2009 at 10:29

1 Answer 1

9
$\begingroup$

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?

$\endgroup$
1
  • $\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, 2009 at 18:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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