O'Reilly logo

Combinatorics by Peter J. Cameron

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

10.  Ramsey’s Theorem

Complete disorder is impossible

T. S. Motzkin (attr.)

image

TOPICS: Pigeonhole Principle; Ramsey’s Theorem; estimates for Ramsey numbers; applications

TECHNIQUES: Double induction; probabilistic existence proof

ALGORITHMS:

CROSS-REFERENCES:

image

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required