Ramsey Numbers Explained: The Party Problem and R(5,5)

Quick answer: A Ramsey number R(s,t) is the smallest number of people at a party that guarantees either s people who all know each other or t people who are all strangers. R(3,3) = 6 and R(4,4) = 18, but R(5,5) is unknown: it is between 43 and 46. Ramsey theory, named after Frank Ramsey (1930), shows that certain patterns are unavoidable once a structure is large enough, whatever the coloring.

Invite six people to a party. However they happen to know each other, you can always find three who are mutual friends or three who are mutual strangers. With only five people, that guarantee fails. This small fact is the doorway to Ramsey theory, one of the most beautiful and frustrating areas of mathematics.

The Party Problem

Draw each guest as a dot and join every pair with a line: red if they know each other, blue if they do not. A Ramsey number asks how many dots force a single-colored triangle, or more generally a single-colored group:

\[ R(s,t) = \text{the smallest } n \text{ such that every red/blue coloring of the lines among } n \text{ dots has a red } K_s \text{ or a blue } K_t. \]

Here \(K_s\) means \(s\) dots all joined to each other.

Why R(3,3) = 6

Pick one guest, Alice, among six. She has 5 relationships, so by the pigeonhole principle at least 3 are the same color, say red, to Bob, Carol and Dan. If any two of Bob, Carol and Dan are joined in red, they form a red triangle with Alice. If not, all three lines among them are blue, a blue triangle. Either way, a single-colored triangle appears.

With 5 guests it fails: arrange them in a pentagon, color the outer edges red and the diagonals (a star) blue. There is no single-colored triangle. So \(R(3,3) = 6\).

Known Ramsey Numbers

Ramsey numberValueStatus
\(R(3,3)\)6Known (classic)
\(R(3,4)\)9Known (1955)
\(R(3,5)\)14Known (1955)
\(R(4,4)\)18Known (1955)
\(R(4,5)\)25Known (McKay and Radziszowski, 1995)
\(R(5,5)\)\(43 \le R(5,5) \le 46\)Exact value unknown; 46 by Angeltveit and McKay (2024 preprint, published 2026)
\(R(6,6)\)\(102 \le R(6,6) \le 160\)Exact value unknown

Paul Erdős famously joked that if aliens demanded the value of \(R(5,5)\) or they would destroy Earth, we should put all our computers to work on it; if they asked for \(R(6,6)\), we should try to destroy the aliens. The number of colorings explodes: 43 dots have \(\binom{43}{2} = 903\) lines (try our combination calculator), so there are \(2^{903}\) colorings, far too many to check one by one. Proving \(R(5,5) \ge 43\) means exhibiting one 42-dot coloring with no single-colored \(K_5\); proving the upper bound means ruling out every coloring of 46 dots.

Why Ramsey Numbers Grow Exponentially

For the diagonal numbers \(R(k) = R(k,k)\), mathematicians know

\[ 2^{k/2} \lesssim R(k) \lesssim 4^k \quad \text{(classical growth bounds)}. \]

The lower bound comes from Erdős’s 1947 probabilistic method: color the lines at random, and for \(n\) about \(2^{k/2}\), a random coloring has no single-colored \(K_k\) with positive probability. That proof showed something exists without constructing it, and launched a whole field. The upper bound \(4^k\) goes back to Erdős and Szekeres in 1935.

Recent Breakthroughs

  • 2023: Marcelo Campos, Simon Griffiths, Robert Morris and Julian Sahasrabudhe proved \(R(k) \le (4 – \varepsilon)^k\) for a small fixed \(\varepsilon > 0\), the first exponential improvement on the 1935 upper bound (published in the Annals of Mathematics in 2026).
  • 2024: Parth Gupta, Ndiame Ndiaye, Sergey Norin and Louis Wei optimized the method to \(3.8^{k + o(k)}\).
  • 2023: Sam Mattheus and Jacques Verstraete proved \(R(4,t)\) grows like \(t^3\) up to logarithmic factors.
  • 2025: Jie Ma, Wujie Shen and Shengjie Xie posted the first exponential improvement on Erdős’s random lower bound for off-diagonal Ramsey numbers \(R(k, Ck)\), for each fixed \(C > 1\) (not the diagonal case).
  • 2026 preprints: a September 2026 preprint by Lu and Wang claims \(R(k) \le 3.69507^k\) for large \(k\), and later announcements claim smaller bases; these are not yet peer reviewed.

The gap between \(2^{k/2}\) and roughly \(3.7^k\) is still enormous, so the true growth rate of \(R(k)\) is one of the central open problems in combinatorics.

Common Misconceptions

“Ramsey theory is about randomness.” Its guarantees cover every coloring, random or not. Randomness is still a key tool, for proving lower bounds.

“Computers can just find R(5,5).” Naive enumeration is hopeless. The bound of 46 needed linear programming and clever reductions plus heavy computation, independently implemented by both authors.

For a geometric cousin, see the happy ending problem.

Watch: Ramsey Theory in Video

If you learn better by watching, these videos are worth your time.

Why complete chaos is impossible || Ramsey Theory (Dr. Trefor Bazett). A clear introduction with the party problem and R(3,3).
Ramsey Theory Introduction (Rehm). A visual walk through Ramsey numbers and why they are hard.

Check Your Understanding

Five quick questions to see how much of this has stuck. Pick an answer and press Submit; you will see a short explanation either way.

Answer each question and press Submit to see your result right away.

1. What is R(3,3)?
Found a bug? Let us know!
2. Which principle proves R(3,3) is at most 6?
Found a bug? Let us know!
3. How many edges does K₅ (5 dots, all joined) have?
Found a bug? Let us know!
4. What is known about R(5,5)?
Found a bug? Let us know!
5. What did Campos, Griffiths, Morris and Sahasrabudhe prove in 2023?
Found a bug? Let us know!

Frequently Asked Questions

What is a Ramsey number in simple terms?

R(s,t) is the smallest group size that guarantees either s people who all know each other or t people who are all strangers, however the relationships are arranged.

Why is R(3,3) equal to 6?

In any group of 6, one person has at least 3 friends or 3 strangers among the other 5, which forces a triangle of one kind. A pentagon arrangement shows 5 people are not enough.

Is R(5,5) known?

No. As of November 2026 it is known only that 43 ≤ R(5,5) ≤ 46; the upper bound by Angeltveit and McKay was published in 2026.

What is Ramsey theory used for?

It underlies results in computer science, information theory and logic, and it explains why patterns appear in any sufficiently large structure.

Keep Exploring

Sources and Further Reading

Related to This Article

What people say about "Ramsey Numbers Explained: The Party Problem and R(5,5) - Effortless Math"?

No one replied yet.

Leave a Reply