Subgraph Counting Identities and Ramsey Numbers To the fond memory of Paul Erdős

Brendan D. McKay^{+}  Stanisław P. Radziszowski^{∗}
Department of Computer Science  Department of Computer Science
Australian National University  Rochester Institute of Technology
Canberra, ACT 0200, Australia  Rochester, NY 14623, USA
bdm@cs.anu.edu.au  spr@cs.rit.edu

Abstract.

For each vertex v of a graph G, we consider the numbers of subgraphs of each isomorphism class which lie in the neighbourhood or complementary neighbourhood of v. These numbers, summed over v, satisfy a series of identities that generalise some previous results of Goodman and ourselves. As sample applications, we improve the previous upper bounds on two Ramsey numbers. Specifically, we show that R(5, 5) ≤ 49 and R(4, 6) ≤ 41. We also give some experimental evidence in support of our conjecture that R(5, 5) = 43.

1. Introduction.

We shall only consider graphs without multiple edges or loops. For s, t, n ≥ 1, an (s, t)-graph is a graph without cliques of order s or independent sets of order t, and an (s, t, n)-graph is an (s, t)-graph of order n. Similarly, an (s, t, n, e)-graph is an (s, t, n)-graph with e edges. Let R(s, t), R(s, t, n) and R(s, t, n, e) denote the set of all (s, t)-graphs, (s, t, n)-graphs and (s, t, n, e)-graphs, respectively. The Ramsey number R(s, t) is defined to be the least n > 0 such that there is no (s, t, n)-graph.

A regularly updated survey of the most recent results on this subject can be found in [20].

In Section 2, we derive some identities involving subgraph counts, which form the basis of our approach. In Section 3, we show that R(5, 5) ≤ 49, which improves over the previous bound of 50 [17]. Nevertheless, the correct value is more likely to be 43, for the reasons we give in Section 4. Finally, in Section 5, we show that R(4, 6) ≤ 41 by linear programming methods. Comprehensive surveys of the history of R(5, 5) and R(4, 6) will be given in the appropriate sections.

+ Supported in part by ARC grant ANU-F95003 and by the Computer Science Department of the Rochester Institute of Technology

∗ Supported in part by NSA grant MDA904-94-H-2009

2. Subgraph identities.

For two graphs J and G, let s(J, G) denote the number of induced subgraphs of G that are isomorphic to J. It will be convenient to permit both J and G to be the “graph” K_{0}, which has no vertices or edges. In this case we define s(K_{0}, G) = 1 for all G and s(J, K_{0}) = 0 for all J ≠ K_{0}.

A summary of much of what is known about this “algebra of subgraphs” can be found in [12]. For our purposes, the following theorem is important.

Theorem 2.1.

(a) For each disconnected graph J, there is a sequence of connected graphs J_{1}, J_{2}, …, J_{k} and a polynomial p_{J} with rational coefficients such that

s(J, G) = p_{J}(s(J_{1}, G), s(J_{2}, G), …, s(J_{k}, G))

for every graph G.

(b) There is no sequence of nonisomorphic connected graphs J_{1}, J_{2}, …, J_{k} and nonzero polynomial p such that

p(s(J_{1}, G), s(J_{2}, G), …, s(J_{k}, G)) = 0

for all graphs G.

Proof. Part (a) was proved by Whitney [26], while part (b) follows from a considerably stronger result of Erdős, Lovász and Spencer [3].

We will need a particular case of part (a) of this theorem, stated as Lemma 2.1 below. For m ≥ 0 and 0 ≤ j ≤ m, define the graphs T_{m,j} as follows. For m = 0, define T_{0,0} = K_{1}. For m > 0, T_{m,0} is the disconnected graph K_{m} ∪ K_{1}, and for j ≥ 0, T_{m,j+1} is formed by adding one edge to T_{m,j}. It is easy to see that this defines T_{m,j} uniquely up to isomorphism and that T_{m,m} = K_{m+1}.

Lemma 2.1. Suppose G is a graph with n vertices. Then, for m ≥ 0,

(n − m)s(K_{m}, G) = ∑_{j=0}^{m} β_{m,j}s(T_{m,j}, G),  (1)

where

β_{m,j} = \{ \begin{matrix}m + 1, & if j = m; \\ 2, & if j = m − 1; \\ 1, & if 0 ≤ j ≤ m − 2. \end{matrix}

Proof. Since n = s(K_{1}, G) and T_{m,0} is the only disconnected graph appearing here, this is an special instance of Theorem 2.1 (a).

The cases m = 0, 1 are easy to check, so we can assume m ≥ 2. Both sides of (1) count the number of subgraphs of the form K_{m} ∪ K_{1}, induced or not. The left side of (1) is obvious in this context. For the right side, consider the number j of edges that join the K_{m} to the K_{1}. These m + 1 vertices induce a subgraph T_{m,j}. Finally, note that each subgraph T_{m,j} can arise in s(K_{m}, T_{m,j}) = β_{m,j} such ways.

For m = 2, Lemma 2.1 becomes

(n − 2)s(K_{2}, G) = s(T_{2,0}, G) + 2s(T_{2,1}, G) + 3s(K_{3}, G),

which is equivalent to Goodman’s identity [7].

We will find it convenient to adopt the following notational conventions. If G is a graph, then VG and EG are its vertex set and edge set, respectively. If v ∈ VG and W ⊆ VG, then N_{G}(v, W) = {w ∈ W | vw ∈ EG}. The subgraph of G induced by W will be denoted by G[W]. Also define the induced subgraphs G_{v}^{+} = G[N_{G}(v, VG)] and G_{v}^{−} = G[VG − N_{G}(v, VG) − {v}].

Lemma 2.2. Let J and G be graphs.

(a) If J has k ≥ 1 vertices of degree |VJ | − 1, then

k s(J, G) = ∑_{v∈VG} s(J′, G_{v}^{+}),

where J′ is the result of removing from J a vertex of degree |VJ | − 1.

(b) If J has k ≥ 1 vertices of degree 0, then

k s(J, G) = ∑_{v∈VG} s(J′′, G_{v}^{−}),

where J′′ is the result of removing from J a vertex of degree 0.

Proof. In case (a), each subgraph isomorphic to J lies in {v} ∪ N_{G}(v, VG) for exactly k vertices v, so both sides of the identity count induced subgraphs isomorpic to J with a vertex of maximum degree distinguished. Case (b) is similar.

Each of the subgraphs involved in Lemma 2.1 matches one of the types considered by Lemma 2.2. This yields a family of identities involving those functions. Let δ_{i,j} denote the Kronecker delta.

Theorem 2.2. For m ≥ 1, every graph G satisfies

\begin{aligned}∑_{v∈VG} s(K_{m}, G_{v}^{−}) & = ∑_{v∈VG}((n/m − s(K_{1}, G_{v}^{+}) + m − 2)s(K_{m−1}, G_{v}^{+}) \\ & + (m − 1)s(K_{m}, G_{v}^{+}) + ∑_{j=1}^{m−2} \frac{(1 + δ_{j,m−2})j}{j + 1} s(T_{m−1,j}, G_{v}^{+})). \end{aligned}

Proof. The case m = 1 is easy to check directly, so we will assume m ≥ 2.

From Lemma 2.2, using (b) for j = 0 and (a) for j > 0, we have

s(T_{m,j}, G) = \{ \begin{matrix}\frac{1}{1 + δ_{m,1}} ∑_{v∈VG} s(K_{m}, G_{v}^{−}), & for j = 0; \\ \frac{1}{j + δ_{j,m}} ∑_{v∈VG} s(T_{m−1,j−1}, G_{v}^{+}), & for 1 ≤ j ≤ m. \end{matrix}

Applying Lemma 2.2 (a) for J = K_{m}, we can substitute into Lemma 2.1 to obtain

\frac{n − m}{m} ∑_{v∈VG} s(K_{m−1}, G_{v}^{+}) = ∑_{v∈VG} s(K_{m}, G_{v}^{−}) + ∑_{j=1}^{m} \frac{β_{m,j}}{j + δ_{j,m}} ∑_{v∈VG} s(T_{m−1,j−1}, G_{v}^{+}).

(2)

All the subgraphs appearing as the first argument of s( ) in (2) are connected except T_{m−1,0}. Using Lemma 2.1 again, we have that

s(T_{m−1,0}, G_{v}^{+}) = \frac{1}{β_{m−1,0}} ((s(K_{1}, G_{v}^{+})−m+1)s(K_{m−1}, G_{v}^{+})− ∑_{j=1}^{m−1} β_{m−1,j}s(T_{m−1,j}, G_{v}^{+})).

Substituting into (2) and collecting similar terms gives the desired identity.

The case of m = 1 is elementary, and the case of m = 2 is equivalent to Goodman’s identity. Though less obvious, the identity for m = 3 can be derived from Lemma 2 of [15]. The later identities are new as far as we know.

It is interesting to consider the question of the completeness of Theorem 2.2. That is, what other identities of similar form are there? We have explored this question by experimental means. Consider identities with the general form

∑_{v∈VG} p(G_{v}^{+}, G_{v}^{−}) = 0,

where p is a polynomial in items of the form s(J, G_{v}^{+}) and s(J, G_{v}^{−}) for some family of connected graphs J. The coefficients can be arbitrary functions of n = s(K_{1}, G). The restriction to connected J is justified by Theorem 2.1. We further forbid the term s(K_{1}, G_{v}^{−}), as it can be replaced by n − 1 − s(K_{1}, G_{v}^{+}).

Define the degree of p to be the maximum total number of vertices appearing (as the first argument of s) in a single term of p. Our experiment was to take large numbers of random graphs of the same order, and count the numbers s(J, G_{v}^{+}) and s(J, G_{v}^{−}) for each vertex v and small connected graph J. Then we formed a matrix of values of the possible terms of p, up to some fixed degree with one row per graph and one column per term. The rank of this matrix, and linear relationships between the columns, tell us about identities satisfied by the set of graphs we have chosen. In particular, linear independence can prove the nonexistence of particular types of identity for these graphs and hence for all graphs. For example, we have established:

Lemma 2.3. The only identities of degree at most 6, in which p can be separated as p(G_{v}^{+}, G_{v}^{−}) = p_{1}(G_{v}^{+})+p_{2}(G_{v}^{−}), are those of Theorem 2.2 and their linear combinations.

If p does not have to separate in the manner of the lemma, we suspect that further identities exist. For example, the following identity of degree 4 holds for such a large number of random graphs (many thousands) that we conjecture it to hold always. Let P_{k} and C_{k} denote the path and cycle of length k, respectively.

Conjecture 1. For every graph G, ∑_{v∈VG}(p_{1}(G_{v}^{+}) + p_{2}(G_{v}^{−}) + p_{3}(G_{v}^{+}, G_{v}^{−})) = 0, where

p_{1}(X) = n(n − 3)s(K_{1}, X) − (n^{2} + 2n − 6)s(K_{1}, X)^{2} + 3ns(K_{1}, X)^{3}
− 2s(K_{1}, X)^{4} + 2(n^{2} + n − 8)s(K_{2}, X) − 12s(K_{2}, X)^{2}
− 12(n − 1)s(K_{1}, X)s(K_{2}, X) + 12s(K_{1}, X)^{2}s(K_{2}, X) + 72s(C_{4}, X)
+ 12(n − 2)s(K_{3}, X) + 24s(K_{1,3}, X) + 24s(P_{4}, X) + 24s(T_{3,1}, X)
+ 12(n + 2)s(P_{3}, X) − 24s(K_{1}, X)s(P_{3}, X) + 32s(T_{3,2}, X),
p_{2}(Y) = 4s(K_{2}, Y)^{2} − 12s(K_{1,3}, Y) − 8s(C_{4}, Y) − 8s(T_{3,1}, Y)
− 24s(T_{3,2}, Y) + 2(n − 8)s(P_{3}, Y),

and

p_{3}(X, Y) = 4s(K_{1}, X)s(P_{3}, Y) − 2(n − 2)s(K_{1}, X)s(K_{2}, Y)
+ 4s(K_{1}, X)^{2}s(K_{2}, Y).

We also have a tentative identity of degree 5, but it is even more complicated. We expect that there is a rich theory of such identities, but we have merely scratched the surface.

3. A proof that R(5, 5) ≤ 49.

A history of the known bounds on R(5, 5) is presented in Table I. The initials “LP” refer to linear programming techniques.

Our theorem that R(4, 5) = 25 [17] implies immediately that R(5, 5) ≤ 50. Moreover, it implies that any (5, 5, 49)-graph G must be regular of degree 24, with each G_{v}^{+} being a (4, 5, 24)-graph and each G_{v}^{−} being the complement of a (4, 5, 24)-graph. (Note that Ḡ, the complement of G, is also a (5, 5, 49)-graph.) Applying the case m = 2 of Theorem 2.2, we find

∑_{v∈VG} s(K_{2}, G_{v}^{−}) = 588 + ∑_{v∈VG} s(K_{2}, G_{v}^{+}).

year  reference  lower upper comments
1965  Abbott [1]  38  quadratic residues in Z_{37}
1965  Kalbfleisch [9]  59  pointer to a future paper
1967  Giraud [6]  58  combinatorics & LP
1968  Walker [24]  57  combinatorics & LP
1971  Walker [25]  55  combinatorics & LP
1973  Irving [8]  42  sum-free sets
1989  Exoo [4]  43  simulated annealing
1992 McKay & Radziszowski [15]  53  (4, 4)-graph enumeration & LP
1994 McKay & Radziszowski [16]  52  LP & computation
1995 McKay & Radziszowski [17]  50  implication of R(4, 5) = 25
1995 McKay & Radziszowski  49  this paper

Table I. The history of bounds on R(5, 5).

Since also s(K_{2}, G_{v}^{−}) = \binom{24}{2} − s(K_{2}, Ḡ_{v}^{+}), we have that

∑_{v∈VG}(s(K_{2}, G_{v}^{+}) + s(K_{2}, Ḡ_{v}^{+})) = 12936.

However, from the computations reported in [17] we know that (4, 5, 24)-graphs have at most 132 edges, and that there are no such graphs with maximum degree greater than 11. This leaves only graphs regular of degree 11, which gives the following key lemma.

Lemma 3.1. Let G be a (5, 5, 49)-graph. Then, for each vertex v, G_{v}^{+} and Ḡ_{v}^{+} are (4, 5, 24, 132)-graphs which are regular of degree 11.

It is possible to derive some reasonably strong restrictions on those (4, 5, 24, 132)- graphs which might fit into a (5, 5, 49)-graph, but we decided to aim instead to find all (4, 5, 24, 132)-graphs. Two such graphs were found previously by Thomason [23], under the stronger conditions of both regularity and a constant number of triangles on each edge. These are the graphs H_{1} and H_{2} given in Figure 1.

Both H_{1} and H_{2} are vertex-transitive, so for information we give their automorphism groups. Define

\begin{aligned}g_{1} & = (0 1 2 3 4 5 6 7 8 9 10 11)(12 13 14 15 16 17 18 19 20 21 22 23), \\ g_{2} & = (0 12)(1 17)(2 22)(3 15)(4 20)(5 13)(6 18)(7 23)(8 16)(9 21)(10 14)(11 19), \\ g_{3} & = (1 11)(2 10)(3 9)(4 8)(5 7)(13 23)(14 22)(15 21)(16 20)(17 19), \\ g_{4} & = (0 12)(1 23)(2 22)(3 21)(4 20)(5 19)(6 18)(7 17)(8 16)(9 15)(10 14)(11 13). \end{aligned}

Then Aut(H_{1}) = ⟨g_{1}, g_{2}, g_{3}⟩, of order 48, and Aut(H_{2}) = ⟨g_{1}, g_{4}⟩, of order 24.

H_{1} H_{2}

    [ \begin{matrix}010010001001 & 010011111001 \\ 101001000100 & 101001111100 \\ 010100100010 & 010100111110 \\ 001010010001 & 001010011111 \\ 100101001000 & 100101001111 \\ 010010100100 & 110010100111 \\ 001001010010 & 111001010011 \\ 000100101001 & 111100101001 \\ 100010010100 & 111110010100 \\ 010001001010 & 011111001010 \\ 001000100101 & 001111100101 \\ 100100010010 & 100111110010 \\ 010011111001 & 000011011000 \\ 101001111100 & 000001101100 \\ 010100111110 & 000000110110 \\ 001010011111 & 000000011011 \\ 100101001111 & 100000001101 \\ 110010100111 & 110000000110 \\ 111001010011 & 011000000011 \\ 111100101001 & 101100000001 \\ 111110010100 & 110110000000 \\ 011111001010 & 011011000000 \\ 001111100101 & 001101100000 \\ 100111110010 & 000110110000 \end{matrix} ]  [ \begin{matrix}011010001011 & 100011000101 \\ 101101000101 & 110001100010 \\ 110110100010 & 011000110001 \\ 011011010001 & 101100011000 \\ 101101101000 & 010110001100 \\ 010110110100 & 001011000110 \\ 001011011010 & 000101100011 \\ 000101101101 & 100010110001 \\ 100010110110 & 110001011000 \\ 010001011011 & 011000101100 \\ 101000101101 & 001100010110 \\ 110100010110 & 000110001011 \\ 110100011000 & 011010001011 \\ 011010001100 & 101101000101 \\ 001101000110 & 110110100010 \\ 000110100011 & 011011010001 \\ 100011010001 & 101101101000 \\ 110001101000 & 010110110100 \\ 011000110100 & 001011011010 \\ 001100011010 & 000101101101 \\ 000110001101 & 100010110110 \\ 100011000110 & 010001011011 \\ 010001100011 & 101000101101 \\ 101000110001 & 110100010110 \end{matrix} ]

Figure 1. Adjacency matrices for H_{1} and H_{2}.

From now on, H will denote a (4, 5, 24, 132)-graph. Since H is 11-regular, it is easy to see that s(K_{2}, H_{v}^{−}) = s(K_{2}, H_{v}^{+}) + 11 for each v. Thus, we can find H by “gluing” together some X ∈ R(3, 5, 11, e) and Y ∈ R(4, 4, 12, e + 11) for some e. The number of possibilities is listed in Table II.

\begin{matrix}e & |R(3, 5, 11, e)| & |R(4, 4, 12, e+11)| \\ 15 & 1 & 8 \\ 16 & 6 & 177 \\ 17 & 19 & 1906 \\ 18 & 31 & 13332 \\ 19 & 30 & 58131 \\ 20 & 13 & 163757 \\ 21 & 4 & 302088 \\ 22 & 1 & 370368 \end{matrix}

Table II. Numbers of potential parts of (4, 5, 24, 132)-graphs.

Theorem 2.2 can help us to reduce the number of possibilities somewhat.

Lemma 3.2. For some v, s(K_{2}, H_{v}^{+}) ≥ 19.

Proof. For 15 ≤ e ≤ 18, the right side of Theorem 2.2 is at most 9 for every graph in R(3, 5, 11, e), but the left side is at least 10 for every graph in R(4, 4, 12, e+11). (These numbers were directly computed from the graphs themselves.) Hence no combination of such graphs can satisfy the identity.

Given Lemma 3.2, we can construct all of R(4, 5, 24, 132) using the methods described in [17], but there are many more cases to process and they are more difficult computationally. Fortunately, we can take advantage of the regularity to improve the efficiency of the search.

To describe the improved search, it is necessary to summarise the setting from [17]. That paper should be consulted for more details.

Suppose we have a particular X ∈ R(3, 5, 11) and Y ∈ R(4, 4, 12) and we wish to build them into H ∈ R(4, 5, 24, 132). We need to choose the edges between X and Y. A feasible cone is a subset of VY that covers no clique of order 3. To avoid cliques of order 4, the neighbourhood in Y of each vertex in X must be a feasible cone. The set of all feasible cones can be packed into a smaller number of intervals of feasible cones, which are sets of cones of the form [B, T] = {W | B ⊆ W ⊆ T }.

Suppose m = |VX |. If C_{0}, …, C_{m−1} are feasible cones, then F (X, Y; C_{0}, …, C_{m−1}) denotes the graph H with vertex v such that H_{v}^{+} = X, H_{v}^{−} = Y and N_{H}(i, VY ) = C_{i} for 0 ≤ i ≤ m − 1. Similarly, if I_{0}, …, I_{m−1} are intervals, then F(X, Y; I_{0}, …, I_{m−1}) consists of all (4, 5, 24, 132)-graphs F (X, Y; C_{0}, …, C_{m−1}) such that C_{i} ∈ I_{i} for 0 ≤ i ≤ m−1. The primary tool is a set of collapsing rules, which take as an argument a sequence (X, Y; I_{0}, …, I_{m−1}) and return a sequence (X, Y; I′_{0}, …, I′_{m−1}) such that I′_{i} ⊆ I_{i} for 0 ≤ i ≤ m − 1 and F(X, Y; I′_{0}, …, I′_{m−1}) = F(X, Y; I_{0}, …, I_{m−1}). A collapsing rule is also permitted to generate the special event FAIL if F(X, Y; I_{0}, …, I_{m−1}) = ∅.

Four collapsing rules are given in [17]. If we have restrictions on the size of feasible cones, we can add some more rules.

Define two functions K, T : 2^{VY} → 2^{VY} such that, for W ⊆ VY ,

K(W) = ⋂{{x, y} | x, y ∈ W and {x, y} ∈ EH };
L(W) = ⋂{{w, x, y, z} | w, x, y, z ∈ W are distinct and {w, x}, {y, z} ∈ EH },

with the understanding that the value of the intersection is VY if it has no arguments. These functions can be precomputed quickly for all W ⊆ VY using simple recurrences.

Suppose that for each u ∈ VX , C_{u} is required to satisfy l_{u} ≤ |C_{u}| ≤ h_{u}. Let the corresponding interval be I_{u} = [B_{u}, T_{u}]. Then we can define the following rules.

(a) Suppose u ∈ VX . if |B_{u}| > h_{u}, then FAIL. if |B_{u}| = h_{u}, then T_{u} := B_{u}

(b) Suppose u ∈ VX . if |T_{u}| < l_{u}, then FAIL if |T_{u}| = l_{u}, then B_{u} := T_{u} (c) Suppose {u, v} ∈ EX and |T_{u}| = l_{u} + 1.

if K(B_{v} ∩ T_{u}) = ∅, then FAIL else B_{u} := B_{u} ∪ (T_{u} − K(B_{v} ∩ T_{u}))

(d) Suppose {u, v} ∈ EX , |T_{u}| = l_{u} + 1, and |T_{v}| = l_{v} + 1. if |L(T_{u} ∩ T_{v})| ≤ 1, then FAIL else B_{u} := B_{u} ∪ (T_{u} − L(T_{u} ∩ T_{v}))

Lemma 3.3. Rules (a)–(d) are valid collapsing rules.

Proof. Rules (a) and (b) are an obvious application of the size restrictions.

Suppose {x, y} ∈ EY , x, y ∈ B_{v} ∩T_{u} and |T_{u}| = l_{u} +1. We can’t have that x, y ∈ C_{u} because then {u, v, x, y} is a clique, so we must have one of x, y missing from C_{u} and all the rest of T_{u} equal to C_{u} (or else |C_{u}| < l_{u}).

Extending the same argument, we see that exactly one element of K(B_{v} ∩ T_{u}) must be avoided and the rest of T_{u} included. This is rule (c).

Suppose {w, x}, {y, z} ∈ EY , where w, x, y, z are distinct elements of T_{u} ∩T_{v}, |T_{u}| = l_{u} + 1, and |T_{v}| = l_{v} + 1. As before, exactly one of w and x, and exactly one of y and z, are not in C_{u} ∩ C_{v}. The restrictions on the sizes of T_{u} and T_{v} imply that each of C_{u} and C_{v} are missing one of {w, x, y, z} (but not the same one) and so must equal all of the rest of T_{u} and T_{v}, respectively. Applying this idea simultaneously to all pairs of edges {w, x}, {y, z} gives rule (d).

The method by which these collapsing rules were built into a search procedure was the same as in [17], so we will not repeat it. Several implementations were made and compared at intermediate points on a large number of examples. Then the fastest was run to completion, establishing the following theorem.

Theorem 3.1. The only two (4, 5, 24, 132)-graphs are those in Figure 1.

Theorem 3.2. R(5, 5) ≤ 49.

Proof. If there exists a (5, 5, 49)-graph G, then by Lemma 3.1 and Theorem 3.1 we know that G_{v}^{+} and Ḡ_{v}^{+} are one of H_{1} and H_{2}. Consider the identity of Theorem 2.2 applied to G for m = 4.

The relevant subgraph counts are as follows.

\begin{aligned}s(K_{2}, H_{1}) & = s(K_{2}, H_{2}) = 132; s(K_{3}, H_{1}) = s(K_{3}, H_{2}) = 176 \\ s(K_{4}, H_{1}) & = s(K_{4}, H_{2}) = 0; s(T_{3,1}, H_{1}) = s(T_{3,1}, H_{2}) = 1584 \\ s(T_{3,2}, H_{1}) & = s(T_{3,1}, H_{2}) = 792 \\ s(K_{4}, H̄_{1}) & = 144; s(K_{4}, H̄_{2}) = 138. \end{aligned}

The terms on the right side of the identity are 132 for both H_{1} and H_{2}, but the terms on the left side are 144 and 138 for the two possible subgraphs. Thus the identity cannot be satisfied and we have a contradiction.

The fact that H_{1} and H_{2} cannot be built into a (5, 5, 49) graph was previously proved by Thomason [23].

4. What is R(5, 5)?

The effort required to bring the upper bound on R(5, 5) down to 49 was considerable, but still it is a long way from the best lower bound of 43. In this section we explain why we believe that the correct value is closer to the lower end of this range. In fact, together with Geoff Exoo, we make the following strong conjecture:

Conjecture 2. R(5, 5) = 43.

We further conjecture, though this time with Geoff’s dissent, that the number of (5, 5, 42)-graphs is precisely 656.

The same set of 656 (5, 5, 42)-graphs, consisting of 328 graphs and their complements, was found by several paths. Firstly, we took a few known (5, 5, 42)-graphs found by Exoo, removed three vertices from them in all possible ways, then extended the resulting (5, 5, 39)-graphs back to (5, 5, 42)-graphs using a variation of the one-vertex extension algorithm given in [17]. This process was repeated until no further (5, 5, 42)- graphs were found.

Needless to say, we checked that none of these 656 graphs can be extended to (5, 5, 43)-graphs.

The second construction method was devised and coded by Geoff Exoo. Starting with a random graph on 30 vertices, edges are inserted or deleted using the simulated annealing rules until a (5, 5, 30)-graph is obtained. Then an extra vertex is appended randomly and the new graph adjusted in the same way to make a (5, 5, 31)-graph. This process is repeated until finally a (5, 5, 42)-graph is obtained. The search is very difficult, and at most several (5, 5, 42)-graphs per day are generated, but we ran it on many computers for a very long time, making 5812 (5, 5, 42)-graphs altogether. The result was that each of the 656 known (5, 5, 42)-graphs was constructed at least once, but no new graphs were found.

A third construction method, using a similar incremental structure but with tabu search instead of simulated annealing, constructed hundreds of (5, 5, 42)-graphs but none were new. A number of attempts to bias the search away from where the known graphs are were unsuccessful in finding anything new. Finally, more than one decade of cpu time was expended in searching the neighbourhoods of the known (5, 5, 42)-graphs, defined by the numbers of common edges or the size of common subgraphs. For example, 100 random 36-vertex subgraphs were formed and extended to 42 vertices in all possible ways, making over 65 million (5, 5, 42)-graphs that were all isomorphic to the known graphs.

The fact that several independent processes that start with a random graph repeatedly find only the known (5, 5, 42)-graphs leads us to strongly suspect that our collection of (5, 5, 42)-graphs is complete. It is not possible to put this belief on a quantitative level, but as a mere illustration suppose that there were in fact 658 (5, 5, 42)-graphs (one extra and its complement) and that Exoo’s program generates (5, 5, 42)-graphs uniformly at random (an unlikely proposition). Then after 5812 trials our chance of not discovering the extra graphs is (656/658)^{5812} ≈ 2.5 × 10^{−7}.

We wish to encourage our readers to devise further heuristic searches for (5, 5, 42)- graphs, to support this evidence. In fact, we propose the construction of (5, 5, 42)-graphs as a challenging benchmark for heuristic search methods.

For completeness, we give some information on the known (5, 5, 42)-graphs, restricting our counts to those with fewer edges than their complements. Of these 328 graphs, 212 have trivial automorphism groups and the others have a single nontrivial involution without fixed points. The number of edges ranges from 423 to 430, with the number of graphs in each class being 1, 7, 29, 66, 89, 77, 43, and 16, respectively. (Note the bimodal nature of this distribution when the complements are included.) All the vertices have degrees between 19 and 22, inclusive. The graphs themselves are available from the authors.

All the isomorphism and automorphism computations required for this paper were performed by the first author’s program nauty [13]. Distribution of tasks across a workstation network was performed with the help of autoson [14].

5. A proof that R(4, 6) ≤ 41

A summary of the history of bounds on R(4, 6) can be found in Table III. In this section we will show how the identities from Section 2 and some data from [17] imply that R(4, 6) ≤ 41.

First, some words about linear programming. The great majority of available linear programming codes employ floating point arithmetic and are subject to the usual questions of correctness and accuracy that inexact arithmetic implies. The linear programs that arise in our work are not exceptionally large, but often have properties (such as high-dimensional optimum facets) that give trouble to floating point codes. Some exact implementations are available, for example in the symbolic algebra package Maple [2], but they are quite slow in operation.

We have taken a hybrid approach to these problems, helped by the fact that there are usually exact solutions to our linear programs which are rational points with small common denominators. Firstly, the routine E04MBF from the NAG library [19] is called to obtain an approximate solution. Sometimes it is necessary to apply it to the dual

year  reference  lower upper comments
1965  Kalbfleisch [9]  30  cyclic graph, not presented
1965  Kalbfleisch [9]  47  bound announced, not derived
1966  Kalbfleisch [10]  34  cyclic graph
1967  Kalbfleisch [11]  46  edge counting
1968  Walker [24]  45  combinatorics & LP
1971  Walker [25]  44  combinatorics & LP
1993  Exoo [5]  35  simulated annealing
1994 McKay & Radziszowski [16]  43  (4, 4)-graph enumeration & LP
1995 McKay & Radziszowski  41  this paper

Table III. The history of bounds on R(4, 6).

program, or to apply it repeatedly with different starting points. When tentative approximate feasible points in both the primal and dual programs are found, they are converted to rational points by guessing a common denominator (using continued fractions). These guessed feasible points are then tested for actual feasibility using the original inequalities and exact arithmetic. If this test succeeds, we have proven the optimality of the solution. To guard against gross errors, all linear program solutions were compared to the approximate solutions given by LINDO [22].

Note that strictly speaking we are dealing with integer linear programs, not rational linear programs. However, in our experience, it is rare for there not to be an integer feasible point with objective equal to the rounded value of the rational optimum. The exceptional cases have no importance that we know of, so we will not attempt to present them here.

We will now describe our approach, in terms of a linear program LP(s, t, n) for an (s, t, n)-graph G. This is similar to, but more general than, linear programs we have defined previously [15, 16].

For convenience, for any graph X, define the functions v(X) = s(K_{1}, X), e(X) = s(K_{2}, X), t(X) = s(K_{3}, X) and p(X) = s(T_{2,1}, X). Then we can write cases m = 2, 3 of Theorem 2.2 as

∑_{v∈VG} 2e(G_{v}^{−}) = ∑_{v∈VG} g_{2}(G_{v}^{+}, |VG|)  (I2)

and

∑_{v∈VG} 3t(G_{v}^{−}) = ∑_{v∈VG} g_{3}(G_{v}^{+}, |VG|),  (I3)

where

\begin{aligned}g_{2}(X, n) & = v(X)(n − 2v(X)) + 2e(X), \\ g_{3}(X, n) & = e(X)(n − 3v(X) + 3) + 6t(X) + 3p(X). \end{aligned}

Suppose we have bounds as follows:

(a) d′ ≤ n − R(s, t−1) and d′′ ≥ R(s−1, t) − 1.

(b) e′_{1}(i) ≤ e(X) ≤ e′′_{1}(i) for every (s−1, t, i)-graph X.

(c) e′_{2}(i) ≤ e(X) ≤ e′′_{2}(i) for every (s, t−1, i)-graph X.

(d) t′(i, j) ≤ t(X) ≤ t′′(i, j) for every (s, t−1, i, j)-graph X.

(e) g′_{3}(i, j) ≤ g_{3}(X, n) ≤ g′′_{3}(i, j) for every (s−1, t, i, j)-graph X. The variables of LP(s, t, n) are as follows.

(i) n_{i} is the number of vertices of G having degree i, for d′ ≤ i ≤ d′′. (ii) g_{i,j} is the number of vertices v of G such that v(G_{v}^{+}) = i and e(G_{v}^{+}) = j, for

d′ ≤ i ≤ d′′ and e′_{1}(i) ≤ j ≤ e′′_{1}(i). (iii) h_{i,j} is the number of vertices v of G such that v(G_{v}^{−}) = i and e(G_{v}^{−}) = j, for

n − d′′ − 1 ≤ i ≤ n − d′ − 1 and e′_{2}(i) ≤ j ≤ e′′_{2}(i). The constraints of LP(s, t, n) are as follows. In each case, the sums are taken over

all values of the summation indices for which the summand exists. (A) ∑_{i} n_{i} = n. (B) ∑_{j} g_{i,j} = n_{i}, for d′ ≤ i ≤ d′′. (C) ∑_{j} h_{n−i−1,j} = n_{i}, for d′ ≤ i ≤ d′′. (D)

2 ∑_{i,j} jh_{n−i−1,j} = ∑_{i,j}(i(n − 2i) + 2j)g_{i,j}.

(E′)

3 ∑_{i,j} t′(i, j)h_{n−i−1,j} ≤ ∑_{i,j} g′′_{3}(i, j)g_{i,j}.

(E′′)

3 ∑_{i,j} t′′(i, j)h_{n−i−1,j} ≥ ∑_{i,j} g′_{3}(i, j)g_{i,j}.

The correctness of (A), (B) and (C) is clear from the interpretation of the variables. Equation (D) is just identity (I2). The two inequalities (E′) and (E′′) are a consequence of identity (I3), comparing lower bounds for one side against upper bounds for the other.

Let us apply our linear programs to show that there are no (4, 6, 41)-graphs. Since R(3, 6) = 18 and R(4, 5) = 25, we can take d′ = 16 and d′′ = 17. The (3, 6)-graphs are known completely [18, 21], so we can find best values of e′_{1}, e′′_{1}, g′ and g′′. However, the values e′_{2}, e′′_{2}, t′ and t′′ depend on the (4, 5, 23)-graphs and (4, 5, 24)-graphs, of which our knowledge is incomplete. Hence we begin by constructing the linear programs LP(4, 5, 23) and LP(4, 5, 24). Using the fact from [17] that (4, 5, 24)-graphs have at most 132 edges, we find the bounds e′_{2}(23) = 98, e′′_{2}(23) = 130, e′_{2}(24) = 109 and e′′_{2}(24) = 132. Bounds on t(X) for (4, 5)-graphs can be found in Table IV.

n = 23  n = 24
e  t  e  t  e  t  e  t
98 90-98  115 106-153  109 112-112  126 130-168
99 88-104  116 109-154  110 111-117  127 133-169
100 87-109  117 113-156  111 110-121  128 135-170
101 85-113  118 116-157  112 110-125  129 138-172
102 83-117  119 119-158  113 109-128  130 142-173
103 82-121  120 122-160  114 108-131  131 146-174
104 82-125  121 126-161  115 108-135  132 176-176
105 84-128  122 129-162  116 107-138
106 85-131  123 133-164  117 107-142
107 87-134  124 138-165  118 109-145
108 89-137  125 142-166  119 112-148
109 91-141  126 147-168  120 114-151
110 92-142  127 153-169  121 117-154
111 94-144  128 159-170  122 119-156
112 97-146  129 166-172  123 122-159
113 100-149  130 172-173  124 125-162
114 103-151  125 127-165

Table IV. Bounds on the number of triangles in (4, 5, n, e)-graphs.

Having the values in Table IV, we can construct LP(4, 6, 41). It is infeasible, which demonstrates the following theorem.

Theorem 5.1. R(4, 6) ≤ 41.

It is perhaps worth noting that exactly the same result is obtained without constraint (E′′). This is also true of the lower bounds in Table IV, which are those needed for constraint (E′), but not for the upper bounds.

Unfortunately, the linear program LP(4, 6, 40) has many feasible points, so the existence of a (4, 6, 40)-graph remains a possibility. However, we note that the result R(4, 6) ≤ 40 would follow if it was known that (4, 5, 22)-, (4, 5, 23)- and (4, 5, 24)-graphs had at least 93, 105 and 113 edges, respectively. These bounds are quite likely to hold, but we have not proved them.

Concerning the exact value of R(4, 6), we expect that the current lower bound of 35 is correct. However, our evidence for this is less persuasive than for our similar feelings about the conjecture that R(5, 5) = 43. We have 30 (4, 6, 34)-graphs so far, produced by making modifications to some graphs provided by Exoo, and proved that there are no others sharing a 31-vertex induced subgraph with one of these 30. However we have not performed any major heuristic searches.

Finally, we give some information on the known (4, 6, 34)-graphs. Of these 30 graphs, 13 have trivial automorphism groups and the others have a single nontrivial involution with 8 fixed points. The number of edges ranges from 222 to 227, with the number of graphs in each class being 2, 4, 8, 10, 5, and 2, respectively. The graphs themselves are available from the authors.

References.

[1] H. L. Abbott, Some Problems in Combinatorial Analysis, Ph. D. Thesis, University of Alberta, Edmonton, 1965.

[2] B. W. Char, K. O. Geddes, G. H. Gonnet, M. B. Monagan and S. M. Watt, MAPLE Reference Manual, WATCOM Publications Limited, Waterloo, 1990.

[3] P. Erdős, L. Lovász and J. Spencer, Strong independence of graphcopy functions, in Graph Theory and Related Topics (J. A. Bondy and U. S. R. Murty, eds.) Academic Press, New York 1979, 165–172.

[4] G. Exoo, A lower bound for R(5, 5), J. Graph Theory, 13 (1989) 97–98.

[5] G. Exoo, On the Ramsey numbers R(4, 6), R(5, 6) and R(3, 12), Ars Combinatoria, 35 (1993) 1–10.

[6] G. R. Giraud, Une majoration du nombre de Ramsey binaire-bicolore en (5,5), C. R. Acad. Sc. Paris, 265, (1967) 809–811.

[7] A. W. Goodman, On sets of acquaintances and strangers at any party, Amer. Math. Monthly, 66 (1959) 778–783.

[8] R. W. Irving, Contributions to Ramsey Theory, Ph. D. thesis, University of Glasgow, 1973.

[9] J. G. Kalbfleisch, Construction of special edge-chromatic graphs, Canadian Math. Bulletin, 8 (1965) 575–584.

[10] J. G. Kalbfleisch, Chromatic Graphs and Ramsey’s Theorem, Ph.D. thesis, University of Waterloo, January 1966.

[11] J. G. Kalbfleisch, Upper bounds for some Ramsey numbers, J. Combinatorial Theory, 2 (1967) 35–42.

[12] B. Kocay, An extension of Kelly’s lemma to spanning subgraphs, Congressus Numerantium, 31 (1981) 109–120.

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

[14] B. D. McKay, Autoson, a distributed batch system for UNIX workstation networks (Version 1.3), Technical Report TR-CS-96-03, Computer Science Department, Aus-

    tralian National University, 1996; http://cs.anu.edu.au/~bdm/autoson.

[15] B. D. McKay and S. P. Radziszowski, A new upper bound for the Ramsey number R(5, 5), Australasian J. Combinatorics, 5 (1992) 13–20.

[16] B. D. McKay and S. P. Radziszowski, Linear programming in some Ramsey problems, J. Combinatorial Theory, Ser. B, 61 (1994) 125–132.

[17] B. D. McKay and S. P. Radziszowski, R(4, 5) = 25, J. Graph Theory, 19 (1995) 309–322.

[18] B. D. McKay and K. M. Zhang, The value of the Ramsey number R(3, 8), J. Graph Theory, 16 (1992) 99–105.

[19] Numerical Algorithms Group, NAG Fortran Library, Oxford, 1993.

[20] S. P. Radziszowski, Small Ramsey numbers, Electronic J. Combinatorics, Dynamic Survey 1, 1994–6;

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

[21] S. P. Radziszowski and D. L. Kreher, On R(3, k) Ramsey graphs: theoretical and computational results, J. Combinatorial Math. and Combinatorial Computing, 4 (1988) 37–52.

[22] L. E. Schrage, User’s Manual for LINDO, The Scientific Press, Palo Alto, 1981.

[23] A. G. Thomason, On finite Ramsey numbers, European J. Combinatorics, 3 (1982) 263–273.

[24] K. Walker, Dichromatic graphs and Ramsey numbers, J. Combinatorial Theory, 5 (1968) 238–243.

[25] K. Walker, An upper bound for the Ramsey number M(5, 4), J. Combinatorial Theory, 11 (1971) 1–10.

[26] H. Whitney, The colouring of graphs, Ann. Math., 33 (1932) 688–718.