×

On random shifted standard Young tableaux and 132-avoiding sorting networks. (English) Zbl 1454.60018

Summary: We study shifted standard Young tableaux (SYT). The limiting surface of uniformly random shifted SYT of staircase shape is determined, with the integers in the SYT as heights. This implies via properties of the Edelman-Greene bijection results about random 132-avoiding sorting networks, including limit shapes for trajectories and intermediate permutations. Moreover, the expected number of adjacencies in SYT is considered. It is shown that on average each row and each column of a shifted SYT of staircase shape contains precisely one adjacency.

MSC:

60C05 Combinatorial probability
05E10 Combinatorial aspects of representation theory
05E16 Combinatorial aspects of groups and algebras
68P10 Searching and sorting
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Angel, Omer; Holroyd, Alexander E.; Romik, Dan; Virág, Bálint, Random sorting networks, Adv. Math., 215, 2, 839-868 (2007) · Zbl 1132.60008 · doi:10.1016/j.aim.2007.05.019
[2] Biane, Philippe, Representations of symmetric groups and free probability, Adv. Math., 138, 1, 126-181 (1998) · Zbl 0927.20008 · doi:10.1006/aima.1998.1745
[3] Björner, Anders; Wachs, Michelle L., Shellable nonpure complexes and posets. II, Trans. Amer. Math. Soc., 349, 10, 3945-3975 (1997) · Zbl 0886.05126 · doi:10.1090/s0002-9947-97-01838-2
[4] Dauvergne, Duncan, The Archimedean limit of random sorting networks (2018)
[5] Davis, Robert; Sagan, Bruce, Pattern-avoiding polytopes, European J. Combin., 74, 48-84 (2018) · Zbl 1398.52014 · doi:10.1016/j.ejc.2018.07.006
[6] Edelman, Paul; Greene, Curtis, Balanced tableaux, Adv. in Math., 63, 1, 42-99 (1987) · Zbl 0616.05005 · doi:10.1016/0001-8708(87)90063-6
[7] Elizalde, Sergi; Roichman, Yuval, Arc permutations, J. Algebraic Combin., 39, 2, 301-334 (2014) · Zbl 1292.05268 · doi:10.1007/s10801-013-0449-6
[8] Fischer, Ilse, A bijective proof of the hook-length formula for shifted standard tableaux (2001)
[9] Fishel, Susanna; Nelson, Luke, Chains of maximum length in the Tamari lattice, Proc. Amer. Math. Soc., 142, 10, 3343-3353 (2014) · Zbl 1326.06006 · doi:10.1090/s0002-9939-2014-12069-7
[10] Flajolet, Philippe; Sedgewick, Robert, Analytic combinatorics, 826 p. pp. (2009), Cambridge Univ. Press: Cambridge Univ. Press, Cambridge · Zbl 1165.05001 · doi:10.1017/CBO9780511801655
[11] Frame, James S.; Robinson, Gilbert de B.; Thrall, Robert M., The hook graphs of the symmetric group, Canad. J. Math., 6, 316-325 (1954) · Zbl 0055.25404 · doi:10.4153/CJM-1954-030-1
[12] Gansner, Emden R., Matrix correspondences and the enumeration of plane partitions (1978) · Zbl 0432.05010
[13] Greene, Curtis; Nijenhuis, Albert; Wilf, Herbert S., A probabilistic proof of a formula for the number of Young tableaux of a given shape, Adv. in Math., 31, 1, 104-109 (1979) · Zbl 0398.05008 · doi:10.1016/0001-8708(79)90023-9
[14] Haiman, Mark D., On mixed insertion, symmetry, and shifted Young tableaux, J. Combin. Theory Ser. A, 50, 2, 196-225 (1989) · Zbl 0697.05005 · doi:10.1016/0097-3165(89)90015-0
[15] Haiman, Mark D., Dual equivalence with applications, including a conjecture of Proctor, Discrete Math., 99, 1-3, 79-113 (1992) · Zbl 0760.05093 · doi:10.1016/0012-365X(92)90368-P
[16] Ivanov, Vladimir, Representation Theory, Dynamical Systems, and Asymptotic Combinatorics, 217, Plancherel measure on shifted Young diagrams, 73-86 (2006), Amer. Math. Soc.: Amer. Math. Soc., Providence, RI · Zbl 1111.05096 · doi:10.1090/trans2/217/06
[17] Kitaev, Sergey, Patterns in Permutations and Words, xxii+494 p. pp. (2011), Springer: Springer, Heidelberg · Zbl 1257.68007 · doi:10.1007/978-3-642-17333-2
[18] Kraśkiewicz, Witold, Reduced decompositions in hyperoctahedral groups, C. R. Acad. Sci. Paris Sér. I Math., 309, 16, 903-907 (1989) · Zbl 0717.05005
[19] Kraśkiewicz, Witold, Reduced decompositions in Weyl groups, European J. Combin., 16, 3, 293-313 (1995) · Zbl 0828.05064 · doi:10.1016/0195-6698(95)90033-0
[20] Linusson, Svante; Potka, Samu, Properties of the Edelman-Greene bijection, J. Comb., 11, 2, 249-273 (2020) · Zbl 1430.05132 · doi:10.4310/JOC.2020.v11.n2.a2
[21] Macdonald, Ian G., Symmetric functions and Hall polynomials (1995), Oxford University Press: Oxford University Press, Oxford · Zbl 0824.05059
[22] Matsumoto, Sho; Śniady, Piotr, Random strict partitions and random shifted tableaux, Selecta Math. (N.S.), 26, 1 (2020) · Zbl 1480.20032 · doi:10.1007/s00029-020-0535-2
[23] Naruse, Hiroshi; Okada, Soichi, Skew hook formula for \(d\)-complete posets via equivariant \(K\)-theory, Algebr. Comb., 2, 4, 541-571 (2019) · Zbl 1417.05011 · doi:10.5802/alco.54
[24] Novelli, Jean-Cristophe; Pak, Igor; Stoyanovskii, Alexander V., A direct bijective proof of the hook-length formula, Discrete Math. Theor. Comput. Sci., 1, 1, 53-67 (1997) · Zbl 0934.05125
[25] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences (2020)
[26] Panova, Greta; Śniady, Piotr, Skew Howe duality and random rectangular Young tableaux, Algebr. Comb., 1, 1, 81-94 (2018) · Zbl 1391.05268 · doi:10.5802/alco.8
[27] Pittel, Boris; Romik, Dan, Limit shapes for random square Young tableaux, Adv. in Appl. Math., 38, 2, 164-209 (2007) · Zbl 1122.60009 · doi:10.1016/j.aam.2005.12.005
[28] Proctor, Robert A., Dynkin diagram classification of \(\lambda \)-minuscule Bruhat lattices and of \(d\)-complete posets, J. Algebraic Combin., 9, 1, 61-94 (1999) · Zbl 0920.06003 · doi:10.1023/A:1018615115006
[29] Reiner, Victor, Note on the expected number of Yang-Baxter moves applicable to reduced decompositions, European J. Combin., 26, 6, 1019-1021 (2005) · Zbl 1071.20003 · doi:10.1016/j.ejc.2004.06.010
[30] Romik, Dan, The Surprising Mathematics of Longest Increasing Subsequences, xii+353 p. pp. (2015), Cambridge University Press: Cambridge University Press, New York · Zbl 1345.05003 · doi:10.1017/CBO9781139872003
[31] Sagan, Bruce E., On selecting a random shifted Young tableau, J. Algorithms, 1, 3, 213-234 (1980) · Zbl 0468.05008 · doi:10.1016/0196-6774(80)90010-3
[32] Sagan, Bruce E., Shifted tableaux, Schur \(Q\)-functions, and a conjecture of R. Stanley, J. Combin. Theory Ser. A, 45, 1, 62-103 (1987) · Zbl 0661.05010 · doi:10.1016/0097-3165(87)90047-1
[33] Sagan, Bruce E., The Symmetric Group. Representations, Combinatorial Algorithms, and Symmetric Functions, 203, xvi+240 p. pp. (2001), Springer-Verlag: Springer-Verlag, New York · Zbl 0964.05070 · doi:10.1007/978-1-4757-6804-6
[34] Sage-Combinat community, Sage-Combinat: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics (2008)
[35] Sage Developers, SageMath, the Sage Mathematics Software System Version 9.1 (2020)
[36] Schilling, Anne; Thiéry, Nicolas M.; White, Graham; Williams, Nathan, Braid moves in commutation classes of the symmetric group, European J. Combin., 62, 15-34 (2017) · Zbl 1358.05308 · doi:10.1016/j.ejc.2016.10.008
[37] Schützenberger, Marcel-Paul, Quelques remarques sur une construction de Schensted, Math. Scand., 12, 1, 117-128 (1963) · Zbl 0216.30202 · doi:10.7146/math.scand.a-10676
[38] Stanley, Richard P., Enumerative Combinatorics. Vol. 2, 62, xii+585 p. pp. (1999), Cambridge University Press: Cambridge University Press, Cambridge · Zbl 0928.05001 · doi:10.1017/CBO9780511609589
[39] Stanley, Richard P., Promotion and evacuation, Electron. J. Combin., 16, 2, 24 p. pp. (2009) · Zbl 1169.06002 · doi:10.37236/75
[40] Stembridge, John R., Shifted tableaux and the projective representations of symmetric groups, Adv. Math., 74, 1, 87-134 (1989) · Zbl 0677.20012 · doi:10.1016/0001-8708(89)90005-4
[41] Stembridge, John R., On the of fully commutative elements of Coxeter groups, J. Algebraic Combin., 5, 4, 353-385 (1996) · Zbl 0864.20025 · doi:10.1023/A:1022452717148
[42] Stembridge, John R., The enumeration of fully commutative elements of Coxeter groups, J. Algebraic Combin., 7, 3, 291-320 (1998) · Zbl 0897.05087 · doi:10.1023/A:1008623323374
[43] Tenner, Bridget E., On the expected number of commutations in reduced words, Australas. J. Combin., 62, 1, 147-154 (2015) · Zbl 1321.05007
[44] Thrall, Robert M., A combinatorial problem, Michigan Math. J., 1, 1, 81-88 (1952) · Zbl 0049.01001 · doi:10.1307/mmj/1028989731
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.