Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)



Lattice paths
and Kazhdan-Lusztig polynomials

Author: Francesco Brenti
Journal: J. Amer. Math. Soc. 11 (1998), 229-259
MSC (1991): Primary 20F55; Secondary 05E99
MathSciNet review: 1460390
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. D. André, Solution directe du probléme résolu par M. Bertrand, C. R. Acad. Sci. Paris 105 (1887), 436-437.
  • 2. M. M. Bayer and L. J. Billera, Generalized Dehn-Sommerville relations for polytopes, spheres and Eulerian partially ordered sets, Invent. Math. 79 (1985), 143-157. MR 86f:52010b
  • 3. A. Björner, A. Garsia, and R. Stanley, An introduction to Cohen-Macaulay partially ordered sets, in Ordered Sets (I. Rival, Editor), Reidal, Dordrecht/Boston, 1982, 583-615. MR 83i:06001
  • 4. A. Björner and M. Wachs, Bruhat order of Coxeter groups and shellability, Adv. in Math. 43 (1982), 87-100. MR 83i:20043
  • 5. A. Björner, Orderings of Coxeter groups, Combinatorics and Algebra, Contemporary Math., vol. 34, Amer. Math. Soc., 1984, 175-195. MR 86i:05024
  • 6. F. Brenti, A combinatorial formula for Kazhdan-Lusztig polynomials, Invent. Math. 118 (1994), 371-394. MR 96c:20074
  • 7. F. Brenti, Combinatorial expansions of Kazhdan-Lusztig polynomials, J. London Math. Soc. (2) 55 (1997), 448-472. CMP 97:13
  • 8. F. Brenti, Kazhdan-Lusztig and $R$-polynomials from a combinatorial point of view, Discrete Math., to appear.
  • 9. L. Comtet, Advanced Combinatorics, Reidel, Dordrecht/Boston, 1974. MR 57:124
  • 10. V. V. Deodhar, Some characterizations of Bruhat ordering on a Coxeter group and determination of the relative Möbius function, Invent. Math. 39 (1977), 187-198. MR 55:8209
  • 11. V. V. Deodhar, On some geometric aspects of Bruhat orderings. I. A finer decomposition of Bruhat cells, Invent. Math. 79 (1985), 499-511. MR 86f:20045
  • 12. M. Dyer, Hecke algebras and reflections in Coxeter groups, Ph. D. Thesis, University of Sydney, 1987.
  • 13. M. Dyer, On the ``Bruhat graph'' of a Coxeter system, Comp. Math. 78 (1991), 185-191. MR 92c:20076
  • 14. M. Dyer, Hecke algebras and shellings of Bruhat intervals, Comp. Math. 89 (1993), 91-115. MR 95c:20053
  • 15. W. Feller, An Introduction to Probability Theory and its Applications, Vol. 1, Wiley, New York, 1950. MR 12:424a
  • 16. I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley-Interscience, New York, 1983. MR 84m:05002
  • 17. J. E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge Studies in Advanced Mathematics, no.29, Cambridge Univ. Press, Cambridge, 1990. MR 92h:20002
  • 18. D. Kazhdan and G. Lusztig, Representations of Coxeter groups and Hecke algebras, Invent. Math. 53 (1979), 165-184. MR 81j:20066
  • 19. D. Kazhdan and G. Lusztig, Schubert varieties and Poincaré duality, Geometry of the Laplace operator, Proc. Sympos. Pure Math. 34, Amer. Math. Soc., Providence, RI, 1980, pp. 185-203. MR 84g:14054
  • 20. R. P. Stanley, Enumerative Combinatorics , vol.1, Wadsworth and Brooks/Cole, Monterey, CA, 1986. MR 87j:05003
  • 21. R. P. Stanley, Generalized $h$-vectors, intersection cohomology of toric varieties, and related results, Adv. Studies Pure Math. 11 (1987), 187-213. MR 89f:52016
  • 22. R. P. Stanley, Log-concave and unimodal sequences in Algebra, Combinatorics and Geometry, Annals of the New York Academy of Sciences 576 (1989), 500-534. MR 92e:05124
  • 23. R. P. Stanley, Subdivisions and local $h$-vectors, J. Amer. Math. Soc. 5 (1992), 805-851. MR 93b:52012
  • 24. D.-N. Verma, Möbius inversion for the Bruhat order on a Weyl group, Ann. Sci. École Norm. Sup. 4 (1971), 393-398. MR 45:139

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (1991): 20F55, 05E99

Retrieve articles in all journals with MSC (1991): 20F55, 05E99

Additional Information

Francesco Brenti
Affiliation: Dipartimento di Matematica, Universitá di Roma “Tor Vergata”, Via della Ricerca Scientifica, I-00133 Roma, Italy

Keywords: Coxeter group, Bruhat order, Kazhdan-Lusztig polynomial, Eulerian poset, lattice path, generalized $h$-vector, Bayer-Billera relations
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.
Article copyright: © Copyright 1998 American Mathematical Society

American Mathematical Society