Ramsey's Theorem

Ramsey’s Theorem

Finite Version (Ramsey’s Theorem for Graphs)

For any integers $r, s \ge 2$, there exists an integer $R(r, s)$ such that any graph on at least $R(r, s)$ vertices contains either a clique of size $r$ or an independent set of size $s$.

Example

$R(3, 3) = 6$: In any party of six people, there are either three mutual acquaintances or three mutual strangers.

Infinite Version

Let $X$ be an infinite set. For any coloring of the $k$-element subsets of $X$ with finitely many colors, there exists an infinite subset $Y \subseteq X$ all of whose $k$-element subsets have the same color.

Known Ramsey Numbers

• $R(3, 3) = 6$
• $R(3, 4) = 9$
• $R(3, 5) = 14$
• $R(4, 4) = 18$
• $R(5, 5)$ is unknown (between 43 and 48)

Proof Ideas

The finite version is proved by induction on $r + s$, using the inequality

Applications

• Combinatorics and extremal graph theory
• Logic and model theory
• Computer science (lower bounds)
• Number theory (Van der Waerden’s theorem)

Philosophical Interpretation

“Complete disorder is impossible” – any sufficiently large system contains ordered substructures.