c Birkhauser Verlag, Basel, 2007 Annals of Combinatorics Embedded Factor Patterns for Deodhar Elements in Kazhdan-Lusztig Theory

AMS Subject Classication: 20C08 Abstract. The Kazhdan-Lusztig polynomials for nite Weyl groups arise in the geometry of Schubert varieties and representation theory. It was proved very soon after their introduction that they have nonnegative integer coefcients, but no simple all positive interpretation for them is known in general. Deodhar [16] has given a framework for computing the Kazhdan-Lusztig polynomials which generally involves recursion. We dene embedded factor pattern avoidance for general Coxeter groups and use it to characterize when Deodhar's algorithm yields a simple combinatorial formula for the Kazhdan-Lusztig polynomials of nite Weyl groups. Equivalently, if (W; S) is a Coxeter system for a nite Weyl group, we classify the elements w 2W for which the Kazhdan-Lusztig basis element C 0w can be written as a monomial of C 0s where s 2 S. This work generalizes results of Billey-Warrington [8] that identied the Deodhar elements in type A as 321-hexagon-avoiding permutations, and Fan-Green [18] that identied the fully-tight Coxeter groups