Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



A uniform bijection between nonnesting and noncrossing partitions

Authors: Drew Armstrong, Christian Stump and Hugh Thomas
Journal: Trans. Amer. Math. Soc. 365 (2013), 4121-4151
MSC (2010): Primary 05A05; Secondary 20F55
Published electronically: March 28, 2013
MathSciNet review: 3055691
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. D. Armstrong, Generalized noncrossing partitions and combinatorics of Coxeter groups, Mem. Amer. Math. Soc. 202 (2006), no. 949. MR 2561274 (2011c:05001)
  • 2. C.A. Athanasiadis, Generalized Catalan numbers, Weyl groups and arrangements of hyperplanes, Bull. London Math. Soc. 36 (2004), 294-302. MR 2038717 (2005b:52055)
  • 3. C.A. Athanasiadis and V. Reiner, Noncrossing partitions for the group $ D_n$, SIAM J. Discrete Math. 18 (2004), 397-417. MR 2112514 (2006b:06004)
  • 4. Y. Berest, P. Etingof, and V. Ginzburg, Finite dimensional representations of rational Cherednik algebras, Int. Math. Res. Not. 19 (2003), 1053-1088. MR 1961261 (2004h:16027)
  • 5. O. Bernardi, Bijective counting of tree-rooted maps and shuffles of parenthesis systems, Electron. J. Combin. 14 (2007), no. 1, R9. MR 2285813 (2007m:05125)
  • 6. D. Bessis and V. Reiner, Cyclic sieving of noncrossing partitions for complex reflection groups, Ann. Comb. 15 (2011), 197-222. MR 2813511
  • 7. A. E. Brouwer and A. Schrijver, On the period of an operator, defined on antichains, Mathematisch Centrum, Amsterdam, 1974. MR 0349497 (50:1990)
  • 8. P. Cellini and P. Papi, $ \operatorname {ad}$-nilpotent ideals of a Borel subalgebra II, J. Algebra 258 (2002), 112-121. MR 1958899 (2004e:17006)
  • 9. W.Y.C. Chen, E.Y.P. Deng, R.R.X. Du, R.P. Stanley, and C.H. Yan, Crossings and nestings of matchings and partitions, Trans. Amer. Math. Soc. 359 (2007), no. 4, 1555-1575. MR 2272140 (2007i:05015)
  • 10. P. Duchet, Sur les hypergraphes invariantes, Discrete Math. 8 (1974), 269-280. MR 0340029 (49:4786)
  • 11. S.-P. Eu and T.-S. Fu, The cyclic sieving phenomenon for faces of generalized cluster complexes, Adv. in Appl. Math. 40 (2008), no. 3, 350-376. MR 2402175 (2009f:05268)
  • 12. 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.
  • 13. J. Fürlinger and J. Hofbauer, $ q$-Catalan numbers, J. Combin. Theory Ser. A 40 (1985), no. 2, 248-264. MR 814413 (87e:05017)
  • 14. M. Haiman, Conjectures on the quotient ring by diagonal invariants, J. Algebraic Combin. 3 (1994), 17-76. MR 1256101 (95a:20014)
  • 15. C.E. Heitsch, Combinatorics on plane trees, motivated by RNA secondary structure configurations, preprint.
  • 16. -, Kreweras complementation and orbits in Catalan lattices, preprint.
  • 17. C. Krattenthaler, Non-crossing partitions on an annulus, in preparation.
  • 18. 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).
  • 19. G. Kreweras, Sur les partitions non-croisées d'un cycle, Discrete Math. 1 (1972), 333-350. MR 0309747 (46:8852)
  • 20. D.I. Panyushev, On orbits of antichains of positive roots, European J. Combin. 30 (2009), no. 2, 586-594. MR 2489252 (2010c:05145)
  • 21. V. Reiner, Non-crossing partitions for classical reflection groups, Discrete Math. 177 (1997), 195-222. MR 1483446 (99f:06005)
  • 22. V. Reiner, D. Stanton, and D. White, The cyclic sieving phenomenon, J. Combin. Theory Ser. A 108 (2004), 17-50. MR 2087303 (2005g:05014)
  • 23. M. Rubey and C. Stump, Crossings and nestings in set partitions of classical types, Electron. J. Combin. 17 (2010), no. 1, R120. MR 2729369 (2012c:05042)
  • 24. D. Rush and X.L. Shi, On orbits of order ideals of minuscule posets, preprint, available at arXiv:1108.5245 (2011).
  • 25. W.A. Stein et al., Sage Mathematics Software (Version 4.6), The Sage Development Team, 2011,
  • 26. J. Striker and N. Williams, Promotion and rowmotion, preprint, available at arXiv:1108.1172 (2011).

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05A05, 20F55

Retrieve articles in all journals with MSC (2010): 05A05, 20F55

Additional Information

Drew Armstrong
Affiliation: Department of Mathematics, University of Miami, Coral Gables, Florida 33146

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

Hugh Thomas
Affiliation: Department of Mathematics and Statistics, University of New Brunswick, Fredericton, New Brunswick, E3B 5A3, Canada

Keywords: Weyl groups, Coxeter groups, noncrossing partitions, nonnesting partitions, cyclic sieving phenomenon, bijective combinatorics
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
Article copyright: © Copyright 2013 American Mathematical Society

American Mathematical Society