Ramsey's Theorem - Proof of The Theorem

Proof of The Theorem

First we prove the theorem for the 2-colour case, by induction on r + s. It is clear from the definition that for all n, R(n, 1) = R(1, n) = 1. This starts the induction. We prove that R(r, s) exists by finding an explicit bound for it. By the inductive hypothesis R(r − 1, s) and R(r, s − 1) exist.

Claim: R(r, s) ≤ R(r − 1, s) + R(r, s − 1): Consider a complete graph on R(r − 1, s) + R(r, s − 1) vertices. Pick a vertex v from the graph, and partition the remaining vertices into two sets M and N, such that for every vertex w, w is in M if (v, w) is blue, and w is in N if (v, w) is red.

Because the graph has R(r − 1, s) + R(r, s − 1) = |M| + |N| + 1 vertices, it follows that either |M| ≥ R(r − 1, s) or |N| ≥ R(r, s − 1). In the former case, if M has a red K_s then so does the original graph and we are finished. Otherwise M has a blue K_r−1 and so has blue K_r by definition of M. The latter case is analogous.

Thus the claim is true and we have completed the proof for 2 colours. We now prove the result for the general case of c colours. The proof is again by induction, this time on the number of colours c. We have the result for c = 1 (trivially) and for c = 2 (above). Now let c > 2.

Claim: R(n₁, ..., n_c) ≤ R(n₁, ..., n_c−2, R(n_c−1, n_c)).

Note, that the right hand side only contains Ramsey numbers for c − 1 colours and 2 colours, and therefore exists and is a finite number t, by the inductive hypothesis. Thus, proving the claim will prove the theorem.

Proof of claim: Consider a graph on t vertices and colour its edges with c colours. Now 'go colour-blind' and pretend that c − 1 and c are the same colour. Thus the graph is now (c − 1)-coloured. By the inductive hypothesis, it contains either a K_ni monochromatically coloured with colour i for some 1 ≤ i ≤ (c − 2) or a K_R(nc−1,nc)-coloured in the 'blurred colour'. In the former case we are finished. In the latter case, we recover our sight again and see from the definition of R(n_c−1, n_c) we must have either a (c − 1)-monochrome K_nc−1 or a c-monochrome K_nc. In either case the proof is complete. – In the 2-color case, if R(r − 1, s) and R(r, s − 1) are both even, the induction inequality can be strengthened to R(r, s) ≤ R(r − 1, s) + R(r, s − 1) − 1.