\documentclass[12pt]{article}
\usepackage{e-jc}

\usepackage{amsthm}
\input amssym.def
\input amssym.tex

\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\sloppy

\theoremstyle{plain}
\newtheorem{thm}{Theorem}

\begin{document}

\title{On the Ramsey Number $R(4,6)$}

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

\date{\dateline{Mar 6, 2012}{Mar 23, 2012}\\
\small Mathematics Subject Classifications: 05C55, 05D10}

\maketitle

\begin{abstract}
The lower bound for the classical Ramsey number $R(4,6)$ is improved
from $35$ to $36$.
The author has found $37$ new edge colorings of $K_{35}$ that
have no complete graphs of order $4$ in the first color, and no complete
graphs of order $6$ in the second color.
The most symmetric of
the colorings
has an automorphism group of order $35$, with one fixed point, and is
presented in detail.
The colorings were found using
a heuristic search procedure.

\end{abstract}

This note deals with a new lower bound for the classical Ramsey number $R(4,6)$.
Recall that 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 recent summary of the state of the art for Ramsey numbers can be found in
the Dynamic Survey \cite{ramsurvey}.

\vspace{5mm}

\noindent
\begin{thm}
$R(4,6) \ge 36$.
\end{thm}

\begin{proof}
The proof is given by the coloring of $K_{35}$ which can
be derived from Table 1, below.
This table contains an adjacency list for the color one graph of 
a two-coloring of $K_{35}$.
All other edges are assigned color two.
\end{proof}
\vspace{5mm}

\begin{table}
\begin{small}
\begin{verbatim}
           0:   2  6  7  9 11 13 15 17 18 20 21 23 24 26 28 32
           1:   3  4  5  9 11 13 15 17 18 21 22 23 25 27 29 33
           2:   0  4  5  8 10 12 14 16 19 20 21 22 25 27 28 32
           3:   1  6  7  8 10 12 14 16 19 20 22 23 24 26 29 33
           4:   1  2  7  8 10 11 13 17 19 20 22 24 26 31 34
           5:   1  2  6  8  9 11 14 17 19 21 23 24 26 30 34
           6:   0  3  5  9 10 11 12 16 18 21 23 25 27 31 34
           7:   0  3  4  8  9 10 15 16 18 20 22 25 27 30 34
           8:   2  3  4  5  7  9 12 15 17 23 24 27 29 31 32
           9:   0  1  5  6  7  8 13 14 16 22 25 26 29 31 32
          10:   2  3  4  6  7 11 13 14 18 21 25 26 28 30 33
          11:   0  1  4  5  6 10 12 15 19 20 24 27 28 30 33
          12:   2  3  6  8 11 13 15 17 18 20 22 25 31 33
          13:   0  1  4  9 10 12 14 16 19 21 23 24 31 33
          14:   2  3  5  9 10 13 15 17 18 20 22 24 30 32
          15:   0  1  7  8 11 12 14 16 19 21 23 25 30 32
          16:   2  3  6  7  9 13 15 19 21 24 27 29 32 34
          17:   0  1  4  5  8 12 14 18 20 25 26 29 32 34
          18:   0  1  6  7 10 12 14 17 22 24 27 28 33 34
          19:   2  3  4  5 11 13 15 16 23 25 26 28 33 34
          20:   0  2  3  4  7 11 12 14 17 23 27 29 30 31
          21:   0  1  2  5  6 10 13 15 16 22 26 29 30 31
          22:   1  2  3  4  7  9 12 14 18 21 26 28 30 31
          23:   0  1  3  5  6  8 13 15 19 20 27 28 30 31
          24:   0  3  4  5  8 11 13 14 16 18 26 27 32 33 34
          25:   1  2  6  7  9 10 12 15 17 19 26 27 32 33 34
          26:   0  3  4  5  9 10 17 19 21 22 24 25 28 29
          27:   1  2  6  7  8 11 16 18 20 23 24 25 28 29
          28:   0  2 10 11 18 19 22 23 26 27 29 31 34
          29:   1  3  8  9 16 17 20 21 26 27 28 30 34
          30:   5  7 10 11 14 15 20 21 22 23 29 34
          31:   4  6  8  9 12 13 20 21 22 23 28 34
          32:   0  2  8  9 14 15 16 17 24 25 33
          33:   1  3 10 11 12 13 18 19 24 25 32
          34:   4  5  6  7 16 17 18 19 24 25 28 29 30 31
\end{verbatim}
\end{small}
\caption{A $(4,6)$-coloring of $K_{35}$.}
\end{table}

This coloring improves the lower bound for $R(4,6)$ from
$35$ to $36$, five short of the upper bound of $41$ \cite{mckrad}.
The coloring has an automorphism group of order $4$, with exactly one
fixed point \cite{nauty}.
It was found using a method that the author had discarded many years ago,
a method we now discuss.

A number of the lower bounds given in the table of two color classical
Ramsey numbers (see Table 1 in the Dynamic Survey \cite{ramsurvey}) were
established by this author using computer search techniques.
Three of these, $R(4,6)$, $R(3,10)$, and $R(5,5)$ \cite{r55,r3n,ars},
are the smallest unsettled cases
for two color classical Ramsey numbers.
They are also, in the opinion of this author, the only
unsettled cases where optimal colorings can be found using computer methods
that manipilate colorings one edge at a time.
These three lower bounds were
established using one (or more) of the following computer search methods.
In each case, the object of the method is to produce colorings with no
monochromatic subgraphs
of order $s$ in color one, and no monochomatic subgraphs of order $t$ in
color two.  Monochromatic copies of such subgraphs in a coloring
will be referred to as {\em bad subgraphs}.

\begin{description}
\item[Method A:]

One begins with a randomly generated edge coloring for a complete
graph whose order $n$ is small enough so that a good coloring can be
obtained easily.
Then using simulated annealing \cite{sa}, or a synthesis of simulated
annealing and tabu search \cite{tabu}, the coloring is transformed into
a good coloring by looking at individual edges, and choosing the color
that minimizes the number of bad subgraphs.
When all bad subgraphs have been eliminated,
$n$ is incremented, and the process is repeated.

\item[Method B:]

This method is different from Method A in two respects.
Instead of beginning with a graph of small order, one begins with a
complete graph of the desired order (e.g., large enough to improve
the lower bound for the Ramsey number).
But the important difference pertains to the objective function.
Instead of simply recoloring edges so as to minimize the number of
bad subgraphs, we add a term to the objective
that attempts to maximize the number
of monochromatic induced copies of $P_4$, the path on $4$ vertices.
The importance of the $P_4$ count in the objective can be as great or greater
than the bad subgraph counts.

\item[Method C:]

Here one begins by searching for highly symmetric colorings, for example
circle colorings (or more generally, Cayley colorings), that have
relatively few bad subgraphs,
and that have one additional property.
They must have individual edges (as opposed to orbits) that,
when recolored, reduce the number of monochromatic subgraphs.
Once such a coloring is found, one proceeds as in Method A.
\end{description}

One further remark on Method B should be made.
Often we used a somewhat more detailed variation of the method.
There are $11$ isomorphism classes of graphs of order $4$, and
hence $11$ essentially different ways to two-color the edges
of a subgraph of order $4$ in a two-coloring of $K_n$.
If we count the number of vertex sets of size four which induce
each of these $11$ possible colorings, we
produce a vector of length $11$.
Edges can be thus recolored
so as to minimize the distance between the computed
vector and a postulated target vector.
The target vector might be determined by looking at known good colorings,
by a higher level optimization process, or by sheer speculation.
Experience has shown that
maximizing the number of induced $P_4$'s is the key ingredient.

All three methods have successfully produced lower bounds for classical
Ramsey numbers.
The current lower bound for $R(5,5)$, for example, was originally established \cite{r55}
using Method C.
Very soon thereafter, we were able to find the same
coloring using Method B, and eventually, using Method A.
Since the idea behind Method B does not seem to have any direct theoretical
justification, and since Method A was faster (counting induced $P_4$'s takes
more time than counting cliques, when the number of cliques is small),
Method B was gradually discarded.

However, Method B has at least one potential advantage.
By manipulating the objective function,
one can drive the search away from known colorings,
and (hopefully) toward new colorings.
So, given the significant increase in computer speed since the mid-1980's,
the author decided to revisit Method B, and apply it to each of the
three frontier cases mentioned above.
In addition to attempting to improve the lower bounds, we were also
interested in finding new examples of colorings that equaled the current
bounds, hoping to find colorings that were in some respect
different from the known examples.  It was such a coloring that
led to the improved lower bound for $R(4,6)$.

In Table 2, we present some data pertaining to the color two
subgraphs from five new $(4,6)$-colorings of $K_{34}$ that were obtained
together (on different machines, but at roughly the same time).  This
table lists the counts for each of the $11$ types of induced subgraphs
of order $4$.  The important column is that of $G_1$, the other four
colorings are presented as representative examples.
The colorings were obtained
using a variety of target vectors (for counts of induced colorings of order $4$),
created more or less {\it ad hoc}.
We emphasize that in the table, the graph described is the color two graph.
The abbreviation $E_4$ denotes the empty (edgeless) graph of order $4$, and
$P_4$ denotes the path of order $4$;
the other abbreviations are fairly standard and of lesser importance.

\begin{table}
\begin{center}
\begin{tabular}{|l|rrrrr|} \hline
 4-subgraph&     $G_1$  &     $G_2$  &     $G_3$  &     $G_4$  &     $G_5$  \\ \hline
    $E_4$  &         0  &         0  &         0  &         0  &         0  \\ 
   $K_2$   &      1886  &      1464  &      1475  &      1484  &      1500  \\ 
  $2 K_2$  &      1640  &      1311  &      1303  &      1427  &      1273  \\ 
    $P_3$  &      4880  &      4204  &      4228  &      4364  &      4208  \\ 
 $K_{1,3}$ &      2167  &      2199  &      2215  &      2092  &      2247  \\ 
    $P_4$  &      9553  &      9190  &      9138  &      9359  &      9152  \\ 
    $K_3$  &      3204  &      2856  &      2834  &      3027  &      2804  \\ 
  $K_3+e$  &     11268  &     11776  &     11784  &     11589  &     11770  \\ 
    $C_4$  &      2558  &      2900  &      2920  &      2687  &      2936  \\ 
  $K_4-e$  &      7634  &      8645  &      8644  &      8534  &      8667  \\ 
    $K_4$  &      1586  &      1831  &      1835  &      1813  &      1819  \\ \hline
\end{tabular}
\end{center}
\caption{Induced subgraph counts in five $(4,6)$-colorings of $K_{34}$.}
\end{table}
  
Observe that the induced subgraph counts are approximately the same in each case,
except for $G_1$.
The other four have subgraph counts that are substantially the same as the
hundreds of other $(4,6)$-colorings the author found previously.
The coloring $G_1$ is quite different from any of these.
The $K_4$ count is only 1586, whereas in no other case did we find
a coloring with less than 1780 monochromatic $K_4$'s (in the $K_6$-free color).
In addition, the number of induced $P_4$'s is significantly larger than in any of
the other colorings.
As soon as these differences were noticed,
we attempted to extend the coloring to $35$ vertices and succeeded immediately.
All $37$ colorings found so far are closely related to $G_1$.

The coloring given in Table 1 is the most symmetric of the $37$ colorings found
to date.
It has an automorphism group of order $4$ \cite{nauty}.
There are six orbits of size $4$,
consisting of vertices $i$, $i+1$, $i+2$ and $i+3$ for $i = 0, 4, 8, 12, 16, 20$.
There are
five orbits of size $2$, consisting of vertices $j$ and $j+1$ for $j = 24, 26, 28, 30, 32$.
Vertex $34$ is a fixed point.
Note that the minimum degree in color $1$ is $11$ and so the maximum degree in color $2$ is
$23$, which is one shy of the maximum possible, in view of the fact that
$R(4,5) = 25$ \cite{ramsurvey}.
Similarly, the minimum degree in color $2$ is $18$, and so the
maximum degree in color $1$ is $16$, which is also one shy of the maximum possible, since
$R(3,6) = 18$ \cite{ramsurvey}.

There are two other colorings that are adjacent to the coloring given
above. They can be obtained from the original by recoloring the
edge $1-3$, and by recoloring the edges $1-3$ and $29-33$.
In both cases, the resulting
coloring has an automorphism group of order two.
In addition to these three colorings,
another group of $34$ good colorings was found
nearby by reversing the colors of between $20$ and $25$
edges (it may be possible to obtain this latter group of colorings by
a shorter route).  This set of $34$ colorings was originally found by
a program that systematically looks for new colorings by changing
the colors of small sets of edges.  Later, some of the colorings
in this set of $34$ were also found by the Method B search program.

The Method B program that found these colorings has run to a successful
conclusion (when searching for $(4,6)$-colorings on $K_{35}$) nearly $1000$ times.
In almost all of these cases, the coloring found was one of the three
colorings that are mentioned at the begining of the previous paragraph.
Only five times have we found a coloring in the group of $34$.

Copies of the $37$ colorings, in different formats, can be found at the
author's web site \cite{exoosite} and at Brendan McKay's web site \cite{mckaysite}.

\begin{thebibliography}{99}

\bibitem{r55}
G. Exoo,
A Lower Bound for $R(5,5)$,
J. Graph Theory 13 (1989) 97-98.

\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{exoosite}
G. Exoo,
Ramsey Numbers, \newline
\verb+http://ginger.indstate.edu/ge/RAMSEY/R46+.

\bibitem{tabu}
Fred Glover,
Tabu Search -- Part 1,
ORSA Journal on Computing 1 (1989) 190-–206.

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

\bibitem{nauty}
B.D. McKay, nauty User's Guide, Technical Report
TR-CS-90-02, Department of Computer Science, Australian National
University (1990).\\ Graph isomorphism/automorphism software,
version 2.4 (2010),\\ available at \verb+http://cs.anu.edu.au/~bdm/nauty+.

\bibitem{mckrad}
B. D. McKay and S. P. Radziszowski,
Subgraph Counting Identities and Ramsey Numbers,
JCT-B 69 (1997) 193-209.

\bibitem{mckaysite}
B. D. McKay, Ramsey Graphs, \newline
\verb+http://cs.anu.edu.au/~bdm/data/ramsey.html+.

\bibitem{ramsurvey}
S. P. Radziszowski,
Small Ramsey Numbers,
Electronic Journal of Combinatorics, DS1, 2011.\\
\verb+http://www.combinatorics.org/issue/view/Surveys+.

\end{thebibliography}

\end{document}
