Billey, Sara C.; Jones, Brant C. Embedded factor patterns for Deodhar elements in Kazhdan-Lusztig theory. (English) Zbl 1189.20008 Ann. Comb. 11, No. 3-4, 285-333 (2007). Summary: The Kazhdan-Lusztig polynomials for finite 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 coefficients, but no simple all positive interpretation for them is known in general. V. V. Deodhar [Geom. Dedicata 36, No. 1, 95-119 (1990; Zbl 0716.17015)] has given a framework for computing the Kazhdan-Lusztig polynomials which generally involves recursion. We define 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 finite Weyl groups. Equivalently, if \((W,S)\) is a Coxeter system for a finite Weyl group, we classify the elements \(w\in W\) for which the Kazhdan-Lusztig basis element \(C_w'\) can be written as a monomial of \(C_s'\) where \(s\in S\). This work generalizes results of S. C. Billey, G. S. Warrington [ J. Algebr. Comb. 13, No. 2, 111-136 (2001; Zbl 0979.05109)] that identified the Deodhar elements in type \(A\) as \(321\)-hexagon-avoiding permutations, and C. K. Fan, R. M. Green [J. Algebra 190, No. 2, 498-517 (1997; Zbl 0899.20018)] that identified the fully-tight Coxeter groups. Cited in 1 ReviewCited in 7 Documents MSC: 20C08 Hecke algebras and their representations 20F55 Reflection and Coxeter groups (group-theoretic aspects) 05E15 Combinatorial aspects of groups and algebras (MSC2010) Keywords:Kazhdan-Lusztig polynomials; finite Weyl groups; Coxeter groups; Deodhar elements; tight elements; 321-hexagons; pattern avoidance; heaps; reduced expressions; weak Bruhat orders; factors Citations:Zbl 0716.17015; Zbl 0979.05109; Zbl 0899.20018 Software:InsEnc PDFBibTeX XMLCite \textit{S. C. Billey} and \textit{B. C. Jones}, Ann. Comb. 11, No. 3--4, 285--333 (2007; Zbl 1189.20008) Full Text: DOI arXiv Online Encyclopedia of Integer Sequences: Number of Deodhar elements in the finite Weyl group D_n.