Chapter 33: Ramsey Theory

Ramsey Theory in its entirety is too complicated to be explained within The Colossal Book of Mathematics mentioned in the book. However, Ramsey Theory can be applied much easier to a recreational view on graph-coloring theory games.  The most famous Ramsey game is known as Sim, which was named after the mathematician Gustavus Simmons. Sim is directly related to the problem, “Prove that at a gathering of any six people, some three of them are either mutual acquaintances or complete strangers to each other.”  This would be accomplished by being played on a complete graph with six separate points known as (K₆), and having two different colors (ex. Blue & Red) to represent a mutual acquaintance connection (Blue) or complete strangers to each other (Red) between the six individuals. Players would then take alternate turns connecting a point with their respective color. The goal is to avoid completing a monochromatic triangle of your color (either blue or red). Therefore, the loser is the first person to connect 3 separate points of his or her own color. In Ramsey Theory talk, the purpose of this is to prove that it is impossible not to complete either sub graph of an entirely red triangle (K₃) or entirely blue triangle (K₃). Meaning, eventually you will complete an entirely red triangle or entirely blue triangle. In Ramsey Theory referring to actual numbers and graphs, the above problem can be expressed as R(3,3) = 6. In the notation, R represents Ramsey number, the first 3 for one of the colored triangles, the second 3 for the other colored triangle, and the 6 for representing the smallest number of points, which both a red or blue triangle is forced.

These ideas of classical Ramsey numbers and theory can lead us to different games. There is the avoidance game or achievement game (known as Sim), and then there is an alternate game which leads to who can complete a larger amount of K₃ monochromatic triangles or who can complete the least amount. Apart from the game R(3,3) = 6, other much more challenging Ramsey games can be played. When changing the values in R(r,s)=K_n , games get much more challenging. If the K₆ value is increased (ex. R(3,3) = 7) then there are now 7 points of which you play the game. If you were to increases K₃ value (ex. R(4,4) = 18) then it also increases the minimum amount to K₁₈ points, and changes the forced complete sub graph to a K₄ monochromatic tetrahedron. However, the jump from R(4,4) to R(5,5) is too complex to determine a K_n complete graph for R(5,5). Stefan Burr, a leading expert on Ramsey theory estimates that the K_n value will never be determined because it is too difficult to analyze.

I found Ramsey Theory to be considerably confusing to entirely understand at once. As I broke it up into parts, understanding Ramsey games helped immensely to understand the Ramsey Theory and its basic principle. Ramsey games are a basic introduction into the realm of the Ramsey theorem. I tried to give a simple recreational math view between Ramsey Theory and Ramsey games. The more an individual understands Ramsey Games and the formula R(r,s), the more one can understand Ramsey’s theorem. Ramsey’s theorem states (simplified), that one will find a completed monochromatic sub graph (ex. a triangle or tetrahedron) in any edge labeling (with color) of a large enough complete graph.