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.
