Combinatorics Of Kazhdan-Lusztig R-Polynomials

The Kazhdan-Lusztig theory was introduced in1979by D. Kazhdan and G. Lusztig in their study of the representations of Coxeter groups and Hecke algebras. It has been widely used in representation theory, algebraic geome-try and combinatorics. The Kazhdan-Lusztig R-polynomial is a fundamental topic in the Kazhdan-Lusztig theory for its connection with the multiplicative structure of Hecke algebras.In this thesis, we mainly investigate some combinatorial properties of the R-polynomials. On one hand, we present a combinatorial proof of the inversion formula of the R-polynomials, which solves a problem raised by F. Brenti in1998. As an application, we get a short proof of the formula of the Mobius function for the Bruhat order. On the other hand, we build a relation between a class of R-polynomials and the q-Fibonacci numbers.This thesis is organized as follows. In Chapter1, we give an overview of the general background of Coxeter groups and Kazhdan-Lusztig theory and a short introduction to the main results of this thesis.In Chapter2, we give a combinatorial proof of the inversion formula of the R-polynomials by using an interpretation of the R-polynomials given by M. Dyer. This solves a problem raised by F. Brenti in1998. Dyer interpreted the R-polynomial Ru,v(q) as the generating function of Bruhat paths from u to v such that the reflections labeled on the edges increase along the path under a reflection ordering. While the reverse of a reflection ordering is still a reflection ordering, we interpret the inversion formula of the R-polynomials in terms of V-paths. By a V-path from u to v with bottom w we mean a Bruhat path from u to v passing through w, such that the reflections labeled on the edges is decreasing from u to w and increasing from w to v. The inversion formula is then proved by constructing an involution Φ on V-paths. Two applications of the involution Φ are also given in this chapter. First, we restrict the involution Φ to V-paths of maximal length from u to v.This induces an involution on the Bruhat interval[u, v] for u<v, which finally leads to a proof of Verma’s formula of the Mobius function for the Bruhat order on Coxeter groups. As a second application, we get a refinement of the inversion formula for the symmetric groups by using a variation of the involution Φ.In Chapter3, we give a combinatorial proof of Deodhar’s general formu-la of the Mobius function for the Bruhat order on Coxeter groups and their parabolic quotients. This formula has attracted much attention since its dis-covery. In particular, A. Bjorner, M. Wachs and J. Stembridge gave two new proofs of the formula by using topological and algebraic techniques, respec-tively. In this chapter we present a short proof of Deodhar’s formula with the aid of a labeling method given by Bjorner and Wachs. This proof is, so far as we know, the first combinatorial proof of Deodhar’s formula.In Chapter4, we build a relation between a class of R-polynomials on the symmetric groups and q-Fibonacci numbers. More precisely, when vn is fixed to be34… n12in the symmetric group Sn,we compute that the R-polynomials Ru,vn(q) are, aside from a simple change of variable,q-analogues of Fibonacci numbers. In particular, this result reduces to Pagliacci’s formula of Re,vn(g), when u takes the identity element e in Sn. With the formula for Ru,vn(q), we also give a formula of the R-polynomial Re,vn,i(q) for vn,i=34…in(i+1)…(n-1)12in terms of q-Fibonacci numbers, which is also a generalization of Pagliacci’s result.