Even in situations where our understanding is extremely limited, it is possible to find a mathematical order using the appropriate tools, and these prove to be highly advantageous.
The question “what is mathematics?” has many answers, which often plunge us into the perpetual argument about whether mathematics is an invention or a discovery. One fascinating answer manages to elegantly escape this trap. According to this viewpoint, mathematics is the human effort to identify patterns in everything. Some may describe this effort as tragic, Sisyphean, and hopeless, while others see it as poetic, sublime, and full of hope. Either way, even if you do not accept this answer as the essence of mathematics itself, the pursuit of regularities, patterns and consistency is undoubtedly one of its main characteristics.
For this reason the mathematical branch known as ”Ramsey’s theorem” is able to capture the complexity and poetic nature of this pursuit. Frank Ramsey, a British mathematician, led a brief but impactful life in the early 20th century. He passed away at the young age of twenty-six due to a disease, leaving behind a rich mathematical legacy, including the proof that initiated an entire new field of mathematics, subsequently named after him.
Ramsey’s theory delves into the concept of order emerging from chaos. It examines structures that have no apparent patterns or regularity, constructed entirely through randomness, and asks which order must inherently exist within them. The typical question that Ramsey's theory addresses is “"How large must a specific structure be to maintain a certain property?”. The basic example, from which the entire theory was developed, illustrates this concept well.
Left a lasting legacy despite his death at a very young age. Frank Ramsey. | Image: Cambridge Wittgenstein archive, public domain
A Party Where Anything Can Happen
Imagine hosting a party with six guests. Among them are family members, colleagues, and a few neighbors, presenting two options for each pair: they either know each other or are strangers. But how many of the pairs are familiar, and how many are strangers? Anything can happen. Chance could bring together six people who all know each other from work or six strangers who have never met each other. Enter Ramsey's theory, which explores whether even in seemingly patternless scenarios, there exists underlying regularity. Consider this example: draw six circles representing the guests and connect some with lines to denote familiarity:
The six guests at the party and their lines of familiarity | Illustration: Michael Gorodin
The first theorem in Ramsey’s theory, which was proven by Ramsey himself, demonstrates that even in the scenario of six randomly selected guests, there must exist some inherent regularity: there will always be a "triangle" formed by three guests who are all familiar with each other or three who are all strangers. While the theorem is more generalized and complex, this concept captures its essence. Is there such a “triangle” in our example? Certainly. There is:
The three gusts marked in red have something in common: they are all strangers to each other | Illustration: Michael Gorodin
The highlighted guests form a “triangle” of strangeness. The three are strangers to each other. Ramsey’s theorem guarantees that regardless of the selection of invited guests and their interconnections, there will always exist a “triangle” of either familiarity or strangeness. How can we demonstrate the existence of such a “triangle” in a party of six guests regardless of their familiarity combinations? Even if we add or remove a familiarity line, a "triangle" will still persist. The proof in this case is not overly complicated:
We will randomly select one guest and examine their connections with the other five guests. With only two possibilities—familiar or stranger—for each of the other five guests, there must be at least three guests with the same status: either familiar or stranger. If the chosen guest knows only two and is a stranger to two, we don't have a total of five guests accounted for. Now we ignore all other guests in the party and focus on our quartet: the guest we chose initially and the other three, who share the same familiarity status. There are two scenarios: either the chosen guest knows all three or knows none of them. Let's assume the former scenario.
Let us assume that the guest we chose knows the three guests in the same familiarity status | Illustration: Michael Gorodin
Next, we examine the mutual familiarity status among these three guests. If any two of them are acquainted, they “form a triangle” of familiarity with our initially chosen guest. Alternatively, if all three lack any familiarity among themselves, they collectively constitute a triangle as the three guests who are entirely unfamiliar with each other.
In any scenario, there exist three individuals with a common familiarity status | Illustration: Michael Gorodin
What if the guest we choose is a stranger to three other guests? The proof remains the same, although we invert all possibilities.If the other three guests are all familiar with each other, they form a triangle of familiarity among themselves. Even if only two of them are strangers, they still constitute a triangle of strangeness with our initial guest of choice.
This is a Ramsey problem (3,3). Why is it called this way? Because it seeks to determine the minimum number of guests necessary to guarantee the presence of either three mutually familiar guests or three mutual strangers. From here, as is customary in mathematics, we start to generalize. What if we want three guests familiar with each other or four strangers, denoted as Ramsey (3,4)? Or even five strangers? More? This problem turns out to be much more difficult than it appears at first glance.
Each of these scenarios can be solved with calculations that, while not overly complicated individually, become increasingly intricate as the numbers grow. For instance, to guarantee a (3,4) party - ensuring either three familiar guests or four strangers - we find that nine guests are required to assure this. These figures are known as “Ramsey numbers”. The Ramsey number (3,5) is, in fact, fourteen. Even these calculations were found to be difficult and highly complex, necessitating a thorough examination of each and every case. As the numbers escalate, so does the complexity of the calculations. The challenge lies in what we have previously discussed: Ramsey’s theory starts with scenarios where our knowledge is minimal.. Yet, this very aspect is what renders the quest for solutions to the Ramsey problem so compelling.
A Handy Novelty
The factor that transformed this from a mathematical curiosity to an actual indispensable tool is the realization that mathematical findings can be valuable in unexpected scenarios. This was exemplified by Ramsey’s theory, which assumed a central role in various problems across a surprisingly wide array of mathematical fields. The ability to assert with certainty the existence of a certain condition or pattern in situations where our knowledge is minimal proved highly advantageous in numerous mathematical contexts and fields. For example, by demonstrating that, in a certain sense, a random scenario is analogous to our hypothetical party, where we lack information about the guests—Ramsey’s theorem enables us to confidently declare “we will chose three people who share a mutual familiarity or unfamiliarity status, meaning that all three know each other or are strangers to each other”. Now with a structured approach and a pattern at hand, we can start working. Increasingly more mathematical investigations were able to employ this tool, intensifying the motivation to solve Ramsey’s problem on a broader scale.
A generalized solution for Ramsey numbers of the form (2,t) was discovered quickly. However, it wasn't until 2019 that a comprehensive finite solution was found for the question of Ramsey numbers of the form (3,t), meaning the form that we have been using so far, indicating the minimum number of guests in the party required to guarantee the presence of either three mutual acquaintances or 't' individuals who are strangers to each other. There was an initial hope that the special method that was developed to address this challenge might yield further insights and advance Ramsey’s theory further. However, such hopes were soon dashed. Something about this theory, which insists on finding the pattern in the chaos, makes it especially elusive.
How elusive? Consider this: We are yet to find a generalized solution for Ramsey numbers (4,t). While we can compute (4,4), and, since 1995, also (4,5), our knowledge ends there. Yet, now we have proof of a remarkably precise approximation. Although we don't know the precise value of Ramsey number (4,6), we can confidently assert it falls within the range of forty-nine to fifty-eight. Similar ranges can be determined for other Ramsey numbers of this format, providing practical and useful accuracy.
At times, humanity’s never ending quest in search for the order in chaos looks like this. Not monumental, reality changing discoveries, but small and uncertain strides, which bring us slowly towards greater knowledge and truth. Each step represents another incremental ascent up this infinite mountain of knowledge.