ALGEBRAIC COMBINATORICS

no. 6
On random shifted standard Young tableaux and 132-avoiding sorting networks
Linusson, Svante1; Potka, Samu1; Sulzgruber, Robin1
1 KTH Royal Institute of Technology Department of Mathematics Stockholm Sweden
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: 10.5802/alco.133
Classification: 60C05, 05E15, 68P10
Keywords: Shifted standard Young tableaux, random 132-avoiding sorting networks
Linusson, Svante 1; Potka, Samu 1; Sulzgruber, Robin 1

1 KTH Royal Institute of Technology Department of Mathematics Stockholm Sweden
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@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
SP  - 1231
EP  - 1258
VL  - 3
IS  - 6
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.133/
DO  - 10.5802/alco.133
LA  - en
ID  - ALCO_2020__3_6_1231_0
ER  - 
%0 Journal Article
%A Linusson, Svante
%A Potka, Samu
%A Sulzgruber, Robin
%T On random shifted standard Young tableaux and 132-avoiding sorting networks
%J Algebraic Combinatorics
%D 2020
%P 1231-1258
%V 3
%N 6
%I MathOA foundation
%U https://alco.centre-mersenne.org/articles/10.5802/alco.133/
%R 10.5802/alco.133
%G en
%F ALCO_2020__3_6_1231_0
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 | DOI | MR | Zbl

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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

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

[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 | DOI | MR | Zbl

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

[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 | DOI | MR | Zbl

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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

[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 | DOI | MR | Zbl

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

[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 | Zbl

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

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

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

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

[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 | DOI | MR | Zbl

[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 | Zbl

[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 | DOI | MR | Zbl

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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

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

[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 | DOI | MR | Zbl

[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 | DOI | Zbl

[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 | DOI | MR | Zbl

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

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

[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 | DOI | MR | Zbl

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

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

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

[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 | Zbl

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

Cited by Sources: