|
|
Mathematics Colloquia and Seminars
Return to
Colloquia & Seminar listing.
Longest increasing subsequences of permutations |
| Student-Run Discrete Math Seminar |
| Speaker: | Dan Romik |
| 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.
|
|