Van der Waerden Theorem

Can you color the integers red and blue such that there are no monochromatic arithmetic progressions (AP's) extending infintely in both directions? Sure -- just color zero and all the positive integers red, and all the negative integers blue.

Now try coloring just the positive integers with red and blue such that there are no one-sided infinite monochromatic AP's. This is almost as easy -- color the first one red, the next two blue, the next three red, the next four blue, and so on. If an AP has step size d, then eventually it will hit a blue integer and eventually hit a red integer, as soon as the monochromatic blocks reach size d.

What about finite AP's? Given any coloring of the positive integers, can you find a monochromatic finite AP of arbitrarily long length?

Surprisingly, yes!

The Van der Waerden theorem says that given any number of colors and specifications for lengths, there's an M large enough so that no matter how you color the first M integers with those colors, you can always find a monochromatic AP of at least one of the given lengths and colors!

Presentation Suggestions:
You may ask students to think about the first two questions (perhaps a bonus problem on a HW) before doing this Fun Fact.

The Math Behind the Fact:
The Van der Waerden theorem follows from the diagonal Van der Waerden theorem in which all the specified lengths are equal. This in turn can be proven with a very clever application of the pigeonhole principle and double induction. The key observation is that one may treat a block of m integers colored with k colors as a single integer colored with k^m colors. The Van der Waerden theorem also follows as a consequence of the much more difficult Hales-Jewett Theorem, which involves monochromatic combinatorial lines in colored high-dimensional lattices. All of these results are part of a branch of mathematics called Ramsey Theory.

How to Cite this Page:
Su, Francis E., et al. "Van der Waerden Theorem." Math Fun Facts. <http://www.math.hmc.edu/funfacts>.

References: Graham, Grotschel, and Lovasz, Handbook of Combinatorics. Graham, Rothschild, Spencer, Ramsey Theory. Keywords:    combinatorics Subjects:    combinatorics Level:    Advanced Fun Fact suggested by:   Aaron Archer Suggestions? Use this form. 3.97 current rating Click to rate this Fun Fact...     *   Awesome! I totally dig it!     *   Fun enough to tell a friend!     *   Mildly interesting     *   Not really noteworthy and see the most popular Facts! Get the Math Fun Facts iPhone App!

Want another Math Fun Fact?

For more fun, tour the Mathematics Department at Harvey Mudd College!