<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume10 Issue3" %>
Permutation Diagrams, Fixed Points and Kazhdan-Lusztig R-Polynomials
Federico Incitti
Department of Mathematics, Royal Institute of Technology, Lindstedts väg 25, 10044 Stockholm, Sweden
Annals of Combinatorics 10 (3) p. 369-387 September, 2006
AMS Subject Classification: 05E15, 20F55
In this paper, we give an algorithm for computing the Kazhdan-Lusztig, R-polynomials in the symmetric group. The algorithm is described in terms of permutation diagrams. In particular we focus on how the computation of the polynomial is affected by certain fixed points. As a consequence of our methods, we obtain explicit formulas for the R-polynomials associated with some general classes of intervals, generalizing results of Brenti and Pagliacci.
Keywords: permutation diagram, fixed point, Bruhat order, Kazhdan-Lusztig polynomial, R-polynomial


1. A. Björner and F. Brenti, Combinatorics of Coxeter Groups, Graduate Texts in Mathematics, Vol. 231, Springer-Verlag, New York, 2005.

2. A. Björner and M. Wachs, Bruhat order of Coxeter groups and shellability, Adv. Math. 43 (1982) 87–100.

3. F. Brenti, Combinatorial properties of the Kazhdan-Lusztig R-polynomials for Sn, Adv. Math. 126 (1997) 21–51.

4. M.J. Dyer, Hecke algebras and shellings of Bruhat intervals, Compositio Math. 89 (1993) 91–115.

5. M.J. Dyer, On minimal lengths of expressions of Coxeter group elements as products of reflections, Proc. Amer. Math. Soc. 129 (9) (2001) 2591–2595.

6. I. Fanti, A. Frosini, E. Grazzini, R. Pinzani, and S. Rinaldi, Polyominoes determined by permutations, Discrete Mathematics & Theoretical Computer Science Proceedings AG (2006) 381–390.

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

8. F. Incitti, The Bruhat order on the involutions of the symmetric group, J. Algebraic Combin. 20 (2004) 243–261.

9. C. Kassel, A. Lascoux, and C. Reutenauer, The singular locus of a Schubert variety, J. Algebra 269 (2003) 74–108.

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

11. M. Pagliacci, Explicit fromulae for some Kazhdan-Lusztig R-polynomials, J. Combin. Theory Ser. A 95 (2001) 74–87.

12. R.P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth and Brooks/Cole, Pacific Grove, CA, 1986.