Schur Numbers

From: Tim Brauch (RnEeMwOs.pVoEst_at_tbrauch.cNOoSPAMm)
Date: 10/28/04 

Date: Thu, 28 Oct 2004 04:45:29 GMT

I am trying to prove that the Schur number S(2) = 5 and S(3) = 14.

The definition I am using for a Schur Number is the smallest number such
that a monochromatic solution to x + y = z DOES exist (I have seen the
Schur Number referenced elsewhere as the largest number such that the
monochromatic solution does not exist).

My proof for S(2) = 5 is as follows:

Label the vertices of K6, the complete graph on six vertices,
{1,2,3,4,5,6}. Partition {1,2,3,4,5} into two arbitrary classes, C1 and C2
corresponding to colors C1 and C2. The color of each edge (i,j) in K6 is
determined by which partition |i - j| is in. By Ramsey theory, K6 must
contain a monochromatic triangle. Ergo, there must be three edges of one
color, say C1. Then these three edges are of the form (v1, v2), (v2, v3),
and (v1, v3). Without loss of generality, assume for the numbers
representing the vertices v3 > v2 > v1. Then we have (v2 - v1) + (v3 - v2)
= (v3 - v1), each of which is in partition C1. Take these values as your
x, y, and z.

I run into a problem, though, with S(3) = 14. By Ramsey theory, I know
R(3,3,3) = 17 and so a similar proof will not work, only if S(3) = 16.

I am in the middle of an exhaustive proof, trying all cases. There are 3^
14 = 4,782,969 possible colorings. Though this number is easily reduced by
cases since n and 2n must be different colors. But that reduces it to 2^7*
3^7 = 279,936 cases. These can be futher narrowed, but there are still
many cases to check. My question is, is there an easier proof than proof
by exhaustion?

 - Tim 

-- 
Timothy M. Brauch
NSF Fellow
Department of Mathematics
University of Louisville
email is:
news (dot) post (at) tbrauch (dot) com