%
% Geoffrey Exoo - A Lower Bound for Schur Numbers...
% Latex source for a 3 page document
%
\documentstyle{article}

\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics 1 (1994),  
\#R8\hfill}
\thispagestyle{empty}

\begin{document}

\title{A Lower Bound for Schur Numbers and Multicolor Ramsey Numbers  
of $K_3$}
\author{
Geoffrey Exoo \\
Department of Mathematics and Computer Science \\
Indiana State University \\
Terre Haute, IN 47809 \\
ge@judy.indstate.edu
}

\date{Submitted: September 13, 1994; Accepted: September 18, 1994}

\maketitle

\begin{abstract}

For $k \geq 5$, we establish
new lower bounds on the Schur numbers $S(k)$
and on the k-color Ramsey numbers of $K_3$.

\end{abstract}

\newcommand{\binco}[2]{\left( \begin{array}{c} #1 \\ #2 \end{array}  
\right)}

\vspace{9mm}

\pagestyle{headings}

For integers $m$ and $n$, let $[m,n]$ denote the set
$\{ i \, | \, m \leq i \leq n \}$.
A set S of integers is called {\it sum-free} if $i , j \in S$
implies $ i+j \not \in S$, where we allow $i = j$.
The Schur function S(k) is defined
for all positive integers as the maximum $n$ such that $[1,n]$ can be
partitioned into $k$ sum-free sets.

The {\it k-color Ramsey number} of the complete graph $K_n$,
often denoted $R_k(n)$, is defined to be the smallest integer $t$,
such that in any k-coloring of the edges of $K_t$, there is a
complete subgraph $K_n$ all of whose edges have the same color.
A sum-free partition of $[1,s]$ gives rise to
a $K_3$-free edge k-coloring of $K_{s+1}$ by identifying the
vertex set of $K_{s+1}$ with $[0,s]$ and by coloring the edge
$uv$ according to the set membership of $ |u-v| $.
Hence $R_k(3) \geq S(k)+2$.

It is known that $S(1) = 1$,
$S(2) = 4$, $S(3) = 13$, and $S(4) = 44$.  The first
three values are easy to verify; the last one is due to
L. D. Baumert \cite{ah}.  The best previously published bounds for
$S(5)$ are $157 \leq S(5) \leq 321$, the lower bound was proved in
\cite{fr} and the upper bound in \cite{wh}.
For Ramsey numbers we know $R_2(3) = 6$ and $R_3(3)=17$;
the current bounds on $R_4(3)$ are $51$ and $65$ \cite{sz}.

Below we list the five
sets of a sum-free partition of $[1,160]$,  Since the partition is
symmetric ($i$ and $161-i$ always belong to the same set), only the
integers from 1 to 80 are listed.

\newpage

\noindent
Set 1:
\vspace{2mm}
   4   5  15  16  22  28  29  39  40  41  42  48  49  59

\noindent
Set 2:
\vspace{2mm}
   2   3   8  14  19  20  24  25  36  46  47  51  62  73

\noindent
Set 3:
\vspace{2mm}
   7   9  11  12  13  17  27  31  32  33  35  37  53  56  57  61  79

\noindent
Set 4:
\vspace{2mm}
   1   6  10  18  21  23  26  30  34  38  43  45  50  54  65  74

\noindent
Set 5:
\vspace{2mm}
  44  52  55  58  60  63  64  66  67  68  69  70  71  72  75  76  77   
78  80

\vspace{6mm}

This proves
that $S(5) \geq 160$.
It follows that
$R_5(3) \geq 162$.  From \cite{ah} and \cite{am} we have
$S(k) \geq c(321)^{k/5} > c(3.17176)^k$ for some positive constant  
$c$.
  From the recurrence $R_k(3) \geq 3 \, R_{k-1}(3) + R_{k-3}(3) - 3$
proved in \cite{ch} we also have $R_6(3) \geq 500$.

This construction was found
using heuristic techniques that will be described below.
We have found approximately 10,000 different
partitions of $[1,160]$; of these, four are symmetric.
These 10,000 partitions are all ``close'' to each other.
In other words, one can begin with one of the partitions,
move an integer from one set to another, and obtain a new partition.
This can be contrasted with the situation for partitions of $[1,159]$
where we found over 100,000 partitions, most of which were not close
in this sense.  It is tempting to conclude that there are far fewer
sum-free partitions of $[1,160]$ than of $[1,159]$.

Two different partitions may generate isomorphic
Ramsey colorings.  With this is mind, we used some
simple criteria to try to determine how many non-isomorphic
Ramsey colorings the 10,000 partitions gave us, and
found that at least 1500
were represented.

To construct these partitions one can use any of the well known
approximation heuristics for
combinatorial optimization problems
(simulated annealing, genetic algorithms, etc.).  The key is to  
choose
the right objective function.
Of those we studied, one family of functions seems to work
particularly well.
To define our function, let $P$ be a partition of $[1,n]$,
and let $P = \{S_1,\ldots,S_k\}$.  For
$1 \leq t \leq n$, let $P_t$ denote the partition of $[1,t]$ induced
by $P$ (i.e., $P_t = \{S_1 \cap [1,t],\ldots,S_k \cap [1,t]\}$).
For integers $i$ and $j$, it is convenient to define
\[ g_n(i,j) = \left\{ \begin{array}{ll}
     0 & \mbox{if $i+j \leq n$,} \\
     2n-i-j & \mbox{otherwise.}
   \end{array}
 \right. \]

Then define:
\[ f_1(P) = max \{ t | P_t \hbox{\it \ is sum-free} \} \]
\[ f_2(P) = \sum_{i=1}^{k} \sum_{s,t \in S_i}g_n(s,t) \]
and finally
\[ f(P) = c_1 f_1(P) + c_2 f_2(P). \]

For appropriate positive constants $c_1$ and $c_2$, $f(P)$ is the  
objective
function for our maximization problem.  In practice, we make
$c_1$ relatively large and $c_2$ relatively small so that
the $f_1$ term is the more important term in the function.
For the case $n=160$ and $k=5$ we obtained best results when
$c_1/c_2$ was allowed to randomly vary in the
range $2^{12}$ to $2^{18}$.
Finally we note the somewhat surprising fact that the
more obvious objective
function, the number of
``monochromatic'' sums in a partition,
seems to be far less effective.

At one point we modified the objective function so as to prefer
partitions having
one large set.
The idea was to find a partition with a set large enough
to improve the lower
bound for $R_4(3)$.
However, the largest set found in any sum-free
partition had 44 elements.
Many such partitions of $[1,n]$, $157 \leq n \leq 160$, were found,
but those with sets containing 45 or more elements seem to be rare,
if they exist.

\begin{thebibliography}{99}

\bibitem{ah}
H. L. Abbott and D. Hanson.
{\em A Problem of Schur and its Generalizations.}
Acta Arithmetica, 20 (1972), 175-187.

\bibitem{am}
H. L. Abbott and L. Moser.
{\em Sum-free Sets of Integers.}
Acta Arithmetica, 11 (1966), 392-396.

\bibitem{ch}
F. R. K. Chung.
{\em On the Ramsey Numbers N(3,3,...,3;2).}
Discrete Math, 5(1973), 317-321.

\bibitem{fr}
H. Fredrickson.
{\em Schur Numbers and the Ramsey Numbers N(3,3,...,3;2).}
J. Combin. Theory Ser A, 27 (1979), 371-379.

\bibitem{sz}
S. P. Radziszowski.
{\em Small Ramsey Numbers.}
Dynamic Survey DS1, Electronic J. Combinatorics 1 (1994), 28 pp.

\bibitem{wh}
E. G. Whitehead.
{\em The Ramsey Number N(3,3,3,3;2).}
Discrete Math, 4 (1973), 389-396.

\end{thebibliography}

\end{document}