## Lattice paths and Kazhdan-Lusztig polynomials

HTML articles powered by AMS MathViewer

- by Francesco Brenti PDF
- J. Amer. Math. Soc.
**11**(1998), 229-259 Request permission

## Abstract:

The purpose of this paper is to present a new non-recursive combinatorial formula for the Kazhdan-Lusztig polynomials of a Coxeter group $W$. More precisely, we show that each directed path in the Bruhat graph of $W$ has a naturally associated set of lattice paths with the property that the Kazhdan-Lusztig polynomial of $u,v$ is the sum, over all the lattice paths associated to all the paths going from $u$ to $v$, of $(-1)^{\Gamma _{\ge 0}+d_+(\Gamma )}q^{(l(v)-l(u)+\Gamma (l(\Gamma )))/2}$ where $\Gamma _{\ge 0}, d_+(\Gamma )$, and $\Gamma (l(\Gamma ))$ are three natural statistics on the lattice path.## References

- D. André,
*Solution directe du probléme résolu par M. Bertrand*, C. R. Acad. Sci. Paris**105**(1887), 436-437. - Margaret M. Bayer and Louis J. Billera,
*Counting faces and chains in polytopes and posets*, Combinatorics and algebra (Boulder, Colo., 1983) Contemp. Math., vol. 34, Amer. Math. Soc., Providence, RI, 1984, pp. 207–252. MR**777703**, DOI 10.1090/conm/034/777703 - A. Björner, A. M. Garsia, and R. P. Stanley,
*An introduction to Cohen-Macaulay partially ordered sets*, Ordered sets (Banff, Alta., 1981) NATO Adv. Study Inst. Ser. C: Math. Phys. Sci., vol. 83, Reidel, Dordrecht-Boston, Mass., 1982, pp. 583–615. MR**661307** - 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,
*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 - Francesco Brenti,
*A combinatorial formula for Kazhdan-Lusztig polynomials*, Invent. Math.**118**(1994), no. 2, 371–394. MR**1292116**, DOI 10.1007/BF01231537 - F. Brenti,
*Combinatorial expansions of Kazhdan-Lusztig polynomials*, J. London Math. Soc. (2)**55**(1997), 448-472. - F. Brenti,
*Kazhdan-Lusztig and $R$-polynomials from a combinatorial point of view*, Discrete Math., to appear. - Louis Comtet,
*Advanced combinatorics*, Revised and enlarged edition, D. Reidel Publishing Co., Dordrecht, 1974. The art of finite and infinite expansions. MR**0460128**, DOI 10.1007/978-94-010-2196-8 - 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 - Vinay V. Deodhar,
*On some geometric aspects of Bruhat orderings. I. A finer decomposition of Bruhat cells*, Invent. Math.**79**(1985), no. 3, 499–511. MR**782232**, DOI 10.1007/BF01388520 - M. Dyer,
*Hecke algebras and reflections in Coxeter groups*, Ph. D. Thesis, University of Sydney, 1987. - Matthew Dyer,
*On the “Bruhat graph” of a Coxeter system*, Compositio Math.**78**(1991), no. 2, 185–191. MR**1104786** - M. J. Dyer,
*Hecke algebras and shellings of Bruhat intervals*, Compositio Math.**89**(1993), no. 1, 91–115. MR**1248893** - Charles Hopkins,
*Rings with minimal condition for left ideals*, Ann. of Math. (2)**40**(1939), 712–730. MR**12**, DOI 10.2307/1968951 - I. P. Goulden and D. M. Jackson,
*Combinatorial enumeration*, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Inc., New York, 1983. With a foreword by Gian-Carlo Rota. MR**702512** - James E. Humphreys,
*Reflection groups and Coxeter groups*, Cambridge Studies in Advanced Mathematics, vol. 29, Cambridge University Press, Cambridge, 1990. MR**1066460**, DOI 10.1017/CBO9780511623646 - David Kazhdan and George Lusztig,
*Representations of Coxeter groups and Hecke algebras*, Invent. Math.**53**(1979), no. 2, 165–184. MR**560412**, DOI 10.1007/BF01390031 - David Kazhdan and George Lusztig,
*Schubert varieties and Poincaré duality*, Geometry of the Laplace operator (Proc. Sympos. Pure Math., Univ. Hawaii, Honolulu, Hawaii, 1979) Proc. Sympos. Pure Math., XXXVI, Amer. Math. Soc., Providence, R.I., 1980, pp. 185–203. MR**573434** - Richard P. Stanley,
*Enumerative combinatorics. Vol. I*, The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, CA, 1986. With a foreword by Gian-Carlo Rota. MR**847717**, DOI 10.1007/978-1-4615-9763-6 - Richard Stanley,
*Generalized $H$-vectors, intersection cohomology of toric varieties, and related results*, Commutative algebra and combinatorics (Kyoto, 1985) Adv. Stud. Pure Math., vol. 11, North-Holland, Amsterdam, 1987, pp. 187–213. MR**951205**, DOI 10.2969/aspm/01110187 - Richard P. Stanley,
*Log-concave and unimodal sequences in algebra, combinatorics, and geometry*, Graph theory and its applications: East and West (Jinan, 1986) Ann. New York Acad. Sci., vol. 576, New York Acad. Sci., New York, 1989, pp. 500–535. MR**1110850**, DOI 10.1111/j.1749-6632.1989.tb16434.x - Richard P. Stanley,
*Subdivisions and local $h$-vectors*, J. Amer. Math. Soc.**5**(1992), no. 4, 805–851. MR**1157293**, DOI 10.1090/S0894-0347-1992-1157293-9 - 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

## Additional Information

**Francesco Brenti**- Affiliation: Dipartimento di Matematica, Universitá di Roma “Tor Vergata”, Via della Ricerca Scientifica, I-00133 Roma, Italy
- MR Author ID: 215806
- Email: brenti@mat.utovrm.it
- Received by editor(s): December 20, 1996
- Received by editor(s) in revised form: July 28, 1997
- Additional Notes: Part of this work was carried out while the author was a member of the Mathematical Sciences Research Institute in Berkeley, California, U.S.A., and was partially supported by NSF grant No. DMS 9022140 and EC grant No. CHRX-CT93-0400.
- © Copyright 1998 American Mathematical Society
- Journal: J. Amer. Math. Soc.
**11**(1998), 229-259 - MSC (1991): Primary 20F55; Secondary 05E99
- DOI: https://doi.org/10.1090/S0894-0347-98-00249-5
- MathSciNet review: 1460390