## Generalized quotients in Coxeter groups

HTML articles powered by AMS MathViewer

- by Anders Björner and Michelle L. Wachs
- Trans. Amer. Math. Soc.
**308**(1988), 1-37 - DOI: https://doi.org/10.1090/S0002-9947-1988-0946427-X
- PDF | Request permission

## Abstract:

For ($W$, $S$) a Coxeter group, we study sets of the form \[ W/V = \{ w \in W|l(wv) = l(w) + l(v)\;{\text {for all}}\;v \in V\} ,\] , where $V \subseteq W$. Such sets $W/V$, here called*generalized quotients*, are shown to have much of the rich combinatorial structure under Bruhat order that has previously been known only for the case when $V \subseteq S$ (i.e., for minimal coset representatives modulo a parabolic subgroup). We show that Bruhat intervals in $W/V$, for general $V \subseteq W$, are lexicographically shellable. The Möbius function on $W/V$ under Bruhat order takes values in $\{ - 1, 0, + 1\}$. For finite groups $W$, generalized quotients are the same thing as lower intervals in the weak order. This is, however, in general not true. Connections with the weak order are explored and it is shown that $W/V$ is always a complete meet-semilattice and a convex order ideal as a subset of $W$ under weak order. Descent classes ${D_I} = \{ w \in W|l(ws) < l(w) \Leftrightarrow s \in I,\;{\text {for all}}\;s \in S\}$, $I \subseteq S$, are also analyzed using generalized quotients. It is shown that each descent class, as a poset under Bruhat order or weak order, is isomorphic to a generalized quotient under the corresponding ordering. The latter half of the paper is devoted to the symmetric group and to the study of some specific examples of generalized quotients which arise in combinatorics. For instance, the set of standard Young tableaux of a fixed shape or the set of linear extensions of a rooted forest, suitably interpreted, form generalized quotients. We prove a factorization result for the quotients that come from rooted forests, which shows that algebraically these quotients behave as a system of minimal "coset" representatives of a subset which is in general not a subgroup. We also study the rank generating function for certain quotients in the symmetric group.

## References

- George E. Andrews,
*The theory of partitions*, Encyclopedia of Mathematics and its Applications, Vol. 2, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1976. MR**0557013** - George E. Andrews and Dominique Foata,
*Congruences for the $q$-secant numbers*, European J. Combin.**1**(1980), no. 4, 283–287. MR**595926**, DOI 10.1016/S0195-6698(80)80027-8 - Garrett Birkhoff,
*Lattice theory*, 3rd ed., American Mathematical Society Colloquium Publications, Vol. XXV, American Mathematical Society, Providence, R.I., 1967. MR**0227053** - Anders Björner,
*Shellable and Cohen-Macaulay partially ordered sets*, Trans. Amer. Math. Soc.**260**(1980), no. 1, 159–183. MR**570784**, DOI 10.1090/S0002-9947-1980-0570784-2 - Anders Björner,
*Orderings of Coxeter groups*, Combinatorics and algebra (Boulder, Colo., 1983) Contemp. Math., vol. 34, Amer. Math. Soc., Providence, RI, 1984, pp. 175–195. MR**777701**, DOI 10.1090/conm/034/777701 - Anders Björner,
*On matroids, groups and exchange languages*, Matroid theory (Szeged, 1982) Colloq. Math. Soc. János Bolyai, vol. 40, North-Holland, Amsterdam, 1985, pp. 25–60. MR**843371**
—, - Anders Björner and Michelle Wachs,
*Bruhat order of Coxeter groups and shellability*, Adv. in Math.**43**(1982), no. 1, 87–100. MR**644668**, DOI 10.1016/0001-8708(82)90029-9 - Anders Björner and Michelle Wachs,
*On lexicographically shellable posets*, Trans. Amer. Math. Soc.**277**(1983), no. 1, 323–341. MR**690055**, DOI 10.1090/S0002-9947-1983-0690055-6
—, - Anders Björner and Michelle L. Wachs,
*$q$-hook length formulas for forests*, J. Combin. Theory Ser. A**52**(1989), no. 2, 165–187. MR**1022316**, DOI 10.1016/0097-3165(89)90028-9 - N. Bourbaki,
*Éléments de mathématique. Fasc. XXXIV. Groupes et algèbres de Lie. Chapitre IV: Groupes de Coxeter et systèmes de Tits. Chapitre V: Groupes engendrés par des réflexions. Chapitre VI: systèmes de racines*, Actualités Scientifiques et Industrielles [Current Scientific and Industrial Topics], No. 1337, Hermann, Paris, 1968 (French). MR**0240238** - Vinay V. Deodhar,
*Some characterizations of Bruhat ordering on a Coxeter group and determination of the relative Möbius function*, Invent. Math.**39**(1977), no. 2, 187–198. MR**435249**, DOI 10.1007/BF01390109 - Richard Dipper and Gordon James,
*Representations of Hecke algebras of general linear groups*, Proc. London Math. Soc. (3)**52**(1986), no. 1, 20–52. MR**812444**, DOI 10.1112/plms/s3-52.1.20 - 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 - A. M. Garsia and J. Remmel,
*Shuffles of permutations and the Kronecker product*, Graphs Combin.**1**(1985), no. 3, 217–263. MR**951014**, DOI 10.1007/BF02582950 - Donald E. Knuth,
*The art of computer programming. Volume 3*, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973. Sorting and searching. MR**0445948** - Albert Nijenhuis and Herbert S. Wilf,
*Combinatorial algorithms*, 2nd ed., Computer Science and Applied Mathematics, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1978. For computers and calculators. MR**510047** - Richard P. Stanley,
*Ordered structures and partitions*, Memoirs of the American Mathematical Society, No. 119, American Mathematical Society, Providence, R.I., 1972. MR**0332509** - Richard P. Stanley,
*Binomial posets, Möbius inversion, and permutation enumeration*, J. Combinatorial Theory Ser. A**20**(1976), no. 3, 336–356. MR**409206**, DOI 10.1016/0097-3165(76)90028-5 - Richard P. Stanley,
*Weyl groups, the hard Lefschetz theorem, and the Sperner property*, SIAM J. Algebraic Discrete Methods**1**(1980), no. 2, 168–184. MR**578321**, DOI 10.1137/0601021 - Jacques Tits,
*Buildings of spherical type and finite BN-pairs*, Lecture Notes in Mathematics, Vol. 386, Springer-Verlag, Berlin-New York, 1974. MR**0470099** - Daya-Nand Verma,
*Möbius inversion for the Bruhat ordering on a Weyl group*, Ann. Sci. École Norm. Sup. (4)**4**(1971), 393–398. MR**291045**, DOI 10.24033/asens.1215

*The weak ordering of a Coxeter group*(to appear).

*Permutation statistics and linear extensions of posets*(to appear).

## Bibliographic Information

- © Copyright 1988 American Mathematical Society
- Journal: Trans. Amer. Math. Soc.
**308**(1988), 1-37 - MSC: Primary 05A99; Secondary 06F99, 20B30, 20F99
- DOI: https://doi.org/10.1090/S0002-9947-1988-0946427-X
- MathSciNet review: 946427