Click on small photo to view larger one.
Faculty Advisor: Brian Ladd
Poster Presentation
|
Click on small photo to view larger one. |
Ramsey Number Examination
Faculty Advisor: Brian Ladd Poster Presentation |
This project looks into how Ramsey Numbers are solved using computers.
A Ramsey Number is the smallest graph size that must contain either a clique
of a given size or an anti-clique of a given size. A Ramsey Number
is written as R(m, n) where m is the clique size and n is the anti-clique
size that we are looking for. Finding Ramsey Numbers has proven to
be extremely difficult due to the exponential growth of the problems.
Recently, computers have been used to help find new numbers, but even their
bounds are quickly reached. For my project, I looked into and experimented
with how computers can be used to find Ramsey Numbers. This is done
using a brute force technique to create all the graphs of a given size
and determine if they contain a clique of size m or an anti-clique of size
n. The first part of the semester I have spent creating a program
that can determine if a graph of a given size is the Ramsey Number for
a given m and n. Now that this program works, I have been working
to increase the speed of the program to try to obtain larger results.
Some speed was gained by creating an iterative version for the two main
recursive functions that I used. Speed has also been increased by
creating code to start and stop the program from various positions allowing
the program to be run using different machines simultaneously. I
should now be able to find R(3, 4) after running my program for a few days,
but R(4, 4) is probably not possible to find by the end of the semester.
St. Lawrence University Homepage /--/ Academics Page |