Final Reports
  School Map
  Discussion Forum
  Technical Guide
  Past Participant
Supercomputing Challenge

Deriving the Ramsey Numbers

Team: 7


Area of Science: Mathematics -- Graph Theory


Definitions: Ramsey numbers are part of a field of mathematics called graph theory. km (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 kn that does not contain a graph of kr or kb 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.

Proposed Project: Our project intends to find n for r and b values that we choose and to improve upon existing limits for these variables. We plan to use Java as our main programming language. We plan to test a possible n by testing all possible colorings of kn and see if there is a coloring that has no red kr and no blue kb. We will use the computer to test these n and solve for certain pairs of r and 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.

Mentor: Dr. David Metzler

Team Members:

  Punit Shah
  Jack Ingalls

Sponsoring Teacher: Jim Mims

Mail the entire Team