Schur's Theorem (Ramsey Theory)

Theorem

For every positive integer $r$, there exists a positive integer $S$, such that for every partition of the integers $\left\{{1, \ldots, S}\right\}$ into $r$ parts, one of the parts contains integers $x$, $y$ and $z$ such that:

$x + y = z$

Proof

Let $n = R \left({3, \ldots, 3}\right)$ where $R \left({3, \ldots, 3}\right)$ denotes the Ramsey number on $r$ colors.

Now take $S$ to be $n$ and partition the integers $\left\{{1, \ldots, n}\right\}$ into $r$ parts, which we denote by colors.

That is:

• The integers in the first part are said to be colored $c_1$
• The integers in the second part are said to be colored $c_2$

... and so on till color $c_r$.

We also then say that $\left\{{1, \ldots, S}\right\}$ has been $r$-colored. This terminology is common in Ramsey theory.

Now consider the complete graph $K_n$.

Now color the edges of $K_n$ as follows:

An edge $xy$ is given color $c$ if $\left|{x - y}\right|$ was colored $c$ in the partitioning.

Now from the definition of $R \left({3, \ldots, 3}\right)$ and Ramsey's Theorem, $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.

$\blacksquare$

An extension

The above proving technique allows to obtain a variety of similar and further going results. Here is just a sample:

THEOREM 1   For every positive integer $r$, there exists a positive integer $S$, such that for every partition of the integers $\left\{{1, \ldots, S}\right\}$ into $r$ parts, one of the parts contains integers $x$, $y$ and $z$ such that:

$x + y = z$   and   $x \ne y$.

It's easy to see that this theorem follows from the following one:

THEOREM 2   For every positive integer $r$, there exists a positive integer $S$, such that for every partition of the integers $\left\{{1, \ldots, S}\right\}$ into $r$ parts, one of the parts contains integers $a$, $b$, $a+b$, $c$, $b+c$, and $d$ such that:

$a + b + c = d$

PROOF The proof is nearly the same as of the original Schur's theorem above, except that one uses  $R(4, \ldots, 4)$.

$\blacksquare$

Source of Name

This entry was named for Issai Schur.