[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 1 to my Current Research Projects

Up 2 to my Home Page

Access count (updated once a day) since 1 Jan 1997: 19707