递增和递减子序列

摘要

我们将概述置换的递增和递减子序列理论．这个领域中的计数问题与RSK算法紧密相关，1，2…．n的一个置换伽的最长递增子序列长度is（w）的期望值的海：近行为由Vershik-Kerov和（几乎）由Logan—Shepp得到．之后，is（w）的整极限分布由Balk，Deift和Johansson确定．这些技术可以被应用到其它的如对合这样的置换类，并且与典型群中元素的本征值分布相关．对于递增递减子序列的许多推广和变异进行了讨论，其中包括模式回避（pattern avoidance）理论，单峰和交错子序列，匹配的交叉和嵌套以及集合划分等理论．