Ramsey theory formalizes the intuition that in any large enough structure, however chaotic, there are regions of uniformity. Some early theorems serve as good examples:

1. (van der Waerden) If the integers are colored (with a finite collection of colors) then at least one color class contains arithmetic progressions of arbitrary length.

2. (Schur) If the integers are colored (with a finite collection of colors) then at least one color class contains a set {x, y, z} such that x + y = z.

3. (Ramsey) For any positive integer k, all sufficiently large graphs contain either a complete graph on k vertices or an independent set on k vertices.

In this talk, I'll describe a proof of Ramsey's theorem and state one of the cornerstones of the theory: the celebrated Hales-Jewett theorem. Finally, I'll discuss a nonconstructive but powerful method for producing large “Ramsey graphs”− graphs that contain no small cliques or independent sets.