×

zbMATH — the first resource for mathematics

Decomposition numbers for finite Coxeter groups and generalised non-crossing partitions. (English) Zbl 1228.05306
Summary: 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\dots\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 [Algorithms and Combinatorics 26, 93–126 (2006; Zbl 1122.05096 ); Sémin. Lothar. Comb. 54, B54l, 34 p. (2005; Zbl 1267.05293)]. The type \( A_n\) decomposition numbers have been computed by I. P. Goulden and D. M. Jackson [Eur. J. Comb. 13, No.5, 357–365 (1992; Zbl 0804.05023)], albeit using a somewhat different language. We explain how to extract the type \( B_n\) decomposition numbers from results of M. Bóna et al. [Adv. Appl. Math. 24, No. 1, 22–56 (2000; Zbl 0957.05056)] 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\leq r_2\leq \dots\leq r_l\), the number of multi-chains \( \pi_1\leq \pi_2\leq \dots\leq \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.

MSC:
05E15 Combinatorial aspects of groups and algebras (MSC2010)
05A05 Permutations, words, matrices
05A10 Factorials, binomial coefficients, combinatorial functions
05A15 Exact enumeration problems, generating functions
05A18 Partitions of sets
06A07 Combinatorics of partially ordered sets
20F55 Reflection and Coxeter groups (group-theoretic aspects)
33C05 Classical hypergeometric functions, \({}_2F_1\)
Software:
coxeter
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] ArmDAA D. Armstrong, \em Generalized noncrossing partitions and combinatorics of Coxeter groups, Mem. Amer. Math. Soc., vol. 202, no. 949, Amer. Math. Soc., Providence, RI, 2009.
[2] AthaAE C. A. Athanasiadis, \em On noncrossing and nonnesting partitions for classical reflection groups, Electron. J. Combin. \bf 5 (1998), Article #R42, 16 pp.
[3] AthaAI C. A. Athanasiadis, \em On some enumerative aspects of generalized associahedra, European J. Combin. \bf 28 (2007), 1208–1215.
[4] AtBWAA C. A. Athanasiadis, T. Brady and C. Watt, \em Shellability of noncrossing partition lattices, Proc. Amer. Math. Soc. \bf 135 (2007), 939–949.
· Zbl 1171.05053
[5] AtReAA C. A. Athanasiadis and V. Reiner, \em Noncrossing partitions for the group \(D_n\), SIAM J. Discrete Math. \bf 18 (2004), 397–417.

[6] AtTzAA C. A. Athanasiadis and E. Tzanaki, \em On the enumeration of positive cells in generalized cluster complexes and Catalan hyperplane arrangements, J. Algebraic Combin. \bf 23 (2006), 355–375.
[7] AtTzAB C. A. Athanasiadis and E. Tzanaki, \em Shellability and higher Cohen-Macaulay connectivity of generalized cluster complexes, Israel J. Math. \bf 167 (2008), 177–191.
[8] BesDAA D. Bessis, \em The dual braid monoid, Ann. Sci. \'Ecole Norm. Sup. (4) \bf 36 (2003), 647–683.
[9] BeCoAA D. Bessis and R. Corran, \em Non-crossing partitions of type \((e,e,r)\), Adv. Math. \bf 202 (2006), 1–49.
[10] BianAA P. Biane, \em Some properties of crossings and partitions, Discrete Math. \bf 175 (1997), 41–53.
· Zbl 0892.05006
[11] BjBrAB A. Bj\"orner and F. Brenti, \em Combinatorics of Coxeter groups, Springer–Verlag, New York, 2005.
[12] BoBLAA M. B\'ona, M. Bousquet, G. Labelle and P. Leroux, \em Enumeration of \(m\)-ary cacti, Adv. Appl. Math. \bf 24 (2000), 22–56.
[13] BoCSAA M. Bousquet, C. Chauve and G. Schaeffer, \em \'Enum\'eration et g\'en\'eration al\'eatoire de cactus \(m\)-aires, Proceedings of the Colloque LaCIM 2000 (Montr\'eal), P. Leroux (ed.), Publications du LaCIM, vol. 27, 2000, pp. 89–100.
[14] BraTAA T. Brady, \em A partial order on the symmetric group and new \(K(π ,1)\)’s for the braid groups, Adv. Math. \bf 161 (2001), 20–40.
· Zbl 1011.20040
[15] BRWaAA T. Brady and C. Watt, \em \(K(π ,1)\)’s for Artin groups of finite type, Geom. Dedicata \bf 94 (2002), 225–250.
· Zbl 1053.20034
[16] BRWaAB T. Brady and C. Watt, \em Non-crossing partition lattices in finite reflection groups, Trans. Amer. Math. Soc. \bf 360 (2008), 1983–2005.
· Zbl 1187.20051
[17] ChaFAA F. Chapoton, \em Enumerative properties of generalized associahedra, S\'eminaire Lotharingien Combin. \bf 51 (2004), Article B51b, 16 pp.
[18] EdelAA P. Edelman, \em Chain enumeration and noncrossing partitions, Discrete Math. \bf 31 (1981), 171–180.
[19] FoReAA S. Fomin and N. Reading, \em Generalized cluster complexes and Coxeter combinatorics, Int. Math. Res. Notices \bf 44 (2005), 2709–2757.
· Zbl 1117.52017
[20] FoReAB S. Fomin and N. Reading, \em Root systems and generalized associahedra, Geometric Combinatorics, 63–131, IAS/Park City Math. Ser., 13, Amer. Math. Soc., Providence, RI, 2007.
[21] FOZeAB S. Fomin and A. Zelevinsky, \em \(Y\)-systems and generalized associahedra, Ann. of Math. (2) \bf 158 (2003), 977–1018.
[22] GoodAA I. J. Good, \em Generalizations to several variables of Lagrange’s expansion, with applications to stochastic processes, Proc. Cambridge Philos. Soc. \bf 56 (1960), 367–380.
· Zbl 0135.18802
[23] GoJaAS I. P. Goulden and D. M. Jackson, \em The combinatorial relationship between trees, cacti and certain connection coefficients for the symmetric group, Europ. J. Combin. \bf 13 (1992), 357–365.
· Zbl 0804.05023
[24] HumpAC J. E. Humphreys, \em Reflection groups and Coxeter groups, Cambridge University Press, Cambridge, 1990.
[25] IrviAA J. Irving, \em Combinatorial constructions for transitive factorizations in the symmetric group, Ph.D. thesis, University of Waterloo, 2004.
[26] KratAC C. Krattenthaler, \em Operator methods and Lagrange inversion: A unified approach to Lagrange formulas, Trans. Amer. Math. Soc. \bf 305 (1988), 431–465.
· Zbl 0653.05007
[27] KratCB C. Krattenthaler, \em The \(F\)-triangle of the generalised cluster complex, in: Topics in Discrete Mathematics, dedicated to Jarik Ne\v set\v ril on the occasion of his 60th birthday, M. Klazar, J. Kratochvil, M. Loebl, J. Matou\v sek, R. Thomas and P. Valtr (eds.), Springer–Verlag, Berlin, New York, 2006, pp. 93–126.
[28] KratCF C. Krattenthaler, \em The \(M\)-triangle of generalised non-crossing partitions for the types \(E_7\) and \(E_8\), S\'eminaire Lotharingien Combin. \bf 54 (2006), Article B54l, 34 pages.
[29] KratCG C. Krattenthaler, \em Non-crossing partitions on an annulus, in preparation.
[30] KrewAC G. Kreweras, \em Sur les partitions non crois\'ees d’un cycle, Discrete Math. \bf 1 (1972), 333–350.
[31] ReadAAN. Reading, \em Chains in the noncrossing partition lattice, SIAM J. Discrete Math. \bf 22 (2008), 875–886.
[32] ReivAG V. Reiner, \em Non-crossing partitions for classical reflection groups, Discrete Math. \bf 177 (1997), 195–222.
· Zbl 0892.06001
[33] StanAP R. P. Stanley, \em Enumerative Combinatorics, Vol. 1, Wadsworth & Brooks/Cole, Pacific Grove, California, 1986; reprinted by Cambridge University Press, Cambridge, 1998.
[34] StanBI R. P. Stanley, \em Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge, 1999.
[35] StemAZ J. R. Stembridge, \em coxeter, \sl Maple package for working with root systems and finite Coxeter groups; available at \tt http://www.math.lsa.umich.edu/\~jrs.
[36] TzanAA E. Tzanaki, \em Combinatorics of generalized cluster complexes and hyperplane arrangements, Ph.D. thesis, University of Crete, Iraklio, 2007.
[37] TzanAC E. Tzanaki, \em Polygon dissections and some generalizations of cluster complexes, J. Combin. Theory Ser. A \bf 113 (2006), 1189–1198.
· Zbl 1105.52009
[38] TzanAB E. Tzanaki, \em Faces of generalized cluster complexes and noncrossing partitions, SIAM J. Discrete Math. \bf 22 (2008), 15–30. \endthebibliography · Zbl 1222.20029
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.