Welcome to MathOverflow

Question

3

1

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 1/2^c, for c = 1, 2, ... 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.

flag	asked Oct 27 2009 at 16:38 Justin 1,336●3●13●25

	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 2009 at 17:15
	Er, an infinite monochromatic complete subgraph, that is. – Jonah Ostroff Oct 27 2009 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. – Justin Oct 27 2009 at 17:33

Kristal Cantwell · Accepted Answer · 2009-12-01 21:13:49Z UTC

6

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:

http://en.wikipedia.org/wiki/Random_graph

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

edited Dec 1 2009 at 21:13

answered Oct 29 2009 at 17:50

Kristal Cantwell
4,021●1●5●17

	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? – Justin Oct 29 2009 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 2009 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? – gmatt Nov 20 2009 at 17:34
	It should have been countably infinite I think I have it right now – Kristal Cantwell Dec 1 2009 at 21:14

Justin · Answer 2 · 2009-10-27 16:46:15Z UTC

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.

Infinite Ramsey theorem with infinitely many colours

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.