Geodesic
Arrays and the combinatorics of Young tableaux
Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 60 (2005) no. 2, pp. 269-334
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The classical theory of Young tableaux is presented in the rather new and non-traditional language of arrays. With the usual operations (or algorithms) of insertion and jeu de taquin as a starting point, more elementary operations on arrays are introduced. The set of arrays equipped with these operations forms an object which can be referred to as a bicrystal. This formalism is presented in the first part of the paper, and its exposition is based on the theorem that the vertical and horizontal operators commute. In the second part the apparatus of arrays is used to present some topics in the theory of Young tableaux, namely, the plactic monoid, Littlewood–Richardson rule, Robinson–Schensted–Knuth correspondence, dual tableaux, plane partitions, and so on. 
@article{RM_2005_60_2_a1,
     author = {V. I. Danilov and G. A. Koshevoy},
     title = {Arrays and the combinatorics of {Young} tableaux},
     journal = {Trudy Matematicheskogo Instituta imeni V.A. Steklova},
     pages = {269--334},
     year = {2005},
     volume = {60},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/RM_2005_60_2_a1/}
}
TY  - JOUR
AU  - V. I. Danilov
AU  - G. A. Koshevoy
TI  - Arrays and the combinatorics of Young tableaux
JO  - Trudy Matematicheskogo Instituta imeni V.A. Steklova
PY  - 2005
SP  - 269
EP  - 334
VL  - 60
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/RM_2005_60_2_a1/
LA  - en
ID  - RM_2005_60_2_a1
ER  - 
%0 Journal Article
%A V. I. Danilov
%A G. A. Koshevoy
%T Arrays and the combinatorics of Young tableaux
%J Trudy Matematicheskogo Instituta imeni V.A. Steklova
%D 2005
%P 269-334
%V 60
%N 2
%U http://geodesic.mathdoc.fr/item/RM_2005_60_2_a1/
%G en
%F RM_2005_60_2_a1
V. I. Danilov; G. A. Koshevoy. Arrays and the combinatorics of Young tableaux. Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 60 (2005) no. 2, pp. 269-334. http://geodesic.mathdoc.fr/item/RM_2005_60_2_a1/

[1] M. Aigner, Kombinatornaya teoriya, Mir, M., 1982 | MR

[2] S. Ariki, “Robinson–Schensted correspondence and left cells”, Adv. Stud. Pure Math., 28 (2000), 1–20 ; arXiv: math.QA/9910117 | MR | Zbl

[3] E. A. Bender, D. E. Knuth, “Enumeration of plane partitions”, J. Combin. Theory Ser. A, 13 (1972), 40–54 | DOI | MR | Zbl

[4] G. Benkart, F. Sottile, J. Stroomer, “Tableau switching: algorithms and applications”, J. Combin. Theory Ser. A, 76:1 (1996), 11–43 | DOI | MR | Zbl

[5] A. D. Berenstein, A. V. Zelevinsky, “Triple multiplicities for $\operatorname{sl}(r+1)$ and the spectrum of the exterior algebra of the adjoint representation”, J. Algebraic Combin., 1:1 (1992), 7–22 | DOI | MR | Zbl

[6] A. Berenstein, A. Zelevinsky, “Tensor product multiplicities, canonical bases and totally positive varieties”, Invent. Math., 143:1 (2001), 77–128 | DOI | MR | Zbl

[7] T. Britz, S. Fomin, “Finite posets and Ferrers shapes”, Adv. Math., 158:1 (2001), 86–127 | DOI | MR | Zbl

[8] A. S. Buch (with an appendix by W. Fulton), “The saturation conjecture (after A. Knutson and T. Tao)”, Enseign. Math. (2), 46:1–2 (2000), 43–60 | MR | Zbl

[9] V. Danilov, A. Karzanov, G. Koshevoy, Discrete strip-concave functions, Gefand–Tsetlin patterns, and related polyhedra, arXiv: math.CO/0404298 | MR

[10] V. I. Danilov, G. A. Koshevoi, “Nilpotentnye operatory i diskretno vognutye funktsii”, Izv. RAN. Ser. matem., 67:1 (2003), 3–20 | MR | Zbl

[11] V. I. Danilov, G. A. Koshevoi, “Diskretnaya vypuklost i ermitovy matritsy”, Tr. MIAN, 241, 2003, 68–89 | MR | Zbl

[12] V. Danilov, G. Koshevoy, Bicrystals and crystal $GL(V),GL(W)$-duality, Preprint RIMS-1485, Kyoto University, Kyoto, 2004 | MR

[13] V. Danilov, G. Koshevoy, “Discrete convexity and unimodularity. I”, Adv. Math., 189:2 (2004), 301–324 | DOI | MR | Zbl

[14] V. Danilov, G. Koshevoy, A simple proof of associativity and commutativity of LR-coefficients (or the hive ring), arXiv: math.CO/0409447 | MR

[15] M. Date, M. Jimbo, T. Miwa, “Representations of $U_q(\frak{gl}(n,C))$ at $q=0$ and the Robinson–Schensted correspondence”, Physics and Mathematics of Strings, eds. L. Brink, D. Friedman, A. M. Polyakov, Word Scientific, Teaneck, NJ, 1990, 185–211 | MR

[16] J. A. De Loera, T. B. McAllister, “Vertices of Gelfand–Tsetlin polytopes”, Discrete Comput. Geom., 32:4 (2004), 459–470 ; arXiv: math.CO/0309329 | DOI | MR | Zbl

[17] P. Deift, “Integrable systems and combitatorial theory”, Notices Amer. Math. Soc., 47:6 (2000), 631–640 | MR | Zbl

[18] S. V. Fomin, “Konechnye chastichno uporyadochennye mnozhestva i diagrammy Yunga”, Dokl. AN SSSR, 243:5 (1978), 1144–1147 | MR | Zbl

[19] S. Fomin, “Knuth equivalence, Jeu de taquin, and the Littlewood–Richardson rule. Appendix 1”, R. P. Stanley. Enumerative Combinatorics, vol. 2, Cambridge Univ. Press, Cambridge, 1999

[20] S. Fomin, A. Zelevinsky, “The Laurent phenomenon”, Adv. in Appl. Math., 28:2 (2002), 119–144 | DOI | MR | Zbl

[21] W. Fulton, Young Tableaux, London Math. Soc. Stud. Texts, 35, Cambridge Univ. Press, Cambridge, 1997 | MR | Zbl

[22] W. Fulton, “Eigenvalues, invariant factors, highest weights, and Schubert calculus”, Bull. Amer. Math. Soc. (N.S.), 37:3 (2000), 209–249 | DOI | MR | Zbl

[23] W. Fulton, J. Harris, Representation Theory. A first course, Springer-Verlag, New York, 1991 | MR

[24] O. Gleizer, A. Postnikov, “Littlewood–Richardson coefficients via Yang–Baxter equation”, Internat. Math. Res. Notices, 14 (2000), 741–774 ; arXiv: math.QA/9909124 | DOI | MR | Zbl

[25] C. Greene, “An extension of Schensted's theorem”, Adv. Math., 14 (1974), 254–265 | DOI | MR | Zbl

[26] F. Griffits, Dzh. Kharris, Printsipy algebraicheskoi geometrii, t. 1, 2, Mir, M., 1982 | MR

[27] M. Haiman, “Dual equivalence with applications, including a conjecture of Proctor”, Discrete Math., 99:1–3 (1992), 79–113 | DOI | MR | Zbl

[28] A. Henriques, J. Kamnitzer, The octahedron recurrence and $gl(n)$ cristals, arXiv: math.CO/0408114 | MR

[29] G. Dzheims, Teoriya predstavlenii simmetricheskikh grupp, Mir, M., 1982 | MR

[30] M. Kashiwara, “On crystal bases”, CMS Conf. Proc., 16 (1995), 155–197 | MR | Zbl

[31] M. Kashiwara, Bases Cristallines des Groupes Quantiques, Cours Spéc., 9, Société Math. France, Paris, 2002 | MR | Zbl

[32] A. N. Kirillov, “Introduction to tropical combinatorics”, Physics and Combinatorics, Proceedings of the Nagoya 2000 2nd International Workshop, eds. A. N. Kirillov, N. Liskova, World Scientific, Singapore, 2001, 82–150 | MR | Zbl

[33] A. N. Kirillov, A. D. Berenstein, “Groups generated by involutions, Gelfand–Tsetlin patterns, and combinatorics of Young tableaux”, Algebra i analiz, 7:1 (1995), 92–152 | MR | Zbl

[34] D. E. Knuth, “Permutations, matrices, and generalized Young tableaux”, Pacific J. Math., 34 (1970), 709–727 | MR | Zbl

[35] A. Knutson, T. Tao, “The honeycomb model of $\operatorname{GL}_n(\mathbb C)$ tensor products. I: Proof of the saturation conjecture”, J. Amer. Math. Soc., 12:4 (1999), 1055–1090 | DOI | MR | Zbl

[36] A. Knutson, T. Tao, C. Woodward, “A positive proof of the Littlewood–Richardson rule using the octahedron recurrence”, Electron. J. Combin., 11, Research Paper 61 (2004) ; arXiv: math.CO/0306274 | MR | Zbl

[37] A. Lascoux, “Double crystal graphs”, Studies in Memory of Issai Schur, Progr. Math., 210, eds. A. Joseph et al., Birkhäuser, Boston, 2003, 95–114 | MR | Zbl

[38] A. Lascoux, B. Leclerc, J.-Y. Thibon, “The plactic monoid”, Algebraic Combinatorics on Words, Encyclopedia Math. Appl., 90, Cambridge Univ. Press, Cambridge, 2002, 164–196 | MR

[39] A. Lascoux, M. P. Schützenberger, “Le monoïde plaxique”, Non-commutative Structures in Algebra and Geometric Combinatorics (Naples, 1978), Quad. Ric. Sci., 109, CNR, Rome, 1981, 129–156 | MR

[40] I. Makdonald, Simmetricheskie funktsii i mnogochleny Kholla, Mir, M., 1985 | MR

[41] Yu. I. Manin, Dokazuemoe i nedokazuemoe, Sov. radio, M., 1979

[42] A. Marshall, I. Olkin, Neravenstva: teoriya mazhorizatsii i ee prilozheniya, Mir, M., 1983 | MR | Zbl

[43] A. Yu. Okunkov, A. M. Vershik, “Novyi podkhod k teorii predstavlenii simmetricheskikh grupp. 2”, Zapiski nauchn. seminarov POMI, 307 (2004), 57–98 | MR

[44] I. Pak, E. Vallejo, Reductions of Young tableau bijections, arXiv: math.CO/0408171

[45] B. E. Sagan, The Symmetric Group, Wadsworth Brooks/Cole, Pacific Grove, CA, 1991 | MR | Zbl

[46] C. Schensted, “Longest increasing and descreasing subsequences”, Canad. J. Math., 13 (1961), 179–191 | MR | Zbl

[47] M. P. Schützenberger, “Promotion des morphismes d'ensembles ordonnés”, Discrete Math., 2 (1972), 73–94 | DOI | MR | Zbl

[48] R. P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge Univ. Press, Cambridge, 1999, with a foreword by G.-C. Rota and Appendix 1 by S. Fomin | MR | Zbl

[49] R. Steinberg, “An occurrence of the Robinson–Schensted correspondence”, J. Algebra, 113:2 (1988), 523–528 | DOI | MR | Zbl

[50] J. R. Stembridge, “Rational tableaux and the tensor algebra of $\operatorname{gl}_n$”, J. Combin. Theory Ser. A, 46:1 (1987), 79–120 | DOI | MR | Zbl

[51] M. A. A. van Leeuwen, “The Littlewood–Richardson rule, and related combinatorics”, MSJ Mem., 11 (2001), 95–145 ; arXiv: math.CO/9908099 | MR | Zbl

[52] M. A. A. van Leeuwen, “The Robinson–Schensted and Schützenberger algorithms, an elementary approach”, Electronic J. Combin., 3:2, Research Paper 15 (1996) | MR

[53] A. V. Zelevinskii, “Obobschennye koeffitsienty Littlvuda–Richardsona, kanonicheskie bazisy i polnaya polozhitelnost”, Globus. Obschematematicheskii seminar, vyp. 1, ed. V. V. Prasolov, M. A. Tsfasman, MTsNMO, M., 2004, 147–160