R(5, 22) and R(6, 21)

A quick post about small Ramsey numbers. I like to write on my blog about things which I do not intend to publish, but also do not want to keep as private knowledge. This is one of these posts.

Stanisław P. Radziszowski writes the following in the 15th revision of his survey on small Ramsey numbers:

One can expect that the lower bounds in Table II are weaker than those in Table I, especially smaller ones, in the sense that some of them should not be that hard to improve, in contrast to the bounds in Table I.

Table II contains slightly larger Ramsey numbers, for instance and . So when one has idle CPU time, it seems to be reasonable to use it here, I thought some weeks ago. And indeed, it is. I found a witness for and a witness for for . This improves the previously known lower bounds by a gigantic 7 in the first case and a nearly as gigantic 6 in the second case. Here you can find a short description of both cases.

And if anyone asks: The upper bounds are much, much, much larger than both lower bounds. Also I did not put any effort into my search, so it is probably very feasible to improve a few more numbers in Table II of the survey.

Advertisement

Sp(6, 2)’s Family, Plots, and Ramsey Numbers

Strongly regular graphs lie on the cusp between highly structured and unstructured. For example, there is a unique strongly regular graph with parameters (36, 10, 4, 2), but there are 32548 non-isomorphic graphs with parameters (36, 15, 6, 6).

Peter Cameron, Random Strongly Regular Graphs?

This a shorter version of this report which I just put on my homepage. But I added more links. I assume that one is familiar with strongly regular graphs (SRGs). One particular SRG, the collinearity graph of , has parameters . A very simple technique, Godsil-McKay (GM) switching, can generate many non-isomorphic graphs with the same parameters. More specifically, there are probably billions such graphs and I generated 13 505 292 of them. This is the number of graphs which you obtain by applying a certain type of GM switching (i.e. using a bipartition of type 4, 59) at most 5 times to . Plots of the number of cliques, cocliques, and the size of the autmorphism group are scattered throughout this post.