This project has many natural extensions and side problems that we could explore. To date, we have only implemented a few primary algorithms reduce the number of colorings that the program test. However, there are many other methods that we could try to implement that would reduce processing time and thus improve our project. One way is simply to run the program on a higher performance computer than the one we are currently using. We ran our program on a 2.2 GHz. Microsoft Windows XP machine with 512 MB of RAM. We are currently working with the Supercomputing Challenge to gain access to a higher performance computer at Los Alamos National Laboratories. This will allow us to test and benchmark our program for larger inputs. We hope to have run our program on a Supercomputer by April 23, 2007, the date of the final presentations.

We can also continue to improve our project by implementing new algorithms to speed up our program. One area is to continue to get rid of some of the unnecessary colorings. This includes improving the primary short-cuts that we use to further reduce the number of nodes. We can also apply these extremely fast methods to other nodes, but this will also add an additional layer of complexity; if we extended our algorithm to additional nodes, there will edges that connect to multiple nodes with controlled colorings and that will have been colored twice. Another algorithm we could implement would take all the colorings with n-1 nodes that do not have the monochromatic subgraphs and then just add one more node to the graph. This essential “recycling” of our work would reduce the number of colorings to work through and the amount of tests that need to be done. Yet another algorithm that could consider implementing is trying different ways of searching for monochromatic subgraphs to see which way is the fastest.

The other main way to speed up the program is to only try a few colorings for any given n. If we find a graph that has no monochromatic subgraphs, then we know that the Ramsey number is larger. Otherwise, the test would be inconclusive. There are many ways to go about this. Working with symmetry is one and could reduce the number of possible colorings by almost a square-rooting factor. For large numbers of colorings, this is a major improvement. Another way is to begin with a coloring and change the segments in a “smart” way such that the number of monochromatic graphs is reduced until there are no more. A way would be to implement some sort of Monte Carlo coloring algorithm that would randomly color a graph and by probability could give us a good chance of finding a coloring that would result in a conclusive result. These methods are very fast, but at the same time they may not always return a conclusive result. This is something we simply have to see.

We hope to implement at least some of these recommendations within the coming weeks.