Mathematics
Ramsey Theory and the Party Problem
Quick fact
The party problem guarantees that among any six people, there always exist three who are all mutual acquaintances or three who are all mutual strangers. This is the Ramsey number R(3,3)=6, meaning no matter how you color the edges of a complete graph on six vertices with two colors, you cannot avoid a monochromatic triangle.
Why this is interesting
At any party with just six people, you are guaranteed to find either three mutual acquaintances or three mutual strangers—no matter how the social connections are arranged. How can we be so sure?
Read the full explanation
Understanding Ramsey Theory and the Party Problem
Imagine a party where every pair of guests are either friends (acquaintances) or strangers. Draw a dot for each guest, and connect every pair of dots with a line: color it red if they are friends, blue if they are strangers. This creates a complete graph on the guests, where every edge is colored one of two colors. Now, pick one guest, Alice. She has five connections to the other five guests. By the pigeonhole principle, at least three of these connections must be the same color—say, red. That means Alice has at least three friends among the others. Let's call them Bob, Carlos, and Dana. If any pair among Bob, Carlos, and Dana are also friends (red edge), then those two plus Alice form a triangle of three mutual friends. If none of them are friends, then all three edges among them are blue, meaning Bob, Carlos, and Dana are three mutual strangers. Either way, we have a monochromatic triangle—three people who are all friends or all strangers. This reasoning works no matter which person you start with or how the friendships are arranged, proving that a group of six always contains the desired trio.
A deeper explanation
The party problem is a special case of a broader concept: the Ramsey number R(s,t). For positive integers s and t, R(s,t) is the smallest number of vertices such that any red-blue coloring of the edges of a complete graph on that many vertices contains either a red Ks (a clique of s vertices all connected by red edges) or a blue Kt. In the party problem, we set s=t=3, looking for a triangle of friendships or strangers. We just proved that 6 guarantees this, but 5 does not: consider a pentagon (5-cycle) colored red and its complement (the other 5 edges) colored blue. This 2-coloring of K5 has no monochromatic triangle, so R(3,3)5. Hence R(3,3)=6. The proof relies on a pigeonhole argument applied to the edges incident to a single vertex, but deeper Ramsey theory generalizes this to larger s and t. The surprising fact is that R(s,t) always exists—this is Ramsey's theorem—and it grows extremely fast. While R(3,3)=6, R(4,4)=18, and R(5,5) is unknown (it lies between 43 and 48). For even larger s, the exact values are hopelessly difficult to compute; the known bounds are far apart. Understanding the party problem illuminates a central idea of Ramsey theory: in sufficiently large systems, complete disorder is impossible—patterns must emerge. This principle appears in many areas, from number theory (e.g., Schur's theorem) to computer science (e.g., in algorithm analysis and communication protocols), showing that inevitable structure can be derived from simple counting arguments.