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$
$\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 ChurchCommented 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$– RandomblueCommented Oct 28, 2009 at 10:29
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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?
answered Oct 27, 2009 at 18:19
-
$\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$ Commented Oct 27, 2009 at 18:28