Abstract
We establish the existence of an involution on tabloids that is analogous to Schützenberger’s evacuation map on standard Young tableaux. We find that the number of its fixed points is given by evaluating a certain Green’s polynomial at \(q = -1\), and satisfies a “domino-like” recurrence relation.
Similar content being viewed by others
Notes
The operation of promotion was originally defined by Schützenberger [34] as an action on the linear extensions of an arbitrary finite poset. It is often seen in the context of standard Young tableaux (e.g., in [27, §2.8], where the map is called \(\partial \)), in which case the poset in question is the diagram of the underlying partition (or, more generally, skew shape), viewed as a subset of \({{\mathbb {N}}}\times {{\mathbb {N}}}\) with the product order.
In our setting, the promotion map on tabloids of shape \(\lambda \) is also a special case of the poset-theoretic notion, but for the poset which is a disjoint union of chains of length \(\lambda _1, \lambda _2, \ldots \), rather than the diagram of \(\lambda \). In particular, if a tabloid \({\widetilde{T}}\) is associated to a tableau T, then the promotion of \({\widetilde{T}}\) is typically not associated to the promotion of T (or, indeed, to any standard Young tableau of shape \(\lambda \)). On the other hand, if we associate a tabloid with a skew standard Young tableau, as mentioned in Sect. 2.2.2, then the promotion as a tabloid agrees with the promotion as a skew tableau.
Each of the descriptions of evacuation given in Sect. 2.1.3 generalizes to the semistandard setting. In particular, \(e_d\) can be computed without recourse to RSK by rotating U 180\(^{\circ }\), replacing each entry i with \(d+1-i\), and using jeu de taquin to rectify the resulting skew tableau.
This follows from the identity \(e_d \circ s_i = s_{d-i} \circ e_d\), which is proved in, e.g., [39, Prop. 2.87(iii)].
There are several ways to compute charge: in addition to the original references mentioned above, see [26, §III.6] and [39, §5.4]. The latter reference gives an algorithm for cocharge that applies even when the content \(\mu \) is not a partition. (For \(T \in \mathrm{{SSYT}}(\lambda , \mu )\), the cocharge of T is equal to \(\sum _{i < j} \min (\mu _i, \mu _j) - c(T)\).)
In the case of semistandard tableaux of shape \(\lambda \), with entries at most d, the fixed points of usual evacuation (\(e_d\)) are given by substituting the alternating sequence \((1, -1, 1, -1, 1, -1, \ldots , \pm 1)\) into the Schur polynomial \(s_\lambda (x_1, \ldots , x_d)\) [45, Thm. 3.1]. When d is even and \(\lambda \) is a rectangle, the fixed points of the other conjugacy class of reflections are given by substituting the almost alternating sequence \(\pm (1, 1, -1, 1, -1, 1, \ldots , \pm 1)\) into the same polynomial [31, Thm. 7.6].
The role of \(\mu \) in the definition of \(\mathrm{{RC}}(\lambda ,\mu )\) (and in the algorithm for \(\Phi \)) is in the computation of the vacancy numbers \(P_r^{(1)}(\nu )\), and only the lengths of the columns of \(\mu \) are relevant to this computation. Thus, permuting rows of \(\mu \) does not affect these definitions.
The standardization of a semistandard tableau T of content \(\langle \mu _1, \ldots , \mu _d \rangle \) is the standard tableau obtained by replacing the 1’s in T with \(1, \ldots , \mu _1\), from left to right; the 2’s in T with \(\mu _1 + 1, \ldots , \mu _1 + \mu _2\), from left to right; etc.
References
Assaf, S.H.: Dual equivalence graphs I: a new paradigm for Schur positivity. Forum Math. Sigma 3, e12 (2015)
Barbasch, D., Vogan, D.: Primitive ideals and orbital integrals in complex classical groups. Math. Ann. 259(2), 153–199 (1982)
Björner, A., Brenti, F.: Combinatorics of Coxeter Groups. Graduate Texts in Mathematics, vol. 231. Springer, New York (2005)
Chmutov, M., Lewis, J.B., Pylyavskyy, P.: Monodromy in Kazhdan–Lusztig cells in affine type A. arXiv:1706.00471v2 (2017)
Chmutov, M., Pylyavskyy, P., Yudovina, E.: Matrix-ball construction of affine Robinson–Schensted correspondence. Sel. Math. (N. S.) 24, 667–750 (2018)
Désarménien, J., Leclerc, B., Thibon, J.-Y.: Hall–Littlewood functions and Kostka–Foulkes polynomials in representation theory. Sém. Lothar. Combin. 32, 38 (1994)
Eriksson, H., Eriksson, K.: Affine Weyl groups as infinite permutations. Electron. J. Combin. 5, R18 (1998)
Frame, J.S., Robinson, G.D.B., Thrall, R.M.: The hook graphs of the symmetric groups. Can. J. Math. 6, 316–324 (1954)
Fulton, W.: Young Tableaux. Cambridge University Press, Cambridge (1997)
Garfinkle, D.: On the classification of primitive ideals for complex classical Lie algebras. I. Compos. Math. 75(2), 135–169 (1990)
Garfinkle, D.: On the classification of primitive ideals for complex classical Lie algebra. II. Compos. Math. 81(3), 307–336 (1992)
Garfinkle, D.: On the classification of primitive ideals for complex classical Lie algebras. III. Compos. Math. 88(2), 187–234 (1993)
Greene, C.: Some partitions associated with a partially ordered set. J. Comb. Theory Ser. A 20, 69–79 (1976)
Greene, C., Kleitman, D.J.: The structure of Sperner \(k\)-families. J. Comb. Theory Ser. A 20, 41–68 (1976)
Green, J.A.: The characters of the finite general linear groups. Trans. Am. Math. Soc. 80, 402–447 (1955)
Kim, D.: On total Springer representations for classical types. Selecta Math. (N. S.) 24(5), 4141–4196 (2018)
Kim, D.: On the affine Schützenberger involution. Math. Res. Lett. 27(3), 809–834 (2020)
Kirillov, A.N., Reshetikhin, N.Y.: The Bethe ansatz and the combinatorics of Young tableaux. Zap. Nauchn. Sem. (LOMI) 155, 65–115 (1986). English translation: J. Sov. Math. 41(2), 925–955 (1988)
Kirillov, A.N., Berenstein, A.D.: Groups generated by involutions, Gel’fand–Tsetlin patterns, and combinatorics of Young tableaux. Algebra i Analiz 7(1), 92–152 (1995). English translation: St. Petersburg Math. J. 7(1), 77–127 (1996)
Kirillov, A.N., Schilling, A., Shimozono, M.: A bijection between Littlewood–Richardson tableaux and rigged configurations. Selecta Math. (N. S.) 8(1), 67–135 (2002)
Krattenthaler, C.: Bijective proofs of the hook formulas for the number of standard Young tableaux, ordinary and shifted. Electron. J. Comb. 2, R13 (1995)
Lascoux, A., Leclerc, B., Thibon, J.-Y.: Crystal graphs and \(q\)-analogues of weight multiplicities for the root system \(A_n\). Lett. Math. Phys. 35(4), 359–374 (1995)
Lascoux, A., Schützenberger, M.-P.: Sur une conjecture de H. O. Foulkes. C. R. Acad. Sci. Paris Sér. A-B 286(7), A323–A324 (1978)
Lascoux, A., Schützenberger, M.-P.: Le monoïde plaxique. In: Noncommutative Structures in Algebra and Geometric Combinatorics (Naples, 1978). Quad. “Ricerca Sci.”, vol. 109, pp. 129–156. CNR, Rome (1981)
Lusztig, G.: Some examples of square integrable representations of semisimple \(p\)-adic groups. Trans. Am. Math. Soc. 277(2), 623–653 (1983)
Macdonald, I.G.: Symmetric Functions and Hall Polynomials. Oxford Mathematical Monographs, 2nd edn. The Clarendon Press, New York (1995)
Manivel, L.: Symmetric functions, Schubert polynomials and degeneracy loci, volume 6 of SMF/AMS Texts and Monographs. American Mathematical Society, Providence, RI; Société Mathématique de France, Paris: Translated from the 1998 French original by John R, p. 3. Swallow, Cours Spécialisés (2001)
Nakayashiki, A., Yamada, Y.: Kostka polynomials and energy functions in solvable lattice models. Selecta Math. (N. S.) 3(4), 547–599 (1997)
Pak, I.: Periodic permutations and the Robinson–Schensted correspondence. http://www.math.ucla.edu/~pak/papers/inf2.pdf (2003). Accessed 29 May 2022
Reiner, V., Stanton, D., White, D.: The cyclic sieving phenomenon. J. Comb. Theory Ser. A 108(1), 17–50 (2004)
Rhoades, B.: Cyclic sieving, promotion, and representation theory. J. Comb. Theory Ser. A 117(1), 38–76 (2010)
Sagan, B.E.: The Symmetric Group. Graduate Texts in Mathematics, vol. 203, 2nd edn. Springer, New York (2001)
Schilling, A., Warnaar, S.O.: Inhomogeneous lattice paths, generalized Kostka polynomials and \(A_{n-1}\) supernomials. Commun. Math. Phys. 202(2), 359–401 (1999)
Schützenberger, M.-P.: Promotion des morphismes d’ensembles ordonnes. Discrete Math. 2(1), 73–94 (1972)
Schützenberger, M.-P.: Propriétés nouvelles des tableaux de Young. In: Séminaire Delange-Pisot-Poitou, 19e année: 1977/78, Exposé No. 26. Secrétariat Math., Paris (1978)
Shi, J.Y.: The generalized Robinson–Schensted algorithm on the affine Weyl group of type \(\widetilde{A}_{n-1}\). J. Algebra 139(2), 364–394 (1991)
Shimozono, M.: A cyclage poset structure for Littlewood–Richardson tableaux. Eur. J. Comb. 22(3), 365–393 (2001)
Shimozono, M.: Multi-atoms and monotonicity of generalized Kostka polynomials. Eur. J. Comb. 22(3), 395–414 (2001)
Shimozono, M.: Crystals for dummies. https://www.aimath.org/WWN/kostka/crysdumb.pdf (2005). Accessed 29 May 2022
Stanley, R.P.: Enumerative combinatorics, vol. 2. Volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin
Stanley, R.P.: Promotion and evacuation. Electron. J. Comb. 16(2), R9 (2009)
Stanley, R.P.: Enumerative Combinatorics. Volume 49 of Cambridge Studies in Advanced Mathematics, vol. 1, 2nd edn. Cambridge University Press, Cambridge (2012)
Stanton, D.W., White, D.E.: A Schensted algorithm for rim hook tableaux. J. Comb. Theory Ser. A 40(2), 211–247 (1985)
Stembridge, J.R.: Some hidden relations involving the ten symmetry classes of plane partitions. J. Comb. Theory Ser. A 68(2), 372–409 (1994)
Stembridge, J.R.: Canonical bases and self-evacuating tableaux. Duke Math. J. 82(3), 585–606 (1996)
Stembridge, J.R.: More \(W\)-graphs and cells: molecular components and cell synthesis. In: Notes from the AIM workshop, Palo Alto. The Atlas of Lie Groups (2008)
van Leeuwen, M.A.A.: The Robinson–Schensted and Schützenberger algorithms, an elementary approach. Electron. J. Comb. 3(2), R15 (1996)
van Leeuwen, M.A.A.: The Littlewood-Richardson rule, and related combinatorics. In: Interaction of Combinatorics and Representation Theory. MSJ Mem., vol. 11, pp. 95–145. Mathematical Society of Japan, Tokyo (2001)
Acknowledgements
The authors are grateful to Kevin Dilks, for initially suggesting the idea of generalizing evacuation in this context; to Sam Hopkins and Thomas McConville, who informed us of our parallel work on related questions; to Brendon Rhoades, for helpful conversations about Kostka–Foulkes polynomials; to Pavlo Pylyavskyy, for numerous conversations; to Vic Reiner, for many fruitful questions and suggestions; and to an anonymous referee, for numerous comments, suggestions, and corrections. MC was supported in part by NSF grant DMS-1503119; GF was supported in part by NSF grants DMS-1464693 and DMS-0943832; JBL was supported in part by NSF grant DMS-1401792.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendix A: More on rigged configurations
Appendix A: More on rigged configurations
In this appendix, we describe the forward direction of the bijection \(\Phi : \mathrm{SSYT}(\lambda ,\mu ) \rightarrow \mathrm{RC}(\lambda ,\mu )\) for the reader’s convenience, and we explain how Theorem 4.11 follows from results of Kirillov, Schilling, and Shimozono [20].
1.1 A.1. The rigged configuration bijection
Recall that a rigged configuration is a pair \((\nu , J)\), where \(\nu = (\nu ^{(1)}, \nu ^{(2)}, \ldots )\) is sequence of partitions, and J is an assignment of a non-negative integer rigging to each row of each partition, such that the rigging attached to a row of length r in \(\nu ^{(k)}\) is at most the vacancy number \(P_r^{(k)}(\nu )\). Say that a row of the partition \(\nu ^{(k)}\) is a singular string if its rigging is equal to the corresponding vacancy number; by convention, every partition has a singular string of length 0.
Definition–Proposition A.1
(Kirillov–Reshetikhin [18]) The bijection \(\Phi : \mathrm{SSYT}(\lambda ,\mu ) \rightarrow \mathrm{RC}(\lambda ,\mu )\) of Theorem 4.11 is computed recursively as follows. The empty tableau maps to the empty rigged configuration. Given a non-empty tableau T, let d be the maximum entry of T, and let U be the tableau obtained from T by removing the right-most box in T that contains d. Assume that \(\Phi (U) = (\nu , J)\) has been computed; we explain how to construct \(\Phi (T) = (\nu ', J')\). Suppose the box removed from T is in row r. Set \(m_r = \infty \) and define a sequence
by taking \(m_j\) to be the biggest number less than or equal to \(m_{j+1}\) such that \(\nu ^{(j)}\) contains a singular string of length \(m_j\). The configuration \(\nu '\) is obtained from \((\nu , J)\) by adding one box to a singular string of length \(m_j\) in \(\nu ^{(j)}\) for each \(j \le r-1\). For each of these \(r-1\) changed rows, the rigging is chosen so that the row is a singular string with respect to the vacancy numbers of \(\nu '\). The riggings of all other rows are unchanged.
An algorithm for the other direction is given in [18, § 3].
Example A.2
Figure 3 shows one step of the algorithm for \(\Phi \). To obtain the rigged configuration in Example 4.10 corresponding to the tableau in Example 4.12, one performs two more steps of the algorithm. The first of these steps adds a box to the fourth row of \(\mu \), which causes the vacancy numbers of \(\nu ^{(1)}\) to increase from 1 to 2.
In Sect. 4.3.2, we required that \(\mu \) be a partition. In fact, for any strict composition \(\mu = \langle \mu _1, \ldots , \mu _d \rangle \), the algorithm in Definition-Proposition A.1 gives a bijection \(\Phi _\mu : \mathrm{{SSYT}}(\lambda , \mu ) \rightarrow \mathrm{{RC}}(\lambda , \mathrm{{sort}}(\mu ))\), where \(\mathrm{{sort}}(\mu )\) is the partition obtained by sorting the parts of \(\mu \).Footnote 7 The existence of these bijections implies that for a permutation \(w \in \mathfrak {S}_d\), the composition \(\Phi _{w \mu }^{-1} \circ \Phi _\mu \) defines a shape-preserving, content-permuting action of the symmetric group on semistandard tableaux. It is asserted in [20] that this action agrees with the action introduced in Sect. 3.4; we supply the omitted proof.
Lemma A.3
For \(T \in \mathrm{{SSYT}}(\lambda ,\mu )\) and \(w \in \mathfrak {S}_d\),
where w(T) denotes the action of Definition–Proposition 3.22.
Proof
It suffices to consider the generators \(s_i\). By [20, Def.-Prop. 8.1 and Lem. 8.5], the maps \(\Psi _i := \Phi _{s_i \mu }^{-1} \circ \Phi _\mu \) are characterized by the properties that \(\Psi _i\) does not change entries greater than \(i+1\), and \(\Psi _{d-1} \circ e_d = e_d \circ \Psi _1\), where \(e_d\) is the evacuation map on semistandard tableaux with entries at most d. The maps \(s_i\) of Definition-Proposition 3.22 satisfy the first property by definition, and the second property by, e.g., [39, Prop. 2.87(iii)]. \(\square \)
1.2 A.2. Relation with work of Kirillov–Schilling–Shimozono
The rigged configurations discussed in Sect. 4.3.2 are a special case of a more general theory of rigged configurations developed by Kirillov, Schilling, and Shimozono in [20]. In this section we introduce the more general setup and notation of that paper, state several of their main theorems, and explain how these theorems imply Theorem 4.11.
Let \(\mathcal {R} = (\mathcal {R}_1, \ldots , \mathcal {R}_d)\) be a sequence of rectangular partitions, and \(\lambda \) an arbitrary partition. In [20], the authors define a set \(\mathrm{{CLR}}(\lambda ; \mathcal {R})\) of Littlewood–Richardson tableaux. The elements of \(\mathrm{{CLR}}(\lambda ; \mathcal {R})\) are a subset of the standard tableaux of shape \(\lambda \), and the cardinality of \(\mathrm{{CLR}}(\lambda ; \mathcal {R})\) is equal to the multiplicity of the Schur function \(s_{\lambda }\) in the product \(s_{\mathcal {R}_1} \cdots s_{\mathcal {R}_d}\). In particular, when \(\mathcal {R} = \mathcal {R}(\mu ) := (\langle \mu _1 \rangle , \ldots , \langle \mu _d \rangle )\) is a sequence of one-row partitions, the cardinality of \(\mathrm{{CLR}}(\lambda ; \mathcal {R}(\mu ))\) is the Kostka number \(K_{\lambda \mu }\), and \(\mathrm{{CLR}}(\lambda ; \mathcal {R}(\mu ))\) consists of the standardizationsFootnote 8 of the elements of \(\mathrm{{SSYT}}(\lambda , \mu )\). Let \({\text {std}}\) denote the standardization map \(\mathrm{{SSYT}}(\lambda , \mu ) \rightarrow \mathrm{{CLR}}(\lambda ; \mathcal {R}(\mu ))\).
We recall several properties of Littlewood–Richardson tableaux. First, evacuation of standard tableaux restricts to a bijection \(e: \mathrm{{CLR}}(\lambda ; \mathcal {R}) \rightarrow \mathrm{{CLR}}(\lambda ; w_0(\mathcal {R}))\), where \(w_0(\mathcal {R}) = (\mathcal {R}_d, \ldots , \mathcal {R}_1)\) [20, paragraph after Lem. 3.8]. Let \(\eta ^t\) denote the transpose (or conjugate) of the partition \(\eta \), and let \(\mathcal {R}^t = (\mathcal {R}_1^t, \ldots , \mathcal {R}_d^t)\). There is a bijection \(\mathrm{{tr_{LR}}}: \mathrm{{CLR}}(\lambda ; \mathcal {R}) \rightarrow \mathrm{{CLR}}(\lambda ^t; \mathcal {R}^t)\) [20, Def. 2.7], and a generalized charge statistic \(c_\mathcal {R} : \mathrm{{CLR}}(\lambda ; \mathcal {R}) \rightarrow \mathbb {Z}_{\ge 0}\) defined in [33, 37]. By [38, Prop. 26 and Thm. 28] or [33, Lem. 6.5], one has
for \(T \in \mathrm{{CLR}}(\lambda ; \mathcal {R})\), where \(n(\mathcal {R}) = \sum _{i < j} |\mathcal {R}_i \cap \mathcal {R}_j|\) and \(\mathcal {R}_1 \cap \mathcal {R}_2\) denotes intersection of Young diagrams. When \(\mathcal {R} = \mathcal {R}(\mu )\), \(\mathrm{{tr_{LR}}}\) is simply the reflection of a standard tableau over the main diagonal, and
where c is the usual charge statistic on semistandard tableaux.Footnote 9 Note also that \(n(\mathcal {R}(\mu )) = b(\mathrm{{sort}}(\mu )) = \sum (i-1)(\mathrm{{sort}}(\mu ))_i\).
Kirillov, Schilling, and Shimozono also define a notion of rigged configuration of type \((\lambda ; \mathcal {R})\); they denote the set of these by \(\mathrm{{RC}}(\lambda ; \mathcal {R})\). A rigged configuration of type \((\lambda ; \mathcal {R}(\mu ))\) is the same as a rigged configuration of type \((\lambda , \mathrm{{sort}}(\mu ))\), as defined in Sect. 4.3.2. The involution \(\Theta \) and the statistic cc naturally generalize to rigged configurations of type \((\lambda ; \mathcal {R})\). In [20, §4.1], the authors define a bijection
Comparing the algorithm of Definition–Proposition A.1 with the description of \(\overline{\phi }_\mathcal {R}\) in [20, §4.2], one sees that
The definition of a rigged configuration of type \((\lambda ; \mathcal {R})\) does not depend on the ordering of the rectangles in \(\mathcal {R}\), so we identify the sets \(\mathrm{{RC}}(\lambda ; \mathcal {R})\) and \(\mathrm{{RC}}(\lambda ; w_0(\mathcal {R}))\). Also set \(\widetilde{\phi }_\mathcal {R} = \Theta \circ \overline{\phi }_\mathcal {R}\).
Theorem A.4
([20, Thm. 5.6, 9.1]) For \(T \in \mathrm{{CLR}}(\lambda ; \mathcal {R})\), one has
-
(1)
\(\Theta (\overline{\phi }_\mathcal {R}(T)) = \overline{\phi }_{w_0(\mathcal {R})}(e(T))\) and
-
(2)
\(cc (\widetilde{\phi }_\mathcal {R}(T)) = c_\mathcal {R}(T)\).
Proof of Theorem 4.11
Suppose \(T \in \mathrm{{SSYT}}(\lambda ,\mu )\). Recall that \(e^* = w_0 \circ e\). By Lemma A.3,
By Theorem A.4(1) and the fact that evacuation commutes with both standardization and transposition of standard tableaux, we have
Thus, \(\Phi _\mu (e^*(T)) = \Theta (\Phi _\mu (T))\), proving part (1).
For part (2), use Theorem A.4(2) and (A.1), (A.2) to obtain
\(\square \)