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.