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.