Combinatorics/Schur's Theorem

From Wikibooks, open books for an open world
Jump to navigation Jump to search

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 c1, the integers in the second part are said to be colored c2 and so on till color cr. We also then say that {1, ..., S} has been r-colored. This terminology is common in Ramsey theory.

Now color the edges of Kn 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 Kn will definitely contain a monochromatic triangle, say built out of the vertices i > j> k. Suppose the triangle is colored cm. Now i - j, i - k and j - k will also be colored cm, 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.