##### Department of Mathematics,

University of California San Diego

****************************

### Math 295 - Mathematics Colloquium

## Richard Stanley

#### MIT

## Increasing and decreasing subsequences

##### Abstract:

We begin by surveying some highlights of the theory of increasing and decreasing subsequences of permutations, including (1) connections with Young tableaux and the $RSK$ algorithm, (2) the expected length is($w$) of the longest increasing subsequence of a random permutation $w$ of $1$,$2$,...,n, and (3) the limiting distribution of is($w$) due to Baik, Deift, and Johansson. We will then discuss how these results carry over to (complete) matchings $M$ on the vertices $1$,$2$,...,$2n$. The analogue of increasing/decreasing subsequences will be shown to be related to crossings and nestings of $M$.

Host: Adriano Garsia

### December 8, 2005

### 3:00 PM

### AP&M 7321

****************************