Kazhdan-Lusztig polynomials: History Problems, and Combinatorial Invariance

Francesco Brenti^{1} Dipartimento di Matematica Universitá di Roma “Tor Vergata” Via della Ricerca Scientifica 00133 Roma, Italy

This is an expository paper on Kazhdan-Lusztig polynomials, and particularly on the recent result concerning their combinatorial invariance, based on my lectures at the 49th Seminaire Lotharingien de Combinatoire. The paper consists of three parts entitled: History; Problems; and Combinatorial Invariance. In the first one we give the main definitions and facts about the Bruhat order and graph, and about the Kazhdan-Lusztig and R-polynomials. In the second one we present, as a sample, two results, one on the R-polynomials and one on the Kazhdan-Lusztig polynomials, which in the author’s opinion illustrate very well the rich combinatorics that hides in these polynomials. Finally, in the third part, we explain the recent result that the Kazhdan-Lusztig and Rpolynomials depend only on a certain poset, and mention some open problems and conjectures related to this.

Most of the results in §1 hold for all Coxeter groups (see [31]) but in order to keep the prerequisites to a minimum (in fact, essentially to zero) this exposition concerns only the symmetric group.

I have tried to keep the presentation as close as possible to that of the lectures that I have given, both in spirit and content. In particular, examples and heuristic explanations are the main features of this exposition.

1 History

1.1 Pre-History (i.e., the symmetric group)

Let [n] = {1, …, n}, and

S_{n} = {σ : [n] → [n] : σ is a bijection}

We write elements of S_{n} in three ways, namely:

• disjoint cycle form (e.g., σ = (7, 5, 2)(1, 3)) ;

• one-line notation (e.g., σ = 3714265); (Meaning that σ(1) = 3, σ(2) = 7, etc...)

1Partially supported by the EC’s IHRP Program, within the Research Training Network “Algebraic Combinatorics in Europe”, grant HPRN-CT-2001-00272.

• matrix (e.g.

σ = [ \begin{matrix}0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{matrix} ]).

There are two important subsets for this story:

S = {(1, 2), (2, 3), …, (n − 1, n)}

and

T = {(i, j) : 1 ≤ i < j ≤ n}.

Note that

σ(i, j) switches σ(i) and σ(j),

while

(i, j)σ switches i and j,

in the one-line notation of σ.

There are also two important statistics. For σ ∈ S_{n} let

inv(σ) = |{(i, j) ∈ [n]^{2} : i < j, σ(i) > σ(j)}|

(number inversions of σ, or length of σ, denoted l(σ)) and

D(σ) = {(i, i + 1) ∈ S : σ(i) > σ(i + 1)}(⇔ l(σ(i, i + 1)) < l(σ))

(descent set of σ ).

1.2 Bruhat graph and Bruhat order

There are two main combinatorial objects related to Kazhdan-Lusztig and Rpolynomials.

The Bruhat graph of S_{n} is the directed graph B(S_{n}) having S_{n} as vertex set and where

u → v

if and only if

there exist (i, j) ∈ T such that v = u(i, j) and l(v) > l(u)

(equivalently, such that v = u(i, j), i < j and u(i) < u(j)).

For example, the Bruhat graph of S_{3} is shown in Figure 1.

[figure: 123; 321; 213; 312; 132; 231]

Figure 1: The Bruhat graph of S_{3}.

Note that this digraph is always acyclic. The transitive closure of B(S_{n}) is the Bruhat order of S_{n}, denoted by ≤. For example, the Bruhat order of S_{3} is shown in Figure 2.

[figure: 123; 321; 213; 312; 132; 231]

Figure 2: The Bruhat order of S_{3}.

One immediate problem presents itself. Namely,

Given u, v ∈ S_{n}, how to decide if u and v are comparable?

For v ∈ S_{n} and i, j ∈ [n] let

v[i, j] =^{def} |{a ≤ i : v(a) ≥ j}|.

So v[i, j] is the rank of the principal submatrix of (the matrix notation of) v with SE corner (i, j).

For example, let v = 7153264. Then v[3, 4] = 2 (see Figure 3).

[ \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \end{matrix} ]

Figure 3.

We then have the following result (see, e.g., [42, Chap. 1], or [28, §10.5])

Theorem 1 Let u, v ∈ S_{n}. Then u ≤ v if and only if u[i, j] ≤ v[i, j] for all i, j ∈ [n].

We conclude this section by mentioning some important Facts about Bruhat order

• Bruhat order is a graded poset and inv is its rank function;

• Bruhat order is Eulerian (i.e., μ(u, v) = (−1)^{l(v)−l(u)} for every u, v);

• Bruhat order is shellable.

Proofs of the preceding results can be found in [7], [19], [26], [31], [46], or [51]. Given u, v ∈ S_{n} we let

[u, v] = {a ∈ S_{n} : u ≤ a ≤ v},

l(u, v) =^{def} l(v) − l(u), and write u ⊲ v if |[u, v]| = 2.

1.3 Kazhdan-Lusztig and R-polynomials

We are now in a position to define Kazhdan-Lusztig and R-polynomials. These polynomials (which can be defined for any Coxeter group) were introduced by Kazhdan and Lusztig in [32] in order to construct representations of the associated Hecke algebra, which is a deformation of the group algebra. Namely, it is the free Z[q, q^{−1}]-module H having {T_{w}}_{w∈S_{n}} as a formal basis and multiplication such that

T_{w}T_{s} = \{ \begin{matrix}T_{ws}, & if s ∉ D(w), \\ qT_{ws} + (q − 1)T, & if s ∈ D(w), \end{matrix}

for all w ∈ W and s ∈ S (so, for q = 1, this is the multiplication of the group algebra). (We refer the interested reader to [31, Chap. 7] for further information about the Hecke algebra of a Coxeter group). The R-polynomials are intimately related to the inversion of the basis elements in this algebra, and are used to define the Kazhdan-Lusztig polynomials which in turn are used to define the representations of the Hecke algebra (see [32]).

The Kazhdan-Lusztig polynomials have then found numerous and unexpected applications also in other areas of mathematics, including the representation theory of semisimple algebraic groups (see, e.g., [1] and the references cited there), the theory of Verma modules (see, e.g., [2], [16]), the algebraic geometry and topology of Schubert varieties (see, e.g., [33], [36], [3]), canonical bases ([27], [50]), and immanant inequalities ([30]). We say something more precise about some of these applications in §2.1.

Despite the plethora of applications that they have, all these polynomials can be defined using only the elementary notions introduced in §§1.1 and 1.2. This is the approach that suits our purposes best, and is the one that we use.

In both cases we have “Theorem-Definitions”.

Theorem 2 There is a unique family of polynomials {R_{u,v}(q)}_{u,v∈S_{n}} ⊆ ℤ[q] satisfying the following conditions:

i) R_{u,v}(q) = 0 if u ≰ v; ii) R_{u,v}(q) = 1 if u = v;

iii) if s ∈ D(v) then

R_{u,v}(q) = \{ \begin{matrix}R_{us,vs}(q), & if s ∈ D(u), \\ qR_{us,vs}(q) + (q − 1)R_{u,vs}(q), & if s ∉ D(u). \end{matrix}  (1)

A proof of the preceding theorem can be found in [31, §7.5]. The polynomials whose existence and uniqueness are guaranteed by Theorem 2 are called the R-polynomials of S_{n}. Theorem 2 can be used to compute the polynomials {R_{u,v}(q)}_{u,v∈W}, by induction on l(v). In fact, if v ≠ e it is possible to find some s ∈ D(v), and then since l(vs) < l(v) we may assume by induction that we have already computed all the R-polynomials appearing on the right hand side of (1). Thus we may use part iii) of Theorem 2 as a recurrence relation for the computation of the R-polynomials, using parts i) and ii) as “initial conditions”. We illustrate this procedure with an example.

Example 3 Suppose that we want to compute R_{123,321}(q) in S_{3}. Choosing s = (1, 2) ∈ D(321) we have from part iii) of Theorem 2 that

R_{123,321}(q) = q R_{213,231}(q) + (q − 1) R_{123,231}(q).

Now choosing s = (2, 3) ∈ D(231) we obtain that

R_{213,231}(q) = q R_{231,213}(q) + (q − 1) R_{213,213}(q) = q − 1,

and

R_{123,231}(q) = q R_{132,213}(q) + (q − 1) R_{123,213}(q)
= (q − 1) R_{123,213}(q)

by Theorem 2. Finally, choosing s = (1, 2) ∈ D(213) we get that

R_{123,213}(q) = q R_{213,123}(q) + (q − 1) R_{123,123}(q) = q − 1

again by Theorem 2. Therefore we conclude that

R_{123,321}(q) = q (q − 1) + (q − 1)^{3} = q^{3} − 2q^{2} + 2q − 1.

In the same way, the reader may want to compute as an exercise that

R_{123,132}(q) = R_{123,213}(q) = q − 1

and

R_{123,312}(q) = R_{123,231}(q) = q^{2} − 2q + 1.

Here are some easy properties of the R-polynomials, which the reader might want to prove as an exercise, using Theorem 2, by induction on l(v).

Easy Properties of R-polynomials

• R_{u,v}(q) is a monic polynomial of degree l(u, v).

• R_{u,v}(0) = (−1)^{l(u,v)}.

• q^{l(u,v)}R_{u,v}(1/q) = (−1)^{l(u,v)}R_{u,v}(q).

We now come to the definition of the Kazhdan-Lusztig polynomials. This is again a “Theorem-Definition”.

Theorem 4 There exists a unique family of polynomials {P_{u,v}(q)}_{u,v∈S_{n}} ⊆ ℤ[q] satisfying the following conditions:

i) P_{u,v}(q) = 0 if u ≰ v;

ii) P_{u,v}(q) = 1 if u = v;

iii) deg(P_{u,v}(q)) < \frac{1}{2}l(u, v) if u < v;

iv)

q^{l(u,v)} P_{u,v} (\frac{1}{q}) = ∑_{u≤a≤v} R_{u,a}(q) P_{a,v}(q)

if u ≤ v.

The preceding theorem was first proved in [32] and a proof of it can also be found in [31, §7.10]. The polynomials {P_{u,v}(q)}_{u,v∈S_{n}} whose existence and uniqueness are guaranteed by Theorem 4 are called the Kazhdan-Lusztig polynomials of S_{n}.

Here is an easy property of the Kazhdan-Lusztig polynomials.

Easy Properties of KL-polynomials

• P_{u,v}(0) = 1.

To help the reader get a feeling for how one works with Theorem 4 we provide the proof of this fact here.

We proceed by induction on l(u, v), the result being true by part ii) of Theorem 4 if l(u, v) = 0. So let l(u, v) > 0. Then we conclude from parts iii) and iv) of Theorem 4 that

0 = ∑_{u≤a≤v} R_{u,a}(0)P_{a,v}(0).

Using one of the easy facts about the R-polynomials and the induction hypothesis we may rewrite this as

P_{u,v}(0) = − ∑_{u<a≤v}(−1)^{l(u,a)}.

Now using one of the fundamental facts about Bruhat order we conclude from this that

P_{u,v}(0) = − ∑_{u<a≤v} μ(u, a) = μ(u, u) = 1,

as desired.

The proof of the preceding fact already shows that the Kazhdan-Lusztig polynomials are considerably more subtle than the R-polynomials. In fact, while for the latter ones one is able to deduce in a fairly straightforward way their degree, leading term, and constant term, for the Kazhdan-Lusztig polynomials we have had to use a more substantial result (the computation of the Möbius function of Bruhat order) just to compute their constant term. In fact, there are no known simple formulas, at present, to compute the leading term and degree of Kazhdan-Lusztig polynomials.

Note that what we have proved implies in particular that:

P_{u,v}(q) = 1 if l(u, v) ≤ 2.

Once the R-polynomials have been computed, then Theorem 4 can be used to compute recursively the polynomials {P_{u,v}(q)}_{u,v∈S_{n}}, by induction on l(u, v). In fact, by induction we may assume that we have already computed the polynomials P_{a,v}(q) for all a ∈ [u, v], a ≠ u. This, by part iv) of Theorem 4, means that we can compute

q^{l(u,v)} P_{u,v} (\frac{1}{q}) − P_{u,v}(q)  (2)

(recall that R_{u,u}(q) = 1 by part ii) of Theorem 2). However, by part iii) of Theorem 4, the coefficient of q^{i} in (2) is the same as the coefficient of q^{i} in −P_{u,v}(q) for all i = 0, …, ⌊\frac{1}{2}(l(u, v) − 1)⌋ (we assume that u < v for else we already know P_{u,v}(q) by parts i) and ii) of Theorem 4) and thus we can compute P_{u,v}(q) from (2). We illustrate this procedure with an example.

Example 5 Let us compute P_{123,321}(q). From part iv) we deduce that

q^{3} P_{123,321}(q^{−1}) − P_{123,321}(q) = R_{123,213}(q) P_{213,321}(q) + R_{123,132}(q) P_{132,321}(q)

+R_{123,231}(q) P_{231,321}(q) + R_{123,312}(q) P_{312,321}(q) + R_{123,321}(q) P_{321,321}(q).

But by parts ii) and iii) of Theorem 4 and what we have just observed we know that P_{u,321}(q) = 1 for all u ∈ S_{3} \ {123}, hence we obtain that

q^{3} P_{123,321}(q^{−1}) − P_{123,321}(q) = R_{123,213}(q) + R_{123,132}(q) + R_{123,231}(q)
+R_{123,312}(q) + R_{123,321}(q).

Assuming, as we are, that we have already computed the R-polynomials we then get

q^{3} P_{123,321}(q^{−1}) − P_{123,321}(q) = (q − 1) + (q − 1) + (q − 1)^{2} + (q − 1)^{2}

+(q^{3} − 2q^{2} + 2q − 1) = q^{3} − 1.

Now, since \frac{1}{2}(l(321) − l(123)) = \frac{3}{2}, we deduce from this, by part iii) of Theorem 4, that

P_{123,321}(q) = 1 .

It is natural to wonder if there is a direct way to compute the Kazhdan-Lusztig polynomials of S_{n}. The following result allows one to compute the KL-polynomials without having to compute the R-polynomials first.

Theorem 6 Let u, v ∈ S_{n}, u ≤ v, and s ∈ D(v). Then

P_{u,v}(q) = q^{1−c}P_{us,vs}(q) + q^{c}P_{u,vs}(q) − ∑_{\{z: s∈D(z)\}} q^{\frac{l(z,v)}{2}} \overline{μ}(z, vs)P_{u,z}(q) (3)

where c = 1 if s ∈ D(u), and c = 0 otherwise, and \overline{μ}(x, y) is the coefficient of q^{\frac{1}{2} (l(x,y)−1)} in P_{x,y}(q) (so \overline{μ}(x, y) = 0 if l(x, y) is even).

A proof of the preceding result can be found in [31, §7.11].

We conclude this section by mentioning a few more properties of KL and R-polynomials.

More properties of KL and R-polynomials

• R_{u,v} = R_{u^{−1},v^{−1}} = R_{w_{0}v,w_{0}u} = R_{vw_{0},uw_{0}} = R_{w_{0}uw_{0},w_{0}vw_{0}}, (where w_{0} = n n − 1 … 3 2 1);

• P_{u,v} = P_{u^{−1},v^{−1}} = P_{w_{0}uw_{0},w_{0}vw_{0}};

• \overline{μ}(u, v) = \overline{μ}(w_{0}v, w_{0}u) = \overline{μ}(vw_{0}, uw_{0}).

Proofs of these results can be found in [31, Prop. 7.6 and §7.13] and [11, §4].

2 Problems

2.1 Motivations

Having seen how long and awkward the computation of the Kazhdan-Lusztig and R-polynomials is one may very well wonder why one should bother to compute them at all.

As mentioned in §1.3, Kazhdan-Lusztig polynomials play a prominent role in several branches of mathematics including representation theory (see, e.g., [1], and the references cited there), and the algebraic geometry and topology of Schubert varieties (see, e.g., [32], [33], and [3]).

Here are the main connections to Schubert varieties. For a permutation v ∈ S_{n+1} let Ω_{v} be the Schubert cell indexed by v, and \overline{Ω}_{v} (Zariski closure) be the corresponding Schubert variety (we refer the reader to, e.g., [42], [28], or [3] for the definition of, and further information about, Schubert cells and varieties). It is well known (and not hard to see) that \overline{Ω}_{v} = ⨄_{u≤v} Ω_{u} so that

u ≤ v ⇔ \overline{Ω}_{u} ⊆ \overline{Ω}_{v}.  (4)

Denote by IH^{∗}(\overline{Ω}_{v}, C)_{Ω_{u}} the (middle perversity) local intersection cohomology of \overline{Ω}_{v} at a (equivalently, any) point of Ω_{u}. This is a graded vector space, and we denote by IH^{i}(\overline{Ω}_{v}, C)_{Ω_{u}} (i ∈ N) its graded pieces (we refer the reader to, e.g., [29], or [35], for further information about intersection (co)homology). The following result was first proved by Kazhdan and Lusztig in [33, Theorem 4.3].

Theorem 7 Let u, v ∈ S_{n+1}, u ≤ v. Then

P_{u,v}(q) = ∑_{i≥0} q^{i} dim_{C}(IH^{2i}(\overline{Ω}_{v}, C)_{Ω_{u}}).

Note that it is known that dim_{C}(IH^{i}(\overline{Ω}_{v}, C)_{Ω_{u}}) = 0 if i ≡ 1 (mod 2).

Theorem 7 implies that the coefficients of P_{u,v}(q) are nonnegative for all u, v ∈ S_{n} (something that Kazhdan and Lusztig had conjectured in [32]). No combinatorial interpretation is known, in general, for these coefficients.

Here are two other connections between the Kazhdan-Lusztig polynomials and the topology and algebraic geometry of Schubert varieties (see, e.g., [33], and [3]).

Corollary 8 Let v ∈ S_{n}. Then

∑_{u≤v} q^{l(u)}P_{u,v}(q) = ∑_{i≥0} dim_{C}(IH^{2i}(\overline{Ω_{v}}))q^{i}

Theorem 9 Let v ∈ S_{n}. Then the following are equivalent:

i) P_{e,v}(q) = 1;

ii) \overline{Ω_{v}} is smooth.

What about the R-polynomials? Do they have any connections to geometry? The following result is a simple consequence of the main theorem in [20].

Theorem 10 Let F be a finite field of order q and u, v ∈ S_{n}. Then

R_{u,v}(q) = |Ω_{v} ∩ Ω_{u}^{∗}|

where Ω_{v}^{∗} is the Shubert cell opposite to Ω_{v}.

In their original paper Kazhdan and Lusztig also conjectured ([32, Conj. 1.5]) a very simple relationship between the values of the Kazhdan-Lusztig polynomials P_{u,v} evaluated at 1 and multiplicities of Verma modules. This important conjecture was proved in 1981 by Beilinson and Bernstein [2], and by Brylinski and Kashiwara [16], and has then been generalized in various different directions (see, e.g., [1, §4]). In all these conjectures, the values of the polynomials at q = 1 compute important representation theoretic objects.

Therefore, one would know many interesting things if one knew the polynomials. So, there is really just one problem, namely:

How to compute these polynomials?

I will give two examples of answers to this problem which, in my opinion, illustrate well the rich combinatorics that hides in these polynomials. There are many other results that could have been chosen (see, e.g., [5],[6],[4], [8],[12],[13],[14], [18],[17], [20],[21], [24],[25],[34],[38],[40],[43], [45],[47],[49],[52]), and my choice here is entirely subjective.

2.2 R-polynomials and increasing subsequences

Let’s begin with the following easy observation.

Lemma 11 Let u, v ∈ S_{n}, u ≤ v. Then there exists a unique polynomial R̃_{u,v}(t) ∈ N[t] such that R_{u,v}(q) = q^{\frac{l(v)−l(u)}{2}} R̃_{u,v}(q^{\frac{1}{2}} − q^{− \frac{1}{2}} ).

Proof. Easy induction, using Theorem 2. □

The combinatorics that we are about to describe relates to these R̃-polynomials. As is usual in combinatorics, it is easier to explain things over an example first.

Let u = 1234, and v = 4321. We compute the polynomial R̃_{u,v}(q) as follows. We first check (e.g., using Theorem 1) that u < v (if u ≰ v then R̃_{u,v}(q) =^{def} 0, if u = v then R̃_{u,v}(q) =^{def} 1, and we are done). If u < v then we locate the largest integer that does not occupy the same position in both u and v. In this case this is 4. We now look at the positions that this integer occupies in u and v. In our case these are the first and fourth positions (it can be proved from Theorem 1 that the position in u is always to the right of the one in v because u < v). Next we find all the increasing subsequences in u that start at the first position and end at the fourth position. In our case there are four such subsequences, namely, 14, 124, 134, and 1234. We now “rotate one step to the right” each one of these subsequences in u to obtain 4 new permutations u^{(1)}, u^{(2)}, u^{(3)}, u^{(4)}. In our case we have u^{(1)} = \underline{1}23\underline{4}, u^{(2)} = \underline{1}\underline{2}3\underline{4}, u^{(3)} = \underline{1}2\underline{3}\underline{4}, and u^{(4)} = \underline{1}\underline{2}\underline{3}\underline{4} (where we have underlined, for emphasis, the elements that we have “rotated” in each case). Then the polynomial R̃_{u,v}(q) is given by

R̃_{u,v}(t) = tR̃_{u^{(1)},v}(t) + t^{2}R̃_{u^{(2)},v}(t) + t^{2}R̃_{u^{(3)},v}(t) + t^{3}R̃_{u^{(4)},v}(t) ,  (5)

(where the exponent of the power of t that multiplies R̃_{u^{(i)},v}(q) is the number of elements that have been “rotated” to obtain u^{(i)}, minus one). It is not hard to see that this algorithm will eventually stop. For example, in our case one obtains the diagram depicted in Figure 4, from which one then reads off

R̃_{1234,4321} = t^{2} + t^{4} + t^{4} + t^{6} + t^{4} = t^{6} + 3t^{4} + t^{2}.

[figure: 1234; 4231; 4213; 4123; 4132; 4312; 4312; 4312; 4321; t; t; t; t; t; t; t^{2}; t; t; t^{2}; t^{3}; t^{2}]

Figure 4.

What is going on?

For u, v ∈ S_{n}, u < v, let

δ = max{i : v^{−1}(i) ≠ u^{−1}(i)}.

Then one has (see, e.g., [10]).

Lemma 12 Let u < v then v^{−1}(δ) < u^{−1}(δ).

Now let C(u, v) be the set of all the increasing subsequences of u that begin at position v^{−1}(δ) and end at position u^{−1}(δ).

For example, let v = 7356142 and u = 1425736, then d = 7, u^{−1}(7) = 5, v^{−1}(7) = 1 and C(u, v) = {(1, 7), (1, 4, 7), (1, 2, 7), (1, 5, 7), (1, 2, 5, 7), (1, 4, 5, 7)}.

Interpret each element of C(u, v) as a cycle.

Then we have (see [10]):

Theorem 13 Let u, v ∈ S_{n}, u < v. Then

R̃_{u,v}(q) = ∑_{w∈C(u,v)}q^{k(w)−1}R̃_{wu,v}(q)  (6)

where k(w) =^{def} n − |{i ∈ [n] : w(i) = i}|.

Note that, unlike the original recursion given by Theorem 2, this recursion does not “branch off” in two cases, and is therefore very easy to solve (see, [10, Theorem 4.1]). Furthermore, it is much faster from a computational point of view.

2.3 Kazhdan-Lusztig polynomials and rooted trees

Let σ ∈ S_{n}. We say that σ is bigrassmannian if and only if |D(σ)| = |D(σ^{−1})| = 1. Note that σ is bigrassmannian if and only if

σ = 12 … a \underbrace{b + 1 … c} \underbrace{a + 1 … b} c + 1 … n

for some 1 ≤ a ≤ b ≤ c ≤ n (i.e., if and only if σ is obtained from the identity permutation by switching two “middle blocks”). Let

B(u) = {σ ≤ u : σ is bigrassmannian}.

The following result was proved by Lascoux and Schutzenberger in [39].

Theorem 14 Let u, v ∈ S_{n}. Then

u ≤ v ⇔ B(u) ⊆ B(v).

If σ ∈ B(u) let

d(σ, u) =^{def} max{i ∈ N : 12 … a − i b + 1 … c + i − 1 a − i + 1 … b c + i … n ≤ u}

Let v ∈ S_{n}. Say that v avoids 3412 if there are no indices 1 ≤ a < b < c < d ≤ n such that

v(c) < v(d) < v(a) < v(b).

Suppose v avoids 3412.

Take the inversion table of vw_{0}, and its nondecreasing rearrangement.

Example 15 Let v = 7541632. Then vw_{0} = 2361457 and I(vw_{0}) = (1, 1, 3, 0, 0, 0, 0) so we get the partition

Associate to this partition a word in {(,)} by associating a

“(” to a vertical step

and a

“)” to a horizontal step

as you follow its boundary from SW to NE.

Example 16 From the partition (1, 1, 3) we get the word

())(()

Now get a rooted tree by “matching the parentheses” (each vertex, except the root, corresponds to a matching pair () and a vertex is a descendant of another if and only if one pair is enclosed by another).

Example 17 For the word ))(())(())() we get

)) \underbrace{(\underbrace{()})} \underbrace{(\underbrace{()})} \underbrace{()}

and therefore

[figure]

Note that the leaves of the tree correspond to the corners of the partition, and therefore to the nonzero values of I(vw_{0}).

Now take the maximal elements of B(vw_{0}). In our running example these are B_{1} = 2341567 and B_{2} = 1263457. Their inversion tables correspond to the maximal rectangles contained in λ(vw_{0}), and therefore to the leaves of the tree (equivalently, the value of the last descent minus its position corresponds to a nonzero value of I(vw_{0}) and conversely, in our running example we get 4 − 3 and 6 − 3). Now label each leaf of the tree by

d(B_{i}, uw_{0})

Note that, since u ≤ v then B_{1}, B_{2} ≤ vw_{0} ≤ uw_{0}.

Let f : { edges of tree } → N be such that:

i) f increases weakly along any path from the root;

ii) the value of f at a final edge is less than or equal to the label of that leaf.

Let |f| = ∑_{e∈E} f(e). Then we have (Lascoux [37]):

Theorem 18 Let u, v ∈ S_{n}, u ≤ v, and v be 3412-avoiding. Then

P_{u,v}(q) = ∑_{f} q^{|f|}

where the sum is over all such functions f.

We illustrate this theorem on an example.

Example 19 Let v = 7536421 and u = 5437621, then uw_{0} = 1267345 and vw_{0} = 1246357. The inversion table of vw_{0} is I(vw_{0}) = (0, 0, 1, 2, 0, 0, 0), and its nondecreasing rearrangement (disregarding zeros) is (1, 2) so

λ(vw_{0}) =

We get the word ()()

and therefore

[figure]

Say that the leftmost leaf of the tree corresponds to the leftmost matching pair in the word, and therefore to the leftmost corner of the partition. The maximal elements of B(vw_{0}) are B_{1} = 1245367 and B_{2} = 1236457. Their inversion tables correspond to the maximal rectangles contained in λ(vw_{0}): so B_{1} corresponds to the leftmost leaf of the tree, and B_{2} to the rightmost one (equivalently, computing the value of the last descent minus its position, we get 5 − 4 = 1 for B_{1} and 6 − 4 = 2 for B_{2}, so B_{1} corresponds to the value 1 of I(vw_{0}), hence to the leftmost corner of the partition, so to the leftmost leaf of the tree, and B_{2} to the other one). We now compute d(B_{1}, uw_{0}) and d(B_{2}, uw_{0}). We have

1245367 ≤ 1267345

and for i = 1

1456237 ≰ 1267345

hence

d(B_{1}, uw_{0}) = 0.

Similarly

1236457 ≤ 1267345

and

1267345 ≤ 1267345

so

d(B_{2}, uw_{0}) = 1.

Associate to the leaves of the tree these integers:

[figure: 0; 1]

(Recall that the leftmost leaf of the tree corresponds to B_{1}, and the other one to B_{2}.) The possible functions f then are:

[figure: 0; 0; 0; 1]

so

P_{u,v} = 1 + q.

The procedure described in the subsection can “a priori”, be applied to any two permutations u, v ∈ S_{n}. It is an open problem to know for which permutations u, v Theorem 18 still holds (i.e., the procedure gives P_{u,v}(q)).

3 Combinatorial Invariance

The main problem, namely:

How to compute these polynomials?

has many related and subproblems.

One of them was posed by G. Lusztig in the early 1980’s [41], and independently by M. Dyer in 1987 ([22]).

Problem 20 Let u, v, σ, τ ∈ S_{n} be such that [u, v] ≅ [σ, τ] (as posets). Then P_{u,v}(q) = P_{σ,τ} (q).

Mathematicians have always had very different opinions on this problem. Let’s stop for a moment and analyze what the problem is saying. The equality of the polynomials is, by Theorem 7, a statement about the equality of certain intersection cohomology vector spaces. The isomorphism of the posets is, by equation (4), a statement that concerns exclusively the inclusion relations between the Schubert subvarieties of \overline{Ω}_{v} and of \overline{Ω}_{τ}.

In effect, if the answer to the problem is yes, then this would mean that you could go to some geometer and say “Please compute the intersection homology of a Schubert variety”, and at her reply “which Schubert variety?” you would say “Oh no..., sorry. I am not allowed to tell you that. I can only tell you, among all the Schubert cells contained in this Schubert variety, which pairs of cells touch each other, and in this case, which is the one of largest dimension”. It is not unlikely that, at your reply, the geometer would probably never talk to you again about mathematics. This is the reason, essentially, why most geometers think that the answer to this problem is no. Philosophically, it is thought that intersection homololgy is a deeper property than adjacency of Schubert cells. Yet, as some geometers have told me “There are many miracles that happen in Schubert varieties, and this could be one of them. It would certainly be one of the most amazing”.

Being rational mathematicians, it is definitely natural to look at the evidence known about this problem.

The answer is known to be yes if l(u, v) ≤ 4. In fact, we have already seen that

P_{u,v} = 1 if l(u, v) ≤ 2,

and it can be proved that if l(u, v) = 3 then

P_{u,v}(q) = \{ \begin{matrix}1, & if c(u, v) = 2, \\ 1 + (c(u, v) − 3)q, & otherwise, \end{matrix}

where c(u, v) denotes the number of coatoms of [u, v]. Furthermore, it can be shown that, if l(u, v) = 4, then

P_{u,v} = 1 + (\frac{B_{2}(u, v)}{2} − c(u, v) − 4)q

where B_{2}(u, v) equals the number of paths in the Bruhat graph of S_{n} from u to v of length 2.

The answer is also known to be yes if the interval [u, v] is a lattice [11, Theorem 6.3].

Theorem 21 Let u, v ∈ S_{n}, u ≤ v, be such that [u, v] is a lattice. Then R_{u,v}(q) = (q −1)^{l(v)−l(u)} (equivalently, P_{u,v}(q) is the “toric h-vector” of [u, v]^{∗}).

Also the property “P_{u,v} = 1” is known to depend only on the poset [u, v]. Given u, v ∈ S_{n}, u ≤ v let

def(u, v) =^{def} |{(i, j) ∈ T : u < u(i, j) ≤ v}|

(so this is the outdegree of u in the subgraph induced by the Bruhat graph on [u, v]).

The following theorem is due to Carrell and Peterson [18, Theorem C].

Theorem 22 Let u, v ∈ S_{n}, u ≤ v. Then the following are equivalent:

i) P_{u,v}(q) = 1;

ii) P_{x,v}(q) = 1 for all x ∈ [u, v];

iii) def(x, v) = l(v) − l(x) for all x ∈ [u, v].

This result suggests that the Kazhdan-Lusztig polynomials should depend on the outdegrees of the directed graph induced by the Bruhat graph on the interval. However, examples show that even if the property “the coefficient of q in P_{u,v} is nonzero” depends only on these outdegrees, the dependence is hard to guess.

3.1 Special matchings

Let’s go back at the beginning. Theorem 4 implies that the Kazhdan-Lusztig polynomials {P_{x,y}}_{x,y∈[u,v]} depend only on the Bruhat interval [u, v] as a poset if and only if this is true for the polynomials {R_{x,y}}_{x,y∈[u,v]}. Since these polynomials are better understood (we know a combinatorial interpretation for them, we know their degrees and leading term...), maybe we should concentrate on them. Let’s take a second look at the fundamental recursion satisfied by these polynomials, namely Theorem 2. This shows that the answer would be yes if one could somehow construct combinatorially, from the poset [u, v], the elements us and vs.

Unfortunately, this is impossible even if u is the identity....

Example 23 Let v = 4123 and u = 1234 (the identity). Then [u, v] is

[figure: 1243; 1234; 1423; 4123; 3124; 2134; 2143; 1324]

Figure 5: The interval [1234, 4123].

and v has only one descent: s = (1, 2). This choice gives the two elements

[figure]

However, this pair is combinatorially indistinguishible from the pair

[figure]

and there is no s ∈ S such that y = vs, x = us.

Actually, for any s ∈ D(v), the map x ↦ xs for x ∈ [e, v] is a complete matching of the Hasse diagram of the poset [e, v]. So the natural question is:

Do these matchings x ↦ xs have any special property?

From known properties of the Bruhat order (see, e.g., [31]), one knows that:

if x ⊲ y and s ∈ S is such that xs ≠ y then xs ≤ ys.

This motivates the following definition. Let P be (any) poset, and M be a complete matching of the Hasse diagram of P. For x ∈ P denote by M(x) the match of x.

Definition 24 We say that M is a special matching if, for all x, y ∈ P, such that M(x) ≠ y, we have that

x ⊲ y ⇒ M(x) ≤ M(y).

Note that this implies, in particular, that if x ⊲ y and M(x) ⊳ x then M(y) ⊳ y and M(y) ⊳ M(x), and dually that if x ⊲ y and M(y) ⊲ y then M(x) ⊲ x and M(x) ⊲ M(y) (see Figures 8 and 9). This concept was first introduced in [15].

Example 25 Let P be a Boolean algebra of rank 3. Then the matching shown in Figure 6 is special, while that shown in Figure 7 is not.

[figure]

Figure 6: A special matching.

[figure]

Figure 7: A matching that is not special.

[figure: y; x; M(x)] ⇒ [figure: M(x); x; y; M(y)]

Figure 8.

[figure: x; y; M(y)] ⇒ [figure: M(x); x; y; M(y)]

Figure 9.

[figure: M(x); x; y; M(y)]

Figure 10: This configuration is always allowed in a special matching.

[figure: y; x; M(x); M(y)]

Figure 11: This configuration is never allowed in a special matching.

3.2 Combinatorial invariance

The natural question now is:

Is any special matching of [e, v] of the form x ↦ xs for some s ∈ D(v) ?

Again, the answer is no!

Example 26 Let v = 4123. Then the poset [e, v] is shown in Figure 5, and D(v) = {(1, 2)}, so the only matching of the form x ↦ xs is the one indicated in Figure 12.

But this poset has two other special matchings, namely those shown in Figure 13, and these are combinatorially indistinguishable from the first one!

[figure: 1243; 1234; 1423; 4123; 3124; 2134; 2143; 1324]

Figure 12

[figure]

Figure 13

Nonetheless, remarkably, the following holds ([15, Theorem 5.2]).

Theorem 27 Let v ∈ S_{n}, and M be a special matching of [e, v]. Then

R_{u,v}(q) = \{ \begin{matrix}R_{M(u),M(v)}(q), & if M(u) ⊲ u, \\ qR_{M(u),M(v)}(q) + (q − 1)R_{u,M(v)}(q), & if M(u) ⊳ u, \end{matrix}  (7)

for all u ∈ [e, v]. So the polynomials R_{x,y}(q)_{x,y∈[e,v]} (and hence P_{x,y}(q)_{x,y∈[e,v]}, and hence the intersection homology of the Schubert variety \overline{Ω}_{v} ) depend only on [e, v] as an abstract poset.

We conclude this section by illustrating Theorem 27 with an example.

[figure: 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18]

Figure 14: A lower interval in a symmetric group.

Example 28 Let P = [e, v] be the lower interval whose Hasse diagram is depicted in Figure 14. (We ask the reader to trust the author on the fact that this poset P is indeed the lower interval of a permutation v, we do not give v since the point of the example is exactly to show how one can compute the polynomials from the poset rather than from the permutation.) Identify, for convenience, the elements of P with the integers from 1 to 18 as in Figure 14. According to Theorem 27, we need to find a special matching M of P. Suppose M(1) = 2. Then this forces M(4) = 9. We have two possible choices for M(3), namely 7 and 8. Suppose we choose M(3) = 7. Then these choices force M = {{1, 2}, {3, 7}, {4, 9}, {5, 14}, {6, 12}, {8, 13}, {10, 15}, {11, 17}, {16, 18}}.

Applying Theorem 27 we obtain that

R_{1,18} = q R_{M(1),M(18)} + (q − 1)R_{1,M(18)} = qR_{2,16} + (q − 1)R_{1,16}

(as well as R_{2,18} = R_{1,16}, R_{3,18} = qR_{7,16} + (q − 1)R_{3,16}, R_{4,18} = qR_{9,16} + (q − 1)R_{4,16}, R_{5,18} = qR_{14,16} + (q − 1)R_{5,16} = (q − 1)R_{5,16}, R_{6,18} = qR_{12,16} + (q − 1)R_{6,16}, R_{7,18} = R_{3,16}, R_{8,18} = qR_{13,16} + (q − 1)R_{8,16}, and similarly R_{9,18} = R_{4,16}, R_{10,18} = (q − 1)R_{10,16}, R_{11,18} = (q − 1)R_{11,16}, R_{12,18} = R_{6,16}, R_{13,18} = R_{8,16}, R_{14,18} = R_{5,16}, R_{15,18} = R_{10,16}, R_{16,18} = (q − 1)R_{16,16}, R_{17,18} = R_{11,16}). We therefore need to compute the polynomials R_{u,16} for all u ≤ 16. Since M is not a special matching of [1, 16] (= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 16} we need to repeat the above procedure to find a special matching, N, of [1, 16]. Suppose that N(1) = 3. This forces N(2) ∈ {7, 8}, and N(4) ∈ {5, 6}. Suppose we choose N(2) = 7 and N(4) = 6 (with some of the other choices we would have gotten stuck later on, however, it can be proved [15, Prop. 4.1], that there is always at least one right choice). Then these choices force N = {{1, 3}, {2, 7}, {4, 6}, {5, 10}, {8, 13}, {9, 12}, {11, 16}}. Applying Theorem 27 we get

R_{1,16} = q R_{3,11} + (q − 1)R_{1,11},
R_{2,16} = (q − 1)R_{2,11},

(as well as R_{3,16} = R_{1,11}, R_{4,16} = (q − 1)R_{4,11}, R_{5,16} = (q − 1)R_{5,11}, R_{6,16} = R_{4,11}, R_{7,16} = R_{2,11}, R_{8,16} = (q − 1)R_{8,11}, R_{9,16} = (q − 1)R_{9,11}, R_{10,16} = R_{5,11}, R_{11,16} = (q − 1)R_{11,11}, R_{12,16} = R_{9,11}, R_{13,16} = R_{8,11} ). We now need to compute the polynomials R_{u,11} for all u ∈ [1, 11] (= {1, 2, 3, 4, 5, 8, 9, 11}). We need a special matching, L, of [1, 11]. One such is L = {{1, 2}, {3, 8}, {4, 9}, {5, 11}}. So by Theorem 27

R_{1,11} = (q − 1)R_{1,5},
R_{2,11} = R_{1,5},
R_{3,11} = (q − 1)R_{3,5},

(as well as R_{4,11} = (q−1)R_{4,5}, R_{5,11} = (q−1)R_{5,5}, R_{8,11} = R_{3,5}, R_{9,11} = R_{4,5}). A special matching of [1, 5] (= {1, 3, 4, 5}) is {{1, 3}, {4, 5}} so from Theorem 27 we get

R_{1,5} = (q − 1)R_{1,4}, R_{3,5} = R_{1,4}, R_{4,5} = (q − 1)R_{4,4}.

Finally, {{1, 4}} is a special matching of [1, 4] (= {1, 4}) and so again by Theorem 27 we obtain R_{1,4} = (q − 1)R_{1,1}. Putting all these relations together we then get

R_{1,18} = q R_{2,16} + (q − 1)R_{1,16}
= q(q − 1)R_{2,11} + (q − 1)(q R_{3,11} + (q − 1)R_{1,11})
= q(q − 1)R_{1,5} + q(q − 1)^{2}R_{3,5} + (q − 1)^{3}R_{1,5}
= q(q − 1)^{2}R_{1,4} + q(q − 1)^{2}R_{1,4} + (q − 1)^{4}R_{1,4}
= 2q(q − 1)^{3} + (q − 1)^{5},

and similarly for all the other polynomials R_{u,18}. Clearly, in the same way we may compute all the polynomials R_{u,v} for u, v ∈ P, u ≤ v. The computation of the Kazhdan-Lusztig polynomials P_{u,v} for u, v ∈ P, u ≤ v, now proceeds using Theorem 4 and induction on l(u, v), just as in Example 5.

3.3 Open Problems

There are several open problems raised by the definition of a special matching. We mention in this section the most outstanding ones, in the author’s opinion.

Problem 29 Which posets have special matchings?

We expect the answer to this question to be rather subtle. For example. The Boolean algebra of rank 3 (also called a 3-crown) has three special matchings, but the poset in Figure 15 (usually called a 4-crown) does not have any special matchings.

[figure]

Figure 15

Given a poset P that has a special matching, it is clear that one could use Theorem 27 to define R-polynomials (and therefore Kazhdan-Lusztig polynomials) for P. Of course, if P has more than one special matching then this definition may turn out to depend on the choice of special matchings. A natural problem is then the following.

Problem 30 For which posets does Theorem 27 give a definition that is independent of the choice of special matching?

The answer to this problem is known to be yes if P is an Eulerian lattice (see [15, Prop. 4.3]), in which case the corresponding “Kazhdan-Lusztig” polynomial turns out to coincide with the toric h-vector of P.

It is well known (see, e.g., [31, §§7.14-7.15]) that the coefficient \overline{μ}(u, v) is often the most important one for the applications of Kazhdan-Lusztig polynomials to representation theory. Based on numerical evidence, I feel that the following may hold.

Conjecture 31 Let u, v ∈ S_{n}, u ≤ v, be such that l(u, v) is odd. Then \overline{μ}(u, v) ≠ 0 if and only if [u, v] does not have a special matching.

This conjecture has been verified for l(u, v) ≤ 5.

Since the statement in Theorem 27 makes sense verbatim for any Coxeter group, one may conjecture the following.

Conjecture 32 Theorem 27 holds for any Coxeter group.

Finally, we conclude with a conjecture which has already been made in [15].

Conjecture 33 Theorem 27 holds for any element u ∈ S_{n} (not just for u equals the identity permutation).

In other words, I conjecture that if u, v ∈ S_{n} are such that [u, v] has a special matching then

R_{a,v} = q^{1−c}R_{M(a),M(v)} + (q − q^{c})R_{a,M(v)}

for all a ∈ [u, v] and any special matching M of [u, v], where c =^{def} 1 if M(a) ⊲ a and c =^{def} 0 if M(a) ⊳ a.

Of course, not all reasonable conjectures turn out to be true (see, e.g., [44]). Note added in proof: Conjecture 32 has been proved for all doubly laced

Coxeter systems by F. Brenti, F. Caselli, M. Marietti, Special matchings and Kazhdan-Lusztig polynomials for doubly laced Coxeter systems, preprint. The second part of Theorem 27 has also been proved, independently, by F. Du Cloux, Rigidity of Schubert closures and invariance of Kazhdan-Lusztig polynomials, Advances in Math., to appear.

References

[1] H. H. Andersen, The irreducible characters for semi-simple algebraic groups and for quantum groups, Proceedings of the International Congress of Mathematicians, Zürich, 1994, 732-743, Birkhäuser, Basel, Switzerland, 1995.

[2] A. Beilinson, J. Bernstein, Localisation de g-modules, C. R. Acad. Sci. Paris, 292 (1981), 15-18.

[3] S. Billey, V. Lakshmibai, Singular loci of Schubert varieties, Progress in Math., 182, Birkhäuser, Boston, MA, 2000.

[4] S. Billey, A. Postnikov, A root system description of pattern avoidance with applications to G/B, preprint.

[5] S. Billey, G. Warrington, Kazhdan-Lusztig polynomials for 321-hexagon-avoiding permutations, J. Algebraic Combin., 13 (2001), 111-136.

[6] S. Billey, G. Warrington, Maximal singular loci for Schubert varieties in SL(n)/B, Trans. Amer. Math. Soc., to appear.

[7] A. Björner and M. Wachs, Bruhat order of Coxeter groups and shellability, Advances in Math. 43 (1982), 87–100.

[8] B. D. Boe, Kazhdan-Lusztig polynonomials for Hermitian symmetric spaces, Trans. Amer. Math. Soc. 309 (1988), 279–294.

[9] T. Braden, R. MacPherson, From moment graphs to intersection cohomology, Math. Ann., 321 (2001), 533-551.

[10] F. Brenti, Combinatorial properties of the Kazhdan-Lusztig R-polynomials for S_{n}, Adv. in Math., 126 (1997), 21-51.

[11] F. Brenti, A combinatorial formula for Kazhdan-Lusztig polynomials, Invent. Math., 118 (1994), 371-394.

[12] F. Brenti, Lattice paths and Kazhdan-Lusztig polynomials, J. Amer. Math. Soc., 11 (1998), 229-259.

[13] F. Brenti, R. Simion, Explicit formulae for some Kazhdan-Lusztig polynomials, J. Algebraic Combin., 11 (2000), 187-196.

[14] F. Brenti, Kazhdan-Lusztig and R-polynomials, Young’s lattice, and Dyck partitions, Pacific J. Math., 207 (2002), 257-286.

[15] F. Brenti, A combinatorial construction for the Kazhdan-Lusztig polynomials of the symmetric group, preprint, available at http://www.mat.uniroma2.it/∼brenti/papers.htm

[16] J.-L. Brylinski, M. Kashiwara, Kazhdan-Lusztig conjecture and holonomic system, Invent. Math. 64 (1981), 387-410.

[17] F. Caselli, Proof of two conjectures of Brenti-Simion on Kazhdan-Lusztig polynomials, J. Algebraic Combin., to appear.

[18] J. Carrell, The Bruhat graph of a Coxeter group, a conjecture of Deodhar, and rational smoothness of Schubert varieties, Algebraic groups and their generalizations: classical methods (University Park, 1991), 53-61, Proc. Sympos. Pure Math. 56, Amer. Math. Soc., Providence, 1994.

[19] V. V. Deodhar, Some characterizations of Bruhat ordering on a Coxeter group and determination of the relative Möbius function, Invent. Math., 39 (1977), 187-198.

[20] V. V. Deodhar, On some geometric aspects of Bruhat orderings. I. A finer decomposition of Bruhat cells, Invent. Math. 79 (1985), 499-511.

[21] V. V. Deodhar, A combinatorial setting for questions in Kazhdan-Lusztig Theory, Geom. Dedicata, 36 (1990), 95-120.

[22] M. Dyer, Hecke algebras and reflections in Coxeter groups, Ph. D. Thesis, University of Sydney, 1987.

[23] M. Dyer, On the “Bruhat graph” of a Coxeter system, Comp. Math., 78 (1991), 185-191.

[24] M. Dyer, Hecke algebras and shellings of Bruhat intervals, Comp. Math., 89 (1993), 91-115.

[25] M. J. Dyer, On coefficients of q in Kazhdan-Lusztig polynomials, Algebraic groups and Lie groups, Austral. Math. Soc. Lect. Ser., 9, Cambridge Univ. Press, Cambridge, 1997, 189-194.

[26] P. H. Edelman, The Bruhat order of the symmetric group is lexicographically shellable, Proc. Amer. Math. Soc., 82 (1981), 355-358.

[27] I. Frenkel, M. Khovanov, A. Kirillov, Kazhdan-Lusztig polynomials and canonical basis, Transform. Groups, 3 (1998), 321-336.

[28] W. Fulton, Young tableaux. With applications to representation theory and geometry. London Mathematical Society Student Texts 35, Cambridge University Press, Cambridge, 1997.

[29] M. Goresky, R. MacPherson, Intersection homology theory, Topology, 19 (1983), 135-162.

[30] M. Haiman, Hecke algebra characters and immanant conjectures, J. Amer. Math. Soc., 6 (1993), 569-595.

[31] J. E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge Studies in Advanced Mathematics, no.29, Cambridge Univ. Press, Cambridge, 1990.

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

[33] D. Kazhdan, G. Lusztig, Schubert varieties and Poincaré duality, Geometry of the Laplace operator, Proc. Sympos. Pure Math. 34, Amer. Math. Soc., Providence, RI, 1980, pp. 185-203.

[34] A. Kirillov, A. Lascoux, Factorization of Kazhdan-Lusztig elements for Grassmannians, Adv. Studies in Pure Math., 28 (2000), 143-154.

[35] F. Kirwan, An introduction to intersection homology theory, Research Notes in Math., 187, Pitman, 1988.

[36] V. Lakshmibai, B. Sandhya, Criterion for smoothness of Schubert varieties in S_{l(n)/B}, Proc. Indian Acad. Sci. Math. Sci., 100 (1990), 45-52.

[37] A. Lascoux, Polynômes de Kazhdan-Lusztig pour les variétés de Schubert vexillaires, C. R. Acad. Sci. Paris Sr. I Math., 321 (1995), 667-670.

[38] A. Lascoux, M.-P. Schützenberger, Polynômes de Kazhdan & Lusztig pour les grassmanniennes, Young tableaux and Schur functions in algebra and geometry, Astérisque, 87-88 (1981), pp. 249-266.

[39] A. Lascoux, M.-P. Schützenberger, Treillis et bases des groupes de Coxeter, Electron. J. Combin., 3(1996), #27, 35pp.

[40] B. Leclerc, J.-Y. Thibon, Littlewood-Richardson coefficients and Kazhdan-Lusztig polynomials, Adv. Studies in Pure Math., 28 (2000), 155-220.

[41] G. Lusztig, private communication, September 1993.

[42] I. G. Macdonald, Notes on Schubert Polynomials, Publ. du LACIM 6, Univ. du Québec, Montréal, 1991.

[43] M. Marietti, Closed product formulas for certain R-polynomials, Europ. J. Combinatorics, 23 (2002), 57-62.

[44] T. McLarnan, G. Warrington, Counterexamples to the 0-1 conjecture, Representation Theory, 7 (2003), 181-195.

[45] P. Polo, Construction of arbitrary Kazhdan-Lusztig polynomials in symmetric groups, Representation Theory, 3 (1999), 90-104.

[46] R. A. Proctor, Classical Bruhat orders and lexicographic shellability, J. Algebra, 77 (1982), 104-126.

[47] B. Shapiro, M. Shapiro, A. Vainshtein, Kazhdan-Lusztig polynomials for certain varieties of incomplete flags, Discrete Math., 180 (1998), 345-355.

[48] R. P. Stanley, Enumerative Combinatorics , vol.1, Wadsworth and Brooks/Cole, Monterey, CA, 1986.

[49] H. Tagawa, On the non-negativity of the first coefficient of Kazhdan-Lusztig polynomials, J. Algebra, 177 (1995), 698-707.

[50] D. Uglov, Canonical bases of higher level q-deformed Fock spaces and Kazhdan-Lusztig polynomials, Physical Combinatorics, Progress in Math., 191, Birkhäuser, Boston, MA, 2000, 249-299.

[51] D.-N. Verma, Möbius inversion for the Bruhat order on a Weyl group, Ann. Sci. École Norm. Sup., 4 (1971), 393-398.

[52] A. Zelevinski, Small resolutions of singularities of Schubert varieties, Funct. Anal. Appl., 17 (1983), 142-144.