Ramsey's Theorem

R(s, t) ≤ R(s-1, t) + R(s, t-1): Ramsey's theorem by induction.

The idea

Theorem (Ramsey's theorem).

For every pair of integers $s, t \ge 2$ there is a number $R(s, t)$ with the following property. However the edges of a complete graph on $R(s, t)$ vertices are colored red and blue, the graph contains either $s$ vertices with every edge among them red or $t$ vertices with every edge among them blue.

The claim covers every coloring, including one designed to avoid both patterns. On a small graph such a coloring may exist; the theorem says that once the graph is large enough, none does, and a red $K_s$ or a blue $K_t$ is forced. The smallest size that forces one is the Ramsey number $R(s, t)$. Its exact value is a separate and notoriously difficult question, known only for very small $s$ and $t$: for instance $R(3, 3) = 6$, which is the case the figure shows.

Ways to work on it

• Walkthrough. Show that any six people include three mutual friends or three mutual strangers, and that five need not.
• Proof. Prove the lemma that makes every Ramsey number finite, and read off the binomial bound it implies.
• Practice. Compute Ramsey bounds from the recurrence and the pigeonhole step behind it.
• Hardest. Pin down R(3, 4) exactly, one better than the recurrence allows.

Not sure where to start? Take the ten-question placement test.