Increasing and Decreasing Subsequences of Permutations and Their Variants
arXiv:math/0512035
Abstract
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.
31 pages
References in corpus (11)
- Level-Spacing Distributions and the Airy Kernel
- Distribution functions for largest eigenvalues and their applications
- On the Wilf-Stanley limit of 4231-avoiding permutations and a conjecture of Arratia
- Analysis of airplane boarding via space-time geometry and random matrix theory
- Combinatorial Representation Theory
- Toeplitz determinants, random growth and determinantal processes
- Combinatorics of patience sorting piles
- Limit shapes for random square Young tableaux and plane partitions
- On the Limiting Distribution for the Longest Alternating Sequence in a Random Permutation
- RSK Insertion for Set Partitions and Diagram Algebras
- Pattern Avoidance and the Bruhat Order