Ramsey's Theorem - Infinite Ramsey Theorem

Infinite Ramsey Theorem

A further result, also commonly called Ramsey's theorem, applies to infinite graphs. In a context where finite graphs are also being discussed it is often called the "Infinite Ramsey theorem". As intuition provided by the pictorial representation of a graph is diminished when moving from finite to infinite graphs, theorems in this area are usually phrased in set-theoretic terminology.

Theorem: Let X be some countably infinite set and colour the elements of X(n) (the subsets of X of size n) in c different colours. Then there exists some infinite subset M of X such that the size n subsets of M all have the same colour.

Proof: The proof is given for c = 2. It is easy to prove the theorem for an arbitrary number of colours using a 'colour-blindness' argument as above. The proof is by (complete) induction on n, the size of the subsets. For n = 1,the statement is equivalent to saying that if you split an infinite set into two sets, one of them is infinite. This is evident. Assuming the theorem is true for n ≤ r, we prove it for n = r + 1. Given a 2-colouring of the (r + 1)-element subsets of X, let a₀ be an element of X and let Y = X\{a₀}. We then induce a 2-colouring of the r-element subsets of Y, by just adding a₀ to each r-element subset (to get an (r + 1)-element subset of X). By the induction hypothesis, there exists an infinite subset Y₁ within Y such that every r-element subset of Y₁ is coloured the same colour in the induced colouring. Thus there is an element a₀ and an infinite subset Y₁ such that all the (r + 1)-element subsets of X consisting of a₀ and r elements of Y₁ have the same colour. By the same argument, there is an element a₁ in Y₁ and an infinite subset Y₂ of Y₁ with the same properties. Inductively, we obtain a sequence {a₀,a₁,a₂,...} such that the colour of each (r + 1)-element subset (a_i(1),a_i(2),...,a_{i(r + 1)}) with i(1) < i(2) < ... < i(r + 1) depends only on the value of i(1). Further, there are infinitely many values of i(n) such that this colour will be the same. Take these a_i(n)'s to get the desired monochromatic set.