Ramsey numbers are part of a field of mathematics called graph theory. k_m (where m is any positive integer) is defined as a graph that contains m points, also known as nodes, with all possible line segments in between each point.

Ramsey numbers show the minimum number n of all the different segment coloring schemes using only blue and red for the graph k_n that does not contain a graph of k_r or k_b the entirely red or blue graph, respectively, for that n. This is abbreviated in the notation: K(r, b)=n where K is a Ramsey function, and r and b are independent variables as described above. n is the result of the function.

Problem Statement:

Our project intends to find n for certain pairs or r and b values that we choose and to improve upon existing limits for these variables. We will test possibly values of n by testing all possible colorings of k_n and see if there is a coloring that works, or does not have a red k_r or blue k_b.

If we are unable to get a definitive value for n, then we will have instead found an upper bound for the Ramsey number at that point, which is what mathematicians currently have for many points. We also plan to improve the time it takes to run the program by certain techniques designed at limiting the possibilities and that reduce complexity by powers of two as we go on to solve more and more complex Ramsey numbers. In the end, we hope to have a program that will help mathematicians solve for some of the more complex Ramsey Numbers.

Solution:

We plan to write our program in Java. So far, we have outlined the initial plans for our first attempt at the program. It will use a “brute force”-type method, in which we test different R(r,s) for different r and s directly. We plan to expand upon this by using other methods to reduce the amount of time needed to find the Ramsey numbers. This includes methods to reduce the number of combinations that the program needs to try and a method that will try to find better lower bounds of some Ramsey Numbers in a quick and efficient way. At the end, we hope to have a program that will run very quickly and will find the Ramsey Numbers we need.

Progress to Date:

As of now, we have compiled a large amount of research about Ramsey numbers. Some of the information relates to the currently known limits on specific Ramsey numbers. We plan to use this information in determining which number to test to minimize unneeded calculation for already known Ramsey numbers. Additionally, we have been working on finding uses for Ramsey numbers outside of pure mathematics.

This research has helped us form the basis for our first algorithm. The initial “brute-force” algorithm that we have developed and described above uses no performance enhancements. As of writing this report, we are debating on what would be the most effective data structure to hold the nodes in order to solve the problem.

As we continue to develop the algorithm, we will create performance enhancements, though we have found it will be useful to first have a program that works.

Expected Results:

Our program will take inputs and calculate the Ramsey Number related to those two inputs. It will also provide us with example graphs that work for certain numbers. In the end, we expect our program to find currently known Ramsey numbers so that we can prove that our program works. We then hope to expand upon the currently known numbers and to decrease the range of what some Ramsey numbers could be. We hope to be able to have created a range of numbers that our program will have specifically found. There might also be a program allowing a user to see an example graph that works for certain numbers. This will help people visualize how Ramsey numbers work and ways to create new theorems related to Ramsey numbers.

Mentor: Dr. David Metzler

Sources:

Exoo, Geoffrey. “Ramsey Numbers,” isu.indstate.edu/ge/RAMSEY/

Haanpää, Harri. “Computational Methods for Ramsey Numbers,” citeseer.ist.psu.edu/cache/papers/cs/30289/ http:zSzzSzwww.tcs.hut.fi zSzPublicationszSzbibdbzSzHUT-TCS-A65.pdf/ computational-methods-for-ramsey.pdf

Radziszowski, Stanisław P. “Small Ramsey Numbers,” www.combinatorics.org/Surveys/ds1/sur.pdf

Rosta, Vera. “Ramsey Theory Applications,” www.combinatorics.org/Surveys/ds13.pdf

Weisstein, Eric W. Wolfram MathWorld, “Ramsey Number,” mathworld.wolfram.com/RamseyNumber.html

Wikipedia, “Ramsey's theorem,” en.wikipedia.org/wiki/Ramsey's_theorem

Team Members:

Punit Shah
Jack Ingalls

Sponsoring Teacher: Jim Mims

Mail the entire Team