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

Clearly, it is possible to colour the edges of an infinite complete graph so that it does not contain any infinite monochromatic complete subgraph. Now what about the following?

Let $G$ be the complete graph with vertex set the positive integers. Each edge of $G$ is then coloured c with probability $\frac{1}{2^c}$, for $c = 1, 2, \dots$ What is the probability that G contains an infinite monochromatic complete subgraph?

It is unclear for me if the answer should be $0, 1$, or something in between.

share|cite|improve this question
You should probably clarify your first sentence. With an infinite number of colors, this is true (just make every edge a different color), but with a finite number of colors, there will always be a monochromatic complete subgraph. I was left scratching my head for a little while there. – Jonah Ostroff Oct 27 '09 at 17:15
Er, an infinite monochromatic complete subgraph, that is. – Jonah Ostroff Oct 27 '09 at 17:16
Sorry, I don't understand your two comments. My first sentence seems fine. Indeed, as you say, just take a different colour for each edge, and your graph will not contain any infinite monochromatic complete subgraph. – Randomblue Oct 27 '09 at 17:33
up vote 10 down vote accepted

Every countably infinite random graph is almost surely the Rado graph which contains all finite and countably infinite graphs as induced subsets. So each color class almost surely contains the Rado graph and hence a infinite monochromatic subgraph. See the following for more details here:

There are also links in the article to other articles including one on the Rado graph.

share|cite|improve this answer
Thanks. I was thinking of an alternate problem: Let G be the complete countable graph and let C be a countably infinite set of colours. Is it possible to devise a random process that picks a colour for each edge of G (the same process is used for each edge), independently of the other edges, such that the probability that G contains an infinite complete monochromatic subgraph is 0? – Randomblue Oct 29 '09 at 18:12
@Justin: Kristal's argument works whenever your random process picks some fixed color with positive probability. So your best bet is probably to find some compact topological group of countable cardinality and use the Haar measure on that as your "random process." But I don't know of such groups, and I'm not sure that one exists. – Harrison Brown Oct 29 '09 at 18:52
Kristal, I may be missing something, but when you say countably finite isn't that redundant, I mean all finite sets are countable by definition no? – user1447 Nov 20 '09 at 17:34
It should have been countably infinite I think I have it right now – Kristal Cantwell Dec 1 '09 at 21:14

Actually, I think the answer should be 1, by the standard two-pass proof of the infinite Ramsey theorem (with finitely many colours):

Take a vertex v. With probability 1 it is adjacent to infinitely many vertices w such that vw is coloured 1. Call S_1 the set of all such w. Repeat on S_1 to get S_2, etc.

share|cite|improve this answer

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.