A uniform bijection between nonnesting and noncrossing partitions

Armstrong, Drew; Stump, Christian; Thomas, Hugh

doi:10.1090/S0002-9947-2013-05729-7

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