NB: A
PDF
version of this announcement (suitable for posting) is also available.
Increasing and decreasing subsequences
Richard Stanley
Massachusetts Institute of Technology
Thursday, May 3, 2007
007 Kemeny Hall, 4 pm
Tea 3:30 pm, 300 Kemeny Hall
Abstract: A subsequence a_{i_1},\dots,a_{i_k} of a
permutation a_1,a_2,\dots, a_n of 1,2,\dots, n is
increasing if a_{i_1}. A
decreasing subsequence is similarly defined. We will survey the
subject of increasing and decreasing subsequences, focusing on what
can be said about the longest increasing and longest decreasing
subsequence of a permutation. Topics will include (a) the relationship
to Young tableaux and the famous RSK algorithm, (b) the asymptotic
behavior of the length of the longest increasing subsequence (due to
Baik, Deift, and Johansson), (c) connections with random matrix
theory, and (d) an extension of the theory from permutations to
complete matchings.
This talk will be accessible to graduate students.