Richard Stanley


University of Miami


Tuesday, January 22, 2019 - 11:00am to 12:00pm



RH 306

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.