A uniform bijection between nonnesting and noncrossing partitions
HTML articles powered by AMS MathViewer
- by Drew Armstrong, Christian Stump and Hugh Thomas PDF
- Trans. Amer. Math. Soc. 365 (2013), 4121-4151 Request permission
Abstract:
In 2007, D.I. Panyushev defined a remarkable map on the set of nonnesting partitions (antichains in the root poset of a finite Weyl group). In this paper we use Panyushev’s map, together with the well-known Kreweras complement, to construct a bijection between nonnesting and noncrossing partitions. Our map is defined uniformly for all root systems, using a recursion in which the map is assumed to be defined already for all parabolic subsystems. Unfortunately, the proof that our map is well defined, and is a bijection, is case-by-case, using a computer in the exceptional types. Fortunately, the proof involves new and interesting combinatorics in the classical types. As consequences, we prove several conjectural properties of the Panyushev map, and we prove two cyclic sieving phenomena conjectured by D. Bessis and V. Reiner.References
- Drew Armstrong, Generalized noncrossing partitions and combinatorics of Coxeter groups, Mem. Amer. Math. Soc. 202 (2009), no. 949, x+159. MR 2561274, DOI 10.1090/S0065-9266-09-00565-1
- Christos A. Athanasiadis, Generalized Catalan numbers, Weyl groups and arrangements of hyperplanes, Bull. London Math. Soc. 36 (2004), no. 3, 294–302. MR 2038717, DOI 10.1112/S0024609303002856
- Christos A. Athanasiadis and Victor Reiner, Noncrossing partitions for the group $D_n$, SIAM J. Discrete Math. 18 (2004), no. 2, 397–417. MR 2112514, DOI 10.1137/S0895480103432192
- Yuri Berest, Pavel Etingof, and Victor Ginzburg, Finite-dimensional representations of rational Cherednik algebras, Int. Math. Res. Not. 19 (2003), 1053–1088. MR 1961261, DOI 10.1155/S1073792803210205
- Olivier Bernardi, Bijective counting of tree-rooted maps and shuffles of parenthesis systems, Electron. J. Combin. 14 (2007), no. 1, Research Paper 9, 36. MR 2285813
- David Bessis and Victor Reiner, Cyclic sieving of noncrossing partitions for complex reflection groups, Ann. Comb. 15 (2011), no. 2, 197–222. MR 2813511, DOI 10.1007/s00026-011-0090-9
- A. E. Brouwer and A. Schrijver, On the period of an operator, defined on antichains, Mathematisch Centrum, Afdeling Zuivere Wiskunde ZW 24/74, Mathematisch Centrum, Amsterdam, 1974. MR 0349497
- Paola Cellini and Paolo Papi, Ad-nilpotent ideals of a Borel subalgebra. II, J. Algebra 258 (2002), no. 1, 112–121. Special issue in celebration of Claudio Procesi’s 60th birthday. MR 1958899, DOI 10.1016/S0021-8693(02)00532-X
- William Y. C. Chen, Eva Y. P. Deng, Rosena R. X. Du, Richard P. Stanley, and Catherine H. Yan, Crossings and nestings of matchings and partitions, Trans. Amer. Math. Soc. 359 (2007), no. 4, 1555–1575. MR 2272140, DOI 10.1090/S0002-9947-06-04210-3
- P. Duchet, Sur les hypergraphes invariantes, Discrete Math. 8 (1974), 269–280 (French). MR 340029, DOI 10.1016/0012-365X(74)90139-3
- Sen-Peng Eu and Tung-Shan Fu, The cyclic sieving phenomenon for faces of generalized cluster complexes, Adv. in Appl. Math. 40 (2008), no. 3, 350–376. MR 2402175, DOI 10.1016/j.aam.2007.01.005
- A. Fink and B.I. Giraldo, A bijection between noncrossing and nonnesting partitions for classical reflection groups, Proceedings of the 21st International Conference on Formal Power Series and Algebraic Combinatorics, DMTCS (2009), 399–412.
- J. Fürlinger and J. Hofbauer, $q$-Catalan numbers, J. Combin. Theory Ser. A 40 (1985), no. 2, 248–264. MR 814413, DOI 10.1016/0097-3165(85)90089-5
- Mark D. Haiman, Conjectures on the quotient ring by diagonal invariants, J. Algebraic Combin. 3 (1994), no. 1, 17–76. MR 1256101, DOI 10.1023/A:1022450120589
- C.E. Heitsch, Combinatorics on plane trees, motivated by RNA secondary structure configurations, preprint.
- —, Kreweras complementation and orbits in Catalan lattices, preprint.
- C. Krattenthaler, Non-crossing partitions on an annulus, in preparation.
- C. Krattenthaler and T.W. Müller, Cyclic sieving for generalised non-crossing partitions associated to complex reflection groups of exceptional type, preprint, available at arXiv:1001.0028 (2010).
- G. Kreweras, Sur les partitions non croisées d’un cycle, Discrete Math. 1 (1972), no. 4, 333–350 (French). MR 309747, DOI 10.1016/0012-365X(72)90041-6
- Dmitri I. Panyushev, On orbits of antichains of positive roots, European J. Combin. 30 (2009), no. 2, 586–594. MR 2489252, DOI 10.1016/j.ejc.2008.03.009
- Victor Reiner, Non-crossing partitions for classical reflection groups, Discrete Math. 177 (1997), no. 1-3, 195–222. MR 1483446, DOI 10.1016/S0012-365X(96)00365-2
- V. Reiner, D. Stanton, and D. White, The cyclic sieving phenomenon, J. Combin. Theory Ser. A 108 (2004), no. 1, 17–50. MR 2087303, DOI 10.1016/j.jcta.2004.04.009
- Martin Rubey and Christian Stump, Crossings and nestings in set partitions of classical types, Electron. J. Combin. 17 (2010), no. 1, Research Paper 120, 19. MR 2729369
- D. Rush and X.L. Shi, On orbits of order ideals of minuscule posets, preprint, available at arXiv:1108.5245 (2011).
- W.A. Stein et al., Sage Mathematics Software (Version 4.6), The Sage Development Team, 2011, http://www.sagemath.org.
- J. Striker and N. Williams, Promotion and rowmotion, preprint, available at arXiv:1108.1172 (2011).
Additional Information
- Drew Armstrong
- Affiliation: Department of Mathematics, University of Miami, Coral Gables, Florida 33146
- Email: armstrong@math.umiami.edu
- Christian Stump
- Affiliation: LaCIM, Université du Québec à Montréal, Montréal, Québec, Canada
- Address at time of publication: Institut für Algebra, Zahlentheorie und Diskrete Mathematik, Universität Hannover, Germany
- MR Author ID: 904921
- ORCID: 0000-0002-9271-8436
- Email: christian.stump@univie.ac.at
- Hugh Thomas
- Affiliation: Department of Mathematics and Statistics, University of New Brunswick, Fredericton, New Brunswick, E3B 5A3, Canada
- MR Author ID: 649257
- ORCID: 0000-0003-1177-9972
- Email: hthomas@unb.ca
- Received by editor(s): March 9, 2011
- Received by editor(s) in revised form: October 7, 2011
- Published electronically: March 28, 2013
- Additional Notes: During the time that he worked on this paper, the first author was supported by NSF Postdoctoral Fellowship DMS-0603567 and NSF grant DMS-1001825
The second author was supported by a CRM-ISM postdoctoral fellowship. He would like to thank the Fields Institute for its hospitality during the time he was working on this paper
The third author was supported by an NSERC Discovery Grant. He would like to thank the Norges teknisk-naturvitenskapelige universitet and the Fields Institute for their hospitality during the time he was working on this paper - © Copyright 2013 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 365 (2013), 4121-4151
- MSC (2010): Primary 05A05; Secondary 20F55
- DOI: https://doi.org/10.1090/S0002-9947-2013-05729-7
- MathSciNet review: 3055691