30 ≤ R(3,3,4) ≤ 31

Konrad Piwakowski  Stanisław P. Radziszowski^{∗}
Department of Foundations of Informatics  Department of Computer Science
Technical University of Gdańsk  Rochester Institute of Technology
80-952 Gdańsk, Poland  Rochester, NY 14623, USA
coni@pg.gda.pl  spr@cs.rit.edu

Abstract

With the help of computer algorithms, we improve the upper bound on the classical three color Ramsey number R(3, 3, 4), and thus we show that the exact value of this number is 30 or 31. We also present computer enumeration of all 3-colorings of edges on at least 14 vertices without monochromatic triangles.

1. Introduction and Notation

An (r_{1}, r_{2}, …, r_{k}) coloring, r_{i} ≥ 1 for 1 ≤ i ≤ k, is an assignment of one of k colors to each edge in a complete graph, such that it does not contain monochromatic complete subgraph K_{r_{i}} in color i, for 1 ≤ i ≤ k. Similarly, an (r_{1}, r_{2}, …, r_{k}; n) coloring is an (r_{1}, …, r_{k}) coloring of K_{n}. Let R(r_{1}, …, r_{k}) and R(r_{1}, …, r_{k}; n) denote the set of all (r_{1}, …, r_{k}) and (r_{1}, …, r_{k}; n) colorings, respectively. The Ramsey number R(r_{1}, …, r_{k}) is defined to be the least n > 0 such that R(r_{1}, …, r_{k}; n) is empty.

A coloring using k colors will be also called a k-coloring. Clearly, any 2-coloring can be considered as a graph. In this paper we will study k-colorings only for k = 2 or k = 3. In the former case we will also use standard graph theory terminology. A regularly updated survey of the most recent results on the best known bounds on multicolor (k > 2) and graph (k = 2) Ramsey numbers can be found in [Rad].

In 1966 Kalbfleisch [Kalb] constructed a cyclic (3, 3, 4; 29) coloring, which to date gives the best known lower bound R(3, 3, 4) ≥ 30. Recently, Piwakowski [Piw] obtained an upper bound R(3, 3, 4) ≤ 32. In this paper we reduce this bound to 31, and we conjecture that the exact value of this Ramsey number is 30. We note that the only known nontrivial value of a multicolor classical (i.e. avoiding monochromatic complete subgraphs) Ramsey number is R(3, 3, 3) = 17 [GG], and at the moment the only other multicolor case which seems not hopeless is R(3, 3, 4).

∗ supported in part by a grant from the NSA number MDA904-94-H-2009.

Two k-colorings are isomorphic if there exist a bijection between the vertices of the underlying complete graphs preserving all the colors of edges, and they are weakly isomorphic if there exists a bijection between vertices which preserves the relation of two edges having the same color. It is convenient to think of a weak isomorphism as a composition of permutation of colors with an isomorphism; for example any graph G, seen as a 2-coloring, is weakly isomorphic to its complement \overline{G}.

Let C be a k-coloring and G be a simple undirected graph. Throughout this paper we will also use the following notation.

deg_{G}(x)  — the degree of vertex x in graph G
n(G), e(G)  — the number of vertices and edges in graph G
V (G), E(G)  — the vertex and edge sets of graph G
N_{G}(x)  — the neighborhood of vertex x in graph G
C[i]  — the graph formed by edges of color i in coloring C
C_{x}^{i}  — the coloring induced in C by vertices in N_{C[i]}(x)
C_{x}^{i}[j]  — the graph formed by edges of color j in coloring C_{x}^{i}
R(a, b, c; ≥ n) — ⋃_{k≥n} R(a, b, c; k)

2. (3, 3, 3) Colorings

The main result of this paper is that (3, 3, 4; 31) colorings don’t exist. If C is a (3, 3, 4; m) coloring then, clearly, for every vertex x, C_{x}^{3} is a (3, 3, 3; deg_{C[3]}(x)) coloring, so the latter are important in the study of R(3, 3, 4). Independently, such colorings are interesting by themselves, and this section gathers basic information about them.

In 1968 Kalbfleisch and Stanton [KS] proved that there are exactly two nonisomorphic (3, 3, 3; 16) colorings; let us denote them by KS_{1} and KS_{2}. Since R(3, 3) = 6, by merging two colors in any (3, 3, 3; n) coloring, we obtain a (3, 6; n) graph. It is interesting that all six (3, 6; 16) graphs obtained in this way from R(3, 3, 3; 16) are isomorphic, yet the 3-colorings KS_{1} and KS_{2} are not even weakly isomorphic. Both KS_{1} and KS_{2} are vertex transitive, and the common underlying (3, 6; 16) graph can be defined over GF (2^{4}) with two vertices being adjacent if and only if their difference is a cube.

Deleting one point from the vertex transitive colorings KS_{1} and KS_{2} leads to exactly two nonisomorphic (3, 3, 3; 15) colorings, with 35 edges in each color. In a technically very complicated paper, but without using a computer, Heinrich [Hein] was able to prove that no other such colorings exist, i.e. |R(3, 3, 3; 15)| = 2.

Our computations related to R(3, 3, 3; n) confirmed all the above results, generated all such colorings on n ≥ 14 vertices, and enumerated all possible (3, 6; n) graphs which form a single color, for all n.

counts of  nonisomorphic weakly nonisomorphic
edge colors  colorings  colorings
31 30 30  249  45
31 31 29  126  23
32 30 29  138  23
32 31 28  60  10
33 29 29  24  5
33 30 28  36  6
34 29 28  12  2
35 28 28  6  1
all  651  115

Table 1. Statistics for R(3, 3, 3; 14) colorings number of

n  (3, 6, n) graphs  splittable  nonsplittable
1  1  1  0
2  2  2  0
3  3  3  0
4  7  7  0
5  14  14  0
6  37  37  0
7  100  100  0
8  356  355  1
9  1407  1395  12
10  6657  6444  213
11  30395  26034  4361
12  116792  58538  58254
13  275086  21921  253165
14  263520  66  263454
15  64732  1  64731
16  2576  1  2575
17  7  0  7
all  761692  114919  646773

Table 2. (3, 6) graphs splittable to (3, 3, 3) colorings

We found that there are exactly 651 nonisomorphic (3, 3, 3; 14) colorings, which is reduced to only 115 up to weak isomorphism. The number of edges in any single color ranges from 28 to 35. Table 1 presents the numbers of these colorings, divided into classes with the same edge count in three colors. Note that the ratio between the last two columns is at most 3!, and it is equal to 6 iff each coloring in this class under all permutations of 3 colors leads to 6 nonisomorphic colorings.

Having at our disposition a data base of all (3, 6; n) graphs [RK], which were verified and used in few previous Ramsey related projects, we have checked for each (3, 6; n) graph whether its complement can be split into two colors yielding a (3, 3, 3; n) coloring. The cumulative data is gathered in Table 2. These splittable graphs are exactly those which can form a single color subgraph in any member of R(3, 3, 3). For example, only 66 graphs can form a single color in a (3, 3, 3; 14) coloring. For this work, all colorings in R(3, 3, 3; ≥14) were generated independently by each of the authors and compared. The computer time needed for obtaining and verifying these results was very small.

3. Algorithm and Computations

The following simple lemma is the basis of the skeleton of our computations showing that R(3, 3, 4) ≤ 31.

Lemma 1. In any (3, 3, 4; 31) coloring C there are three vertices x,y and z such that xyz forms a triangle in the third color, and C_{x}^{3}, C_{y}^{3}, C_{z}^{3} ∈ R(3, 3, 3; ≥ 14).

Proof. R(3, 4) = 9 implies that the minimum degree in the graph C[3] is at least 14 = 31 − 8 − 8 − 1. Since R(3, 3, 3) = 17, C must have triangles in the third color. Thus a triangle, as required by the lemma, exists.

Given an arbitrary (3, 3, 3; n) coloring C, consider the set of colorings obtained by distinguishing each of the n(n − 1)/2 edges in C. Let M denote the set of all such weakly nonisomorphic colorings with a distinguished edge, obtained from R(3, 3, 3; ≥ 14), where weak isomorphisms preserve the distinguished edges (a distinguished edge can be considered as having color 4). With computer help we have found that M consists of exactly 5670 (3, 3, 3) colorings with a distinguished edge: 3 on 16 vertices, 13 on 15 vertices, and 5654 on 14 vertices. We will write (C, e) ∈ M to denote that the edge e has been distinguished in coloring C.

Assume C and xyz are as in Lemma 1. Clearly, each of (C_{x}^{3}, {y, z}), (C_{y}^{3}, {x, z}), and (C_{z}^{3}, {x, y}) must be weakly isomorphic to some coloring in the set M. The colorings in M form the starting points of the main algorithm constructing (3, 3, 4; m) colorings from a triangle in color 3 supporting three overlapping elements of M. The following algorithm was executed for all triples, repetitions allowed, of (3, 3, 3) colorings with a distinguished edge in M.

The Algorithm

Step 1: Let (C_{1}, e_{1}), (C_{2}, e_{2}), (C_{3}, e_{3}) ∈ M. The distinguished edges e_{1}, e_{2}, e_{3} have color 3. Produce 16 starting configurations X by exchanging colors 1 and 2 in C_{2} and C_{3} (4 possibilities) and, independently, by assembling a triangle T from the edges e_{1}, e_{2}, e_{3} by identifying their endpoints in pairs (4 possibilities).

Step 2: Without loss of generality, assume that X = (C_{1}, {y, z}), (C_{2}, {x, z}), (C_{3}, {x, y}) with T = {x, y, z}. Reject X if

deg_{C_{1}[3]}(y) ≠ deg_{C_{2}[3]}(x),
deg_{C_{1}[3]}(z) ≠ deg_{C_{3}[3]}(x),

or

deg_{C_{2}[3]}(z) ≠ deg_{C_{3}[3]}(y).

Otherwise, find all possible embedding of X into the situation as in Lemma 1 by permuting vertices in N_{C_{2}[3]}(x), N_{C_{3}[3]}(x) and N_{C_{3}[3]}(y), while keeping the vertices of T fixed. Identify N_{C_{1}[3]}(y) with N_{C_{2}[3]}(x), N_{C_{1}[3]}(z) with N_{C_{3}[3]}(x), and N_{C_{2}[3]}(z) with N_{C_{3}[3]}(y). If the identified neighborhoods induce identical colorings in all three cases, then such relabeled X can be considered a partial coloring on

m = n(C_{1}) + n(C_{2}) + n(C_{3}) − deg_{C_{1}[3]}(y) − deg_{C_{1}[3]}(z) − deg_{C_{2}[3]}(z)

vertices. Reject X if it contains a triangle in color 1 or 2. After this step, the colored edges of X are only those which where taken from some C_{i} and the edges in color 3 between T and V (X) − T.

Step 3: For every partial coloring on m vertices obtained in Step 2, assign three possible colors to each uncolored edge, and iterate the following process. For each edge with more than one possible color, delete colors which lead to a forbidden clique or violate obvious degree restrictions. Terminate if some edge has no possible colors. If there is no edge for which the deletion of possible colors is enforced, then go to Step 4. There is no branching in this step.

Step 4: Perform the exhaustive search for all possible extensions of partial colorings obtained in Step 3 to full (3, 3, 4) colorings on m vertices.

The algorithm outlined above did not produce any full (3, 3, 4) coloring on the input set M. A large number of partial colorings were produced at Steps 2 and 3. These were generated by two independent implementations by each of the two authors, and they always agreed up to isomorphism. In addition, the Step 4 was tested on other data known to produce nonempty results.

Theorem 1. There does not exist a (3, 3, 4) coloring C with a triangle xyz in color 3, such that deg_{C[3]}(x), deg_{C[3]}(y), deg_{C[3]}(z) > 13.

Proof. The computations described above showed that no such coloring exists.

Two excellent programs, written by Brendan McKay, were used in this work: nauty [McK] for testing isomorphism of edge colorings, and autoson for distributing a large number of small tasks over a local area network. The total time required for all computations was about 0.5 CPU years, mostly on Sun Sparcstations and SGI Indys. This was achieved in a reasonable amount of time by employing a number of computers simultaneously.

4. New Bound

Theorem 2. 30 ≤ R(3, 3, 4) ≤ 31.

Proof. The lower bound follows from a cyclic coloring of the edges of K_{29} with vertex set Z_{29}, in which {1, 4, 10, 12}, {2, 5, 6, 14} and {3, 7, 8, 9, 11, 13} are the vertex distances in Z_{29} of the first, second, and third color, respectively. This coloring was found by Kalbfleisch [Kalb]. Lemma 1 and Theorem 1 give the upper bound.

Theorem 3. R(3, 3, 4) = 31 if and only if there exists a (3, 3, 4; 30) coloring C such that every triangle T ⊂ C[3] has a vertex x ∈ T with deg_{C[3]}(x) = 13, and furthermore C has at least 14 vertices v such that deg_{C[1]}(v) = deg_{C[2]}(v) = 8 and deg_{C[3]}(v) = 13.

Proof. By Theorem 2 it is sufficient to show that any (3, 3, 4; 30) coloring C has the properties as required on the right hand side. R(3, 4) = 9 implies that for every vertex v, deg_{C[3]}(v) ≥ 13 = 30 − 8 − 8 − 1. Thus the first part is an immediate consequence of Theorem 1. For the second part, assume that C has at most 13 vertices with the required degree distribution. Then, for at least 17 vertices deg_{C[3]}(v) ≥ 14, and since R(3, 3, 3) = 17 we conclude further that some three of them form a triangle in color 3. This contradicts Theorem 1, and completes the proof.

It appears that our current approach is not efficient enough to proceed similarly with all (3, 3, 3; 13) colorings, though such computations would lead to the determination of the exact value of R(3, 3, 4). We conjecture that R(3, 3, 4) = 30. The evidence to support it consists of the intermediate results of the computations completed for this work, which showed that the known (3, 3, 4; ≥ 28) colorings are quite exceptional. In addition, we have also performed a large number of heuristic searches for such colorings, without finding any new ones. The only known (3, 3, 4; 29) coloring is the one found by Kalbfleisch (described above), and the only known (3, 3, 4; 28) coloring is obtained from it by the deletion of one vertex.

References

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

[Hein] K. Heinrich, Proper colourings of K_{15}, Journal of the Australian Mathematical Society, Series A, 24 (1977), 465–495.

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

[KS] J. G. Kalbfleisch and R. G. Stanton, On the maximal triangle-free edge-chromatic

graphs in three colors, Journal of Combinatorial Theory, 5 (1968), 9–20.

[McK] B. D. McKay, Nauty users’ guide (version 1.5), Technical report TR-CS-90-02, Computer Science Department, Australian National University, 1990.

[Piw] K. Piwakowski, On Ramsey number R(4, 3, 3) and triangle-free edge-chromatic graphs in three colors, to appear in Discrete Mathematics.

[Rad] S. P. Radziszowski, Small Ramsey numbers, Electronic Journal of Combinatorics, Dynamic Survey 1, 1994–6. WWW reference:

http://ejc.math.gatech.edu:8080/Journal/Surveys/index.html.

[RK] S. P. Radziszowski and D. L. Kreher, On (3, k) Ramsey Graphs: Theoretical and Computational Results, Journal of Combinatorial Mathematics and Combinatorial Computing, 4 (1988) 37–52.