Browse issues
no. 2
A bijective proof of Macdonald’s reduced word formula
Billey, Sara C.1; Holroyd, Alexander E.2; Young, Benjamin J.3
1 Department of Mathematics, University of Washington, Box 354350, Seattle, WA 98195, USA
2 Microsoft Research, 1 Microsoft Way, Redmond, WA 98052, USA
3 Department of Mathematics, 1222 University of Oregon, Eugene, OR 97403, USA
Algebraic Combinatorics, Volume 2 (2019) no. 2, pp. 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:
Accepted:
Published online:
DOI: 10.5802/alco.23

Billey, Sara C. 1; Holroyd, Alexander E. 2; Young, Benjamin J. 3

1 Department of Mathematics, University of Washington, Box 354350, Seattle, WA 98195, USA
2 Microsoft Research, 1 Microsoft Way, Redmond, WA 98052, USA
3 Department of Mathematics, 1222 University of Oregon, Eugene, OR 97403, USA
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@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{\textquoteright}s} reduced word formula},
     journal = {Algebraic Combinatorics},
     pages = {217--248},
     publisher = {MathOA foundation},
     volume = {2},
     number = {2},
     year = {2019},
     doi = {10.5802/alco.23},
     zbl = {1409.05024},
     mrnumber = {3934829},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.23/}
}
TY  - JOUR
AU  - Billey, Sara C.
AU  - Holroyd, Alexander E.
AU  - Young, Benjamin J.
TI  - A bijective proof of Macdonald’s reduced word formula
JO  - Algebraic Combinatorics
PY  - 2019
SP  - 217
EP  - 248
VL  - 2
IS  - 2
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.23/
DO  - 10.5802/alco.23
LA  - en
ID  - ALCO_2019__2_2_217_0
ER  - 
%0 Journal Article
%A Billey, Sara C.
%A Holroyd, Alexander E.
%A Young, Benjamin J.
%T A bijective proof of Macdonald’s reduced word formula
%J Algebraic Combinatorics
%D 2019
%P 217-248
%V 2
%N 2
%I MathOA foundation
%U https://alco.centre-mersenne.org/articles/10.5802/alco.23/
%R 10.5802/alco.23
%G en
%F ALCO_2019__2_2_217_0
Billey, Sara C.; Holroyd, Alexander E.; Young, Benjamin J. 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/articles/10.5802/alco.23/

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

[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, Paper no. P4.6, 39 pages | MR | Zbl

[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 | DOI | MR | Zbl

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

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

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

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

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

[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 (Series in Discrete Mathematics and Theoretical Computer Science) (1994), pp. 183-190 | Zbl

[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 | DOI | MR | Zbl

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

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

[13] Garsia, Adriano The Saga of Reduced Factorizations of Elements of the Symmetric Group, Publications du Laboratoire de Combinatoire et d’Informatique Mathématique, 29, Laboratoire de combinatoire et d’informatique mathématique, 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 | Zbl

[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 | DOI | MR | Zbl

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

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

[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 | DOI | Zbl

[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 | DOI | Zbl

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

[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 | DOI | Zbl

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

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

[26] Lascoux, Alain Transition on Grothendieck polynomials, Proceedings of the Nagoya 2000 International Workshop (Physics and Combinatorics), World Scientific, 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

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

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

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

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

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

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

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

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

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

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

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

[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 | DOI | MR | Zbl

[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) | Zbl

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

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

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

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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

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

Cited by Sources: