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)



Decomposition numbers for finite Coxeter groups and generalised non-crossing partitions

Authors: C. Krattenthaler and T. W. Müller
Journal: Trans. Amer. Math. Soc. 362 (2010), 2723-2787
MSC (2000): Primary 05E15; Secondary 05A05, 05A10, 05A15, 05A18, 06A07, 20F55, 33C05
Published electronically: December 17, 2009
MathSciNet review: 2584617
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Given a finite irreducible Coxeter group $ W$, a positive integer $ d$, and types $ T_1,T_2,\dots,T_d$ (in the sense of the classification of finite Coxeter groups), we compute the number of decompositions $ c=\sigma_1\sigma_2\cdots\sigma_d$ of a Coxeter element $ c$ of $ W$, such that $ \sigma_i$ is a Coxeter element in a subgroup of type $ T_i$ in $ W$, $ i=1,2,\dots,d$, and such that the factorisation is ``minimal'' in the sense that the sum of the ranks of the $ T_i$'s, $ i=1,2,\dots,d$, equals the rank of $ W$. For the exceptional types, these decomposition numbers have been computed by the first author in [``Topics in Discrete Mathematics,'' M. Klazar et al. (eds.), Springer-Verlag, Berlin, New York, 2006, pp. 93-126] and [Séminaire Lotharingien Combin. 54 (2006), Article B54l]. The type $ A_n$ decomposition numbers have been computed by Goulden and Jackson in [Europ. J. Combin. 13 (1992), 357-365], albeit using a somewhat different language. We explain how to extract the type $ B_n$ decomposition numbers from results of Bóna, Bousquet, Labelle and Leroux [Adv. Appl. Math. 24 (2000), 22-56] on map enumeration. Our formula for the type $ D_n$ decomposition numbers is new. These results are then used to determine, for a fixed positive integer $ l$ and fixed integers $ r_1\le r_2\le \dots\le r_l$, the number of multi-chains $ \pi_1\le \pi_2\le \dots\le \pi_l$ in Armstrong's generalised non-crossing partitions poset, where the poset rank of $ \pi_i$ equals $ r_i$ and where the ``block structure'' of $ \pi_1$ is prescribed. We demonstrate that this result implies all known enumerative results on ordinary and generalised non-crossing partitions via appropriate summations. Surprisingly, this result on multi-chain enumeration is new even for the original non-crossing partitions of Kreweras. Moreover, the result allows one to solve the problem of rank-selected chain enumeration in the type $ D_n$ generalised non-crossing partitions poset, which, in turn, leads to a proof of Armstrong's $ F=M$ Conjecture in type $ D_n$, thus completing a computational proof of the $ F=M$ Conjecture for all types. It also allows one to address another conjecture of Armstrong on maximal intervals containing a random multi-chain in the generalised non-crossing partitions poset.

References [Enhancements On Off] (What's this?)

  • 1. D. Armstrong, Generalized noncrossing partitions and combinatorics of Coxeter groups, Mem. Amer. Math. Soc., vol. 202, no. 949, Amer. Math. Soc., Providence, RI, 2009.
  • 2. C. A. Athanasiadis, On noncrossing and nonnesting partitions for classical reflection groups, Electron. J. Combin. 5 (1998), Article #R42, 16 pp. MR 1644234 (99i:05204)
  • 3. C. A. Athanasiadis, On some enumerative aspects of generalized associahedra, European J. Combin. 28 (2007), 1208-1215. MR 2305586 (2008c:05005)
  • 4. C. A. Athanasiadis, T. Brady and C. Watt, Shellability of noncrossing partition lattices, Proc. Amer. Math. Soc. 135 (2007), 939-949. MR 2262893 (2007j:05221)
  • 5. 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)
  • 6. C. A. Athanasiadis and E. Tzanaki, On the enumeration of positive cells in generalized cluster complexes and Catalan hyperplane arrangements, J. Algebraic Combin. 23 (2006), 355-375. MR 2236611 (2007c:20095)
  • 7. C. A. Athanasiadis and E. Tzanaki, Shellability and higher Cohen-Macaulay connectivity of generalized cluster complexes, Israel J. Math. 167 (2008), 177-191. MR 2448023
  • 8. D. Bessis, The dual braid monoid, Ann. Sci. École Norm. Sup. (4) 36 (2003), 647-683. MR 2032983 (2004m:20071)
  • 9. D. Bessis and R. Corran, Non-crossing partitions of type $ (e,e,r)$, Adv. Math. 202 (2006), 1-49. MR 2218819 (2007a:20035)
  • 10. P. Biane, Some properties of crossings and partitions, Discrete Math. 175 (1997), 41-53. MR 1475837 (98h:05020)
  • 11. A. Björner and F. Brenti, Combinatorics of Coxeter groups, Springer-Verlag, New York, 2005. MR 2133266 (2006d:05001)
  • 12. M. Bóna, M. Bousquet, G. Labelle and P. Leroux, Enumeration of $ m$-ary cacti, Adv. Appl. Math. 24 (2000), 22-56. MR 1741339 (2001c:05072)
  • 13. M. Bousquet, C. Chauve and G. Schaeffer, Énumération et génération aléatoire de cactus $ m$-aires, Proceedings of the Colloque LaCIM 2000 (Montréal), P. Leroux (ed.), Publications du LaCIM, vol. 27, 2000, pp. 89-100.
  • 14. T. Brady, A partial order on the symmetric group and new $ K(\pi,1)$'s for the braid groups, Adv. Math. 161 (2001), 20-40. MR 1857934 (2002k:20066)
  • 15. T. Brady and C. Watt, $ K(\pi,1)$'s for Artin groups of finite type, Geom. Dedicata 94 (2002), 225-250. MR 1950880 (2004i:20066)
  • 16. T. Brady and C. Watt, Non-crossing partition lattices in finite reflection groups, Trans. Amer. Math. Soc. 360 (2008), 1983-2005. MR 2366971 (2008k:20088)
  • 17. F. Chapoton, Enumerative properties of generalized associahedra, Séminaire Lotharingien Combin. 51 (2004), Article B51b, 16 pp. MR 2080386 (2005e:17013)
  • 18. P. Edelman, Chain enumeration and noncrossing partitions, Discrete Math. 31 (1981), 171-180. MR 583216 (81i:05018)
  • 19. S. Fomin and N. Reading, Generalized cluster complexes and Coxeter combinatorics, Int. Math. Res. Notices 44 (2005), 2709-2757. MR 2181310 (2006g:05230)
  • 20. S. Fomin and N. Reading, Root systems and generalized associahedra, Geometric Combinatorics, 63-131, IAS/Park City Math. Ser., 13, Amer. Math. Soc., Providence, RI, 2007. MR 2383126
  • 21. S. Fomin and A. Zelevinsky, $ Y$-systems and generalized associahedra, Ann. of Math. (2) 158 (2003), 977-1018. MR 2031858 (2004m:17010)
  • 22. I. J. Good, Generalizations to several variables of Lagrange's expansion, with applications to stochastic processes, Proc. Cambridge Philos. Soc. 56 (1960), 367-380. MR 0123021 (23:A352)
  • 23. I. P. Goulden and D. M. Jackson, The combinatorial relationship between trees, cacti and certain connection coefficients for the symmetric group, Europ. J. Combin. 13 (1992), 357-365. MR 1181077 (93g:05148)
  • 24. J. E. Humphreys, Reflection groups and Coxeter groups, Cambridge University Press, Cambridge, 1990. MR 1066460 (92h:20002)
  • 25. J. Irving, Combinatorial constructions for transitive factorizations in the symmetric group, Ph.D. thesis, University of Waterloo, 2004.
  • 26. C. Krattenthaler, Operator methods and Lagrange inversion: A unified approach to Lagrange formulas, Trans. Amer. Math. Soc. 305 (1988), 431-465. MR 924765 (89d:05017)
  • 27. C. Krattenthaler, The $ F$-triangle of the generalised cluster complex, in: Topics in Discrete Mathematics, dedicated to Jarik Nešetřil on the occasion of his 60th birthday, M. Klazar, J. Kratochvil, M. Loebl, J. Matoušek, R. Thomas and P. Valtr (eds.), Springer-Verlag, Berlin, New York, 2006, pp. 93-126. MR 2249265 (2007g:05194)
  • 28. C. Krattenthaler, The $ M$-triangle of generalised non-crossing partitions for the types $ E_7$ and $ E_8$, Séminaire Lotharingien Combin. 54 (2006), Article B54l, 34 pages.
  • 29. C. Krattenthaler, Non-crossing partitions on an annulus, in preparation.
  • 30. G. Kreweras, Sur les partitions non croisées d'un cycle, Discrete Math. 1 (1972), 333-350. MR 0309747 (46:8852)
  • 31. N. Reading, Chains in the noncrossing partition lattice, SIAM J. Discrete Math. 22 (2008), 875-886. MR 2424827
  • 32. V. Reiner, Non-crossing partitions for classical reflection groups, Discrete Math. 177 (1997), 195-222. MR 1483446 (99f:06005)
  • 33. R. P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth & Brooks/Cole, Pacific Grove, California, 1986; reprinted by Cambridge University Press, Cambridge, 1998. MR 1442260 (98a:05001)
  • 34. R. P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge, 1999. MR 1676282 (2000k:05026)
  • 35. J. R. Stembridge, coxeter, Maple package for working with root systems and finite Coxeter groups; available at˜jrs.
  • 36. E. Tzanaki, Combinatorics of generalized cluster complexes and hyperplane arrangements, Ph.D. thesis, University of Crete, Iraklio, 2007.
  • 37. E. Tzanaki, Polygon dissections and some generalizations of cluster complexes, J. Combin. Theory Ser. A 113 (2006), 1189-1198. MR 2244140 (2007c:05201)
  • 38. E. Tzanaki, Faces of generalized cluster complexes and noncrossing partitions, SIAM J. Discrete Math. 22 (2008), 15-30. MR 2383226

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 05E15, 05A05, 05A10, 05A15, 05A18, 06A07, 20F55, 33C05

Retrieve articles in all journals with MSC (2000): 05E15, 05A05, 05A10, 05A15, 05A18, 06A07, 20F55, 33C05

Additional Information

C. Krattenthaler
Affiliation: Fakultät für Mathematik, Universität Wien, Nordbergstraße 15, A-1090 Vienna, Austria

T. W. Müller
Affiliation: School of Mathematical Sciences, Queen Mary & Westfield College, University of London, Mile End Road, London E1 4NS, United Kingdom

Keywords: Root systems, reflection groups, Coxeter groups, generalised non-crossing partitions, annular non-crossing partitions, chain enumeration, M\"obius function, $M$-triangle, generalised cluster complex, face numbers, $F$-triangle, Chu--Vandermonde summation
Received by editor(s): June 30, 2008
Received by editor(s) in revised form: December 10, 2008
Published electronically: December 17, 2009
Additional Notes: The first author’s research was partially supported by the Austrian Science Foundation FWF, grant S9607-N13, in the framework of the National Research Network “Analytic Combinatorics and Probabilistic Number Theory”
Article copyright: © Copyright 2009 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society