Lattice paths and Kazhdan-Lusztig polynomials

Brenti, Francesco

doi:10.1090/S0894-0347-98-00249-5

Lattice paths and Kazhdan-Lusztig polynomials
HTML articles powered by AMS MathViewer

by Francesco Brenti

J. Amer. Math. Soc. 11 (1998), 229-259

DOI: https://doi.org/10.1090/S0894-0347-98-00249-5

PDF | 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