Wayne's Ramsey Graph Research

[In fact, the famous mathematician Paul Erdos once related the following anecdote (paraphrased from memory): ``Say aliens invade the Earth and threaten to obliterate it in one year's time unless we compute R(5,5). If we marshalled the world's best minds and fastest computers, then within a year we could probably calculate the value. If the aliens demanded R(6,6), however, we would be better off preparing for interstellar war.'']

For my course project in Derek Corneil's graduate Graph Theory course CSC 2410, I decided to try throwing some serious brute force at finding graphs which would put lower bounds on small Ramsey Numbers. That is, I would generate a graph with n nodes, and then find the largest clique and largest independent set. Say these were of size k-1 and l-1, respectively. Then, by the above definition, this graph proves that R(k,l)>n.

For the course project, I used 114 workstations at the University of Toronto to search every possible circulant graph with 1 to 64 nodes. The circulant pictured here has 35 nodes, but contains neither a clique of size 3 nor an independent set of size 9, thus proving R(3,9) > 35. This circulant is a critical graph because R(3,9) is known to be equal to 36. We found another critical circulant on 24 nodes for R(4,5), which is known to be 25. The first rows of the adjacency matrices of these graphs are, respectively, 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 (pictured), and 0 1 1 0 1 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 1 0 1 1. (A circulant is completely specified by specifying the first row of the adjacency matrix.)

Unfortunately, no new bounds were found after searching all circulants on 1 to 64 nodes, although we came within 1 or 2 of the best known lower bounds in several cases.

Some time in the near (or distant...) future, Demetrios Achlioptas, David Neto, and I plan to spend some more time on this, looking at more general graphs than circulants, which will hopefully be more "powerful" in the finding-Ramsey-numbers sense. We will probably use something akin to Markus Meringer's regular graph generating stuff.

The World Combinatorics Exchange home page contains a section entitled Dynamic Surveys which maintains an up-to-date copy of Stanislaw Radziszowski's paper on Small Ramsey Numbers in PDF format. The paper contains a brief survey of all types of Ramsey Numbers, and the current best known bounds.

Up 2 to my Home Page