Utilizing a Cancellation Algorithm to improve the Bounds of R(5,5)

Jason C. Stone
Westmoore High School, Science Department
Oklahoma City, Oklahoma 73170

Abstract

In this paper classical two color Ramsey numbers that qualify for the special case R(k,k) were analyzed for common traits that might exist among members of the case. Three traits were observed, and the were used in the construction of a computer program that was produced in order to nullify numbers located with in the set upper and lower bounds of R(5,5). By utilizing the cancellation algorithm, the bounds of R(5,5) were improved to the point of intersection at the integer 50. This intersection validates the statement R(5,5)=50 .

INTRODUCTION

As one looks into the heavens, the sky is dotted with random specks of light, yet within this chaotic system the mind perceives orderly shapes. Frank P. Ramsey, an English mathematician, philosopher, and economist, proved that complete disorder is an impossibility (1)(2). Every large set of numbers, points or objects necessarily contains a highly regular pattern. For example, given enough stars one can always find a group that nearly forms a particular pattern: a straight line, a triangle, or even a big dipper. This is the basis for Ramsey theory, which simply states that any structure will inherently contain an orderly substructure (1)(5).

Ramsey first discovered his theory when he was faced by a special case for a hypothesis made by Russell and Alfred North Whitehead in their paper, Principa Mathimatica. Ramsey's paper, "On a Problem of Formal Logic", appeared in the Proceedings of the London Mathematical Society (3). Although the paper chiefly concerned mathematical logic, a far reaching combinatorial result was needed by Ramsey to achieve his objective. The combinatorial contribution that emerged is known as Ramsey theory (3)(5).

It was at a preliminary stage that Ramsey's theory remained due to his premature death in 1930 at the age of 26 (1)(2)(3). In 1933, two Hungarian mathematicians, Paul Erdos and George Szekeres, rediscovered Ramsey theory when they attempted to solve the problem: "If five points lie in a plane so that no three points form a straight line, prove that four of the points will always form a convex quadrilateral. While examining general forms of this question they were able to apply Ramsey theory to this problem and provide a new proof (1)(5).

A Ramsey number is the minimum integer of r = R(p,q) such that in all cases when the edges creating a networked polygon of r points are arbitrarily colored red and blue there will always exist a networked monochromatic sub-graph of either p or q points (1)(2)(3)(4)(5). A Ramsey number is represented by a graph of r points where no more than two points are in a line. Each point is then connected to all other points and a network is formed as in Figure 1. Since Figure 1 is a hexagon we can say that 6 = R(p,q). Next we must determine the values of p and q. These are simply the number of points that will always form a smaller networked polygon where all lines are the same color (monochromatic), q for red and p for blue, no matter what combination of red and blue lines are used to create the larger network. In this example the value for p and q have been determined to both be 3, meaning a red or blue triangle will always exist regardless of the combination of red and blue lines applied to a networked hexagon, thus we can say that 6=R(3,3) (1)(2)(3)(4). Since both conditions in this problem require a network of 3, we can say that p = q. Therefor this problem is represented by the special case equation r = R(k,k) (2,4). This research deals primarily with the R(k,k) special case of classical two color Ramsey numbers.

This concept is further illustrated by a problem that appeared in the William Lowell Putnam Mathematics Competition in 1953, and is stated as follows:

"How many people are required at a party so that it is certain that there exists either 3 mutual acquaintances or 3 mutual strangers? (2)"

If one were to create a graph for each of the combinations of red and blue lines in a networked polygon of 6 points, and then search those graphs for monochromatic networks of three points (a red or blue triangle), they would find that at least one exist at each of the 32,768 possibilities. Thus, again we can state that r = 6, and therefore R(3,3) = 6.

Figure 1

(Notice that at both combinations of red and blue lines a triangle exist.)

Many forms of this question have been widely used in mathematics journals and competitions. This exposure of Ramsey numbers has played a key role in its current popularity. Unfortunately, finding Ramsey numbers has been an arduous task that is all to often unfruitful. To date, only a handful of specific numbers are known. However, with the advent of faster computers that are capable of handling algorithms of incredible complexity, many mathematicians have made significant headway in the area of improving upper and lower bounds (the values for r in which a certain Ramsey number must exist) and in finding the specific numbers (4). Greenwood and Gleason proved in 1955 that R(3,5) =14 and R(4,4)=18 (4). Dery proved that R(3,6) = 18, and Graver and Yackel discovered R(3,7) = 23 (4). In 1990 McKay and Zhang Ke Min showed that R(3,8) = 28 and Radziszowski and McKay showed that R(4,5) = 25; both by using computer algorithms (3)(5).

It is estimated that 11 years of computer time was used in the search for R(4,5). At one time up to 110 computers were working on the problem (3). Mathematicians believe it could take at least two more decades before computers are capable of processing the proof of R(5,5), the next piece of the Ramsey puzzle (3). In describing the difficulty of finding the next two values for the case R(k,k), Erdos often relates this anecdote:

Aliens invade the earth and threaten to obliterate it in a year s time unless human beings can find the Ramsey number for red five and blue five. We could marshal the world's best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack(1).

If one were to analyze every red and blue combination in a graph of 49 points, a possible answer for R(5,5), they would have to analyze a whopping 2^1176 graphs, a task that is not practical or insightful. Since a bruteforce method of determining R(5,5) is out of the realm of probability, it was the goal of this research to utilize a more subtle logic.

METHODOLOGY

For a number to qualify as a Ramsey number:

r must = R(p,q)

Where r = total number of points, p = number of points in the Red sub-graph, and q = total number of points in the blue sub-graph; and where all of the graphs created with r points contain a sub-graph of either p or q size. If any graph does not contain a sub-graph p or q then it is eliminated as a possible Ramsey number for the above equation. Thus, an effective way to find a Ramsey number is to eliminate graphs within its bounds. The Ramsey number will exist at the point where the upper and lower bounds meet.

First, since the value of R(4,5) was determined in 1993 by Radziszowski and McKay; Erdos and Szeker s equation for determining an upper bound was applied as follows (2)(5):

R(p,q) < or = R(p-1,q) + R(p,q-1)
R(5,5) < or = R(5-1,q) + R(p,5-1)
R(5,5) < or = R(4,5) + R(4,5)
R(5,5) < or = 25 + 25
R(5,5) < or = 50

Next the upper bounds of the only known Ramsey numbers that qualify for the special case R(k,k) were reestablished using the same method. The results being:

R(2,2) < or = 2
R(3,3) < or = 6
R(4,4) < or = 18

By comparing these results to a table of known Ramsey numbers (4), a surprising observation was made: the upper bounds of all three of the above equations equal their Ramsey numbers. This suggested that a feasible solution for R(5,5) would be it s upper bound, 50. Thus, an effective method for finding the value of R(5,5) would be to eliminate all numbers below this limit. This could be accomplished by showing at least one graph of 49 points where a monochromatic sub-graph of 5 points did not exist. This would positively eliminate all values < or = 49 as possible solutions for R(5,5) and verify that R(5,5) = 50.

Since, as stated in the introduction, searching all possible red and blue line graphs of 49 points would be impractical (and impossible with my computer resources), the graphs that occurred just before the known R(k,k) numbers were analyzed for clues that could aid in canceling all values < or = 49 for R(5,5). These graphs are represented by the equations:

R(3,3) > 5
R(4,4) > 17

(R(2,2) > 1 was not analyzed since it contains only one point)

The red and blue line combinations that canceled out the above equations as solutions for R(3,3) and R(4,4), respectively, were then analyzed. Three important common traits were observed (the observations are described in the results section). These traits were then utilized in searching for R(5,5).

Although applying these traits minimized the number of graph combinations to be analyzed, the number was still far to great to be manually manipulated. Thus, a computer program was written to create the needed combinations. A second problem was identifying the existence of monochromatic networks of 5. As one can see by the graph on page 10, visual identification would be extremely difficult and in light of the number of graphs that must be analyzed (2,704,156), quite impossible. Therefore, a monochromatic network-finding program was constructed to receive and examine the patterns produced by the first program. The source code for both programs are not available in this document.

The program was then allowed to run for several hours until a graph that did not contain a monochromatic network of 5 points was found.

RESULTS AND CALCULATIONS

When the preceding method of canceling the number before the upper bound was applied to both of the known Ramsey numbers that qualify for the special case R(k,k) two graphs were created; a graph of 5 points where no 3 pointed monochromatic networks exited and a graph of 17 points were no monochromatic sub-graph of 4 points existed.

Figure 2

(There does not exist a monochromatic sub-graph of 3 on the left or one of 4 on the right.)

From these graphs three important observations were made:

1. Both of the graphs could be created by repeating a definite pattern of red and blue lines from each point, when the lines were completed from origin to termination in a constant direction, either clockwise or counterclockwise. The patterns were as follow:

5 < R(3,3)
Red Blue Blue Red
and
17 < R(4,4)
Red Red Blue Red Blue Blue Blue Red Red Blue Blue Blue Red Blue Red Red

2. If one divided the patterns into two equal halves, the two resulting subpatterns were reciprocals:

RB BR
RRBRBBBR RBBBRBRR

3. In both graphs the number of red and blue lines were equal.

Although interesting, these observations hold little significance in themselves. However, if one makes the assumption that these traits are common among all graphs that occur just before a Ramsey number of the special case R(k,k), the number of graphs that must be analyzed in order to cancel all values < or = 49 decreases dramatically.

1. Since every point must utilize the same line pattern, there are only approximately 2 ^48 possible graphs. This is derived from the number of red and blue patterns possible among 48 lines. Although this number of graphs is still difficult to analyze with today s computational equipment, it is a significant improvement over the original 2^1176 possible graphs.

2. By applying observation number two, we know that the line patterns can be split into two patterns that are reciprocals of each other. Thus, it is only necessary to analyze combinations of 24 and then apply the reciprocal of the patterns to gain the second half. This leaves only 2^24 or 16,777,216 possible combinations.

3. Finally, since the third observation states that the number of red lines must equal the number of blue, we can determine the number of combinations with a permutation where 12 red and 12 blue are taken 24 at a time.

n!
p!q!

24!
12!12!

6.204484017332E23
479001600 * 479001600

2,704,156

We find that there are 2,704,156 combinations remaining.

The next step was to discern which of the combinations would create a 49 pointed graph where no monochromatic sub-graphs of 5 points existed. The patterns were generated by the computer algorithm described below:

1. Twenty four digit binary numbers were incremented, and all blank positions to the left were filled with zeros.

010110100101010101010010 + 1 = 010110100101010101010011

2. The incremented numbers were then read into a 24 position array where all empty spots were filled with zeros.

010110100101010101010011

3. All of the positions in the array were then added. If the value returned as 12, then the array would contain 12 ones and 12 zeros, and the values would continue. If the array returned any other value, then the pattern would be discarded and the program would return to step one. (Observation #3)

0+1+0+1+1+0+1+0+0+1+0+1+0+1+0+1+0+1+0+1+0+0+1+1= 12

4. The values that qualified to continue were then read backward and attached to the forward versions of the same pattern. This creates a pattern of 48 ones and zeros that when split in half produce two sub patterns that are reciprocals of each other. (Observation #2)

010110100101010101010011 110010101010101001011010

5. The ones and zeros were then converted to Reds and Blues, 1=red and 0=blue, and the pattern was repeated from 48 points to create a networked graph of 49 points. (Observation #1)

010110100101010101010011 110010101010101001011010
BRBRRBRBBRBRBRBRBRBRBBRR RRBBRBRBRBRBRBRBBRBRRBRB

(The r and b pattern has been applied to each of the 49 points)

After the graphs were generated they were checked for monochromatic networks of 5 by a another computer algorithm. Since the pattern was the same from each point the algorithm was only applied to point zero. It follows a blue line from one point to another and checks to see that all previously visited points are connected to this point with a blue line. It then determines all other blue paths from that point. It follows one blue line to a point that it has not yet visited. It checks to see that the new point is connected with a blue line to all points previously visited, etc. If a point is found that does not have a blue line going to all previous points, then that path is abandoned and another blue trail is followed from the point before the dead end. If five points are found that are connected with blue lines then the monochromatic network of 5 is colored green and the program skips to the next red and blue pattern. If all possible blue paths have been explored and no blue networks of five are discovered, the algorithm is repeated on red lines. If this process does not yield a red network of 5 then the program stops and displays the pattern verifying that R(5,5) > 49.

These programs were allowed to run on a home PC with an Intel Pentium 120 processor and 16 megs of RAM. After several hours of processing time the program found the following pattern to contain no monochromatic networks of five.

BBBRRRBBBRRRBRBRBRBRBRBRRBRBRBRBRBRBRRRBBBRRRBBB

Since a graph was found that did not contain a red or blue network of five points, all values < or = 49 could not be solutions for R(5,5). Thus, the lower bound was improved to 50. Since the upper bound is also 50, the two bounds meet and the following statement was verified:

49 < R(5,5) = 50

(See graph below)

DISCUSSIONS & CONCLUSIONS

Although these results seem very promising, it is important to note that when dealing with algorithms one must submit all results to algorithms utilizing a separate logic. Thus, the next step in my search was to feed the combinations into a network finding program that utilizes a different logic than the tracing program. This algorithm has been developed and is described in the addendum. If this algorithm confirms my results, I will send my findings to several Ramsey theorists who have developed their own network finding software. It is hoped that these programs will confirm this research and further solidify the statement R(5,5) = 50.

The value for R(5,5) is not the only notable implication of this research. These findings seemingly call for a revision of Erdos and Szeker s equation for determining an upper bound for the special case R(k,k). Instead of:

R(p,q) < or = R(p-1,q) + R(p,q-1)

the revised equation would be:

R(k,k) = R(k-1,k) + R(k,k-1)

If this revised equation holds true and my observations can be applied to all members of the special case R(k,k), then the search for R(6,6) and R(5,6) could possibly be accomplished by applying the methods used in this research on each of the values within the bounds of R(5,6), which are currently 58 to 97 (4).
For instance:

1.

R(6,6) = R(5,6) + R(6,5)
R(6,6) = 97 (the upper bound for R(5,6)) + 97
R(6,6) = 194
etc.

2. Subtract one from highest possible value of R(6,6) (i.e. 194) and analyze the patterns of that graph in the same method as described in this study, only searching for monochromatic networks of six. If a graph is not found that is void of a network of six, then the process could be repeated on the next highest value for R(6,6), 193, 192, etc.

3. The first graph found that does not contain a network of six will validate the value of the number of points in that graph plus one, and the value of R(5,6) will be that number divided by two.

The applications for Ramsey numbers are just being explored. Ramsey theorist are assisting engineers to build better communications networks as well as information transmission and retrieval systems. Ramsey theorist have also discovered some of the mathematical tools that will guide scientists in the next century. Perhaps most importantly, Ramsey theory probes the inner structure of mathematics, a structure that transcends the universe.

ACKNOWLEDGMENTS

I would like to thank Jim Shadowin for his great assistance in developing the Visual C programs. Thanks to Sonny Pfeffer for aiding me in the construction of my display. Thanks to James Renolds for the background information. Special thanks to Tyrone Dover, for his many insights, Vu Thai, for introducing me to Ramsey Theory, and of course my mother and father, for their understanding and support. I also would like to thank Mr. Brauser, for teaching me what it takes to win, and the entire Westmoore science department. GO! GO! GO! WIN! WIN! WIN!

REFERNCES