Registration Dates Kickoff Proposals Interims Evaluations Final Reports Expo STI School Map Sponsors Mail Discussion Forum Technical Guide Past Participant   Survey
Supercomputing Challenge

# Deriving the Ramsey Numbers

Team: 7

School: ALBUQUERQUE ACADEMY

Area of Science: Mathematics -- Graph Theory

Proposal:

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:

Sponsoring Teacher: Jim Mims