## Speaker:

## Institution:

## Time:

## Host:

## Location:

An increasing subsequence of a permutation $a_1, a_2,\dots, a_n$ of

$1,2,\dots, n$ is a subsequence $b_1,b_2,\dots,b_k$ satisfying

$b_1<b_2<\cdots<b_k$, and similarly for decreasing subsequence. The

earliest result in this area is due to Erd\H{o}s and Szekeres in 1935: any

permuation of $1,2,\dots,pq+1$ has an increasing subsequnce of length

$p+1$ or a decreasing subsequence of length $q+1$. This result turns out

to be closely connected to the RSK algorithm from the representation

theory of the symmetric group. A lot of work has been devoted to the

length $k$ of the longest increasing subsequence of a permutation

$1,2,\dots,n$, beginning with Ulam's question of determining the average

value of this number over all such permutations, and culminating with the

result of Baik-Deift-Johansson on the limiting distribution of this

length. There are many interesting analogues of longest increasing

subsequences, such as longest alternating subsequences, i.e.,

subsequences $b_1,b_2,\dots, b_k$ of a permutation $a_1, a_2,\dots, a_n$

satisfying $b_1>b_2<b_3>b_4<\cdots$. The limiting distribution of the

length of the longest alternating subsequence of a random permutation

behaves very differently from the length of the longest increasing

subsequence. We will survey these highlights from the theory of

increasing and decreasing subsequences.