Peak algebras, paths in the Bruhat graph and Kazhdan-Lusztig polynomials

Abstract

We obtain a nonrecursive combinatorial formula for the Kazhdan-Lusztig polynomials which holds in complete generality and which is simpler and more explicit than any existing one, and which cannot be linearly simplified. Our proof uses a new basis of the peak subalgebra of the algebra of quasisymmetric functions.

Keywords

• lattice paths
• coxeter groups
• cd-index
• quasi-symmetric functions
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
• [math.math-co] mathematics [math]/combinatorics [math.co]