hosted by the Harvey Mudd College Math Department created, authored and ©1999-2010 by Francis Su

The Math Fun Facts App!

List All : List Recent : List Popular
About Math Fun Facts / How to Use
Contributors / Fun Facts Home
© 1999-2010 by Francis Edward Su

From the Fun Fact files, here is a Fun Fact at the Advanced level:

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

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
Fun Fact suggested by:   Aaron Archer
Suggestions? Use this form.
4.34
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!
New: get the MathFeed iPhone App!

Brings you news and views on math:
showcasing its power, beauty, and humanity

Want another Math Fun Fact?

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