Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
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?)


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

DOI: http://dx.doi.org/10.1090/S0002-9947-09-04981-2
PII: S 0002-9947(09)04981-2
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.