JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 20, No 3 (2004)

Cristian Lenart

Schubert polynomials were introduced in the context of the geometry of flag varieties. This paper investigates some of the connections not yet understood between several combinatorial structures for the construction of Schubert polynomials; we also present simplifications in some of the existing approaches to this area. We designate certain line diagrams for permutations known as rc-graphs as the main structure. The other structures in the literature we study include: semistandard Young tableaux, Kohnert diagrams, and balanced labelings of the diagram of a permutation. The main tools in our investigation are certain operations on rc-graphs, which correspond to the coplactic operations on tableaux, and thus define a crystal graph structure on rc-graphs; a new definition of these operations is presented. One application of these operations is a straightforward, purely combinatorial proof of a recent formula (due to Buch, Kresch, Tamvakis, and Yong), which expresses Schubert polynomials in terms of products of Schur polynomials. In spite of the fact that it refers to many objects and results related to them, the paper is mostly self-contained.

1. N. Bergeron, “A combinatorial construction of Schubert polynomials,” J. Combin. Theory Ser. A 60 (1992), 168-182. LENART
2. N. Bergeron and S. Billey, “RC-graphs and Schubert polynomials,” Experimental Math. 2 (1993), 257-269.
3. N. Bergeron and F. Sottile, “Skew Schubert functions and the Pieri formula for flag manifolds,” Trans. Amer. Math. Soc. 354 (2002), 651-673.
4. I.N. Bernstein, I.M. Gelfand, and S.I. Gelfand, “Schubert cells and cohomology of the spaces G/P. Russian Math. Surveys 28 (1973), 1-26.
5. S. Billey. Private communication, April 2001.
6. S.C. Billey, W. Jockusch, and R.P. Stanley, “Some combinatorial properties of Schubert polynomials,” J. Alg. Combin. 2 (1993), 345-374.
7. A. Buch, A. Kresch, H. Tamvakis, and A. Yong, “Schubert Polynomials and quiver formulas,” Duke Math. J. 122 (2004), 125-143.
8. P. Edelman and C. Greene, “Balanced tableaux” Adv. Math. 63 (1987), 42-99.
9. S. Fomin and C. Greene, “Noncommutative Schur functions and their applications,” Discrete Math. 193 1998), 179-200.
10. S. Fomin, C. Greene, V. Reiner, and M. Shimozono, “Balanced labellings and Schubert polynomials,” European J. Combin. 18 (1997), 373-389.
11. S. Fomin and A.N. Kirillov, “The Yang-Baxter equation, symmetric functions, and Schubert polynomials,” Discrete Math. 153 (1996), 123-143.
12. S. Fomin and R.P. Stanley, “Schubert polynomials and the nilCoxeter algebra” Adv. Math. 103 (1994), 196- 207.
13. W. Fulton. Young Tableaux, volume 35 of London Math. Soc. Student Texts. Cambridge Univ. Press, Cambridge and New York, 1997.
14. A. Joseph, A. Melnikov, and R. Rentschler (Eds.), “Studies in Memory of Issai Schur, chapter Double crystal graphs (by A. Lascoux)” Progress in Mathematics. Birkh\ddot auser, Boston, MA, 2002.
15. A. Knutson and E. Miller, “Gr\ddot obner Geometry of Schubert Polynomials,” Ann. of Math. (2), to appear.
16. M. Kogan, “Generalization of Schensted insertion algorithm to the cases of hooks and semi-shuffles,” J. Combin. Theory Ser. A 102 (2003), 110-135.
17. M. Kogan and A. Kumar, “A proof of Pieri's formula using generalized Schensted insertion algorithm for rc-graphs,” Proc. Amer. Math. Soc. 130 (2002), 2525-2534.
18. A. Kohnert, “Weintrauben, Polynome, Tableaux,” Bayreuther Mathematische Schriften 38 (1991), 1-97.
19. B. Kostant and S. Kumar, “The nil Hecke ring and cohomology of G/P,” Adv. Math. 62 (1986), 187-237.
20. V. Lakshmibai and C.S. Seshadri, “Standard monomial theory,” In Proceedings of the Hyderabad Conference on Algebraic Groups (Hyderabad, 1989) pages 279-322, Madras,
1991. Manoj Prakashan.
21. A. Lascoux, “Le mono\ddot ıde plaxique,” Quad. de la Ricerca Scientifica 109 (1981), 129-156.
22. A. Lascoux and M.-P. Sch\ddot utzenberger, “Polyn\hat omes de Schubert,” C. R. Acad. Sci. Paris Sér. I Math. 294 (1982), 393-396.
23. A. Lascoux and M.-P. Sch\ddot utzenberger, “Structure de Hopf de l'anneau de cohomologie et de l'anneau de Grothendieck d'une variété de drapeaux,” C. R. Acad. Sci. Paris Sér. I Math. 295 (1982), 629-633. .
24. A. Lascoux and M.-P. Sch\ddot utzenberger, “Fonctorialité des polyn\hat omes de Schubert,” In R. Fossum, W. Haboush, M. Hochster, and V. Lakshmibai (eds.), Invariant Theory (Denton, TX, 1986), volume 88 of Contemp. Math. pp. 585-598. Amer. Math. Soc., Providence, RI, 1989.
25. A. Lascoux and M.-P. Sch\ddot utzenberger, “Tableaux and noncommutative Schubert polynomials,” Funct. Anal. Appl. 23 (1989), 63-64.
26. A. Lascoux and M.-P. Sch\ddot utzenberger, “Keys and standard bases,” in D. Stanton (ed.), Invariant Theory and Tableaux, vol. 19 of The IMA Vol. in Math. and Its Appl., Berlin-Heidelberg-New York, 1990, pp. 125-144. Springer-Verlag.
27. C. Lenart and F. Sottile, “Skew Schubert polynomials,” Proc. Amer. Math. Soc. 131 (2003), 3319-3328.
28. P. Littelmann, “A Littlewood-Richardson rule for symmetrizable Kac-Moody algebras,” Invent. Math. 116 (1994), 329-346.
29. P. Littelmann, “Paths and root operators in representation theory,” Ann. of Math. 142(2) (1995), 499-525.
30. M. Lothaire, Algebraic Combinatorics on Words, chapter The plactic monoid (by A. Lascoux, B. Leclerc, and J.-Y. Thibon), Cambridge University Press, Cambridge, 2002, pp. 144-172.
31. I.G. Macdonald, “Notes on Schubert Polynomials,” Laboratoire de combinatoire et d'informatique mathématique (LACIM), Université du Québec `a Montréal, Montréal, 1991.
32. L. Manivel, “Symmetric functions, Schubert polynomials and degeneracy loci,” SMF/AMS Texts and Mono- graphs,
6. Cours Spécialisés. American Mathematical Society, Providence, RI; Société Mathématique de France, Paris,
2001. Translated from the 1998 French original by John R. Swallow.
33. E. Miller, “Mitosis recursion for coefficients of Schubert polynomials,” J. Combin. Theory Ser. A 103 (2003), 223-235.
34. V. Reiner and M. Shimozono, “Key polynomials and a flagged Littlewood-Richardson rule,” J. Combin Theory Ser. A 70 (1995), 107-143.
35. V. Reiner and M. Shimozono, “Plactification,” J. Algebraic Combin. 4 (1995), 331-351.
36. R. Winkel, “Diagram rules for the generation of Schubert polynomials,” J. Combin Theory Ser. A 86 (1999), 14-48.
37. R. Winkel, “A derivation of Kohnert's algorithm from Monk's rule,” Sem. Loth. Comb. B48f, 2003.