Return to Colloquia & Seminar listing
Longest increasing subsequences of permutations
Student-Run Discrete Mathematics| Speaker: | Dan Romik, UC Davis |
| Location: | 3106 MSB |
| Start time: | Thu, Nov 5 2009, 1:10PM |
Description
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.