A Lower Bound for Schur Numbers and Multicolor Ramsey Numbers of K_{3}

Geoffrey Exoo Department of Mathematics and Computer Science Indiana State University Terre Haute, IN 47809 ge@judy.indstate.edu

Submitted: September 13, 1994; Accepted: September 18, 1994

Abstract

For k ≥ 5, we establish new lower bounds on the Schur numbers S(k) and on the k-color Ramsey numbers of K_{3}.

For integers m and n, let [m, n] denote the set {i | m ≤ i ≤ n}. A set S of integers is called sum-free if i, j ∈ S implies i + j ∉ 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 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) ≥ 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 [1]. The best previously published bounds for S(5) are 157 ≤ S(5) ≤ 321, the lower bound was proved in [4] and the upper bound in [6]. 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 [5].

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.

Set 1: 4 5 15 16 22 28 29 39 40 41 42 48 49 59

Set 2: 2 3 8 14 19 20 24 25 36 46 47 51 62 73

Set 3: 7 9 11 12 13 17 27 31 32 33 35 37 53 56 57 61 79

Set 4: 1 6 10 18 21 23 26 30 34 38 43 45 50 54 65 74

Set 5: 44 52 55 58 60 63 64 66 67 68 69 70 71 72 75 76 77 78 80

This proves that S(5) ≥ 160. It follows that R_{5}(3) ≥ 162. From [1] and [2] we have S(k) ≥ c(321)^{k/5} > c(3.17176)^{k} for some positive constant c. From the recurrence R_{k}(3) ≥ 3 R_{k−1}(3) + R_{k−3}(3) − 3 proved in [3] we also have R_{6}(3) ≥ 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 nonisomorphic 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}, …, S_{k}}. For 1 ≤ t ≤ n, let P_{t} denote the partition of [1, t] induced by P (i.e., P_{t} = {S_{1} ∩ [1, t], …, S_{k} ∩ [1, t]}). For integers i and j, it is convenient to define

g_{n}(i, j) = \{ \begin{matrix}0 & if i + j ≤ n, \\ 2n − i − j & otherwise. \end{matrix}

Then define:

f_{1}(P) = max{t|P_{t} is sum-free}

f_{2}(P) = ∑_{i=1}^{k} ∑_{s,t∈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 sumfree partition had 44 elements. Many such partitions of [1, n], 157 ≤ n ≤ 160, were found, but those with sets containing 45 or more elements seem to be rare, if they exist.

References

[1] H. L. Abbott and D. Hanson. A Problem of Schur and its Generalizations. Acta Arithmetica, 20 (1972), 175-187.

[2] H. L. Abbott and L. Moser. Sum-free Sets of Integers. Acta Arithmetica, 11 (1966), 392-396.

[3] F. R. K. Chung. On the Ramsey Numbers N(3,3,...,3;2). Discrete Math, 5(1973), 317-321.

[4] H. Fredrickson. Schur Numbers and the Ramsey Numbers N(3,3,...,3;2). J. Combin. Theory Ser A, 27 (1979), 371-379.

[5] S. P. Radziszowski. Small Ramsey Numbers. Dynamic Survey DS1, Electronic J. Combinatorics 1 (1994), 28 pp.

[6] E. G. Whitehead. The Ramsey Number N(3,3,3,3;2). Discrete Math, 4 (1973), 389-396.