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.

  • $\begingroup$ 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. $\endgroup$ Oct 27 '09 at 17:15
  • $\begingroup$ Er, an infinite monochromatic complete subgraph, that is. $\endgroup$ Oct 27 '09 at 17:16
  • $\begingroup$ 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. $\endgroup$
    – Randomblue
    Oct 27 '09 at 17:33

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.

  • $\begingroup$ 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? $\endgroup$
    – Randomblue
    Oct 29 '09 at 18:12
  • $\begingroup$ @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. $\endgroup$ Oct 29 '09 at 18:52
  • $\begingroup$ 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? $\endgroup$
    – user1447
    Nov 20 '09 at 17:34
  • $\begingroup$ It should have been countably infinite I think I have it right now $\endgroup$ 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.


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.