  We survey the theory of increasing and decreasing subsequences of
permutations. Enumeration problems in this area are closely related to the RSK
algorithm. The asymptotic behavior of the expected value of the length is(w) of
the longest increasing subsequence of a permutation w of 1,2,...,n was obtained
by Vershik-Kerov and (almost) by Logan-Shepp. The entire limiting distribution
of is(w) was then determined by Baik, Deift, and Johansson. These techniques
can be applied to other classes of permutations, such as involutions, and are
related to the distribution of eigenvalues of elements of the classical groups.
A number of generalizations and variations of increasing/decreasing
subsequences are discussed, including the theory of pattern avoidance, unimodal
and alternating subsequences, and crossings and nestings of matchings and set
partitions.
