Ramsey Numbers

The first table gives some new (July 2005) lower bounds for Ramsey numbers. These improve the values given in the most recent edition of the Dynamic Survey. The colorings will be available soon.

New Lower Bounds for Classical Ramsey Numbers from Cayley Colorings

R(3,18) > 98
R(3,20) > 110
R(4,9) > 72
R(4,16) > 162
R(5,9) > 124
R(5,10) > 142
R(5,11) > 158
R(5,12) > 184
R(5,13) > 208
R(5,14) > 234
R(5,15) > 264
R(6,7) > 112
R(6,10) > 178
R(3,3,7) > 80
R(3,3,8) > 100
R(3,3,9) > 116
R(3,4,5) > 80
R(3,4,6) > 106
R(3,4,7) > 142
R(3,5,5) > 128
R(5,5,5) > 416

This rest of this page gathers links to older constructions for various Ramsey numbers. The constructions given here are mine; for a more complete list see the Dynamic Survey.

Older Lower Bounds for Multicolor Ramsey Numbers

Here are a new links to colorings obtained using the "growth method", a simple technique I described in Volume 1 of the Electronic Journal of Combinatorics. Note that the colorings are not circle colorings. They might be called "linear" colorings, in that for i < j, the color of the edge joining vertex i to vertex j depends only on j-i.

R(4,4,4,4) > 577 Matrix (gzipped) Chords
R(5,5,5) > 414 Matrix (gzipped) Chords
R(3,3,3,4) > 92 Matrix Chords
R(3,3,4,4) > 170 Matrix Chords
R(3,3,7) > 78 Matrix Chords

Ramsey Colorings from Non-cyclic Groups

The next group of links below are to files containing adjacency matrices for Ramsey colorings of complete graphs. Most of these establish best known lower bounds for classical Ramsey numbers. They are all new and were made using nonabelian groups of order pq (for primes p and q) using two different techniques. The coloring for R(4,8) is a Cayley coloring, i.e., both color graphs are Cayley graphs. The underlying group is the nonabelian group of order 55. The latter three colorings were obtained using a technique described here.

More recently, colorings that give new lower bounds for R(4,9) and R(3,20) were found using a broader class of nonabelian groups.

R(4,8) > 55
R(3,27) > 157
R(3,31) > 197
R(5,17) > 283

Old Ramsey Colorings from the Dynamic Survey

Here are some links to some of the constructions for classical Ramsey numbers that are referenced in the Dynamic Survey.

R(4,6) > 34 R(3,10) > 39 R(5,5) > 42 R(4,7) > 48
R(3,12) > 51 R(5,6) > 57 R(5,9) > 115 R(5,10) > 140
R(5,11) > 152 R(5,12) > 180 R(5,13) > 192 R(5,14) > 220
R(5,15) > 236 R(6,7) > 108 R(6,8) > 121 R(6,9) > 152
R(6,10) > 166 R(3,4,5) > 79 R(4,5;3) > 32 R(5,5;4) > 33

Complete Graphs Missing One Edge

Finally, here is paper which describes some of the entries from Table III of the Dynamic Survey. The graphs can be found here.

Geoff Exoo