A bijective proof of Macdonald’s reduced word formula
Algebraic Combinatorics, Volume 2 (2019) no. 2, p. 217-248
We give a bijective proof of Macdonald’s reduced word identity using pipe dreams and Little’s bumping algorithm. This proof extends to a principal specialization due to Fomin and Stanley. Such a proof has been sought for over 20 years. Our bijective tools also allow us to solve a problem posed by Fomin and Kirillov from 1997 using work of Wachs, Lenart, Serrano and Stump. These results extend earlier work by the third author on a Markov process for reduced words of the longest permutation.
Received : 2017-08-30
Accepted : 2018-05-29
Published online : 2019-03-05
DOI : https://doi.org/10.5802/alco.23
@article{ALCO_2019__2_2_217_0,
     author = {Billey, Sara C. and Holroyd, Alexander E. and Young, Benjamin J.},
     title = {A bijective proof of Macdonald's reduced word formula},
     journal = {Algebraic Combinatorics},
     publisher = {MathOA foundation},
     volume = {2},
     number = {2},
     year = {2019},
     pages = {217-248},
     doi = {10.5802/alco.23},
     language = {en},
     url = {https://alco.centre-mersenne.org/item/ALCO_2019__2_2_217_0}
}
A bijective proof of Macdonald’s reduced word formula. Algebraic Combinatorics, Volume 2 (2019) no. 2, pp. 217-248. doi : 10.5802/alco.23. https://alco.centre-mersenne.org/item/ALCO_2019__2_2_217_0/

[1] Bergeron, Nantel; Billey, Sara C. RC-graphs and Schubert polynomials, Exp. Math., Volume 2 (1993) no. 4, pp. 257-269 | Article | MR 1281474 | Zbl 0803.05054

[2] Billey, Sara C.; Hamaker, Zachary; Roberts, Austin; Young, Benjamin Coxeter-Knuth graphs and a signed Little map for type B reduced words, Electron. J. Comb., Volume 21 (2014) no. 4, P4.6, 39 pages | MR 3284055 | Zbl 1298.05006

[3] Billey, Sara C.; Jockusch, William; Stanley, Richard P. Some Combinatorial Properties of Schubert Polynomials, J. Algebr. Comb., Volume 2 (1993) no. 4, pp. 345-374 | MR 1241505 | Zbl 0790.05093

[4] Bressoud, David M. Proofs and Confirmations: The Story of the Alternating-Sign Matrix Conjecture, Cambridge University Press, Spectrum Series (1999), xv+274 pages | Zbl 0944.05001

[5] Carlitz, Leonard A combinatorial property of q-Eulerian numbers, Am. Math. Mon., Volume 82 (1975), pp. 51-54 | Article | MR 0366683 | Zbl 0296.05007

[6] Chevalley, Claude Sur les décompositions cellulaires des espaces G/B, Algebraic Groups and their generalizations: Classical methods (University Park, PA, 1991), American Mathematical Society (Proceedings of Symposia in Pure Mathematics) Volume 56, Part 1 (1994), pp. 1-23 | Zbl 0824.14042

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

[8] Foata, Dominique On the Netto inversion number of a sequence, Proc. Am. Math. Soc., Volume 19 (1968), pp. 236-240 | Article | MR 223256 | Zbl 0157.03403

[9] Fomin, Sergey; Kirillov, Anatol N. Grothendieck polynomials and the Yang-Baxter equation, Proceedings of the Sixth Conference in Formal Power Series and Algebraic Combinatorics, American Mathematical Society (Series in Discrete Mathematics and Theoretical Computer Science) (1994), pp. 183-190

[10] Fomin, Sergey; Kirillov, Anatol N. Yang-Baxter Equation, Symmetric Functions, and Schubert Polynomials, Discrete Math., Volume 153 (1996) no. 1-3, pp. 123-143 | Article | MR 1394950 | Zbl 0852.05078

[11] Fomin, Sergey; Kirillov, Anatol N. Reduced words and plane partitions, J. Algebr. Comb., Volume 6 (1997) no. 4, pp. 311-319 | MR 1471891 | Zbl 0882.05010

[12] Fomin, Sergey; Stanley, Richard P. Schubert Polynomials and the NilCoxeter Algebra, Adv. Math., Volume 103 (1994) no. 2, pp. 196-207 | Zbl 0809.05091

[13] Garsia, Adriano The Saga of Reduced Factorizations of Elements of the Symmetric Group, Laboratoire de combinatoire et d’informatique mathématique, Publications du Laboratoire de Combinatoire et d’Informatique Mathématique, Volume 29 (2002)

[14] Gessel, Ira M.; Viennot, Xavier Determinants, paths, and plane partitions (1989) (manuscript)

[15] Gupta, Hansraj A new look at the permutations of the first n natural numbers, Indian J. Pure Appl. Math., Volume 9 (1978) no. 6, pp. 600-631 | MR 495467 | Zbl 0386.05005

[16] Haglund, James; Loehr, Nicholas; Remmel, Jeffrey B. Statistics on wreath products, perfect matchings, and signed words, Eur. J. Comb., Volume 26 (2005) no. 6, pp. 835-868 | Article | MR 2143200 | Zbl 1063.05009

[17] Hamaker, Zachary; Marberg, Eric; Pawlowski, Brendan Transition formulas for involution Schubert polynomials (2016) (https://arxiv.org/abs/1609.09625 )

[18] Hamaker, Zachary; Young, Benjamin Relating Edelman-Greene insertion to the Little map, J. Algebr. Comb., Volume 40 (2014) no. 3, pp. 693-710 | MR 3265229 | Zbl 1309.05007

[19] Kasteleyn, Pieter W. The statistics of dimers on a lattice: I. The number of dimer arrangements on a quadratic lattice, Physica, Volume 27 (1961) no. 12, pp. 1209-1225 | Article | Zbl 1244.82014

[20] Knutson, Allen Schubert polynomials and symmetric functions; notes for the Lisbon combinatorics summer school 2012 (2012) (http://www.math.cornell.edu/~allenk/schubnotes.pdf )

[21] Knutson, Allen; Miller, Ezra Gröbner geometry of Schubert polynomials, Ann. Math., Volume 161 (2005) no. 3, pp. 1245-1318 | Article | Zbl 1089.14007

[22] Kogan, Mikhail Schubert geometry of Flag Varieties and Gelfand-Cetlin theory, Massachusetts Institute of Technology (2000) (Ph. D. Thesis) | MR 2716977

[23] Koike, Kazuhiko; Terada, Itaru Young-diagrammatic methods for the representation theory of the classical groups of type B n ,C n ,D n , J. Algebra, Volume 107 (1987) no. 2, pp. 466-511 | Zbl 0622.20033

[24] Lam, Thomas; Lapointe, Luc; Morse, Jennifer; Schilling, Anne; Shimozono, Mark; Zabrocki, Mike k-Schur Functions and Affine Schubert Calculus, The Fields Institute for Research in the Mathematical Sciences, Fields Institute Monographs, Volume 33 (2014) | MR 3379711 | Zbl 1360.14004

[25] Lam, Thomas; Shimozono, Mark A Little bijection for affine Stanley symmetric functions, Sémin. Lothar. Comb., Volume 54A (2005), B54Ai, 12 pages | MR 2264936 | Zbl 1178.05009

[26] Lascoux, Alain Transition on Grothendieck polynomials, Proceedings of the Nagoya 2000 International Workshop, World Scientific (Physics and Combinatorics) (2000), pp. 164-179

[27] Lascoux, Alain; Schützenberger, Marcel-Paul Polynômes de Schubert, C. R. Acad. Sci., Paris, Sér. I, Volume 294 (1982), pp. 447-450 | Zbl 0495.14031

[28] Lascoux, Alain; Schützenberger, Marcel-Paul Symmetry and flag manifolds, Invariant theory (Montecatini, 1982), Springer (Lecture Notes in Mathematics) Volume 996 (1983), pp. 118-144 | Article | MR 718129 | Zbl 0542.14031

[29] Lascoux, Alain; Schützenberger, Marcel-Paul Schubert Polynomials and the Littlewood-Richardson Rule, Lett. Math. Phys., Volume 10 (1985), pp. 111-124 | Article | MR 815233 | Zbl 0586.20007

[30] Lenart, Cristian A unified approach to combinatorial formulas for Schubert polynomials, J. Algebr. Comb., Volume 20 (2004) no. 3, pp. 263-299 | MR 2106961 | Zbl 1056.05146

[31] Little, David P. Combinatorial aspects of the Lascoux-Schützenberger tree, Adv. Math., Volume 174 (2003) no. 2, pp. 236-253 | MR 1963694 | Zbl 1018.05102

[32] Little, David P. Factorization of the Robinson–Schensted–Knuth correspondence, J. Comb. Theory, Ser. A, Volume 110 (2005) no. 1, pp. 147-168 | Article | MR 2128971 | Zbl 1059.05106

[33] Macdonald, Ian G. Notes on Schubert Polynomials, Université du Québec, Publications du Laboratoire de combinatoire et d’informatique mathématique, Volume 6 (1991) | MR 1161461

[34] Manivel, Laurent Symmetric Functions, Schubert Polynomials and Degeneracy Loci, American Mathematical Society, SMF/AMS Texts and Monographs, Volume 6 (2001) | MR 1852463 | Zbl 0998.14023

[35] Monks Gillespie, Maria A combinatorial approach to the q,t-symmetry relation in Macdonald polynomials, Electron. J. Comb., Volume 23 (2016) no. 2, P2.38, 64 pages | MR 3512660 | Zbl 1337.05109

[36] Novick, Mordechai A bijective proof of a major index theorem of Garsia and Gessel, Electron. J. Comb., Volume 17 (2010) no. 1, 64, 12 pages | MR 2644850 | Zbl 1189.05010

[37] Postnikov, Alexander; Stanley, Richard P. Chains in the Bruhat order, J. Algebr. Comb., Volume 29 (2009) no. 2, pp. 133-174 | MR 2475632 | Zbl 1238.14036

[38] Proctor, Robert A. Odd symplectic groups, Invent. Math., Volume 92 (1988) no. 2, pp. 307-332 | MR 936084 | Zbl 0621.22009

[39] Proctor, Robert A. New symmetric plane partition identities from invariant theory work of De Concini and Procesi, Eur. J. Comb., Volume 11 (1990) no. 3, pp. 289-300 | Article | MR 1059559 | Zbl 0726.05008

[40] Reiner, Victor; Tenner, Bridget Eileen; Yong, Alexander Poset edge densities, nearly reduced words, and barely set-valued tableaux (2016) (https://arxiv.org/abs/1603.09589 )

[41] Serrano, Luis; Stump, Christian Generalized triangulations, pipe dreams, and simplicial spheres, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), The Association. Discrete Mathematics & Theoretical Computer Science (DMTCS) (Discrete Mathematics and Theoretical Computer Science) (2011), pp. 885-896 | Zbl 1355.05078

[42] Serrano, Luis; Stump, Christian Maximal fillings of moon polyominoes, simplicial complexes, and Schubert polynomials, Electron. J. Comb., Volume 19 (2012) no. 1, P16, 18 pages | MR 2880647 | Zbl 1244.05239

[43] Skandera, Mark An Eulerian partner for inversions, Sémin. Lothar. Comb., Volume 46 (2001), B46d, 19 pages | MR 1848722 | Zbl 0982.05006

[44] Stanley, Richard P. On the Number of Reduced Decompositions of Elements of Coxeter Groups, Eur. J. Comb., Volume 5 (1984), pp. 359-372 | Article | MR 782057 | Zbl 0587.20002

[45] Stanley, Richard P. Permutations (2009) (http://www-math.mit.edu/~rstan/papers/perms.pdf )

[46] Stembridge, John R. A weighted enumeration of maximal chains in the Bruhat order, J. Algebr. Comb., Volume 15 (2002) no. 3, pp. 291-301 | MR 1900629 | Zbl 1008.20037

[47] Wachs, Michelle L. Flagged Schur functions, Schubert polynomials, and symmetrizing operators, J. Comb. Theory, Ser. A, Volume 40 (1985) no. 2, pp. 276-289 | Article | MR 814415 | Zbl 0579.05001

[48] Weigandt, Anna; Yong, Alexander The prism tableau model for Schubert polynomials, J. Comb. Theory, Ser. A, Volume 154 (2018), pp. 551-582 | Article | MR 3718077 | Zbl 1373.05219

[49] Young, Benjamin A Markov growth process for Macdonald’s distribution on reduced words (2014) (https://arxiv.org/abs/1409.7714 )