Combinatorics/Schur's Theorem

Schur's theorem states that for every positive integer r, there exists a positive integer S, such that for every partition of the integers {1, ..., S} into r parts, one of the parts contains integers x, y and z with

x + y = z.

Proof: Let n = R(3, ..., 3) where R(3, ..., 3) denotes the Ramsey number on r colors. Now take S to be n and partition the integers {1, ..., n} into r parts, which we denote by colors. That is, the integers in the first part are said to be colored c₁, the integers in the second part are said to be colored c₂ and so on till color c_r. We also then say that {1, ..., S} has been r-colored. This terminology is common in Ramsey theory.

Now color the edges of K_n as follows: An edge xy (this denotes an edge which joins vertices x and y) is given color c if |x - y| was colored c in the partitioning. Now K_n will definitely contain a monochromatic triangle, say built out of the vertices i > j> k. Suppose the triangle is colored c_m. Now i - j, i - k and j - k will also be colored c_m, i.e. will belong to the same part in the partition. It only remains to take x = i - j, y = j - k and z = i - k to complete the proof.