Introduction to Combinatorics, 2nd Edition

CHAPTER 4

RAMSEY THEORY

The Erdös–Szekeres theorem and Dilworth’s lemma guarantee the existence of particular substructures of certain combinatorial configurations. Large disordered structures contain ordered substructures. We continue this theme by presenting two cornerstones of Ramsey theory: Ramsey’s theorem on graphs and van der Waerden’s theorem on arithmetic progressions. In the process we discuss related results, including Schur’s theorem on equations. We also investigate bounds and asymptotics of Ramsey numbers using techniques from number theory and probability. The central pursuit is always to find ordered substructures of large disordered structures. We want to find order in randomness.

4.1 Ramsey’s theorem

The following problem appeared in the 1953 William Lowell Putnam Mathematical Competition:

Six points are in general position in space (no three in a line, no four in a plane). The fifteen line segments joining them in pairs are drawn and then painted, some segments red, some blue. Prove that some triangle has all its sides the same color.

The description of the six points in general position and the segments joining them in pairs is just another way of defining the graph K₆. We introduce a few more graph theory terms. A coloring of the set of edges of a graph G is a function f : E(G) → S, where S is a set of colors. A coloring partitions E(G) into color classes. If f is constant, then G is monochromatic.

Now we may rephrase the Putnam question as follows: If each ...