Applying Tabu Search to Determine New Ramsey Graphs

Konrad Piwakowski

Technical University of Gdańsk Department of Foundations of Informatics^{∗} Narutowicza 11/12 80-952 Gdańsk, Poland e-mail: coni@sunrise.pg.gda.pl

Submitted: November 16, 1995; Accepted: January 24, 1996.

Abstract

In this note an adaptation of heuristic tabu search algorithm for finding Ramsey graphs is presented. As a result, seven new lower bounds for classical Ramsey numbers are established: R(3, 13) ≥ 59, R(4, 10) ≥ 80, R(4, 11) ≥ 96, R(4, 12) ≥ 106, R(4, 13) ≥ 118, R(4, 14) ≥ 129, and R(5, 8) ≥ 95.

1 Introduction

Let us define a (k, l; n)-Ramsey graph, or in short (k, l; n)-Rg, to be a graph on n vertices which does not contain clique of order k or an independent set of order l. The Ramsey number R(k, l) is defined to be the smallest integer n > 0 such that, there is no (k, l; n)-Rg. Our approach to establishing a new lower bound for a Ramsey number, R(k, l) ≥ n, is based on the idea of heuristic search for a (k, l; n − 1)-Rg in a space of highly regular graphs on n − 1 vertices. Similar methods have been used to improve lower bounds for small classical Ramsey numbers by searching restricted space of graphs. For example, see [1], [6], [9], and [10]. Others can be found referenced in Radziszowski’s excellent extensive survey of known bounds and values of various kinds of Ramsey numbers [8]

The following sections contain descriptions of our algorithms, and the Ramsey graphs which imply the new lower bounds. Some of these bounds were previously announced in [7].

2 Tabu search

2.1 General framework

The tabu search (T S) method is a heuristic procedure which has proved to be very efficient in solving many combinatorial optimization problems. A detailed description of it is given in [4]. Our approach makes use of T S in its simplest form outlined below.

For a given optimization problem: min_{s∈S} f(s), where f is called objective function and S denote the space of all allowed states, T S starts from an initial state s ∈ S chosen arbitrarily and explores the space S by moving from one state to another subject to a defined neighborhood function Nb : S → 2^{S}. During each step, the actual state s is replaced by its neighbor having the least value of f. If more than one state has the same minimal value the tie is broken randomly. This process is stopped when a new state satisfies the required condition. In order to avoid some of the possible loops, a FIFO queue called the tabu list is provided. Its aim is to remember recently visited states which are forbidden and cannot be chosen during state replacement. We show this simple form of T S in pseudo-code:

∗ The computational results presented in this paper were partly obtained using machines from the Academic Computer Center in Gdańsk TASK.

• choose any s ∈ S as the initial state

• initialize tabu list T = ∅

• while s is not acceptable do: • insert s into T

• if T is full remove the oldest element

• replace s with s′ ∈ Nb(s) ∖ T satisfying f(s′) = min_{u∈Nb(s)∖T} f(u)

2.2 Adaptation for search of Ramsey graphs

To implement T S for a particular application, one must specify the search space S, objective function f, neighborhood function Nb, final acceptance criterion, method of choosing initial state and length of the tabu list T. In this paper we only give the specifications used in our computational experiments.

Let us assume that we are looking for a (k, l; n)-Rg, where k ≤ l.

Restricted space of graphs. For a given edge partition of a complete graph K_{n} into r graphs: E = {G_{1}, G_{2}, …, G_{r}}, where V (G_{i}) = V (K_{n}) for 1 ≤ i ≤ r, E(K_{n}) = ⋃_{i=1}^{r} E(G_{i}) and E(G_{i}) ∩ E(G_{j}) = ∅ for 1 ≤ i ≠ j ≤ r, we define the space S to be the family of all graphs without independent sets of size l, obtained by the union of any subset of E:

S = {G_{I} = ⋃_{i∈I} G_{i} | I ⊆ {1, 2, …, r}, K_{l} ⊈Ḡ_{I}} .

We have considered many different types of partition E. However, the results which improve the known lower bounds of Ramsey numbers were established using only two such types. One of them leads to the search among cyclic graphs. The other slightly generalizes the previous one. A detailed discussion of the partitions used is presented in the next section.

The neighborhood function. Two graphs G_{I} and G_{J} are defined to be neighbors iff one of them can be obtained from another by union with exactly one element from E:

G_{I} ∈ Nb(G_{J}) ⇔ |(I ∪ J) ∖ (I ∩ J))| = 1

The objective function and the final acceptance criterion are clear: f(G) is simply equal to the number of cliques of size k contained in G, and the process stops iff f(G) = 0.

The tabu list is slightly different from that of the previous general description. It is easy to see that one iteration in this implementation is always a union or disunion of a previously reached graph and one element of E. Instead of remembering recently generated graphs, the tabu list only keeps the indices of elements of E which were used during recent replacements. Replacements leading to insertion or removal of an element of E which is on the tabu list are not allowed. The tabu queue defined in this way is more restrictive than in the definition but consumes much less computation time. The length of the tabu list was adjusted experimentally depending on the parameters k, l, n, r (usually between \frac{1}{10}r and \frac{3}{10}r).

A complete graph K_{n} is taken as the initial state.

3 Results

3.1 Cyclic graphs

Following the earlier works mentioned in the Introduction, we first concentrated on cyclic graphs. For a given vertex set {0, 1, …, n − 1} define the distance function d(v, w) = min{|v − w| , n − |v − w|}. Each graph of the partition E contains edges which have the same distance d:

E = \{G_{1}, G_{2}, …, G⌊_{\frac{n}{2}}⌋\},
{v, w} ∈ E(G_{i}) ⇔ d(v, w) = i.

Using this specification we obtained surprisingly good results. In a short time our algorithm found examples of cyclic Ramsey graphs demonstrated almost all the lower bounds established by Radziszowski and Kreher in [9], where exhaustive searches for cyclic graphs were performed. This fact confirms efficiency of our heuristic. Moreover, new lower bounds have been established for the following numbers: R(4, 10), R(4, 11), R(4, 12), R(4, 13), R(4, 14), and R(5, 8). The values of the new bounds and the indices of the E-components of the corresponding cyclic graphs are presented in Table I. For comparison, we give a list of the best lower bounds for these Ramsey numbers known before. R(4, 10) ≥ 72 [1]. R(4, 11) ≥ 77 as a consequence of R(4, 9) ≥ 69 [9] and R(4, 3) = 9 [5]. R(4, 12) ≥ 86 as a consequence of R(4, 9) ≥ 69 [9] and R(4, 4) = 18 [5]. Recently, a new lower bound R(4, 12) ≥ 98 has been announced (as [2]) in the latest revision of [8]. R(4, 13) ≥ 97 as a consequence of R(4, 7) ≥ 49 [3]. R(4, 14) ≥ 103 [1]. R(5, 8) ≥ 94 [9].

Table I. New lower bounds and corresponding cyclic Ramsey graphs.

Ramsey New
number lower  Cyclic (k, l; r − 1) − Ramsey graph
R(k, l) bound r
R(4, 10)  80  6, 8, 11, 12, 15, 16, 22, 25, 26, 27, 32, 34, 35
R(4, 11)  96  3, 5, 6, 7, 10, 11, 12, 14, 20, 22, 24, 42, 44, 45, 46
R(4, 12)  106  4, 6, 7, 10, 11, 20, 22, 24, 29, 32, 35, 40, 43, 47, 48, 49
R(4, 13)  118  5, 16, 17, 23, 25, 31, 34, 36, 37, 40, 43, 45, 47, 48, 49, 55, 58
R(4, 14)  129  4, 7, 8, 11, 20, 22, 23, 24, 27, 30, 41, 49, 51, 54, 59, 60, 62
R(5, 8)  95  2, 6, 7, 9, 10, 14, 16, 17, 21, 27, 30, 31, 32, 35, 39, 40, 41, 43, 44, 45, 47

3.2 (3, 13; 58)-Ramsey graph

Let a set of 2n vertices be formed by two sets A = {a_{0}, a_{1}, …, a_{n−1}} and B = {b_{0}, b_{1}, …, b_{n−1}}. Define the partition E as follows:

E = \{G_{1}^{A}, G_{2}^{A}, …, G⌊\frac{n}{2}⌋^{A}, G_{1}^{B}, G_{2}^{B}, …, G⌊\frac{n}{2}⌋^{B}, G_{0}^{C}, G_{1}^{C}, …, G_{n−1}^{C}\}
{a_{i}, a_{j}} ∈ E(G_{d(i,j)}^{A}) for 0 ≤ i ≠ j < n
{b_{i}, b_{j}} ∈ E(G_{d(i,j)}^{B}) for 0 ≤ i ≠ j < n
{a_{i}, b_{j}} ∈ E(G_{d′(i,j)}^{C}) for 0 ≤ i, j < n, where
d(i, j) = min{|i − j| , n − |i − j|}
d′(i, j) = (j − i + n) mod n.

Using this partition E we derived (3, 13; 58)-Rg G_{3}^{A} ∪ G_{4}^{A} ∪ G_{10}^{A} ∪ G_{12}^{A} ∪ G_{2}^{B} ∪ G_{3}^{B} ∪ G_{10}^{B} ∪ G_{14}^{B} ∪ G_{0}^{C} ∪ G_{5}^{C} ∪ G_{13}^{C} ∪ G_{18}^{C} which improves the best previously known lower bound R(3, 13) ≥ 58 [6] by one.

Finally, let us note that a better lower bound R(3, 13) ≥ 60 was claimed in [11]. Unfortunately, the cyclic graph C_{59}(1, 3, 5, 7, 16, 25) described in that paper as a (3, 13; 59)-Rg contains a number of independent sets of size 13, for example {0, 2, 6, 10, 14, 20, 24, 28, 32, 38, 42, 46, 50}.

References

[1] F. Bannani, Bounds on classical Ramsey numbers, Ph.D. thesis, Carleton University, Ottawa, November 1988.

[2] N. J. Calkin, P. Erdős, and C. A. Tovey, New Ramsey bounds from cyclic graphs of prime order, in preparation, 1995.

[3] G. Exoo, Appling optimization algorithm to Ramsey problems, Graph Theory, Combinatorics, Algorithms and Applications (Philadelphia) (Y. Alavi, ed.), SIAM, 1989, pp. 175– 179.

[4] F. Glover, E. Taillard, and D. De Werra, A user’s guide to tabu search, Annals of Operations Research 41 (1993), 3–28.

[5] R. E. Greenwood and A. M. Gleason, Combinatorial relations and chromatic graphs, Canadian Journal of Mathematics 7 (1955), 1–7.

[6] J. G. Kalbfleisch, Chromatic graphs and Ramsey’s theorem, Ph.D. thesis, University of Waterloo, January 1966.

[7] K. Piwakowski, Some remarks on classical Ramsey numbers, System Modelling Control 7 (Zakopane, Poland), vol. 2, 1993, pp. 106–110.

[8] S. P. Radziszowski, Small Ramsey numbers, Electronic Journal of Combinatorics 1 (1994),

28 pages, link Dynamic Survey from http://ejc.math.gatech.edu:8080/Journal/
ejc-wce.html.

[9] S. P. Radziszowski and D. L. Kreher, Search algorithm for Ramsey graphs by union of group orbits, Journal of Graph Theory 12 (1988), 59–72.

[10] QingXian Wang, GongBen Wang, and ShuDa Yan, A search algorithm and new lower bounds for Ramsey numbers R(3, q), to appear.

[11] Jiguo Xie and Xiaoxian Zhang, A new lower bound for Ramsey number R(3, 13), Journal of Lanzhou Railway Institute 12 (1993), 87–89, (in Chinese).