Special matchings and Kazhdan-Lusztig polynomials

In 1979 Kazhdan and Lusztig defined, for every Coxeter group W, a family of polynomials, indexed by pairs of elements of W, which have become known as the Kazhdan-Lusztig polynomials of W, and which have proven to be of importance in several areas of mathematics. In this paper, we show that the combinatorial concept of a special matching plays a fundamental role in the computation of these polynomials. Our results also imply, and generalize, the recent one in [Adv. in Math. 180 (2003) 146-175] on the combinatorial invariance of Kazhdan-Lusztig polynomials.