$R(5,5)\leq 46$

The Ramsey number $R(s,t)$ is defined to be the smallest $n$ such that every graph of order $n$ contains either a clique of $s$ vertices or an independent set of $t$ vertices. See [7] for a survey on the currently known bounds for small Ramsey numbers.

The lower bound of $43$, which was establised by Exoo [4] in 1989, is still the best. The upper bound of $49$ was proved by the second author and Radziszowski [6], and this was recently improved by the authors [1] to $48$.

A Ramsey graph of type $(s,t)$ is a simple graph with no clique of size $s$ or independent set of size $t$. Let $\mathcal{R}(s,t)$ denote the set of (isomorphism classes of) Ramsey graphs of type $(s,t)$, and let $\mathcal{R}(s,t,n)$ denote the subset of those with $n$ vertices. Let $\mathcal{R}(s,t,n,e=e_{0})$ denote the subset of $\mathcal{R}(s,t,n)$ having $e_{0}$ edges, and similarly for $\mathcal{R}(s,t,n,e\leq e_{0})$ and $\mathcal{R}(s,t,n,e\geq e_{0})$. Let $e(s,t,n)$, respectively $E(s,t,n)$, denote the minimal, respectively maximal, number of edges of such a Ramsey graph.

The improvements in the upper bound for $R(5,5)$ are intimately connected to our understanding of $\mathcal{R}(4,5,n)$ for $n$ large. Recall from [5] that $R(4,5)=25$. It follows that any vertex $v$ of a graph in $\mathcal{R}(5,5,m)$ must have degree $m-25\leq d(v)\leq 24$.

It follows immediately that $R(5,5)\leq 50$, and that any graph in $\mathcal{R}(5,5,49)$ must be regular of degree $24$. This, together with a partial census of the set $\mathcal{R}(4,5,24)$, allowed the second author and Radziszowski [6] to prove that $R(5,5)\leq 49$. Their argument can be summarised as follows. First, they proved that $E(4,5,24)=132$, and found the two graphs in $\mathcal{R}(4,5,24,e=132)$.

Recall the following identity, e.g. from the $m=2$ case of [6, Theorem 2.2]: Given a graph $F$ and a vertex $v\in VF$, let $F_{v}^{+}$ be the induced subgraph on the vertices adjacent to $v$ and let $F_{v}^{-}$ be the induced subgraph on the vertices not adjacent to $v$. Then, if $F$ has $n$ vertices we have, writing $e(\cdot)$ for the number of edges in its argument and $d(v)$ for the degree of vertex $v$,

Given a hypothetical graph $F\in\mathcal{R}(5,5,49)$, the above equation forces the neighbourhoods of all the vertices in $F$ to be one of those two graphs in $\mathcal{R}(4,5,24,e=132)$ and the dual neighbourhoods to be one of the dual graphs. The authors then used further subgraph identities to obtain a contradiction.

The method used in both [1] and the present paper can be summarized with the help of Figure 1, which shows a graph in $\mathcal{R}(5,5,n)$, where $n=48$ in [1] and $n=46$ here. Consider two adjacent vertices $a,b$. The neighbourhood of $a$ is $H=\{b\}\cup K\cup B$ and that of $b$ is $G=\{a\}\cup K\cup A$. Both of these neighbourhoods are in $\mathcal{R}(4,5)$. $C$ is the part of the graph adjacent to neither $a$ nor $b$.

Using a mixture of theory and computation we compile a collection of pairs $\{(G,a),(H,b)\}$ such that $G_{a}^{+}$ is isomorphic to $H_{b}^{+}$ and every graph in $\mathcal{R}(5,5,n)$ necessarily contains a pair in our collection overlapped as in the figure with $a$ adjacent to $b$. We call a pair like $(G,a)$ a pointed graph. Next, for each pair of pointed graphs in our collection, we determine all the ways to fill in edges in the places indicated by heavy dashed lines in the figure without creating cliques or independent sets of size 5. We call this gluing along the edge $ab$. The choice of $C_{1}\subseteq C$ is arbitrary so we may choose any $C_{1}$ that is necessarily present if this structure extends to a graph in $\mathcal{R}(5,5,n)$.

In the case of [1], our strategy was to start with $C_{1}=\emptyset$, so that only edges between $A$ and $B$ were sought. This produced a large but manageable number of solutions. Then we attempted to extend each solution to a graph in $\mathcal{R}(5,5)$ by adding one additional vertex. Since no such extension existed in any of the cases, we concluded that $\mathcal{R}(5,5,48)=\emptyset$.

With $n=46$, choosing $C_{1}=\emptyset$ is impractical as the number of valid ways to add edges between $A$ and $B$ is extremely large. Instead, we chose a larger $C_{1}$ and found that the number of solutions became manageable. The method for choosing $C_{1}$ differed between the approaches of the two authors, and will be described in Sections 6 and 7.

We next outline the method for choosing a collection of pairs $\{(G,a),(H,b)\}$ of pointed graphs.

The proof that $R(5,5)\leq 48$ in [1] can be summarised as follows. First we determined the complete catalogue of $\mathcal{R}(4,5,24)$, which contains a total of $352{,}366$ graphs. Given a hypothetical graph $F\in\mathcal{R}(5,5,48)$, either $F$ or its dual must have a pair of adjacent vertices $a,b$ of degree $24$ whose neighbourhoods intersect in some subgraph $K\in\mathcal{R}(3,5,d)$ for $d\leq 11$. (The fact that it is possible to choose $d\leq 11$ requires a proof, see [1].) Let $G=F_{b}^{+}$ and $H=F_{a}^{+}$ be the neighbourhoods of $b$ and $a$ in $F$. Then $K=G_{a}^{+}=H_{b}^{+}$, and a large subgraph of $F$ can be reconstructed as $G\cup_{K}H$. Hence it suffices to consider all ways of gluing $G\cup_{K}H$ for $K\in\mathcal{R}(3,5,d)$ where $d\leq 11$ and $G,H\in\mathcal{R}(4,5,24)$, and that is precisely what we did in [1]. There is one gluing operation required for each pair of pointed graphs of type $K$ and for each automorphism of $K$, and in total we computed approximately $2$ trillion gluing operations. As mentioned above we will call this gluing along an edge. Note that [1] relied on the complete catalogue of $\mathcal{R}(4,5,24)$ but did not use any linear programming.

In the current paper we take the ideas from [6] and [1] much further. For a hypothetical graph $F\in\mathcal{R}(5,5,46)$ every vertex must have degree $d(v)\in\{21,22,23,24\}$, and we consider parts of $\mathcal{R}(4,5,n)$ for $n=21,22,23,24$. From [5] we know that $\mathcal{R}(4,5,n)$ is quite large for $n=21,22,23$. Indeed, in [5] the authors estimated that $|\mathcal{R}(4,5,21)|\approx 5.5\times 10^{17}$, $|\mathcal{R}(4,5,22)|\approx 1.9\times 10^{15}$ and $|\mathcal{R}(4,5,23)|\approx 10^{11}$. (See the Appendix for updated estimates.) Hence any approach that relies on the complete catalogue of these Ramsey graphs is impractical.

Instead we use linear programming to reduce the number of graphs we need to consider. The basic idea is to determine $\mathcal{R}(4,5,n,e\geq e_{0})$ for $n=21,22,23$ and suitable $e_{0}$ (which depends on $n$) and exclude these graphs by gluing along an edge as described above. Then we can use linear programming to finish the proof of Theorem 1.1.

In more detail, we determine the sets $\mathcal{R}(4,5,23,e\geq 119)$, $\mathcal{R}(4,5,22,e\geq 113)$ and $\mathcal{R}(4,5,21,e\geq 107)$. We also consider $\mathcal{R}(4,5,24,e\geq 127)$. Then we glue these graphs along an edge. There are some additional challenges:

1. (1)

   The method used in [5, 1] to determine $\mathcal{R}(4,5,24)$ is too slow to determine $\mathcal{R}(4,5,n)$ for $n=21,22,23$, so we cannot simply compute all of $\mathcal{R}(4,5,n)$ and throw away the graphs with too few edges. We explain our approach in Section 3.

2. (2)

   The method used in [1] to glue two graphs along an edge produces far too many output graphs, and even if we could collect them all it would take too long to compute all possible ways to add one vertex while staying within $\mathcal{R}(5,5)$. We get around that by adding extra vertices straight away when gluing along an edge as in [1].

In addition, we show in Section 5 that we do not have to perform all possible gluing operations. In fact, we show that we can leave out some of the more time-consuming gluing operations.

We estimate that completing the census of $\mathcal{R}(4,5,n,e\geq e_{0})$ took approximately $15$ years of CPU time while gluing the necessary graph took another $15$ years of CPU time. Hence the whole project took about $30$ years of CPU time for the first author to complete.

In the interests of confidence, all the computations were repeated by the second author using independent programs and usually with different methods. This replication, which produced identical results, took about $50$ years of additional CPU time.

Recall that in [1] the authors completed the census of graphs in $\mathcal{R}(4,5,24)$ that was started in [5], and that $|\mathcal{R}(4,5,24)|=352{,}366$. To proceed, we also need to know something about the graphs in $\mathcal{R}(4,5,n)$ for $n=21,22,23$. As mentioned in the introduction there are far too many such graphs, see [5, Table 3].

Fortunately we do not need all of the graphs in $\mathcal{R}(4,5,n)$ but only the ones with a large number of edges. We consider $\mathcal{R}(4,5,n)$ for $n=24,23,22,21$ in turn. Note that different choices for how many graphs of each type to consider are possible. For example, we could consider $\mathcal{R}(4,5,22,e=114)$ only at the price of having to consider $\mathcal{R}(4,5,23,e\geq 118)$ instead of $\mathcal{R}(4,5,23,e\geq 119)$. It also seems like it would suffice to consider $\mathcal{R}(4,5,24,e\geq 128)$ rather than $\mathcal{R}(4,5,24,e\geq 127)$. But if we did that we would have to weaken Proposition 5.3 and perform more of the more difficult gluing operations.

Define the following sets:

We also define $\bar{A}$ to be the dual of $A$, and so on. So for example, $\bar{A}=\mathcal{R}(5,4,24,e\leq 149)$. Let

and define $\bar{E}$ dually.

Now consider the special case of a graph $F\in\mathcal{R}(5,5,46)$. Then every vertex of $F$ has degree in $\{21,22,23,24\}$ and we can write (1.1) as

On the first line, with $d(v)=24$, $F_{v}^{-}\in\mathcal{R}(5,4,21)$ while $F_{v}^{+}\in\mathcal{R}(4,5,24)$, and so on. We can rewrite $\operatorname{excess}(F)$ as

Given such an $F\in\mathcal{R}(5,5,46)$, suppose each $F_{v}^{+}\not\in E$ and each $F_{v}^{-}\not\in\bar{E}$. Then each vertex $v\in VF$ contributes at least $1$ to $\operatorname{excess}(F)$, so $\operatorname{excess}(F)\geq 46$ and hence we cannot have $\textnormal{excess}(F)=0$. This suggests a proof strategy: Deal with the relatively small number of graphs in $E$ (and $\bar{E}$) separately, and then use the above equation for $\textnormal{excess}(F)$ to finish.

The obvious strategy is to consider all pointed graphs constructed from $E$, and glue every pair of pointed graphs of type $K$ for each $K\in\mathcal{R}(3,5,d)$. If we can do this, it will imply that there are at most $4$ vertices of $F\in\mathcal{R}(5,5,46)$ with neighbourhoods in $E$ and $4$ vertices with dual neighbourhoods in $\bar{E}$, and we get $\operatorname{excess}(F)\geq 6$.

There are two problems with this strategy:

Define the following sets of graphs:

Define $\bar{E}_{i}$ to be the dual graphs. Given a graph $G\in\mathcal{R}(4,5,n)$, let $P(G)$ denote the corresponding set of pointed graphs. This set usually consists of $n$ pointed graphs, although some pointed graphs might be isomorphic. We pick an ordering of all the possible pointed graphs. Here the most difficult graphs to glue should come first. Let $P_{k}(G)$ denote the pointed graphs obtained as follows: First, find the $n$ pointed graphs for $G$ (without removing isomorphic graphs). Then sort them according to difficulty, and throw away the $k-1$ most difficult pointed graphs. At this point we can throw away isomorphic copies of the remaining pointed graphs.

Given $F\in\mathcal{R}(5,5,46)$, we can consider the induced subgraph $F[E]$ of $F$ on the vertices with neighbourhood in $E$. Similarly, let $F[\bar{E}]$ denote the induced subgraph of $F$ on the vertices with dual neighbourhood in $\bar{E}$.

In the following, we abuse notation by saying that a vertex $v\in VF$ is in $E$ if its neighbourhood is in $E$, and similarly for $E_{i}$. We will also write $F[E]$ for the induced subgraph on the vertices in $E$. We will need the following two lemmas:

Given $F$, it suffices to glue along a single edge in $F[E]$. Hence it follows from Proposition 5.3 that it suffices to do the following gluings:

In this section we describe the method used by the first author. It follows the description in Section 2, with $G$, $H$ chosen from the pairs listed in Theorem 5.4. Each gluing problem can be encoded as a SAT problem whose clauses forbid cliques or independent sets of size $5$. We also added symmetry breaking clauses to distinguish the vertices of $C_{1}$.

If $|G|+|H|-|K|\geq 37$ we chose $C_{1}$ to be empty, and if $|G|+|H|-|K|<37$ we chose $C_{1}$ so that the output graphs (if any) have exactly 37 vertices.

We are entitled to make some additional assumptions about $C_{1}$, and some experimentation suggested the following: Pick a vertex $v$ in $K$ of maximal degree $d$ in $G\cup_{K}H$, and choose $C_{1}$ so that it is adjacent to $\min(|C_{1}|,21-d)$ of the vertices in $C_{1}$. In other words, we try to choose $v$ and $C_{1}$ so that $v$ has degree $21$. We can do that because any vertex of $F\in\mathcal{R}(5,5,46)$ has degree at least $21$.

When running our solver, we then prioritised branching on variables corresponding to edges in the neighbourhood of $v$. If $v$ has degree $21$ in $G\cup_{K}H\cup C_{1}$ then the neighbourhood of $v$ has to be in $\mathcal{R}(4,5,21)$, and because $\mathcal{R}(4,5,21)$ is at least somewhat smaller than $\mathcal{R}(4,5,19)$ or $\mathcal{R}(4,5,20)$ (see the appendix) this provided an additional bottleneck in the calculation.