Abstract
In his study of Kazhdan–Lusztig cells in affine type A, Shi has introduced an affine analog of Robinson–Schensted correspondence. We generalize the Matrix-Ball Construction of Viennot and Fulton to give a more combinatorial realization of Shi’s algorithm. As a byproduct, we also give a way to realize the affine correspondence via the usual Robinson–Schensted bumping algorithm. Next, inspired by Lusztig and Xi, we extend the algorithm to a bijection between the extended affine symmetric group and collection of triples \((P, Q, \rho )\) where P and Q are tabloids and \(\rho \) is a dominant weight. The weights \(\rho \) get a natural interpretation in terms of the Affine Matrix-Ball Construction. Finally, we prove that fibers of the inverse map possess a Weyl group symmetry, explaining the dominance condition on weights.
Similar content being viewed by others
References
Ariki, S.: Robinson–Schensted correspondence and left cells. arXiv:math/9910117 (1999)
Barbasch, D., Vogan, D.: Primitive ideals and orbital integrals in complex classical groups. Math. Ann. 259, 153–199 (1982)
Bergman, G.M.: The diamond lemma for ring theory. Adv. Math. 29(2), 178–218 (1978)
Britz, T., Fomin, S.: Finite posets and Ferrers shapes. Adv. Math. 158(1), 86–127 (2001)
Chmutov, M.: Affine Matrix-Ball Construction Java program. https://sites.google.com/site/affiners/ (2015)
Fulton, W.: Young tableaux: with applications to representation theory and geometry, Volume 35 of London Mathematical Society Student Texts. Cambridge University Press (1997)
Garsia, A.M., McLarnan, T.J.: Relations between Young’s natural and the Kazhdan–Lusztig representations of \(S_n\). Adv. Math. 69(1), 32–92 (1988)
Greene, C., Kleitman, D.J.: The structure of Sperner \(k\)-families. J. Comb. Theory Ser. A 20(1), 41–68 (1976)
Honeywill, T.: Combinatorics and Algorithms Associated with the Theory of Kazhdan–Lusztig Cells. PhD thesis, University of Warwick (2005)
Kazhdan, D., Lusztig, G.: Representations of Coxeter groups and Hecke algebras. Invent. Math. 53, 165–184 (1989)
Lusztig, G.: Cells in affine Weyl groups, IV. J. Fac. Sci. Univ. Tokyo Sect. IA Math. 36(2), 297–328 (1989)
Pak, I.: Periodic permutations and the Robinson–Schensted correspondence. http://www.math.ucla.edu/pak/papers/inf2.pdf (2003)
Shi, J. Y.: Kazhdan–Lusztig cells of certain affine Weyl groups. Volume 1179 of Lecture Notes in Mathematics. Springer (1986)
Shi, J.Y.: The generalized Robinson–Schensted algorithm on the affine Weyl group of type \(A_{n-1}\). J. Algebra 139(2), 364–394 (1991)
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
Viennot, G.: Une forme géométrique de la correspondance de Robinson–Schensted. Combinatoire et représentation du groupe symétrique 29–58 (1977)
Xi, N.: The Based Ring of Two-Sided Cells of Affine Weyl Groups of Type \(A_{n-1}\). Volume 749 of Memoirs of the American Mathematical Society. American Mathematical Society (2002)
Acknowledgements
The authors are grateful to Joel Lewis and an anonymous referee for reading the paper and providing valuable feedback, and to Darij Grinberg for helpful comments.
Author information
Authors and Affiliations
Corresponding author
Additional information
In memory of V. A. Yasinskiy.
MC was partially supported by NSF Grants DMS-1148634 and DMS-1503119; PP was partially supported by NSF Grants DMS-1148634, DMS-1351590, and Sloan Fellowship.
Rights and permissions
About this article
Cite this article
Chmutov, M., Pylyavskyy, P. & Yudovina, E. Matrix-Ball Construction of affine Robinson–Schensted correspondence. Sel. Math. New Ser. 24, 667–750 (2018). https://doi.org/10.1007/s00029-018-0402-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00029-018-0402-6