Up: Student Seminars for 2013
Top: Math Department Student Seminars

From Pigeonhole Principles to the Erdös-Szekeres Theorem

by

Alan Taylor
Union College

April 11, 2013
12:45 pm
Bailey Hall 201

Refreshments will be served in Bailey Hall 204


Abstract:

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.
Up: Student Seminars for 2013
Top: Math Department Student Seminars

[HOME]
Union College Math Department Home Page
Comments to: math@union.edu
Created automatically on: Fri Apr 20 00:55:00 EDT 2018