A bijective proof of Macdonald’s reduced word formula
Algebraic Combinatorics, Tome 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.

Reçu le :
Accepté le :
Publié le :
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{\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 = {http://www.numdam.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
DA  - 2019///
SP  - 217
EP  - 248
VL  - 2
IS  - 2
PB  - MathOA foundation
UR  - http://www.numdam.org/articles/10.5802/alco.23/
UR  - https://zbmath.org/?q=an%3A1409.05024
UR  - https://www.ams.org/mathscinet-getitem?mr=3934829
UR  - https://doi.org/10.5802/alco.23
DO  - 10.5802/alco.23
LA  - en
ID  - ALCO_2019__2_2_217_0
ER  - 
Billey, Sara C.; Holroyd, Alexander E.; Young, Benjamin J. A bijective proof of Macdonald’s reduced word formula. Algebraic Combinatorics, Tome 2 (2019) no. 2, pp. 217-248. doi : 10.5802/alco.23. http://www.numdam.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 | 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 | Article | MR 1241505 | Zbl 0790.05093

[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 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) (Proceedings of Symposia in Pure Mathematics), Volume 56, Part 1, American Mathematical Society, 1994, pp. 1-23 | Zbl 0824.14042

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

[8] Foata, Dominique On the Netto inversion number of a sequence, Proc. Am. Math. Soc., Volume 19 (1968), pp. 236-240 | Article | 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 (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 | 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 | Article | Zbl 0809.05091

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

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

[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 (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 | Article

[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 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 (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 0495.14031

[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 | 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 | Article | 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, Publications du Laboratoire de combinatoire et d’informatique mathématique, 6, Université du Québec, 1991 | MR 1161461

[34] Manivel, Laurent Symmetric Functions, Schubert Polynomials and Degeneracy Loci, SMF/AMS Texts and Monographs, 6, American Mathematical Society, 2001 | 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 | Article | Zbl 1238.14036

[38] Proctor, Robert A. Odd symplectic groups, Invent. Math., Volume 92 (1988) no. 2, pp. 307-332 | Article | 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

[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 1391.05269

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

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

Cité par Sources :