This project intends to calculate Ramsey numbers as efficiently as possible. Ramsey numbers, a topic in mathematics and graph theory, give the smallest graph size so that when its edges are colored in any pattern of only two colors, the graph must contain subgraphs of size r or b, which are both integers. Applications of Ramsey numbers include in the areas of telecommunication, network security, and networking related fields; Ramsey numbers could be used to find the minimum number of necessary connections between computers in a network to create the most secure yet productive network.

We developed a program in Java to calculate Ramsey numbers. The program first takes three integer inputs: the sizes of the two subgraphs that the program will be searching for and a guess of what the Ramsey number will be for the inputted subgraph sizes. The program creates a virtual representation of the graph and begins to iterate through all possible edge colorings, finding whether there are monochromatic subgraphs in each coloring or not. If the program finds a coloring with no monochromatic subgraphs, then it knows that the Ramsey number is greater than the guess and outputs a key for the second, graphics program that will draw the graph and its coloring to prove visually that the program is correct. However, if the graph has no monochromatic colorings, the program knows that the Ramsey number if less than or equal to the guess. By testing various guesses, the user can calculate Ramsey number or narrow the known range of higher input value Ramsey numbers.

Some of the major innovations of the project were the algorithms developed to reduce both the number of colorings to analyze and the processing time. While a “brute-force” approach to calculating Ramsey numbers would test every coloring and every subgraph, our strategic algorithms only tested a subset of the total colorings. These improvements decreased computing time.

The results of the program and algorithms were very promising. For low guesses like seven, the program could theoretically reduce computing time by 80%. This percentage increases for even larger guesses. In practice, even after implementing just one of our performance enhancement algorithms, there was a 33% processing time reduction. Combined with the other algorithms and programming tactics like exiting loops once the program has enough information to form a generalization, the computing time savings would likely approach their theoretical values for larger graph sizes.

This research demonstrates that a computer-based approach to calculating Ramsey numbers is possible and that the algorithms that we used to calculate and reduce the computing time of the program are all accurate and useful in this context. While our time savings alone might not be enough to calculate Ramsey numbers with large inputs, these algorithms could be used in a much larger and broader professional research project intending to use supercomputers to calculate Ramsey numbers.

The major achievements of the project were accurately and efficiently calculating Ramsey numbers within an expandable code structure.

We hope to run our program on a Los Alamos National Labs supercomputer by April 23, 2007.