Bijecting hidden symmetries for skew staircase shapes

Hamaker, Zachary; Morales, Alejandro H.; Pak, Igor; Serrano, Luis; Williams, Nathan

doi:10.5802/alco.285

Hamaker, Zachary ¹; Morales, Alejandro H.²; Pak, Igor ³; Serrano, Luis ⁴; Williams, Nathan ⁵

¹ Department of Mathematics University of Florida Gainesville, FL 32611
² Department of Mathematics and Statistics University of Massachusetts Amherst, MA 01003
³ Department of Mathematics University of California Los Angeles, CA 90095
⁴ Zapata Computing Canada Inc. 325 Front St. W Toronto, ON, M5V 2Y1
⁵ Department of Mathematical Sciences University of Texas at Dallas Richardson, TX 75080

Algebraic Combinatorics, Volume 6 (2023) no. 4, pp. 1095-1118.

Abstract

We present a bijection between the set $SYT (λ / μ)$ of standard Young tableaux of staircase minus rectangle shape $λ = δ_{k}$ , $μ = (b^{a})$ , and the set ${ShSYT}^{'} (η)$ of marked shifted standard Young tableaux of a certain shifted shape $η = η (k, a, b)$ . Numerically, this result is due to DeWitt (2012). Combined with other known bijections this gives a bijective proof of the product formula for $| SYT (λ / μ) |$ . This resolves an open problem by Morales, Pak and Panova (2019), and allows an efficient random sampling from $SYT (λ / μ)$ . Other applications include a bijection for semistandard Young tableaux, and a bijective proof of Stembridge’s symmetry of LR–coefficients of the staircase shape. We also extend these results to set-valued standard Young tableaux in the combinatorics of $K$ -theory, leading to new proofs of results by Lewis and Marberg (2019) and Abney-McPeek, An and Ng (2020).

Received: 2021-04-07
Revised: 2022-10-10
Accepted: 2022-12-13
Published online: 2023-08-29

DOI: 10.5802/alco.285

Classification: 05E10, 05A19, 05E05, 17B10
Keywords: tableau, shifted tableau, Schur P-function, Worley–Sagan insertion, mixed shifted insertion, shifted Hecke insertion, Knuth class, shifted Knuth class, K-Knuth class, queer Lie superalgebra

Author's affiliations:

Hamaker, Zachary ¹; Morales, Alejandro H. ²; Pak, Igor ³; Serrano, Luis ⁴; Williams, Nathan ⁵

¹ Department of Mathematics University of Florida Gainesville, FL 32611
² Department of Mathematics and Statistics University of Massachusetts Amherst, MA 01003
³ Department of Mathematics University of California Los Angeles, CA 90095
⁴ Zapata Computing Canada Inc. 325 Front St. W Toronto, ON, M5V 2Y1
⁵ Department of Mathematical Sciences University of Texas at Dallas Richardson, TX 75080

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@article{ALCO_2023__6_4_1095_0,
     author = {Hamaker, Zachary and Morales, Alejandro H. and Pak, Igor and Serrano, Luis and Williams, Nathan},
     title = {Bijecting hidden symmetries for skew staircase shapes},
     journal = {Algebraic Combinatorics},
     pages = {1095--1118},
     publisher = {The Combinatorics Consortium},
     volume = {6},
     number = {4},
     year = {2023},
     doi = {10.5802/alco.285},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.285/}
}

TY  - JOUR
AU  - Hamaker, Zachary
AU  - Morales, Alejandro H.
AU  - Pak, Igor
AU  - Serrano, Luis
AU  - Williams, Nathan
TI  - Bijecting hidden symmetries for skew staircase shapes
JO  - Algebraic Combinatorics
PY  - 2023
SP  - 1095
EP  - 1118
VL  - 6
IS  - 4
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.285/
DO  - 10.5802/alco.285
LA  - en
ID  - ALCO_2023__6_4_1095_0
ER  -

%0 Journal Article
%A Hamaker, Zachary
%A Morales, Alejandro H.
%A Pak, Igor
%A Serrano, Luis
%A Williams, Nathan
%T Bijecting hidden symmetries for skew staircase shapes
%J Algebraic Combinatorics
%D 2023
%P 1095-1118
%V 6
%N 4
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.285/
%R 10.5802/alco.285
%G en
%F ALCO_2023__6_4_1095_0

Hamaker, Zachary; Morales, Alejandro H.; Pak, Igor; Serrano, Luis; Williams, Nathan. Bijecting hidden symmetries for skew staircase shapes. Algebraic Combinatorics, Volume 6 (2023) no. 4, pp. 1095-1118. doi : 10.5802/alco.285. https://alco.centre-mersenne.org/articles/10.5802/alco.285/

References
Cited by

[1] Abney-McPeek, Fiona; An, Serena; Ng, Jakin S. The Stembridge equality for skew stable Grothendieck polynomials and skew dual stable Grothendieck polynomials, Algebr. Comb., Volume 5 (2022) no. 2, pp. 187-208 | MR | Zbl

[2] Aitken, A. C. The monomial expansion of determinantal symmetric functions, Proc. Roy. Soc. Edinburgh Sect. A, Volume 61 (1943), pp. 300-310 | MR | Zbl

[3] Alman, Josh; Vassilevska Williams, Virginia A refined laser method and faster matrix multiplication, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), [Society for Industrial and Applied Mathematics (SIAM)], Philadelphia, PA (2021), pp. 522-539 | DOI

[4] 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

[5] Ardila, Federico; Serrano, Luis G. Staircase skew Schur functions are Schur $P$ -positive, J. Algebraic Combin., Volume 36 (2012) no. 3, pp. 409-423 | DOI | MR | Zbl

[6] Berenstein, A. D.; Zelevinsky, A. V. Triple multiplicities for $sl (r + 1)$ and the spectrum of the exterior algebra of the adjoint representation, J. Algebraic Combin., Volume 1 (1992) no. 1, pp. 7-22 | DOI | MR | Zbl

[7] Billey, Sara C.; Jockusch, William; Stanley, Richard P. Some combinatorial properties of Schubert polynomials, J. Algebraic Combin., Volume 2 (1993) no. 4, pp. 345-374 | DOI | MR | Zbl

[8] Brewster Lewis, Joel; Marberg, Eric Enriched set-valued $P$ -partitions and shifted stable Grothendieck polynomials, Math. Z., Volume 299 (2021) no. 3-4, pp. 1929-1972 | MR | Zbl

[9] Bubley, Russ; Dyer, Martin Faster random generation of linear extensions, Discrete Math., Volume 201 (1999) no. 1-3, pp. 81-88 | DOI | MR | Zbl

[10] Buch, Anders Skovsted; Samuel, Matthew J. $K$ -theory of minuscule varieties, J. Reine Angew. Math., Volume 719 (2016), pp. 133-171 | DOI | MR | Zbl

[11] Bump, Daniel Lie groups, Graduate Texts in Mathematics, 225, Springer, New York, 2013, xiv+551 pages | DOI

[12] Choi, Seung-Il; Kwon, Jae-Hoon Crystals and Schur $P$ -positive expansions, Electron. J. Combin., Volume 25 (2018) no. 3, Paper no. 3.7, 27 pages | MR

[13] Ciocan-Fontanine, Ionuţ; Konvalinka, Matjaž; Pak, Igor The weighted hook length formula, J. Combin. Theory Ser. A, Volume 118 (2011) no. 6, pp. 1703-1717 | DOI | MR | Zbl

[14] Clifford, Edward; Thomas, Hugh; Yong, Alexander $K$ -theoretic Schubert calculus for $OG (n, 2 n + 1)$ and jeu de taquin for shifted increasing tableaux, J. Reine Angew. Math., Volume 690 (2014), pp. 51-63 | DOI | MR | Zbl

[15] DeWitt, Elizabeth Angela Identities Relating Schur s-Functions and Q-Functions, Ph. D. Thesis, University of Michigan (2012), 67 pages https://deepblue.lib.umich.edu/handle/2027.42/93841 | MR

[16] Drube, Paul Set-valued tableaux and generalized Catalan numbers, Australas. J. Combin., Volume 72 (2018), pp. 55-69 | MR | Zbl

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

[18] Feit, W. The degree formula for the skew-representations of the symmetric group, Proc. Amer. Math. Soc., Volume 4 (1953), pp. 740-744 | DOI | MR | Zbl

[19] Fischer, Ilse A bijective proof of the hook-length formula for shifted standard tableaux, 2001 | arXiv

[20] Foley, Angèle M.; King, Ronald C. Determinantal and Pfaffian identities for ninth variation skew Schur functions and $Q$ -functions, European J. Combin., Volume 93 (2021), Paper no. 103271, 31 pages | MR | Zbl

[21] Gaetz, Christian; Mastrianni, Michelle; Patrias, Rebecca; Peck, Hailee; Robichaux, Colleen; Schwein, David; Tam, Ka Yu $K$ -Knuth equivalence for increasing tableaux, Electron. J. Combin., Volume 23 (2016) no. 1, Paper no. 1.40, 37 pages | MR | Zbl

[22] Gessel, Ira M. Multipartite $P$ -partitions and inner products of skew Schur functions, Combinatorics and algebra (Boulder, Colo., 1983) (Contemp. Math.), Volume 34, Amer. Math. Soc., Providence, RI, 1984, pp. 289-317 | DOI | MR | Zbl

[23] Gordenko, Anna Limit shapes of large skew Young tableaux and a modification of the TASEP process, 2020 | arXiv

[24] Grinberg, Darij; Reiner, Victor Hopf Algebras in Combinatorics, 2014 (an expanded version with solutions is available in the ancillary file, 1203 pp) | arXiv

[25] 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

[26] 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

[27] Hamaker, Zachary; Keilthy, Adam; Patrias, Rebecca; Webster, Lillian; Zhang, Yinuo; Zhou, Shuqi Shifted Hecke insertion and the $K$ -theory of $O G (n, 2 n + 1)$ , J. Combin. Theory Ser. A, Volume 151 (2017), pp. 207-240 | DOI | MR

[28] Hamaker, Zachary; Marberg, Eric; Pawlowski, Brendan Involution words II: braid relations and atomic structures, J. Algebraic Combin., Volume 45 (2017) no. 3, pp. 701-743 | DOI | MR | Zbl

[29] Hamaker, Zachary; Marberg, Eric; Pawlowski, Brendan Involution words: counting problems and connections to Schubert calculus for symmetric orbit closures, J. Combin. Theory Ser. A, Volume 160 (2018), pp. 217-260 | DOI | MR | Zbl

[30] Hamaker, Zachary; Marberg, Eric; Pawlowski, Brendan Schur $P$ -positivity and involution Stanley symmetric functions, Int. Math. Res. Not. IMRN (2019) no. 17, pp. 5389-5440 | DOI | MR | Zbl

[31] Hamaker, Zachary; Marberg, Eric; Pawlowski, Brendan Fixed-point-free involutions and Schur $P$ -positivity, J. Comb., Volume 11 (2020) no. 1, pp. 65-110 | MR | Zbl

[32] Hamaker, Zachary; Morales, Alejandro; Pak, Igor; Serrano, Luis; Williams, Nathan Mixed Shifted Insertion, 2021 https://cocalc.com/share/b8a5580510561b4e7f0950cdbab7c6ab1e73eaac/Mixed%20Shifted%20Insertion.sagews?viewer=share Mixed Shifted Insertion.sagews (March 26, 2021), SageMath

[33] Hamaker, Zachary; Patrias, Rebecca; Pechenik, Oliver; Williams, Nathan Doppelgängers: bijections of plane partitions, Int. Math. Res. Not. IMRN (2020) no. 2, pp. 487-540 | DOI | Zbl

[34] Hanlon, Phil; Sundaram, Sheila On a bijection between Littlewood-Richardson fillings of conjugate shape, J. Combin. Theory Ser. A, Volume 60 (1992) no. 1, pp. 1-18 | DOI | MR | Zbl

[35] Hawkes, Graham; Paramonov, Kirill; Schilling, Anne Crystal analysis of type $C$ Stanley symmetric functions, Electron. J. Combin., Volume 24 (2017) no. 3, Paper no. 3.51, 32 pages | MR | Zbl

[36] Hiroshima, Toya $𝔮$ -crystal structure on primed tableaux and on signed unimodal factorizations of reduced words of type $B$ , Publ. Res. Inst. Math. Sci., Volume 55 (2019) no. 2, pp. 369-399 | DOI | MR | Zbl

[37] Ikeda, Takeshi; Naruse, Hiroshi $K$ -theoretic analogues of factorial Schur $P$ - and $Q$ -functions, Adv. Math., Volume 243 (2013), pp. 22-66 | DOI | MR | Zbl

[38] Jerrum, Mark R.; Valiant, Leslie G.; Vazirani, Vijay V. Random generation of combinatorial structures from a uniform distribution, Theoret. Comput. Sci., Volume 43 (1986) no. 2-3, pp. 169-188 | DOI | MR | Zbl

[39] Kerov, S. A $q$ -analog of the hook walk algorithm for random Young tableaux, J. Algebraic Combin., Volume 2 (1993) no. 4, pp. 383-396 | DOI | MR | Zbl

[40] Konvalinka, Matjaž The weighted hook length formula III: Shifted tableaux, Electron. J. Combin., Volume 18 (2011) no. 1, Paper no. 101, 29 pages | MR | Zbl

[41] Krattenthaler, C.; Schlosser, M. J. The major index generating function of standard Young tableaux of shapes of the form “staircase minus rectangle”, Ramanujan 125 (Contemp. Math.), Volume 627, Amer. Math. Soc., Providence, RI, 2014, pp. 111-122 | MR | Zbl

[42] Lai, Tri; Morales, Alejandro; Pak, Igor, 2023 (in preparation)

[43] Linusson, Svante; Potka, Samu; Sulzgruber, Robin On random shifted standard Young tableaux and 132-avoiding sorting networks, Algebr. Comb., Volume 3 (2020) no. 6, pp. 1231-1258 | Numdam | MR | Zbl

[44] Macdonald, I. G. Symmetric functions and Hall polynomials, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1995, x+475 pages (With contributions by A. Zelevinsky, Oxford Science Publications)

[45] Marberg, Eric A symplectic refinement of shifted Hecke insertion, J. Combin. Theory Ser. A, Volume 173 (2020), Paper no. 105216, 50 pages | MR | Zbl

[46] Marberg, Eric; Pawlowski, Brendan $K$ -theory formulas for orthogonal and symplectic orbit closures, Adv. Math., Volume 372 (2020), Paper no. 107299, 43 pages | MR | Zbl

[47] Marberg, Eric; Pawlowski, Brendan On some properties of symplectic Grothendieck polynomials, J. Pure Appl. Algebra, Volume 225 (2021) no. 1, Paper no. 106463, 22 pages | MR | Zbl

[48] Monical, Cara; Pankow, Benjamin; Yong, Alexander Reduced word enumeration, complexity, and randomization, Electron. J. Combin., Volume 29 (2022) no. 2, Paper no. 2.46, 28 pages | MR | Zbl

[49] Morales, Alejandro H.; Pak, Igor; Panova, Greta Hook formulas for skew shapes I. $q$ -analogues and bijections, J. Combin. Theory Ser. A, Volume 154 (2018), pp. 350-405 | DOI | MR | Zbl

[50] Morales, Alejandro H.; Pak, Igor; Panova, Greta Hook formulas for skew shapes III. Multivariate and product formulas, Algebr. Comb., Volume 2 (2019) no. 5, pp. 815-861 | Numdam | MR | Zbl

[51] Morse, Jennifer; Pan, Jianping; Poh, Wencin; Schilling, Anne A crystal on decreasing factorizations in the 0-Hecke monoid, Electron. J. Combin., Volume 27 (2020) no. 2, Paper no. 2.29, 48 pages | MR | Zbl

[52] Nijenhuis, Albert; Wilf, Herbert S. Combinatorial algorithms (Computer Science and Applied Mathematics), 1978, p. xv+302 (For computers and calculators) | Zbl

[53] Pak, Igor; Petrov, Fedor Hidden symmetries of weighted lozenge tilings, Electron. J. Combin., Volume 27 (2020) no. 3, Paper no. 3.44, 19 pages | MR | Zbl

[54] Pak, Igor; Vallejo, Ernesto Combinatorics and geometry of Littlewood-Richardson cones, European J. Combin., Volume 26 (2005) no. 6, pp. 995-1008 | MR | Zbl

[55] Pak, Igor; Vallejo, Ernesto Reductions of Young tableau bijections, SIAM J. Discrete Math., Volume 24 (2010) no. 1, pp. 113-145 | MR | Zbl

[56] Patrias, Rebecca; Pylyavskyy, Pavlo Combinatorics of $K$ -theory via a $K$ -theoretic Poirier-Reutenauer bialgebra, Discrete Math., Volume 339 (2016) no. 3, pp. 1095-1115 | DOI | MR | Zbl

[57] Patrias, Rebecca; Pylyavskyy, Pavlo Dual filtered graphs, Algebr. Comb., Volume 1 (2018) no. 4, pp. 441-500 | Numdam | MR | Zbl

[58] 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

[59] Purbhoo, Kevin A marvellous embedding of the Lagrangian Grassmannian, J. Combin. Theory Ser. A, Volume 155 (2018), pp. 1-26 | DOI | MR | Zbl

[60] Reiner, Victor; Shaw, Kristin M.; van Willigenburg, Stephanie Coincidences among skew Schur functions, Adv. Math., Volume 216 (2007) no. 1, pp. 118-152 | DOI | MR | Zbl

[61] Reiner, Victor; Tenner, Bridget Eileen; Yong, Alexander Poset edge densities, nearly reduced words, and barely set-valued tableaux, J. Combin. Theory Ser. A, Volume 158 (2018), pp. 66-125 | DOI | MR | Zbl

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

[63] 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

[64] Sagan, Bruce E. The symmetric group, Graduate Texts in Mathematics, 203, Springer-Verlag, New York, 2001, xvi+238 pages (Representations, combinatorial algorithms, and symmetric functions) | DOI

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

[66] Schneider, Carsten; Sulzgruber, Robin Asymptotic and exact results on the complexity of the Novelli-Pak-Stoyanovskii algorithm, Electron. J. Combin., Volume 24 (2017) no. 2, Paper no. 2.28, 33 pages | MR | Zbl

[67] Serrano, Luis The shifted plactic monoid, Math. Z., Volume 266 (2010) no. 2, pp. 363-392 | DOI | MR | Zbl

[68] Stanley, Richard P. Enumerative Combinatorics. Vol. 2, Cambridge University Press, 1999 | DOI

[69] Stanley, Richard P. Enumerative Combinatorics. Vol. 1, Cambridge University Press, 2012

[70] Stembridge, J. R. Private Communication, Email to V. Reiner, 2006 (available at https://tinyurl.com/vcjaj845)

[71] 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

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

[73] Sun, Wangru Dimer model, bead and standard Young tableaux: finite cases and limit shapes, 2018 | arXiv

[74] Thomas, Hugh; Yong, Alexander An $S_{3}$ -symmetric Littlewood-Richardson rule, Math. Res. Lett., Volume 15 (2008) no. 5, pp. 1027-1037 | DOI | MR | Zbl

[75] Thomas, Hugh; Yong, Alexander Longest increasing subsequences, Plancherel-type measure and the Hecke insertion algorithm, Adv. in Appl. Math., Volume 46 (2011) no. 1-4, pp. 610-642 | DOI | MR | Zbl

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

[77] Wilson, David Bruce Determinant algorithms for random planar structures, Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans, LA, 1997), ACM, New York (1997), pp. 258-267 | MR | Zbl

[78] Worley, Dale Raymond A theory of shifted Young tableaux, Ph. D. Thesis, Massachusetts Institute of Technology (1984) https://dspace.mit.edu/handle/1721.1/15599 | MR

[79] Yun, Taedong Diagrams of Affine Permutations and Their Labellings, Ph. D. Thesis, Massachusetts Institute of Technology (2013) https://dspace.mit.edu/handle/1721.1/83702 | MR

[80] Zelevinsky, A. V. A generalization of the Littlewood-Richardson rule and the Robinson-Schensted-Knuth correspondence, J. Algebra, Volume 69 (1981) no. 1, pp. 82-94 | DOI | MR | Zbl

Cited by Sources: