**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.