From Pigeonhole Principles to the Erdös-Szekeres Theorem
April 11, 2013
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.
|Union College Math Department Home Page|
Comments to: email@example.com
Created automatically on: Tue Oct 23 16:00:34 EDT 2018