R(5,5) ≤ 48

The Ramsey numbers R(s,t)

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. Understanding the values of R(s,t) is among the most important, fruitful, and frustrating questions in combinatorics.

43 ≤ R(5,5) ≤ 48

Vigleik Angeltveit and  Brendan D. McKay proved that the value of the diagonal Ramsey number R(5,5) is at most 48. Here is the paper.

The proof of  is via computer verification, checking approximately two trillion separate cases! Congratulations Brendan and Vigleik! (I heard about it from Greg Kuperberg.)

The best known lower bound of 42 was established  by Exoo in 1989.  The previous best upper bound of 49 was proved by Brendan McKay and Stanislaw P. Radziszowski.

By this 4-days old theorem we now have 43 ≤ R(5, 5) ≤ 48. Brendan and Vigleik write “The actual value of R(5, 5) is widely believed to be 43, because a lot of computer resources have been expended in an unsuccessful attempt to construct a Ramsey (5,5)-graph of order 43.” 

R(4,5) =25

In 1995 Brendan McKay and Stanislaw Radziszowski famously proved that R(4, 5) = 25. Listing all graphs with 24 vertices which admit a coloring without a clique on 5 vertices or an independent set with 4 vertices is a major part of the current proof.

Here is, more or less,  how Greg described the achievement on FB: How many people can you have at a party such that no 5 are all acquainted and no 5 are all strangers? It has been known for nearly 30 years that 42 people is possible, and known for 20 years that 49 is not possible. The momentous news  is that 48 is also not possible.

Greg continuation was a little cryptic to me: According to the paper, most mathematicians with any opinion on the matter agree with Douglas Adams that 42 is the answer. (By convention, the question is phrased in terms of the first impossible value, which is now known to be at least 43 and at most 48, and conjectured to be the former.) In response to my confusion Barry Simon added a ring theoretic aspect:  Gil Kalai Isn’t the answer to “the ring of what” always: “one ring to rule them all” sort of like what “42” always means.