Introduction to Ramsey Theory: Students' Projects

Base case: \(s, t = 3,\ s + t = 6\text{.}\) Since \(R(2, 2) = 2,\ R(3, 2) = R(2, 3) = 3,\ R(2, 4) = R(4, 2) = 4,\ R(3, 3) = 6\text{.}\) This means that when \(s + t = 4,\ 5,\ 6\) there must exist a Ramsey number.

Inductive hypothesis: assume \(n \geq 6\) and for any \(u, v \geq 3\) such that \(u + v = n\text{,}\) the Ramsey number \(R(u, v)\) exists.

Inductive step: let \(s, t, \geq 3\) such that \(s + t = n + 1\text{.}\) Since \((s - 1) + t = s + (t - 1) = n\text{.}\) By assumption, both \(R(s - 1, t)\) and \(R(s, t - 1)\) exists. Let \(M = R(s - 1, t) + R(s, t - 1)\text{.}\) Now consider a two–colouring (red and blue) of the complete graph \(K_M\text{.}\)

Each vertex in this graph will have degree \(M - 1 = R(s - 1, t) + R(s, t - 1) - 1\text{.}\) Now focus on one vertex, and count the number of edges that are red and the number of edges that are blue.

By the pigeonhole principle, there are at least \(R(s - 1, t)\) red edges or at least \(R(s, t - 1)\) blue edges.

Assume there are at least \(R(s - 1, t)\) red edges.

Now consider the subgraph of \(K_M\text{,}\) \(K_{R(s - 1, t)}\text{.}\) By definition, there must be a red \(K_{s - 1}\) or a blue \(K_t\text{.}\) If \(K_{R(s - 1, t)}\) contains a red \(K_{s - 1}\text{,}\) we have a red \(K_s\) since the initial vertex's incident edges were all red as well.

In the other case, there is a blue \(K_t\) in \(K_{R(s - 1, t)}\text{,}\) which implies that \(K_M\) also has a blue \(K_t\text{.}\)

This proves that any two–colouring of the edges contains a red \(K_s\) or a blue \(K_t\text{.}\)

By the principle of mathematical induction, there exists a \(R(s, t)\text{,}\) which is bounded by \(R(s - 1, t) + R(s, t - 1)\text{.}\) [14.2.3.3]