Schur's Theorem in Ramsey Theory asserts that for every positive integer $r$, there is some positive integer $S(r)$ such that for every partition of the set $\{1,\ldots,S\}$ into $r$ parts, one of the parts contains integers $x,y,z$ with $x+y=z$. The standard proof uses Ramsey theory and graph colorings. See and (Ramsey_Theory) for the proofs.
My question is, both of these proofs seem to be saying that this integer $S(r)$ is equal to the Ramsey number $R(3,\ldots,3)$ on $r$ colors. But when $r=2$, it is well known that $R(3,3)=6$ (see ) but the Schur number $S(2)=5$ (see ).
What am I missing here?
$\endgroup$ 51 Answer
$\begingroup$The key observation here is that a coloring f of the interval [1,n] induces a coloring of the complete graph on n+1 vertices by coloring the edge (i,j) with f(|j-i|), and a monochromatic triangle in the induced coloring of the complete graph corresponds to a monochromatic Schur configuration in the original coloring of [1,n]. HOWEVER, this connection only works one way. If you are given a coloring of the complete graph on n+1 vertices, YOU CANNOT induce a coloring on the interval [1,n] by assigning |i-j| the color of the edge (i,j). To see this, observe that (1,2), (2,3), and (3,4) may all have different colors in the graph coloring, so it would not be well defined to assign 1 = |2-1| = |3-2| = |4-3| the color of any one of the preceding edges.
$\endgroup$
