On random shifted standard Young tableaux and 132-avoiding sorting networks
Algebraic Combinatorics, Volume 3 (2020) no. 6, pp. 1231-1258.

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.

Received:
Revised:
Accepted:
Published online:
DOI: https://doi.org/10.5802/alco.133
Classification: 60C05,  05E15,  68P10
Keywords: Shifted standard Young tableaux, random 132-avoiding sorting networks
@article{ALCO_2020__3_6_1231_0,
     author = {Linusson, Svante and Potka, Samu and Sulzgruber, Robin},
     title = {On random shifted standard {Young} tableaux and 132-avoiding sorting networks},
     journal = {Algebraic Combinatorics},
     pages = {1231--1258},
     publisher = {MathOA foundation},
     volume = {3},
     number = {6},
     year = {2020},
     doi = {10.5802/alco.133},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.133/}
}
TY  - JOUR
AU  - Linusson, Svante
AU  - Potka, Samu
AU  - Sulzgruber, Robin
TI  - On random shifted standard Young tableaux and 132-avoiding sorting networks
JO  - Algebraic Combinatorics
PY  - 2020
DA  - 2020///
SP  - 1231
EP  - 1258
VL  - 3
IS  - 6
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.133/
UR  - https://doi.org/10.5802/alco.133
DO  - 10.5802/alco.133
LA  - en
ID  - ALCO_2020__3_6_1231_0
ER  - 
Linusson, Svante; Potka, Samu; Sulzgruber, Robin. On random shifted standard Young tableaux and 132-avoiding sorting networks. Algebraic Combinatorics, Volume 3 (2020) no. 6, pp. 1231-1258. doi : 10.5802/alco.133. https://alco.centre-mersenne.org/articles/10.5802/alco.133/

[1] Angel, Omer; Holroyd, Alexander E.; Romik, Dan; Virág, Bálint Random sorting networks, Adv. Math., Volume 215 (2007) no. 2, pp. 839-868 | Article | MR 2355610 | Zbl 1132.60008

[2] Biane, Philippe Representations of symmetric groups and free probability, Adv. Math., Volume 138 (1998) no. 1, pp. 126-181 | Article | MR 1644993 | Zbl 0927.20008

[3] Björner, Anders; Wachs, Michelle L. Shellable nonpure complexes and posets. II, Trans. Amer. Math. Soc., Volume 349 (1997) no. 10, pp. 3945-3975 | Article | MR 1401765 | Zbl 0886.05126

[4] Dauvergne, Duncan The Archimedean limit of random sorting networks (2018) (https://arxiv.org/abs/1802.08934)

[5] Davis, Robert; Sagan, Bruce Pattern-avoiding polytopes, European J. Combin., Volume 74 (2018), pp. 48-84 | Article | MR 3846227 | Zbl 1398.52014

[6] Edelman, Paul; Greene, Curtis Balanced tableaux, Adv. in Math., Volume 63 (1987) no. 1, pp. 42-99 | Article | MR 871081 | Zbl 0616.05005

[7] Elizalde, Sergi; Roichman, Yuval Arc permutations, J. Algebraic Combin., Volume 39 (2014) no. 2, pp. 301-334 | Article | MR 3159254 | Zbl 1292.05268

[8] Fischer, Ilse A bijective proof of the hook-length formula for shifted standard tableaux (2001) (https://arxiv.org/abs/math/0112261)

[9] Fishel, Susanna; Nelson, Luke Chains of maximum length in the Tamari lattice, Proc. Amer. Math. Soc., Volume 142 (2014) no. 10, pp. 3343-3353 | Article | MR 3238412 | Zbl 1326.06006

[10] Flajolet, Philippe; Sedgewick, Robert Analytic combinatorics, Cambridge Univ. Press, Cambridge, 2009, 826 pages | Article | Zbl 1165.05001

[11] Frame, James S.; Robinson, Gilbert de B.; Thrall, Robert M. The hook graphs of the symmetric group, Canad. J. Math., Volume 6 (1954), pp. 316-325 | Article | MR 62127 | Zbl 0055.25404

[12] Gansner, Emden R. Matrix correspondences and the enumeration of plane partitions (1978) (Ph. D. Thesis) | MR 2940848

[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., Volume 31 (1979) no. 1, pp. 104-109 | Article | MR 521470 | Zbl 0398.05008

[14] Haiman, Mark D. On mixed insertion, symmetry, and shifted Young tableaux, J. Combin. Theory Ser. A, Volume 50 (1989) no. 2, pp. 196-225 | Article | MR 989194 | Zbl 0697.05005

[15] Haiman, Mark D. Dual equivalence with applications, including a conjecture of Proctor, Discrete Math., Volume 99 (1992) no. 1–3, pp. 79-113 | Article | MR 1158783 | Zbl 0760.05093

[16] Ivanov, Vladimir Plancherel measure on shifted Young diagrams, Representation Theory, Dynamical Systems, and Asymptotic Combinatorics (Amer. Math. Soc. Transl. Ser. 2), Volume 217, Amer. Math. Soc., Providence, RI, 2006, pp. 73-86 | Article | MR 2276102 | Zbl 1111.05096

[17] Kitaev, Sergey Patterns in Permutations and Words, Monographs in Theoretical Computer Science. An EATCS Series, Springer, Heidelberg, 2011, xxii+494 pages | Article | Zbl 1257.68007

[18] Kraśkiewicz, Witold Reduced decompositions in hyperoctahedral groups, C. R. Acad. Sci. Paris Sér. I Math., Volume 309 (1989) no. 16, pp. 903-907 | MR 1055219 | Zbl 0717.05005

[19] Kraśkiewicz, Witold Reduced decompositions in Weyl groups, European J. Combin., Volume 16 (1995) no. 3, pp. 293-313 | Article | MR 1330543 | Zbl 0828.05064

[20] Linusson, Svante; Potka, Samu Properties of the Edelman–Greene bijection, J. Comb., Volume 11 (2020) no. 2, pp. 249-273 | Article | MR 4060944 | Zbl 1430.05132

[21] Macdonald, Ian G. Symmetric functions and Hall polynomials, Oxford Mathematical Monographs, Oxford University Press, Oxford, 1995 | Zbl 0824.05059

[22] Matsumoto, Sho; Śniady, Piotr Random strict partitions and random shifted tableaux, Selecta Math. (N.S.), Volume 26 (2020) no. 1, Paper no. 10 | Article | MR 4056839 | Zbl 07161024

[23] Naruse, Hiroshi; Okada, Soichi Skew hook formula for d-complete posets via equivariant K-theory, Algebr. Comb., Volume 2 (2019) no. 4, pp. 541-571 | Article | MR 3997510 | Zbl 1417.05011

[24] Novelli, Jean-Cristophe; Pak, Igor; Stoyanovskii, Alexander V. A direct bijective proof of the hook-length formula, Discrete Math. Theor. Comput. Sci., Volume 1 (1997) no. 1, pp. 53-67 | MR 1605030 | Zbl 0934.05125

[25] OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences, 2020 (http://oeis.org)

[26] Panova, Greta; Śniady, Piotr Skew Howe duality and random rectangular Young tableaux, Algebr. Comb., Volume 1 (2018) no. 1, pp. 81-94 | Article | MR 3857160 | Zbl 1391.05268

[27] Pittel, Boris; Romik, Dan Limit shapes for random square Young tableaux, Adv. in Appl. Math., Volume 38 (2007) no. 2, pp. 164-209 | Article | MR 2290809 | Zbl 1122.60009

[28] Proctor, Robert A. Dynkin diagram classification of λ-minuscule Bruhat lattices and of d-complete posets, J. Algebraic Combin., Volume 9 (1999) no. 1, pp. 61-94 | Article | MR 1676724 | Zbl 0920.06003

[29] Reiner, Victor Note on the expected number of Yang–Baxter moves applicable to reduced decompositions, European J. Combin., Volume 26 (2005) no. 6, pp. 1019-1021 | Article | MR 2143207 | Zbl 1071.20003

[30] Romik, Dan The Surprising Mathematics of Longest Increasing Subsequences, Institute of Mathematical Statistics Textbooks, Cambridge University Press, New York, 2015, xii+353 pages | Article | Zbl 1345.05003

[31] Sagan, Bruce E. On selecting a random shifted Young tableau, J. Algorithms, Volume 1 (1980) no. 3, pp. 213-234 | Article | MR 604864 | Zbl 0468.05008

[32] Sagan, Bruce E. Shifted tableaux, Schur Q-functions, and a conjecture of R. Stanley, J. Combin. Theory Ser. A, Volume 45 (1987) no. 1, pp. 62-103 | Article | MR 883894 | Zbl 0661.05010

[33] Sagan, Bruce E. The Symmetric Group. Representations, Combinatorial Algorithms, and Symmetric Functions, Graduate Texts in Mathematics, 203, Springer-Verlag, New York, 2001, xvi+240 pages | Article | Zbl 0964.05070

[34] Sage-Combinat community Sage-Combinat: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics, 2008 (http://combinat.sagemath.org)

[35] Sage Developers SageMath, the Sage Mathematics Software System Version 9.1, 2020 (http://www.sagemath.org)

[36] Schilling, Anne; Thiéry, Nicolas M.; White, Graham; Williams, Nathan Braid moves in commutation classes of the symmetric group, European J. Combin., Volume 62 (2017), pp. 15-34 | Article | MR 3621720 | Zbl 1358.05308

[37] Schützenberger, Marcel-Paul Quelques remarques sur une construction de Schensted, Math. Scand., Volume 12 (1963) no. 1, pp. 117-128 | Article | MR 190017 | Zbl 0216.30202

[38] Stanley, Richard P. Enumerative Combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, 62, Cambridge University Press, Cambridge, 1999, xii+585 pages | Article | MR 1676282 | Zbl 0928.05001

[39] Stanley, Richard P. Promotion and evacuation, Electron. J. Combin., Volume 16 (2009) no. 2, The Björner Festschrift volume, Paper no. 9, 24 pages | Article | MR 2515772 | Zbl 1169.06002

[40] Stembridge, John R. Shifted tableaux and the projective representations of symmetric groups, Adv. Math., Volume 74 (1989) no. 1, pp. 87-134 | Article | MR 991411 | Zbl 0677.20012

[41] Stembridge, John R. On the of fully commutative elements of Coxeter groups, J. Algebraic Combin., Volume 5 (1996) no. 4, pp. 353-385 | Article | MR 1406459 | Zbl 0864.20025

[42] Stembridge, John R. The enumeration of fully commutative elements of Coxeter groups, J. Algebraic Combin., Volume 7 (1998) no. 3, pp. 291-320 | Article | MR 1616016 | Zbl 0897.05087

[43] Tenner, Bridget E. On the expected number of commutations in reduced words, Australas. J. Combin., Volume 62 (2015) no. 1, pp. 147-154 | MR 3337183 | Zbl 1321.05007

[44] Thrall, Robert M. A combinatorial problem, Michigan Math. J., Volume 1 (1952) no. 1, pp. 81-88 | Article | Zbl 0049.01001

Cited by Sources: