## From Pigeonhole Principles to the Erdös-Szekeres Theorem |

**Alan Taylor**

Union College

April 11, 2013

12:45 pm

Bailey Hall 201

Refreshments will be served in Bailey Hall 204

The pigeonhole principle is the obvious assertion that if $n$ pigeons are placed into $m$ pigeonholes and $n > m$, then at least one of the pigeonholes must contain more than one pigeon. The Erdös-Szekeres theorem is the non-obvious assertion that within any sequence of $n^2 + 1$ distinct positive integers, there is either an increasing subsequence of length $n + 1$ or a decreasing subsequence of length $n + 1$. We will prove that the Erdös-Szekeres theorem is equivalent to a natural (and equally obvious) generalization of the pigeonhole principle and we will briefly discuss some related results.Last month, by the way, was the 100th anniversary of the birth of Paul Erdös, the most prolific mathematician who ever lived.

For additional information, send e-mail to math@union.edu or call (518) 388-6246.

Union College Math Department Home PageComments to: math@union.edu Created automatically on: Fri Apr 20 00:55:00 EDT 2018 |