The Kazhdan-Lusztig polynomials for finite Weyl groups arise in representation theory as well as the geometry of Schubert varieties. 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. Deodhar has given a framework, which generally involves recursion, to express the Kazhdan-Lusztig polynomials in a very attractive form. We use a new kind of pattern-avoidance that can be defined for general Coxeter groups to characterize when Deodhar's algorithm yields a non-recursive combinatorial formula for Kazhdan-Lusztig polynomials Px,w(q) of finite Weyl groups. This generalizes results of Billey-Warrington which identified the 321-hexagon-avoiding permutations, and Fan-Green which identified the fully-tight Coxeter groups. We also show that the leading coefficient known as µ(x,w) for these Kazhdan--Lusztig polynomials is always either 0 or 1. Finally, we generalize the simple combinatorial formula for the Kazhdan--Lusztig polynomials of the 321-hexagon-avoiding permutations to the case when w is hexagon avoiding and maximally clustered.
Résumé. Les polynômes de Kazhdan-Lusztig Px,w(q) des groupes de Weyl finis apparaissent en théorie des représent-ations, ainsi qu'en géométrie des variétés de Schubert. Il a été démontré peu après leur introduction qu'ils avaient des coefficients entiers positifs, mais on ne connaît toujours pas d'interprétation combinatoire simple de cette propriété dans le cas général. Deodhar a proposé un cadre donnant un algorithme, en général récursif, calculant des formules attractives pour les polynômes de Kazhdan-Lusztig. Billey-Warrington ont démontré que cet algorithme est non récursif lorsque w évite les hexagones et les 321 et qu'il donne des formules combinatoires simples. Nous introduisons une notion d'évitement de schémas dans les groupes de Coxeter quelconques nous permettant de généraliser les résultats de Billey-Warrington à tout groupe de Weyl fini. Nous montrons que le coefficient de tête µ(x,w) de ces polynômes de Kazhdan-Lusztig est toujours 0 ou 1. Cela généralise aussi des résultats de Fan-Green qui identifient les groupes de Coxeter complètement serrés. Enfin, en type A, nous obtenons une classe plus large de permutations évitant la récursion.