% % Geoffrey Exoo - Some New Ramsey Colorings % Latex source for a 6 page document % \documentstyle[11pt]{article} \textwidth 6.0in \textheight 9.0in \oddsidemargin 0.1in \evensidemargin 0.1in %\hoffset -.75in \pagestyle{myheadings} \markright{\sc the electronic journal of combinatorics 5 (1998), \#R29\hfill} \thispagestyle{empty} \begin{document} \title{Some New Ramsey Colorings} \author{ Geoffrey Exoo \\ Department of Mathematics and Computer Science \\ Indiana State University \\ Terre Haute, IN 47809 \\ ge@fred.indstate.edu } \date{Submitted: April 19, 1998; Accepted: May 14, 1998.} \maketitle \begin{abstract} New lower bounds for 15 classical Ramsey numbers are established. Several of the colorings are found using a new variation of local search heuristics. Several others are found using known colorings as building blocks. \end{abstract} \begin{center} AMS Subject Classifications: {05D10, 05D04}\hfill \end{center} \footnotetext[1]{Current address: Schneider Logistics, Green Bay, WI 54303, USA. Email: exoog@schneider.com.} \vspace{9mm} \pagestyle{headings} \begin{center} {\bf Introduction} \end{center} In this note, several lower bounds for classical Ramsey numbers are improved using two different methods. First we use a new synthesis of simulated annealing and tabu search to establish several new bounds. Then some constructions that use smaller constructions as building blocks are described. In total, we improve 13 entries in Radziszowski's table of two-color classical Ramsey numbers \cite{sprds}, and also add two entries to his list of classical multicolor bounds. \begin{center} {\bf A Simple Search Algorithm} \end{center} The algorithm is outlined in the context of minimizing an integer function of binary (boolean) variables. Let $f = f(x_1,\dots,x_k)$ be such a function. Three important data structures are required: a {\em current solution vector}, a {\em history list}, and a {\em temperature}. The current solution vector is denoted by $V = (x_1 , \dots , x_k)$. In addition, $V_i$ will denote to the vector obtained from $V$ by changing bit $i$, i.e., $V_i = (x_1, \dots , x_{i-1}, 1 - x_i, x_{i+1}, \dots , x_k)$. As the algorithm proceeds, the current solution vector is repeatedly changed. Each time it is changed, the old vector is saved in a history list, $H$, of previous solution vectors. This is an essential idea from tabu search \cite{tabu}. The algorithm also has a notion of temperature, as in simulated annealing. In this case, the temperature, $T$, is a positive integer which restricts the range of choices the algorithm has for changing $V$. During each iteration, we compute $d_i = f(V_i) - f(V)$, for $1 \le i \le k$. {}From the set $\{d_i\}$, the $T$ smallest values are collected, and from these, one is chosen randomly. The corresponding change is then incorporated into the new solution vector. \begin{tabbing} {\bf The algorithm:} \= \\ \> initialize $V$ randomly \\ \> set $H = $ empty list \\ \> set $T = MAXTEMP$ \\ \> loop \= : \\ \> \> append $V$ to $H$ \\ \> \> for \= each $i$ in $(1 \dots k)$ \\ \> \> \> if \= $V_i \in H$ then \\ \> \> \> \> set $d_i = MAXINT$ \\ \> \> \> else \\ \> \> \> \> set $d_i = f(V_i) - f(V)$ \\ \> \> let $d_j$ be chosen randomly from among the T smallest $d_i$ \\ \> \> set $V = V_j$ \end{tabbing} \vspace{3mm} When using the method to generate Ramsey colorings, the function $f$ counts monochromatic cliques and the solution vector is the list colors assigned to sets of edges. There are many choices for edge sets, we used the same ones used in \cite{piw}, where two types of colorings were examined: colorings where the adjacency matrix is a circulant and colorings where the adjacency matrix can be built from square circulant blocks. Colorings of the first type have been used since the beginning of work on the Ramsey number problem. Those of the second type were first used explicitly by Mathon \cite{mathon}. A few auxiliary functions are needed to complete the implementation. The only real difficulty is posed by the clique counting functions: one that counts cliques, and one that counts cliques that use a given set of edges. The latter function is really the more important, since it is used to compute the $d_i$ (see the outline above). It is important that this function be fast. The choice of temperatures seems to be important. We initialized $T$ to a value of approximately $k/10$, and then decremented it every two or three iterations until it reached one. If, after a number of iterations at one, no further improvement was seen, we set it back to the initial value. The other nontrivial implementation detail concerns the history list. In our implementation, this list was effectively infinite, since the number of iterations was never very large (50000 iterations for the R(6,10) coloring was probably the maximum). In this regard, we differ from \cite{piw}. \begin{center} {\bf Constructions} \end{center} The first set of constructions are circle colorings. Recall that a {\em circle coloring} of $K_n$ (the complete graph on $n$ vertices) is a coloring where the vertices are identified with the integers mod $n$, such that the color of the edge joining vertices $i$ and $j$ depends only on $i-j$. To specify a circle two-coloring it is sufficient to list the differences which are assigned color 1. A circle coloring is {\em symmetric} if the differences $i$ and $n-i$ are assigned the same color, for all $i$, $1 \leq i < n$. Below we list thirteen constructions obtained by applying our method to circle colorings. All the colorings are symmetric, so in each case we give $n$, followed by the differences up to $n/2$ which are assigned the first color. The last two circle colorings use three and four colors, respectively, so the differences assigned to each of the colors are listed. \begin{verbatim} R(5,9) > 115: 1, 2, 3, 14, 15, 16, 20, 22, 23, 24, 26, 28, 35, 36, 37, 39, 42, 45, 47, 49, 52, 55 R(6,7) > 108: 3, 4, 6, 7, 9, 10, 14, 17, 20, 23, 25, 27, 29, 30, 32, 33, 34, 39, 40, 42, 43, 46, 47, 48 R(6,8) > 121: 2, 4, 5, 7, 11, 12, 13, 14, 15, 18, 20, 28, 30, 31, 34, 35, 40, 41, 44, 46, 47, 48, 49, 53, 56, 60 R(6,9) > 152: 4, 6, 10, 11, 12, 15, 16, 19, 21, 22, 24, 26, 31, 34, 36, 40, 42, 43, 47, 49, 50, 52, 53, 54, 60, 64, 66, 67, 69, 70, 72 R(6,10) > 166: 2, 10, 11, 12, 14, 17, 18, 27, 28, 30, 32, 33, 36, 37, 38, 39, 40, 41, 43, 46, 48, 51, 55, 57, 59, 61, 62, 68, 69, 72, 73, 74, 77, 80, 81 R(3,4,5) > 79: Color 1: 5, 8, 11, 14, 17, 21, 23, 24, 27, 30, 36 Color 2: 3, 4, 7, 9, 15, 16, 18, 19, 26, 32, 37, 38, 39 Color 3: 1, 2, 6, 10, 12, 13, 20, 22, 25, 28, 29, 31, 33, 34, 35 R(3,3,3,4) > 86: Color 1: 1, 4, 6, 9, 11, 14, 19, 24, 26, 29, 39, 42 Color 2: 3, 10, 15, 16, 17, 23, 36, 41, 43 Color 3: 2, 7, 12, 13, 22, 27, 30, 33, 38 Color 4: 5, 8, 18, 20, 21, 25, 28, 31, 32, 34, 35, 37, 40 \end{verbatim} We also used the algorithm to look for colorings in which the adjacency matrix can be partitioned into equal sized square blocks, each of which is a circulant matrix. In both cases the adjacency matrix $A$ is given in terms of six blocks. The block structure of $A$ is the same for both colorings: \vspace{2mm} \[ A = \left( \begin{array}{ccc} B & E & G \\ E^t & C & F \\ G^t & F^t & D \end{array} \right) \] \vspace{2mm} It remains to specify the individual blocks $B$, $C$, $D$, $E$, and $F$ for the two cases. We use $n(a_1 a_2 \dots a_t)$ to denote the circulant matrix with (color) 1 entries in positions $a_1$, $a_2$, .., $a_k$. Each of these blocks has color 2 on the main diagonal (of the block). Since the off diagonal blocks ($E$, $F$, and $G$) are not necessarily symmetric, all differences are listed. \newpage \begin{verbatim} R(3,12) > 51: B = 17(7 8 9 10) C = 17(2 6 11 15) D = 17(1 4 13 16) E = 17(2 3 15 16) F = 17(2 7 12) G = 17(2 13 16) \end{verbatim} \vspace{2mm} \begin{verbatim} R(4,8) > 54: B = 18(1 4 5 13 14 17) C = 18(3 6 7 11 12 15) D = 18(3 8 9 10 15) E = 18(0 3 7 9 10 12 17) F = 18(0 5 7 8 16) G = 18(0 3 4 6 9 12 14 16) \end{verbatim} \begin{center} {\bf Building Block Constructions} \end{center} In the course of using the method described above, we obtained values for $R(5,t)$ for $9 \leq t \leq 15$ that improved the entries in the two color table \cite{sprds}. However, it turns out that we can do even better with a different method. Below we describe colorings that improve the lower bounds for $R(5,t)$, $10 \leq t \leq 15$. All the colorings are made the same way. In each case we begin with the adjacency matrix $B$ of a $(3,t-1)$-coloring. Let $C$ be the matrix obtained from $B$ by replacing all the $2$'s by $1$'s and $1$'s by $2$'s, except along the main diagonal. In both both $B$ and $C$ we place $1$'s along their main diagonals. (Note: this reverses the color assignment on the diagonals of the blocks used in the constructions for $R(4,8)$ and $R(3,12)$ given above.) Then our $(5,t)$-colorings will have adjacency matrices with the following form: \vspace{2mm} \[ A = \left( \begin{array}{llll} B & C & B & B \\ C^t & B & B & B \\ B^t & B^t & B & C \\ B^t & B^t & C^t& B \end{array} \right) \] \vspace{2mm} The complete the constructions, we need to specify the $(3,t-1)$-colorings that we are using. These are given in the table below. Note that the sub-colorings for $t=10$ and $t=12$ were first found by Kalbfleisch \cite{kalb}. \begin{center} \begin{tabular}{|r||c|l|} \hline $t$ & Number of vertices & $(3,t-1)$-coloring used \\ \hline 10 & 140 & 35(1,7,11,16) \\ 11 & 152 & 38(1,4,11,13,19) \\ 12 & 180 & 45(3,10,11,12,16) \\ 13 & 192 & 48(5,6,8,15,22,24) \\ 14 & 220 & 55(3,7,11,12,13,27) \\ 15 & 236 & 59(3,9,11,15,16,21) \\ \hline \end{tabular} \vspace{5 mm} \noindent {\bf Table. } $(5,t)$-colorings. \end{center} \begin{thebibliography}{99} \bibitem{tabu} F. Glover, E. Taillard, and D. De Werra. {\em A User's Guide to Tabu Search.} Annals of Operations Research. 41 (1993) 3-28. \bibitem{kalb} J. Kalbfleisch. {\em Chromatic Graphs and Ramsey's Theorem.} Ph.D. Thesis. University of Waterloo, January, 1966. \bibitem{piw} K. Piwakowski. {\em Applying Tabu Search to Determine New Ramsey Graphs.} Electronic J. Combinatorics. 3 (1996) \#R6. \bibitem{mathon} R. Mathon. {\em Lower Bounds for Ramsey Numbers and Association Schemes.} Journal of Combinatorial Theory, Series B. 42 (1987) 122-127. \bibitem{sprds} S. P. Radziszowski. {\em Small Ramsey Numbers.} Dynamic Survey DS1, Electronic J. Combinatorics. 1 (1994), 28 pp. \end{thebibliography} \end{document}