Return to Colloquia & Seminar listing
Longest increasing subsequences of permutations
Student-Run Discrete Math Seminar| Speaker: | Dan Romik, UC Davis |
| Location: | 3106 MSB |
| Start time: | Thu, Nov 5 2009, 1:10PM |
In this talk I will tell the story of the problem known as Ulam's problem, namely of understanding the asymptotic behavior of the length of a longest increasing subsequence of a random permutation of order N. This problem, studied since the 1960's, has resulted in a number of surprising discoveries and turns out to be related to deep results from probability theory. (Some of these discoveries have even lead to a Fields medal!) I will also mention a connection to the classical Erdos-Szekeres theorem in combinatorics, and a surprising result concerning the behavior of permutations which are extremal examples for that theorem.