Increasing and decreasing subsequences and their variants

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