×

zbMATH — the first resource for mathematics

A uniform bijection between nonnesting and noncrossing partitions. (English) Zbl 1271.05011
Summary: In 2007, D. I. Panyushev [Eur. J. Comb. 30, No. 2, 586–594 (2009; Zbl 1165.06001)] 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. and V. Reiner [Ann. Comb. 15, No. 2, 197–222 (2011; Zbl 1268.20041)].

MSC:
05A18 Partitions of sets
05E15 Combinatorial aspects of groups and algebras (MSC2010)
05A05 Permutations, words, matrices
20F55 Reflection and Coxeter groups (group-theoretic aspects)
Software:
SageMath
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Drew Armstrong, Generalized noncrossing partitions and combinatorics of Coxeter groups, Mem. Amer. Math. Soc. 202 (2009), no. 949, x+159. · Zbl 1191.05095 · doi:10.1090/S0065-9266-09-00565-1 · doi.org
[2] Christos A. Athanasiadis, Generalized Catalan numbers, Weyl groups and arrangements of hyperplanes, Bull. London Math. Soc. 36 (2004), no. 3, 294 – 302. · Zbl 1068.20038 · doi:10.1112/S0024609303002856 · doi.org
[3] Christos A. Athanasiadis and Victor Reiner, Noncrossing partitions for the group \?_\?, SIAM J. Discrete Math. 18 (2004), no. 2, 397 – 417. · Zbl 1085.06001 · doi:10.1137/S0895480103432192 · doi.org
[4] Yuri Berest, Pavel Etingof, and Victor Ginzburg, Finite-dimensional representations of rational Cherednik algebras, Int. Math. Res. Not. 19 (2003), 1053 – 1088. · Zbl 1063.20003 · doi:10.1155/S1073792803210205 · doi.org
[5] Olivier Bernardi, Bijective counting of tree-rooted maps and shuffles of parenthesis systems, Electron. J. Combin. 14 (2007), no. 1, Research Paper 9, 36. · Zbl 1115.05002
[6] David Bessis and Victor Reiner, Cyclic sieving of noncrossing partitions for complex reflection groups, Ann. Comb. 15 (2011), no. 2, 197 – 222. · Zbl 1268.20041 · doi:10.1007/s00026-011-0090-9 · doi.org
[7] A. E. Brouwer and A. Schrijver, On the period of an operator, defined on antichains, Mathematisch Centrum, Amsterdam, 1974. Mathematisch Centrum Afdeling Zuivere Wiskunde ZW 24/74. · Zbl 0282.06003
[8] 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. · Zbl 1033.17008 · doi:10.1016/S0021-8693(02)00532-X · doi.org
[9] 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. · Zbl 1108.05012
[10] P. Duchet, Sur les hypergraphes invariantes, Discrete Math. 8 (1974), 269 – 280 (French). · Zbl 0288.05132 · doi:10.1016/0012-365X(74)90139-3 · doi.org
[11] 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. · Zbl 1147.05014 · doi:10.1016/j.aam.2007.01.005 · doi.org
[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. · Zbl 1391.05047
[13] J. Fürlinger and J. Hofbauer, \?-Catalan numbers, J. Combin. Theory Ser. A 40 (1985), no. 2, 248 – 264. · Zbl 0581.05006 · doi:10.1016/0097-3165(85)90089-5 · doi.org
[14] Mark D. Haiman, Conjectures on the quotient ring by diagonal invariants, J. Algebraic Combin. 3 (1994), no. 1, 17 – 76. · Zbl 0803.13010 · doi:10.1023/A:1022450120589 · doi.org
[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). · Zbl 1271.05102
[19] G. Kreweras, Sur les partitions non croisées d’un cycle, Discrete Math. 1 (1972), no. 4, 333 – 350 (French). · Zbl 0231.05014 · doi:10.1016/0012-365X(72)90041-6 · doi.org
[20] Dmitri I. Panyushev, On orbits of antichains of positive roots, European J. Combin. 30 (2009), no. 2, 586 – 594. · Zbl 1165.06001 · doi:10.1016/j.ejc.2008.03.009 · doi.org
[21] Victor Reiner, Non-crossing partitions for classical reflection groups, Discrete Math. 177 (1997), no. 1-3, 195 – 222. · Zbl 0892.06001 · doi:10.1016/S0012-365X(96)00365-2 · doi.org
[22] V. Reiner, D. Stanton, and D. White, The cyclic sieving phenomenon, J. Combin. Theory Ser. A 108 (2004), no. 1, 17 – 50. · Zbl 1052.05068 · doi:10.1016/j.jcta.2004.04.009 · doi.org
[23] 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. · Zbl 1277.05011
[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, http://www.sagemath.org.
[26] J. Striker and N. Williams, Promotion and rowmotion, preprint, available at arXiv:1108.1172 (2011). · Zbl 1260.06004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.