Ramsey Theory Explained: The Party Riddle and R(m,n)
Ramsey’s theorem guarantees that in any sufficiently large gathering, a specific pattern of mutual relationships must appear, no matter how the relationships are arranged. The classic case proves that among 6 people, there must be either 3 mutual strangers or 3 mutual friends, while 5 people are not always enough. This principle extends to graphs, multiple colors, infinite sets, and even a 2016 computer-verified proof about Pythagorean triples.
Table of Contents
Key Takeaways
- Among any 6 people at a party, there must exist either 3 mutual strangers or 3 mutual friends, a result written as R(3,3) = 6.
- A party of 5 people does not guarantee this outcome, which is why R(3,3) equals 6 and not a smaller number.
- The exact value of R(4,4) is known to be 18, but R(5,5) has never been pinned down exactly, only bounded between 43 and 49.
- The multicolor Ramsey number R(3,3,3), involving friends, strangers, and enemies simultaneously, equals 17.
- In May 2016, researchers Heule, Kullmann, and Marek proved that every 2-coloring of the natural numbers contains a monochromatic Pythagorean triple, using a computer proof that took roughly two days on a supercomputer to check about one trillion cases.
What is the party riddle that started Ramsey theory?
Consider a party of 6 people. Any two of them are either meeting for the first time (strangers) or already know each other (friends). The riddle asks you to show that among these 6 people there must be either 3 mutual strangers or 3 mutual friends. It also asks you to show that this guarantee fails for a party of only 5 people, meaning 5 is not enough to force the pattern.
Working through this riddle by hand is the best way to understand why the number 6 is special rather than arbitrary. The proof strategy used to solve it generalizes directly into the recurrence relation used to prove Ramsey’s theorem itself.
How is the general Ramsey number R(m,n) defined?
Mathematician Frank Ramsey generalized the party riddle into a formal definition. R(m,n) = v means that in a party of v people, there are always at least m mutual friends or at least n mutual strangers, and this guarantee fails in a party of only v-1 people. Under this definition, the party riddle above states that R(3,3) = 6.
Ramsey’s theorem proves that such a number v must always exist for any choice of m and n. This is a genuine existence question: it is not obvious in advance that there should be some party size guaranteeing, for example, 100 mutual friends or 1000 mutual strangers. Ramsey’s theorem answers yes, and it also supplies an upper bound on how large v must be.
How is the Ramsey recurrence R(m,n) ≤ R(m-1,n) + R(m,n-1) proved?
The core inequality behind Ramsey’s theorem is:
##R(m,n)\leq R(m-1,n) + R(m,n-1)##.
Combined with a simple induction argument, this recurrence yields Ramsey’s theorem in full. The proof works as follows: take a party with R(m-1,n) + R(m,n-1) guests and select one arbitrary guest, referred to here as Mister T.
Every other guest either knows Mister T or does not know Mister T, splitting the remaining guests into exactly two groups. This gives the relationship:
[tex]R(m-1,n) + R(m,n-1) = \text{number of people knowing Mister T} + \text{number of people not knowing Mister T} + 1[/tex]
From this, either the group knowing Mister T has at least R(m-1,n) people, or the group not knowing him has at least R(m,n-1) people.
If the first group reaches R(m-1,n) people, it must contain either m-1 mutual friends or n mutual strangers. The strangers case immediately gives n mutual strangers in the whole party. The friends case gives m mutual friends once Mister T is added to the m-1 friends.
If instead the second group reaches R(m,n-1) people, it must contain either m mutual friends or n-1 mutual strangers. The friends case directly gives m friends in the party. The strangers case gives n mutual strangers once Mister T is added to the n-1 strangers. Either way, the recurrence holds.
What happens with three or more relationship types?
Ramsey’s result extends beyond two categories. Suppose people at a party can be friends, strangers, or enemies. If a party of v people always contains at least m friends, or at least n strangers, or at least k enemies, and this fails for v-1 people, then R(m,n,k) = v. The key inequality governing this case is:
[tex]R(m,n,k) \leq R(m,R(n,k)).[/tex]
In a party with R(m,R(n,k)) people, there are either m friends or R(n,k) non-friends. In the second case, the non-friends themselves must contain either n strangers or k enemies, so one of the three desired monochromatic groups always appears.
This generalizes further into standard graph theory notation. Every unordered pair among v vertices is colored with one of c colors, and v = R(n_1,…,n_c) if any such coloring forces a monochromatic complete subgraph on n_i vertices for some color i, while v-1 vertices do not guarantee this. For any finite list of positive integers n_1 through n_c, such a finite v is proven to exist.
Which exact Ramsey numbers are actually known?
Very few exact Ramsey numbers have been computed, and the difficulty grows extremely fast as the numbers increase.
| Ramsey number | Value or bound | Note |
|---|---|---|
| R(1,n) and R(n,1) | 1, for every n | Trivial case |
| R(2,n) and R(n,2) | n, for every n | Trivial case |
| R(3,3) | 6 | The classic party riddle |
| R(4,4) | 18 | Exactly known |
| R(5,5) | Between 43 and 49 | Exact value unknown |
| R(3,3,3) | 17 | Three-color case |
A widely quoted anecdote attributed to a contemporary of mathematician Paul Erdős illustrates just how quickly these problems become intractable:
“Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5,5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6,6). In that case, he believes, we should attempt to destroy the aliens.”
Beyond two colors, exact multicolor Ramsey numbers are known for almost no cases apart from the trivial ones. R(3,3,3) = 17 is one of the rare exceptions that has been computed exactly.
What does infinite Ramsey theory say?
Ramsey theory also applies to infinite sets. Take a countably infinite set of vertices and color every unordered pair with one of c colors. Ramsey theory guarantees that there exists an infinite subset of vertices for which every pair within that subset receives the same color.
This generalizes further: if every n-tuple of vertices is colored using finitely many colors, there is still guaranteed to be an infinite subset on which every n-tuple shares the same color. These infinite versions of Ramsey’s theorem extend naturally to even larger cardinalities beyond countable infinity.
What is the Boolean Pythagorean triples problem and how was it solved?
The Boolean Pythagorean triples problem is a Ramsey-type question that was resolved in May 2016. Ramsey-type questions generally ask: given a structure split into finitely many pieces, how large must that structure be before one piece is guaranteed to contain a specified substructure?
Three integers form a Pythagorean triple if they are the side lengths of a right triangle. The problem asks whether every natural number can be colored either red or blue so that no Pythagorean triple (a,b,c) ends up entirely one color.
Researchers Heule, Kullmann, and Marek proved in 2016 that this is impossible: any 2-coloring of the natural numbers must produce a monochromatic Pythagorean triple. They further showed that the numbers from 1 to 7824 can be 2-colored with no monochromatic triple, but every 2-coloring of the numbers from 1 to 7825 necessarily contains one.
The proof was produced by reducing the problem to about one trillion cases and checking all of them with a supercomputer over roughly two days. Written out in full, this would rank among the largest explicit mathematical proofs ever produced.
Computer-assisted proofs like this one remain philosophically controversial among mathematicians. Such proofs can settle a truth value definitively while offering little human-understandable insight into why the result holds. The Boolean Pythagorean triples problem is solved in the sense that its truth value at 7825 is settled, even though a conceptual explanation for why that specific threshold matters remains elusive.
Frequently Asked Questions
What does R(3,3) = 6 actually mean?
It means that in any party of 6 people, there must always exist either 3 people who are all mutual strangers or 3 people who are all mutual friends, no matter how the friendships are arranged. It also means that a party of only 5 people cannot always guarantee this pattern, which is why the number is exactly 6 rather than smaller.
Why is R(5,5) not known exactly?
Calculating exact Ramsey numbers requires checking an enormous number of possible colorings, and the number of cases grows extremely quickly as m and n increase. R(5,5) is currently only known to lie between 43 and 49, and finding its exact value is considered one of the hardest open problems in the field.
Who was Paul Erdős and why is he mentioned with Ramsey numbers?
Paul Erdős was a mathematician closely associated with combinatorics and Ramsey theory. An anecdote attributed to a contemporary of his is often used to illustrate how quickly Ramsey number problems become computationally impossible, contrasting the feasibility of computing R(5,5) with the near-impossibility of computing R(6,6).
What is a monochromatic subgraph in Ramsey theory?
A monochromatic subgraph is a group of vertices in a colored graph where every connecting edge shares the same color. In the party riddle framing, this corresponds to a group of people who are either all mutual friends or all mutual strangers.
What did the 2016 Boolean Pythagorean triples proof actually establish?
It established that any way of coloring every natural number either red or blue will always produce at least one Pythagorean triple where all three numbers share the same color. Researchers Heule, Kullmann, and Marek confirmed this by computer, verifying about one trillion cases and identifying 7825 as the specific threshold number involved.
Does infinite Ramsey theory work the same way as the finite version?
The underlying idea is similar: color all pairs (or larger tuples) from a set using finitely many colors, and a large enough monochromatic subset is guaranteed to exist. In the infinite case, that guaranteed subset itself turns out to be infinite, and the result extends to tuples larger than pairs and to cardinalities beyond countable infinity.
Advanced education and experience with mathematics
“We don’t know what’s special about 7825 that would ruin everything.Reference https://www.physicsforums.com/insights/friends-strangers-7825-computers/“This isn't like the four-color theorem. This is a computation that doesn't require any second-order logic. Beyond 7825, the induction is trivial for us humans, and we can let the computer halt. With only a finite amount of exact bead-pushing, what would such a question even mean? What could an answer to "why" be, except "I just showed you"?
Facinating @micromass!
Great article!R(5,5) is between 43 and 49. So we have an example of a group of 42 where no subgroup of 5 exists, and we have a proof that groups of 50 people have to have such a subgroup?Constructing it with the given recursive rule leads to a higher upper bound:R(4,3) <= R(3,3) + R(4,2) = 6+4 = 10R(5,3) <= R(4,3) + R(3,3) = 16R(4,4) <= R(4,3) + R(3,4) = 20R(5,4) <= R(4,4) + R(5,3) = 36R(5,5) <= R(5,4) + R(4,5) = 72
To start with: It's been a great pleasure to read your Insight. I wonder if Ramsey's theory will share a similar fortune as many other problems that could be formulated so easily. I'm always surprised again how some numbers or their properties fascinates us. When I think of Pythagoras I usually think of him as an ancient esoteric, a charlatan. On the other hand when it comes to Ramanujan I think of him as one of the greatest, possibly the greatest virtuoso who ever played on the gamut of numbers. Does this discrepancy exist because Ramanujan contributed so much more to number theory than taxicab numbers or am I simply unfair to Pythagoras.It's also worth reading Simon Singh's book on Fermat's Last Theorem. It brought literally thousands of hobby mathematicians to try a solution because it could be stated so easily. Today it's believed that Fermat never had a real proof of it, or at best only for the case ##n=3.## One must know that at the time, some scholars made fun of it to write their colleagues letters, in which they stated to have proven something without actually given a proof, just to see whether the other one can find out. Nevertheless it was a real booster for number theory. The proof itself, however, is only understood by a handful of mathematicians (meanwhile maybe some more) and requires deep insights into the theory of elliptic curves and (as far as I know) the theory of modular forms. It is agreed to be proven, although only a few could verify this. What makes such a situation different from a computer based handling of cases? I remember I once had a computer proven some cases as well to verify a theorem. Long after it has been accepted, I found some loopholes in the program. It didn't change the result, for I could close them but nobody (except me) ever really noticed. Another prominent example is the Four-Color-Theorem.As in chess, I think we will have to develop a common ground on which we will judge computer based proofs. Personally I think it will require to say goodbye to some selfish human attitudes.Back to ##7825 = 5^2 cdot P_{5cdot P_{5+1}}##. What fascinates us on numbers? One can probably take any number and construct obscure relations around it. I like the hypothesis that it comes from our evolutionary based need to recognize patterns. It is kind of fascinating by itself that this pattern-recognition led to so many theorems and knowledge in number theory. And that it has such an enormous history from Pythagoras, over Ramanujan to Wiles.
Nice article Micro!