TheoremProved

Ramsey's theorem

Statement

For any positive integers $r, s$ , there exists a least integer $R(r,s)$ such that every 2-coloring of the edges of the complete graph $K_n$ with $n \ge R(r,s)$ contains either a monochromatic $K_r$ in the first color or a monochromatic $K_s$ in the second color.

Why is it true?

Complete disorder is impossible at scale: if a party is large enough, there must be either a group of $r$ people who all know each other or a group of $s$ people who are all strangers. No matter how you try to mix red and blue edges to avoid cliques, once the graph is big enough a uniform pocket is forced to appear.

Proof sketch

Prove by induction on $r+s$ that $R(r,s) \le R(r-1,s) + R(r,s-1)$ . Pick a vertex $v$ in a 2-colored $K_n$ with $n = R(r-1,s) + R(r,s-1)$ ; by the pigeonhole principle, $v$ has either at least $R(r-1,s)$ red neighbors or at least $R(r,s-1)$ blue neighbors. In the first case, the red neighborhood either contains a red $K_{r-1}$ (which together with $v$ forms a red $K_r$ ) or a blue $K_s$ ; the second case is symmetric.

Topics that use this theorem

Ramsey theory

Related theorems

Pigeonhole principle Szemerédi's theorem

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

Frank P. Ramsey (1930). On a Problem of Formal Logic · DOI:10.1112/plms/s2-30.1.264