\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P68}{20(1)}{2013}

\usepackage{amsthm,amsmath,amssymb}

% \usepackage{enumerate}

\newtheorem{theorem}{Theorem}

\begin{document}


\title{\bf On Some Small Classical Ramsey Numbers}

\author{
Geoffrey Exoo \\
Department of Mathematics and Computer Science \\
Indiana State University \\
Terre Haute, IN 47809 \\
ge@cs.indstate.edu \\
}

\date{\dateline{Feb 17, 2013}{Mar 13, 2013}{Mar 24, 2013}}

\maketitle

\begin{center}
\small{Mathematics Subject Classifications: 05C55,05D10}
\end{center}

\begin{abstract}
  This note is a report on a computer investigation of some small
  classical Ramsey numbers.  We establish new lower bounds for the
  classical Ramsey numbers $R(3,11)$ and $R(4,8)$.  In the first case,
  the bound is improved from $46$ (a record that had stood for 46
  years) to $47$; and in the second case the bound is improved from
  $57$ to $58$.
\end{abstract}

The classical Ramsey number $R(s,t)$ is the smallest integer $n$
such that in any two-coloring of the edges of $K_n$ there is a monochromatic
copy of $K_s$ in the first color or a monochromatic copy of $K_t$ in the
second color.
A comprehensive summary of the current state of the art
can be found in the dynamic
survey on Small Ramsey Numbers \cite{ramsurvey}.

In this note we present constructions that improve the lower bounds
for the Ramsey numbers $R(3,11)$ and $R(4,8)$, and then describe
the the modification in our search algorithm that led to the 
improvement in the $R(3,11)$ bound.
Listings for these colorings are given at the end of this paper,
and can also be found at the authors web site \cite{ginger}.

\section{R(3,11)}

The best published bounds for $R(3,11)$ are $46 \leq R(3,11) \leq 50$.
The lower bound of $46$ was established 46 years ago \cite{kalb}, whereas the
upper bound is very recent \cite{goerad}.
The graph that established the lower bound is the circle graph
$45(1,3,5,12,19)$.
In this note we present a graph which
improves the lower bound by one.

\noindent
\begin{theorem}
$R(3,11) \ge 47$.
\end{theorem}

\begin{proof}
The proof is given by the coloring of $K_{46}$ which can
be derived from Listing 1 at the end of the paper,
wherein the adjacency list for the color one graph in
a $(3,11)$-coloring of $K_{46}$ is given.
\end{proof}

\vspace{3mm}

In all,
we found $143447$ pairwise non-isomorphic
$(3,11)$-colorings of $K_{46}$.  Of these, $141829$ have a trivial
automorphism group, and $1618$ have exactly one non-trivial
automorphism.
The number of edges in these graphs that are assigned color one
ranges from $217$ to $228$.
Note that a $10$-regular graph of order $46$ has $230$ edges.
Adjacency matrices for several  of these colorings can be
found at the authors web site \cite{ginger}.

\section{R(3,10)}

An effort was also made to improve the lower bound for $R(3,10)$.
The current bounds in this case are
$40 \leq R(3,10) \leq 42$.
The lower bound was established in \cite{r3n} and the upper bound
was recently established in \cite{goerad}.

We were able to come tantilizingly close to a new lower bound,
finding $810$ pairwise non-isomorphic colorings of
$K_{40}$ with exactly one monochromatic triangle in color one and
no monochromatic copies of $K_{10}$ in color two.

In all we generated thousands of $(3,10)$-colorings
of $K_{39}$.  Using these colorings as a starting point, Jan Goedgebeur
\cite{jan} has created a catalog of nearly $50 000 000$ $(3,10)$-colorings of $K_{39}$.

\section{R(4,8)}

In \cite{fujita}, Fujita used the SAT solver {\it miniSat} to improve the lower
bound on $R(4,8)$ from 56 to 57.  Using Fujita's graph as a starting point,
we were able to improve the bound to 58 using the method outlined in \cite{r46}.

\noindent
\begin{theorem}
$R(4,8) \ge 58$.
\end{theorem}

\begin{proof}
The proof is given by the coloring of $K_{57}$ which can
be derived from listing 2, at the end of this note.
This listing shows the adjacency list for the color one graph in
a two coloring of $K_{57}$.
\end{proof}

\section{The Construction Algorithm}

The method used to find our $R(3,11)$ colorings is similar to the
method described in \cite{r46}, with an important difference,
which we now describe.

In general,
the goal of
the algorithm is to produce a $(s,t)$-coloring of $K_n$.
One begins with a coloring
obtained either randomly
\footnote{To be more precise, we might replace {\em random} by {\em pseudo-random}.}
or from a known good coloring of a smaller complete
graph.  Then each edge is examined, in random order, and counts are made of the
number of $K_s$ subgraphs in color one that would result if the edge were assigned
color one, and of the number of $K_t$ subgraphs that would result if the edge
were assigned color two.

When dealing with diagonal Ramsey numbers (where $s = t$) one can simply compare
the counts, choosing the better color most of the time, but choosing the other
with a small probability (usually depending on the difference in the counts).
This would be a typical implementation of {\em simulated annealing} \cite{sa}.

For off-diagonal Ramsey numbers, there is additional issue.
One needs to determine how much weight to assign to a
$K_s$ in color 1 as a opposed to a $K_t$ in color 2.  Empirical evidence
suggests that the weights should be approximately inversely proportional
to the $3/2$-power of the number of vertices in the complete subgraphs that one
is trying to avoid.  So in the case of $R(3,11)$, each monochromatic $K_3$ in
color one would count $(11/3)^{1.5} \approx 7$ times as much as a
monochromatic $K_{11}$ in color two.
This is roughly the way subgraphs weights were assigned in
\cite{r3n}, \cite{ars}, and \cite{r46}
to obtain new Ramsey bounds.

As with all randomized search methods, the essential problem here is how to
avoid getting stuck in local minima.  Typically this is
done by occasionally picking the edge that produces the largest (weighted)
subgraph count, instead of the smallest.  In the algorithm that produced
the $(3,11)$-coloring presented here, we added a second method.  The relative
weights of the two types of monochromatic subgraphs were changed at regular
intervals.
In this particular case, the weight of a monochromatic
$K_{11}$ in color two was fixed at $1$, while the weight of a monochromatic
$K_{3}$ in color one was allowed to vary from $1$ to $13$.
Within this
range the $K_3$ weight was determined by a piecewise linear sawtooth
function of time, except that when a new best coloring was achieved (measured by
an unweighted subgraph count), the $K_3$ weight returned to the
minimum value ($1$).


%\newpage

\section{Adjacency Lists}

\begin{small}
\begin{verbatim}
1 2 5 8 11 26 28 32 37 41
0 4 15 19 22 29 31 33 40 44
0 7 13 21 30 31 38 40 44
12 13 21 22 23 24 28 34 39 41
1 7 11 21 26 30 32 37 38 41
0 13 16 21 31 34 36 38 45
7 8 11 13 15 23 25 28 41
2 4 6 12 22 24 27 29 33 34
0 6 12 18 24 27 30 38 39 40
12 13 14 17 23 24 30 33 36 37
17 19 20 21 23 24 32 33 34 35
0 4 6 12 22 31 35 40 42 44
3 7 8 9 11 15 19 20 25 45
2 3 5 6 9 19 20 26 32 35
9 19 21 22 26 32 34 38 45
1 6 12 26 32 34 35 37 42
5 17 19 22 32 33 40 41 43 44
9 10 16 26 28 29 31 39
8 26 28 29 31 33 37 44
1 10 12 13 14 16 30 36 37 42
10 12 13 22 40 41 42 43 44
2 3 4 5 10 14 27 29 43
1 3 7 11 14 16 20 30 36 37
3 6 9 10 26 27 29 38 43 45
3 7 8 9 10 25 42 43 44 45
6 12 24 26 27 29 30 33 37 38
0 4 13 14 15 17 18 23 25 36
7 8 21 23 25 28 31 35 42 44
0 3 6 17 18 27 36 38 43 45
1 7 17 18 21 23 25 32 35 42
2 4 8 9 19 22 25 34 35 45
1 2 5 11 17 18 27 32 41 43
0 4 10 13 14 15 16 29 31 36
1 7 9 10 16 18 25 39 42
3 5 7 10 14 15 30 40 43 44
10 11 13 15 27 29 30 38 41 43
5 9 19 22 26 28 32 39 40 41
0 4 9 15 18 19 22 25 39 40
2 4 5 8 14 23 25 28 35
3 8 17 33 36 37 43 44 45
1 2 8 11 16 20 34 36 37 45
0 3 4 6 16 20 31 35 36
11 15 19 20 24 27 29 33
16 20 21 23 24 28 31 34 35 39
1 2 11 16 18 20 24 27 34 39
5 12 14 23 24 28 30 39 40
\end{verbatim}
\end{small}

\noindent
{\bf Listing 1.} The Color 1 Graph in a $(3,11)$-coloring of $K_{46}$.


\begin{small}
\begin{verbatim}
2 3 5 6 10 11 12 19 22 23 25 26 36 37 42 43 45 46 50 56
3 4 6 7 11 12 13 19 23 24 25 26 27 37 38 43 44 46 47 50 53
0 4 5 7 8 12 13 14 24 25 27 28 38 39 44 45 47 53 56
0 1 5 6 8 9 14 15 25 26 28 29 39 40 41 45 46 48 55
1 2 6 7 9 10 14 15 16 26 27 29 30 40 41 42 46 47 51 54
0 2 3 7 8 10 11 16 17 27 28 30 31 41 42 43 47 54 55
0 1 3 4 8 9 11 12 17 18 28 29 31 32 42 43 44 53 55
1 2 4 5 9 10 12 13 18 29 30 32 33 43 44 45 52 53 54
2 3 5 6 10 11 13 14 20 30 31 33 34 44 45 46 50 52 54 56
3 4 6 7 11 12 13 14 15 20 21 31 32 34 35 45 46 47 50 53
0 4 5 7 8 12 13 15 16 21 22 32 33 35 36 46 47 49 53
0 1 5 6 8 9 13 14 16 17 22 23 33 34 36 37 47 49 50 55
0 1 2 6 7 9 10 14 15 16 17 18 23 24 34 35 37 38 48 50 51 55
1 2 7 8 9 10 11 15 16 18 24 25 35 36 38 39 48 49 51 52
2 3 4 8 9 11 12 16 17 19 20 25 26 36 37 39 40 49 52
3 4 9 10 12 13 17 18 19 20 21 26 27 37 38 40 41 51 52 53
4 5 10 11 12 13 14 18 21 22 27 28 38 39 41 42 52 53 56
5 6 11 12 14 15 19 20 22 23 27 28 29 39 40 42 43 48 52
6 7 12 13 15 16 19 20 21 23 24 28 29 30 40 41 43 44 48
0 1 14 15 17 18 28 29 31 32 37 45 48 49 51 53 54 56
8 9 14 15 17 18 22 23 25 26 30 31 32 42 43 45 46 48 50
9 10 15 16 18 23 24 26 27 31 32 33 43 44 46 47 50 52 56
0 10 11 16 17 20 24 25 27 28 32 33 34 44 45 47 52 55 56
0 1 11 12 17 18 20 21 25 26 28 29 33 34 35 45 46 53 55
1 2 12 13 18 21 22 26 27 29 30 34 35 36 46 47 49 52 53 54
0 1 2 3 13 14 20 22 23 27 28 30 31 35 36 37 47 49 52 54 55
0 1 3 4 14 15 20 21 23 24 28 29 31 32 37 38 49 50 55
1 2 4 5 15 16 17 21 22 24 25 29 30 32 33 38 39 50 54
2 3 5 6 16 17 18 19 22 23 25 26 30 31 33 34 39 40 50 54
3 4 6 7 17 18 19 23 24 26 27 31 32 34 35 40 41 51 52
4 5 7 8 18 20 24 25 27 28 32 33 35 36 41 42 49 51 52
5 6 8 9 19 20 21 25 26 28 29 33 34 36 37 42 43 49 52
6 7 9 10 19 20 21 22 26 27 29 30 34 35 37 38 43 44 49 56
7 8 10 11 21 22 23 27 28 30 31 35 36 38 39 44 45 48 49
8 9 11 12 22 23 24 28 29 31 32 36 37 39 40 45 46 49 51
9 10 12 13 23 24 25 29 30 32 33 37 38 40 41 46 47 51 53
0 10 11 13 14 24 25 30 31 33 34 38 39 40 41 42 47 54 56
0 1 11 12 14 15 19 25 26 31 32 34 35 39 40 42 43 48
1 2 12 13 15 16 26 27 32 33 35 36 40 41 43 44 48 56
2 3 13 14 16 17 27 28 33 34 36 37 41 42 43 44 45 49 50 56
3 4 14 15 17 18 28 29 34 35 36 37 38 42 43 45 46 48 50 53
3 4 5 15 16 18 29 30 35 36 38 39 43 44 46 47 48 49 52 54
0 4 5 6 16 17 20 30 31 36 37 39 40 44 45 47 50 52 54
0 1 5 6 7 17 18 20 21 31 32 37 38 39 40 41 45 46 50 51
1 2 6 7 8 18 21 22 32 33 38 39 41 42 46 47 51 52 54
0 2 3 7 8 9 19 20 22 23 33 34 39 40 42 43 47 52 54 55
0 1 3 4 8 9 10 20 21 23 24 34 35 40 41 43 44 51 55
1 2 4 5 9 10 11 21 22 24 25 35 36 41 42 44 45 49 51 56
3 12 13 17 18 19 20 33 37 38 40 41 49 50 54 55 56
10 11 13 14 19 24 25 26 30 31 32 33 34 39 41 47 48 50 51 53 55
0 1 8 9 11 12 20 21 26 27 28 39 40 42 43 48 49 51 53 54 56
4 12 13 15 19 29 30 34 35 43 44 46 47 49 50 54 55 56
7 8 13 14 15 16 17 21 22 24 25 29 30 31 41 42 44 45 53
1 2 6 7 9 10 15 16 19 23 24 35 40 49 50 52 54 55 56
4 5 7 8 19 24 25 27 28 36 41 42 44 45 48 50 51 53 55
3 5 6 11 12 22 23 25 26 45 46 48 49 51 53 54 56
0 2 8 16 19 21 22 32 36 38 39 47 48 50 51 53 55
\end{verbatim}
\end{small}

\noindent
{\bf Listing 2.} The Color 1 Graph in a $(4,8)$-coloring of $K_{57}$.

\begin{thebibliography}{99}

\bibitem{r3n}
G. Exoo,
On Two Classical Ramsey Numbers of the Form $R(3,n)$,
SIAM J. Discrete Math,  2 (1989) 488-490.

\bibitem{ars}
G. Exoo,
Announcement: On the Ramsey Numbers $R(4,6)$, $R(5,6)$, and $R(3,12)$,
Ars Combinatoria,
35 (1993) 85.

\bibitem{r46}
G. Exoo,
On the Ramsey Number $R(4,6)$,
Electronic Journal of Combinatorics,
Electron. J. Comb. 19 \#P66, 2012.

\bibitem{ginger}
G. Exoo,
Ramsey Numbers,
\verb+http://ginger.indstate.edu/ge/RAMSEY+

\bibitem{fujita}
H. Fujita,
A new lower bound for the Ramsey number R(4,8),
arXiv 1212.1328 (2012).

\bibitem{jan}
J. Goedgebeur,
Personal communication.

\bibitem{goerad}
J. Goedgebeur and S.P. Radziszowski,
New computational upper bounds for Ramsey numbers R(3,k).
arXiv 1210.5826 (2012), submitted.

\bibitem{kalb}
J.G. Kalbfleisch,
Chromatic Graphs and Ramsey’s Theorem,
{\it Ph.D. Thesis}, University of Waterloo,
January 1966.

\bibitem{sa}
S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi,
Optimization by Simulated Annealing,
Science 220 (1983) 671-680.

\bibitem{ramsurvey}
S. P. Radziszowski,
Small Ramsey Numbers,
Electron. J. Combin.,
Dynamic Survey \#DS1, 2011.
\verb+(http://www.combinatorics.org/Surveys)+

\end{thebibliography}

\end{document}