<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 11 Issue 3-4" %>
Embedded Factor Patterns for Deodhar Elements in Kazhdan-Lusztig Theory
Sara C. Billey1 and Brant C. Jones2
1Department of Mathematics, University of Washington, Box 354350, Seattle, WA 98195-4350, USA
2Department of Mathematics, One Shields Avenue, University of California, Davis, CA 95616, USA
Annals of Combinatorics 11 (3-4) p.285-333 September, 2007
AMS Subject Classification: 20C08
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. Deodhar [16] 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 finiteWeyl groups. Equivalently, if (W, S) is a Coxeter system for a finite Weyl group, we classify the elements w 2W for which the Kazhdan-Lusztig basis element C'w w can be written as a monomial of C's s where s ∈S. This work generalizes results of Billey-Warrington [8] that identified the Deodhar elements in type A as 321-hexagon-avoiding permutations, and Fan-Green [18] that identified the fully-tight Coxeter groups.
Keywords: Kazhdan-Lusztig polynomials, Deodhar elements, tight element, 321-hexagon, pattern avoidance, heaps, reduced expressions, two-sided weak Bruhat order, factor


1. D.A. Beck, The combinatorics of symmetric functions and permutation enumeration of the hyperoctahedral group, Discrete Math. 163 (1-3) (1997) 13-45.

2. A. Beilinson and J. Bernstein, Localization of g-modules, C. R. Acad. Sci. Paris S´er. I Math. 292 (1981) 15-18.

3. S.C. Billey, Pattern avoidance and rational smoothness of Schubert varieties, Adv. Math. 139 (1) (1998) 141-156.

4. S.C. Billey and T. Braden, Lower bounds for Kazhdan-Lusztig polynomials from patterns, Transform. Groups 8 (4) (2003) 321-332.

5. S.C. Billey,W. Jockusch, and R.P. Stanley, Some combinatorial properties of Schubert polynomials, J. Algebraic Combin. 2 (4) (1993) 345-374.

6. S.C. Billey and T.-K. Lam, Vexillary elements in the hyperoctahedral group, J. Algebraic Combin. 8 (2) (1998) 139-152.

7. S.C. Billey and A. Postnikov, Smoothness of Schubert varieties via patterns in root subsystems, Adv. Appl. Math. 34 (3) (2005) 447-466.

8. S.C. Billey and G.S. Warrington, Kazhdan-Lusztig polynomials for 321-hexagon-avoiding permutations, J. Algebraic Combin. 13 (2) (2001) 111-136.

9. A. Björner and F. Brenti, Combinatorics of Coxeter Groups, Undergraduate Texts in Mathematics, Vol. 231, Springer, New York, 2005.

10. M. Bóna, Combinatorics of Permutations, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2004.

11. M. Bousquet-Mélou and S. Butler, Forest-like permutations, Ann. Combin., to appear.

12. F. Brenti, The intersection cohomology of Schubert varieties is a combinatorial invariant, Europ. J. Combin. 25 (8) (2004) 1151-1167.

13. J.-L. Brylinski and M. Kashiwara, Kazhdan-Lusztig conjectures and holonomic systems, Invent. Math. 64 (3) (1981) 387-410.

14. P. Cartier and D. Foata, Problèmes Combinatoires de Commutation et Réarrangements, Lecture Notes in Mathematics, No. 85, Springer-Verlag, Berlin, 1969.

15. V. Deodhar, A brief survey of Kazhdan-Lusztig theory and related topics, In: Algebraic Groups and Their Generalizations: Classical Methods, B.J. Parshall Ed., Proceedings of Symposia in Pure Math, Vol. 56 (1), Amer. Math. Soc., Providence, RI, 1994.

16. V. Deodhar, A combinatorial setting for questions in Kazhdan-Lusztig theory, Geom. Dedicata 36 (1) (1990) 95-119.

17. K. Eriksson, The numbers game and Coxeter groups, Discrete Math. 139 (1-3) (1995) 155- 166.

18. C.K. Fan and R.M. Green, Monomials and Temperley-Lieb algebras, J. Algebra 190 (2) (1997) 498-517.

19. V. Gasharov, Factoring the poincaré polynomials for the Bruhat order on Sn, J. Combin. Theory Ser. A 83 (1) (1998) 159-164.

20. J.E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge Studies in Advanced Mathematics, Vol. 29, Cambridge University Press, Cambridge, 1990.

21. B.C. Jones, Kazhdan-Lusztig polynomials for maximally-clustered hexagon-avoiding permutations, preprint, arXiv:math.CO/0704.3067.

22. D. Kazhdan and G. Lusztig, Representations of Coxeter groups and Hecke algebras, Invent. Math. 53 (2) (1979) 165-184.

23. D. Kazhdan and G. Lusztig, Schubert varieties and Poincar´e duality, Proc. Sympos. Pure Math. 36 (1980) 185-203.

24. V. Lakshmibai and B. Sandhya, Criterion for smoothness of Schubert varieties in Sl(n)=B, Proc. Indian Acad. Sci. Math. Sci. 100 (1) (1990) 45-52.

25. A. Lascoux and M.-P. Sch¨utzenberger, Polynˆomes de Kazhdan & Lusztig pour les grassmanniennes, In: Young Tableaux and Schur Functors in Algebra and Geometry, Ast´erisque, Vol. 87, Soci´et´e Math´ematique de France, Paris, (1981) pp. 249-266.

26. G. Lusztig, Tight monomials in quantized enveloping algebras, In: Quantum Deformations of Algebras and Their Representations, Israel Math. Conf. Proc., Vol. 7, Bar-Ilan Univ., Ramat Gan, (1993) pp. 117-132.

27. T. Mansour, Coloured permutations containing and avoiding certain patterns, Ann. Comb. 7 (3) (2003) 349-355.

28. T. Mansour, Pattern avoidance in coloured permutations, Sém. Lothar. Combin. 46 (2001/02) Art. B46g.

29. T. Mansour and J. West, Avoiding 2-letter signed patterns, S´em. Lothar. Combin. 49 (2002- 04) Art. B49a.

30. A. Marcus and G. Tardos, Excluded permutation matrices and the Stanley-Wilf conjecture, J. Combin. Theory Ser. A 107 (1) (2004) 153-160.

31. T.J. McLarnan and G.S. Warrington, Counterexamples to the 0􀀀1 conjecture, Represent. Theory 7 (2003) 181-195.

32. P. Polo, Construction of arbitrary Kazhdan-Lusztig polynomials in symmetric groups, Represent. Theory 3 (1999) 90-104.

33. R. Simion, Combinatorial statistics on type-B analogues of noncrossing partitions and restricted permutations, Electron. J. Combin. 7 (2000) #R9.

34. R. Simion and F.W. Schmidt, Restricted permutations, Europ. J. Combin. 6 (4) (1985) 383- 406.

35. D.A. Spielman and M. Bóna, An infinite antichain of permutations, Electron. J. Combin. 7 (2000) #N2.

36. Z. Stankova and J. West, Explicit enumeration of 321, hexagon-avoiding permutations, Discrete Math. 280 (1-3) (2004) 165-189.

37. R.P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge Studies in Advanced Mathematics, Vol. 49, Cambridge University Press, Cambridge, 1997.

38. R.P. Stanley, On the number of reduced decompositions of elements of Coxeter groups, Europ. J. Combin. 5 (4) (1984) 359-372.

39. J.R. Stembridge, On the fully commutative elements of Coxeter groups, J. Algebraic Combin. 5 (4) (1996) 353-385.

40. J.R. Stembridge, Some combinatorial aspects of reduced words in finite Coxeter groups, Trans. Amer. Math. Soc. 349 (4) (1997) 1285-1332.

41. J.R. Stembridge, The enumeration of fully commutative elements of Coxeter groups, J. Algebraic Combin. 7 (3) (1998) 291-320.

42. R. Tarjan, Sorting using networks of queues and stacks, J. Assoc. Comput. Mach. 19 (1972) 341-346.

43. B. Tenner, Pattern avoidance and the Bruhat order, J. Combin. Theory Ser. A 114 (5) (2007) 888-905.

44. B. Tenner, Reduced decompositions and permutation patterns, J. Algebraic Combin. 24 (3) (2006) 263-284.

45. J. Tits, Le problème des mots dans les groupes de Coxeter, In: Symposia Mathematica, Vol. 1, Academic Press, London, (1969) pp. 175-185.

46. V. Vatter, Enumeration schemes for restricted permutations, Combin. Probab. Comput., to appear.

47. G.X. Viennot, Heaps of pieces. I. Basic definitions and combinatorial lemmas, In: Graph Theory and its Applications: East and West, Ann. New York Acad. Sci., Vol. 576, New York Acad. Sci., New York, (1989) pp. 542-570.

48. A. Woo and A. Yong, Governing singularities of Schubert varieties, J. Algebra, to appear.

49. A. Woo and A. Yong, When is a Schubert variety Gorenstein?, Adv. Math. 207 (1) (2006) 205-220.