COMBINATORIAL EXPANSIONS OF KAZHDAN–LUSZTIG POLYNOMIALS

Abstract

We introduce two related families of polynomials, easily computable by simple recursions into which any Kazhdan–Lusztig (and inverse Kazhdan–Lusztig) polynomial of any Coxeter group can be expanded linearly, and we give combinatorial interpretations to the coefficients in these expansions. This yields a combinatorial rule for computing the Kazhdan–Lusztig polynomials in terms of paths in a directed graph, and a completely combinatorial reformulation of the nonnegativity conjecture [15, p. 166].