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

Among any six people, some three are mutual acquaintances or some three are mutual strangers, while five people can be arranged to avoid both, so six is the exact threshold.

Are exact Ramsey numbers known?

Only a handful are known exactly; even R(5,5) is open, with current knowledge only narrowing it to a range, because the search space grows too fast to settle by computation.

Ramsey's Theorem and Ramsey Numbers

Ramsey's theorem guarantees that any sufficiently large two-colored complete graph contains a monochromatic clique, and Ramsey numbers quantify how large is sufficient.

Definition

The Ramsey number R(s,t) is the least integer n such that every red-blue coloring of the edges of the complete graph on n vertices contains a red clique on s vertices or a blue clique on t vertices.

Scope

This topic covers the graph form of Ramsey's theorem, the definition of Ramsey numbers R(s,t), the classical small cases such as R(3,3)=6, the Erdos-Szekeres upper bound and Erdos's probabilistic lower bound, and the extension to multicolor and hypergraph Ramsey numbers. It is the quantitative heart of Ramsey theory.

Core questions

How large must a complete graph be to force a monochromatic clique of given size?
What are the known exact values and bounds for Ramsey numbers?
How do probabilistic arguments give lower bounds on Ramsey numbers?
How does the theorem generalize to several colors and to hypergraphs?

Key concepts

Ramsey's theorem for graphs
Ramsey number R(s,t)
Monochromatic cliques
Erdos-Szekeres bound
Probabilistic lower bounds
Multicolor and hypergraph Ramsey numbers

Key theories

Erdos-Szekeres upper bound: Ramsey numbers are finite and bounded by R(s,t) being at most the binomial coefficient of s+t-2 choose s-1, a recurrence-based bound that proves Ramsey's theorem with explicit estimates.
Erdos's probabilistic lower bound: By counting expected monochromatic cliques in a random coloring, Erdos showed in 1947 that the diagonal Ramsey number R(s,s) grows at least exponentially, a founding application of the probabilistic method.

Clinical relevance

The probabilistic method introduced through Ramsey-number lower bounds became a central tool across combinatorics and theoretical computer science, and Ramsey-type guarantees underpin lower bounds in communication and data structures.

History

Erdos and Szekeres rediscovered and quantified Ramsey's theorem in 1935 while studying convex polygons; Erdos's 1947 random-coloring lower bound launched the probabilistic method.

Key figures

Frank Ramsey
Paul Erdos
George Szekeres

Seminal works

graham1990

Frequently asked questions

Why is R(3,3) equal to six?: Among any six people, some three are mutual acquaintances or some three are mutual strangers, while five people can be arranged to avoid both, so six is the exact threshold.
Are exact Ramsey numbers known?: Only a handful are known exactly; even R(5,5) is open, with current knowledge only narrowing it to a range, because the search space grows too fast to settle by computation.