Schur's Theorem proof for Ramsey Theory misunderstanding?

762 Views Asked by At

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 https://en.wikibooks.org/wiki/Combinatorics/Schur%27s_Theorem and https://proofwiki.org/wiki/Schur%27s_Theorem_(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 https://oeis.org/A003323) but the Schur number $S(2)=5$ (see https://oeis.org/A030126).

What am I missing here?

1

There are 1 best solutions below

0
On

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.