×

Longest increasing subsequences, Plancherel-type measure and the Hecke insertion algorithm. (English) Zbl 1227.05262

Summary: We define and study the Plancherel-Hecke probability measure on Young diagrams; the Hecke algorithm of Buch-Kresch-Shimozono-Tamvakis-Yong is interpreted as a polynomial-time exact sampling algorithm for this measure. Using the results of Thomas-Yong on jeu de taquin for increasing tableaux, a symmetry property of the Hecke algorithm is proved, in terms of longest strictly increasing/decreasing subsequences of words.
This parallels classical theorems of Schensted and of Knuth, respectively, on the Schensted and Robinson-Schensted-Knuth algorithms. We investigate, and conjecture about, the limit typical shape of the measure, in analogy with work of Vershik-Kerov, Logan-Shepp and others on the “longest increasing subsequence problem” for permutations. We also include a related extension of Aldous-Diaconis on patience sorting. Together, these results provide a new rationale for the study of increasing tableau combinatorics, distinct from the original algebraic-geometric ones concerning \(K\)-theoretic Schubert calculus.

MSC:

05E05 Symmetric functions and generalizations
05E10 Combinatorial aspects of representation theory
60C05 Combinatorial probability
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aldous, D.; Diaconis, P., Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem, Bull. Amer. Math. Soc., 36, 413-432 (1999) · Zbl 0937.60001
[2] Baik, J.; Deift, P.; Johansson, K., On the distribution of the length of the longest increasing subsequence of random permutations, J. Amer. Math. Soc., 12, 1119-1178 (1999) · Zbl 0932.05001
[3] Biane, P., Approximate factorization and concentration for characters of symmetric groups, Int. Math. Res. Not., 2001, 4, 179-192 (2001) · Zbl 1106.20304
[4] Björner, A.; Brenti, F., Combinatorics of Coxeter Groups, Grad. Texts in Math., vol. 231 (2005), Springer: Springer New York · Zbl 1110.05001
[5] Borodin, A.; Olshanski, G., Asymptotics of Plancherel-type random partitions, J. Algebra, 313, 40-60 (2007) · Zbl 1117.60051
[6] Buch, A., A Littlewood-Richardson rule for the \(K\)-theory of Grassmannians, Acta Math., 189, 37-78 (2002) · Zbl 1090.14015
[7] Buch, A.; Kresch, A.; Shimozono, M.; Tamvakis, H.; Yong, A., Stable Grothendieck polynomials and \(K\)-theoretic factor sequences, Math. Ann., 340, 2, 359-382 (2008) · Zbl 1157.14036
[8] Dembo, A.; Zeitouni, O., Large deviations and applications, (Handbook of Stochastic Analysis and Applications. Handbook of Stochastic Analysis and Applications, Stat. Textb. Monogr., vol. 163 (2002), Dekker: Dekker New York), 351-416 · Zbl 1002.60024
[9] Edelman, P.; Greene, C., Balanced tableaux, Adv. Math., 63, 1, 42-99 (1987) · Zbl 0616.05005
[10] Erdős, P.; Szekeres, G., A combinatorial problem in geometry, Compos. Math., 2, 463-470 (1935) · Zbl 0012.27010
[11] Fomin, S.; Greene, C., Noncommutative Schur functions and their applications, Discrete Math., 193, 1-3, 179-200 (1998), selected papers in honor of Adriano Garsia (Taormina, 1994) · Zbl 1011.05062
[12] Greene, C., An extension of Schenstedʼs theorem, Adv. Math., 14, 254-265 (1974) · Zbl 0303.05006
[13] Hammersley, J. M., A few seedlings of research, (Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, vol. 1 (1972), University of California Press), 345-394 · Zbl 0236.00018
[14] Houdré, C.; Litherland, T., On the longest increasing subsequence for finite and countable alphabets, preprint · Zbl 1243.60022
[15] Johansson, K., Discrete orthogonal polynomial ensembles and the Plancherel measure, Ann. of Math. (2), 153, 1, 259-296 (2001) · Zbl 0984.15020
[16] Knuth, D. E., Permutations, matrices and generalized Young tableaux, Pacific J. Math., 34, 709-727 (1970) · Zbl 0199.31901
[17] Lascoux, A.; Schützenberger, M.-P., Structure de Hopf de lʼanneau de cohomologie et de lʼanneau de Grothendieck dʼune variété de drapeaux, C. R. Acad. Sci. Paris Sér. I Math., 295, 11, 629-633 (1982) · Zbl 0542.14030
[18] Logan, B. F.; Shepp, L. A., A variational problem for random Young tableaux, Adv. Math., 26, 206-222 (1977) · Zbl 0363.62068
[19] Mallows, C. L., Patience sorting, Bull. Inst. Math. Appl., 9, 216-224 (1973)
[20] Schensted, C., Longest increasing and decreasing subsequences, Canad. J. Math., 13, 179-191 (1961) · Zbl 0097.25202
[21] Stanley, R. P., Polygon dissections and standard Young tableaux, J. Combin. Theory Ser. A, 76, 175-177 (1996) · Zbl 0859.05075
[22] Stanley, R. P., Enumerative Combinatorics, vol. 2 (1999), Cambridge University Press, (with an appendix by S. Fomin) · Zbl 0928.05001
[23] R.P. Stanley, Increasing and decreasing subsequences and their variants, in: Proceedings of the International Congress of Mathematicians, Madrid, Spain, 2006.; R.P. Stanley, Increasing and decreasing subsequences and their variants, in: Proceedings of the International Congress of Mathematicians, Madrid, Spain, 2006. · Zbl 1133.05002
[24] Thomas, H.; Yong, A., A jeu de taquin theory for increasing tableau, with applications to \(K\)-theoretic Schubert calculus, J. Algebra Number Theory, 3, 2, 121-148 (2009) · Zbl 1229.05285
[25] Tracy, C.; Widom, H., On the distributions of the lengths of longest monotone subsequences in random words, Probab. Theory Related Fields, 119, 350-380 (2001) · Zbl 0989.60012
[26] Vershik, A. M.; Kerov, S. V., Asymptotic behavior of the Plancherel measure of the symmetric group and the limit form of Young tableaux, Dokl. Akad. Nauk SSSR. Dokl. Akad. Nauk SSSR, Soviet Math. Dokl., 233, 527-531 (1977), English translation: · Zbl 0406.05008
[27] Vershik, A. M.; Kerov, S. V., Asymptotic behavior of the maximum and generic dimensions of irreducible representations of the symmetric group, Funktsional. Anal. i Prilozhen., 19, 1, 25-36 (1985) · Zbl 0592.20015
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.