10. Ramsey’s Theorem
Complete disorder is impossible
T. S. Motzkin (attr.)
TOPICS: Pigeonhole Principle; Ramsey’s Theorem; estimates for Ramsey numbers; applications
TECHNIQUES: Double induction; probabilistic existence proof
In 1930, F. P. Ramsey1 proved a lemma in a paper on mathematical logic. The lemma has proved to be of greater importance than the theorem it was used to prove,2 and has given its author’s name to an area where combinatorics, logic, topology and probability interact. Roughly speaking, a theorem ...