\documentclass[12pt]{article}
\usepackage{amssymb,latexsym}
\usepackage{epsf,epsfig,amsmath}
\usepackage{lscape} 
\newtheorem{thm}{Theorem}
\newtheorem{pro}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{con}[thm]{Conjecture}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{probl}[thm]{Problem}
\newtheorem{exe}[thm]{Example}
\newtheorem{defi}[thm]{Definition}
\usepackage{color}
\newcommand{\LL}{l}
\begin{document}

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8
\font\its=cmti8
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 49 \rms (2003), Article~B49b\hfill}
\def\thepage{}
%
%

\begin{center}
{\Large \bf Kazhdan-Lusztig polynomials: History \\
Problems, and Combinatorial Invariance }
 \vspace{0.8cm} \\
 Francesco Brenti\footnote{Partially supported by the EC's IHRP
Program, within the Research Training Network ``Algebraic Combinatorics
in Europe'', grant HPRN-CT-2001-00272.} \\
Dipartimento di Matematica \\
Universit\'{a} di Roma ``Tor Vergata''\\
Via della Ricerca Scientifica \\
00133 Roma, Italy
\end{center}


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 $R$-polynomials depend only
on a certain poset, and mention some open problems and conjectures related
to this. 

Most of the results in \S 1 hold for all Coxeter
groups (see \cite{Hum}) 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.

\section{History}

\subsection{Pre-History (i.e., the symmetric group)}

Let $[n] = \{ 1, \ldots , n \}$, and
\[ S_{n} =\{ \sigma : [n] \rightarrow  [n] : \; \sigma  \;  \mbox{is a bijection} \} \]

We write elements of $S_{n}$ in three ways, namely:
\begin{itemize}
\item {\em disjoint cycle form} (e.g., $\sigma =(7,5,2)(1,3)$) ;
\item {\em one-line notation} (e.g., $\sigma =3714265  $);
(Meaning that $\sigma(1)=3$, $\sigma(2)=7$, etc...)
\item matrix (e.g.
\[ \sigma = \left[ \begin{array}{ccccccc}
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{array} \right] ). \]
\end{itemize}

There are two important subsets for this story:
\[ S = \{ (1,2),(2,3), \ldots , (n-1,n) \} \]
and
\[ T = \{ (i,j): \; 1 \leq i <j \leq n \}. \]

Note that 
\begin{center}
$\sigma (i,j)$ switches $\sigma (i)$ and $\sigma (j)$,
\end{center}
while
\begin{center}
$(i,j) \sigma $ switches $i$ and $j$,
\end{center}
in the one-line notation of $\sigma$.

There are also two important statistics. 
For $\sigma \in S_{n}$ let
\[ \mbox{inv}(\sigma) =| \{  (i,j) \in [n]^{2}: i<j, \; \sigma (i) > \sigma (j) \} | \]
(number {\em inversions} of $\sigma$, or {\em length} of $\sigma$, denoted 
$l(\sigma )$) and
\[ D(\sigma ) = \{ (i,i+1) \in S : \; \sigma (i) > \sigma (i+1)\} 
(\Leftrightarrow l(\sigma(i,i+1)) < l(\sigma ) ) \]
({\em descent set} of $\sigma $ ). 



%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
%\markboth{\SMALL ROLAND BACHER AND LAURENT MANIVEL}{\SMALL HOOKS AND POWERS OF\ PARTS IN PARTITIONS}
%
%

\subsection{Bruhat graph and Bruhat order}

There are two main combinatorial objects related to Kazhdan-Lusztig and
$R$-polynomials. 

The {\em Bruhat graph} of $S_{n}$ is the directed graph $B(S_{n})$ having $S_{n}$ as 
vertex set and where 
$$u \rightarrow v$$ 
 if and only if 
\begin{center} there exist $(i,j) \in T$ such
that $v =u(i,j)$ and $l(v) >l(u)$ 
\end{center}
(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.
\begin{center}
\begin{picture}(80,80)(-30,-30)
\put(0,0){\vector(2,1){25}}
\put(0,0){\vector(-2,1){25}}
\put(0,0){\line(2,-1){25}}
\put(0,0){\line(-2,-1){25}}
\put(0,-25){\vector(0,10){50}}
\put(25,20){\vector(-3,2){15}}
\put(-25,20){\vector(3,2){15}}
\put(10,-30){\vector(3,2){15}}
\put(-10,-30){\vector(-3,2){15}}
\put(35,-8){\vector(0,1){18}}
\put(-35,-8){\vector(0,1){18}}
\put(0,-35){\makebox(0,0){123}}
\put(0,35){\makebox(0,0){321}}
\put(-35,-15){\makebox(0,0){213}}
\put(-35,15){\makebox(0,0){312}}
\put(35,-15){\makebox(0,0){132}}
\put(35,15){\makebox(0,0){231}}
\end{picture}
\end{center}
\begin{center}
Figure 1: The Bruhat graph of $S_{3}$.
\end{center}

Note that this digraph is always acyclic.

The transitive closure of $B(S_{n})$ is the {\em Bruhat order} of $S_{n}$, 
denoted by $\leq $.

For example, the Bruhat order of $S_{3}$ is shown in Figure 2.

\begin{center}
\begin{picture}(40,50)
\put(20,10){\line(1,1){10}}
\put(20,10){\line(-1,1){10}}
\put(10,20){\line(0,1){10}}
\put(10,30){\line(1,1){10}}
\put(20,40){\line(1,-1){10}}
\put(30,30){\line(0,-1){10}}
\put(10,20){\line(2,1){20}}
\put(10,30){\line(2,-1){20}}
\put(20,10){\circle*{2}}
\put(10,20){\circle*{2}}
\put(10,30){\circle*{2}}
\put(20,40){\circle*{2}}
\put(30,30){\circle*{2}}
\put(30,20){\circle*{2}}
\put(20,5){\makebox(0,0){$\scriptstyle 123$}}
\put(20,45){\makebox(0,0){$\scriptstyle 321$}}
\put(39,20){\makebox(0,0){$\scriptstyle 213$}}
\put(39,30){\makebox(0,0){$\scriptstyle 312$}}
\put(1,20){\makebox(0,0){$\scriptstyle 132$}}
\put(1,30){\makebox(0,0){$\scriptstyle 231$}}
\end{picture}
\end{center}
\begin{center}
Figure 2: The Bruhat order of $S_{3}$.
\end{center}


One immediate problem presents itself. Namely,
\begin{center}
Given $u,v \in S_{n}$, how to decide if $u$ and $v$ are comparable?
\end{center}


For $v \in S_{n}$ and $i,j \in [n]$ let
\[ v[i,j] \stackrel{\rm def}{=} |\{ a \leq i : \;  v(a) \geq 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). 
\[
\left[ \begin{array}{ccccccc}
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{array} \right]  
\]
\begin{center}
Figure 3.
\end{center}

We then have the following result (see, e.g., \cite[Chap. 1]{Mac}, or
\cite[\S 10.5]{Ful})
\begin{thm}
\label{u.2}
Let $u,v \in S_{n}$. Then $ u \leq v$ if and only if $u [i,j] \leq v[i,j]$ for all
$i,j \in [n]$.
\end{thm}

We conclude this section by mentioning some important 
\begin{flushleft}
{\bf Facts about Bruhat order}
\end{flushleft} 

\begin{itemize}
\item Bruhat order is a graded poset and inv is its rank function;
\item Bruhat order is Eulerian (i.e., $\mu (u,v) =(-1)^{l(v)-l(u)}$ for every $u,v$);
\item Bruhat order is shellable.
\end{itemize}

\noindent 
Proofs of the preceding results can be found in
\cite{BW}, \cite{Deo1}, \cite{Ede}, \cite{Hum}, \cite{Pro}, or \cite{Ver}.

Given $u,v \in S_{n}$ we let 
$$ [u,v] = \{ a \in S_{n} : u \leq a \leq v \}, $$
$ l(u,v) \stackrel{\rm def}{=} l(v)-l(u)$, and write $u \lhd v$ if $|[u,v]|=2$.


\subsection{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 \cite{K-L} in order to construct representations of the 
associated Hecke algebra, which is a deformation of the group algebra. Namely, it
is the free ${\bf Z}[q,q^{-1}]$-module $\cal H$
having $\{ T_{w} \}_{w \in S_{n}}$ as a formal
basis and multiplication such that
\[ T_{w}T_{s} = \left\{ \begin{array}{ll} 
T_{ws} , & \mbox{if $s \not \in D(w)$,} \\
q T_{ws}+(q-1)T , & \mbox{if $s \in D(w)$,}
\end{array} \right. \]
for all $w \in W$ and $s \in S$ (so, for $q=1$, this is the multiplication of the
group algebra).
(We refer the interested reader to \cite[Chap. 7]{Hum} 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 \cite{K-L}).

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., \cite{And} and the references cited there), the theory
of Verma modules (see, e.g., \cite{BB}, \cite{BK}), the algebraic
geometry and topology of Schubert varieties (see, e.g., \cite{KL2}, \cite{La-Se},
\cite{BL}), canonical bases (\cite{FKK}, \cite{Ug}), 
and immanant inequalities (\cite{Ha}). 
We say something more precise about some of these applications in \S 2.1.

Despite the plethora of applications that they have, all these polynomials can be
defined using only the elementary notions introduced in \S \S 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''.

\begin{thm} \label{8.1.1} 
There is a unique family of  polynomials 
$\{ R_{u,v}(q) \} _{u,v \in S_{n}} \subseteq {\mathbb Z}[q]$ 
satisfying the following conditions: \begin{description} 
\item[i)] $R_{u,v}(q)=0$ if $u \not \leq v$; 
\item[ii)] $R_{u,v}(q)=1$ if $u=v$; 
\item[iii)] if $s \in D(v)$ then 
\begin{equation} 
\label{8.1.1.0} 
R_{u,v}(q) = \left\{ \begin{array}{ll} R_{us,vs}(q), & 
\mbox{if $s \in D(u)$,} \\ qR_{us,vs}(q)+(q-1)R_{u,vs}(q), & 
\mbox{if $s \not \in D(u)$.} \end{array} \right.  
\end{equation} \end{description} 
\end{thm}  

A proof of the preceding theorem can be found in 
\cite[\S 7.5]{Hum}. The polynomials whose existence and uniqueness are guaranteed by  
Theorem \ref{8.1.1} are called the {\em $R$-polynomials} 
\index{$R$-polynomial} of $S_{n}$.   Theorem \ref{8.1.1} can be used to 
compute the polynomials $\{ R_{u,v}(q) \} _{u,v \in W}$, by induction on 
$\LL(v)$. In fact, if $v \neq e$ it is possible to find some  $s \in D(v)$, 
and then since $\LL(vs)<\LL(v)$  we may assume by induction  that we have already 
computed all the $R$-polynomials appearing on the right hand side of (\ref{8.1.1.0}).  
Thus we may use part  iii)  of Theorem \ref{8.1.1}  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.

\begin{exe} 
Suppose that we want to compute 
$R_{123,321}(q)$ in $S_{3}$. Choosing $s=(1,2) \in D(321)$ we have 
from part iii) of Theorem  \ref{8.1.1} that 
\[ R_{123,321}(q)=q \, R_{213,231}(q)+(q-1) \,R_{123,231}(q) . \] 
Now choosing $s=(2,3) \in D(231)$ we obtain that  
\[ R_{213,231}(q)= q \, R_{231,213}(q) +(q-1) \, R_{213,213}(q) =q-1 , \]   
and 
\begin{eqnarray*}  
R_{123,231}(q)  =  q \, R_{132,213}(q) +(q-1) \, R_{123,213}(q) \\  
=   (q-1) \, R_{123,213}(q)   \end{eqnarray*}  
by  Theorem \ref{8.1.1}.   
Finally, choosing $s=(1,2) \in 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 \ref{8.1.1}. Therefore we conclude that  
\[ R_{123,321}(q) = q \, (q-1)+(q-1)^{3} =q^{3}-2q^{2}+2q-1 . \] 
\end{exe}
 
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 \ref{8.1.1}, by induction
on $\LL(v)$. 
\vspace{0.2cm} 
\begin{flushleft}
{\bf Easy Properties of $R$-polynomials}  
\end{flushleft}

\begin{itemize}
\item 
$R_{u,v}(q)$ is a monic polynomial  of degree  $l(u,v)$.
\item  
$R_{u,v}(0)=(-1)^{\LL(u,v)}$. 
\item 
$q^{l(u,v)}R_{u,v}(1/q)=(-1)^{\LL(u,v)}R_{u,v}(q)$. 
\end{itemize}

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

\begin{thm}  
\label{8.1.2}  
There exists a unique family of   
polynomials $\{ P_{u,v}(q) \} _{u,v \in S_{n}} \subseteq {\mathbb Z}[q]$   
satisfying the following conditions:  
\begin{description}  
\item[i)] $P_{u,v}(q)=0$ if $u \not \leq v$;  
\item[ii)] $P_{u,v}(q)=1$ if $u=v$;  
\item[iii)] deg$(P_{u,v}(q)) < \frac{1}{2} \LL(u,v)$ if $u<v$;  
\item[iv)]   
\[ q^{\LL(u,v)} \, P_{u,v} \left( \frac{1}{q} \right) = 
\sum _{u \leq a \leq v} R_{u,a}(q) \, P _{a,v} (q) \]  if $u \leq v$.  
\end{description}  
\end{thm}    

The preceding theorem was first proved in
\cite{K-L} and a proof of it can also be found
in \cite[\S 7.10]{Hum}. The polynomials $\{ P_{u,v}(q) \} _{u,v \in S_{n}}$ whose  
existence and uniqueness are guaranteed by   
Theorem \ref{8.1.2} are called the {\em Kazhdan-Lusztig polynomials}  
of $S_{n}$.

Here is an easy property of the Kazhdan-Lusztig polynomials.
\begin{flushleft}
{\bf Easy Properties of $KL$-polynomials}  
\end{flushleft}

\begin{itemize}
\item  
$P_{u,v}(0)=1$. 
\end{itemize}

To help the reader get a feeling for how one works with Theorem \ref{8.1.2}
we provide the proof of this fact here.

We proceed by induction on $\LL(u,v)$, the result being true by part ii)  
of Theorem \ref{8.1.2} if $\LL(u,v)=0$. So let    $\LL(u,v)>0$. 
Then we conclude from parts iii) and iv) of Theorem  \ref{8.1.2} that  
\[ 0  = \sum _{u \leq a \leq 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) = - \sum _{u<a \leq v} (-1)^{\LL(u,a)} . \]  
Now using one of the fundamental facts about Bruhat order 
we conclude from this that   
\[ P_{u,v}(0) = - \sum _{u<a \leq v} \mu (u,a) = \mu (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\"{o}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 \; \; \mbox{ if } \; \;  \LL(u,v) \leq 2.  \]

Once the $R$-polynomials have been computed,    
then Theorem \ref{8.1.2} can be used  to compute recursively the polynomials 
$\{ P_{u,v}(q)\} _{u,v \in S_{n}}$,  by induction on $\LL(u,v)$. In fact, by 
induction  we may assume that  we have already computed the polynomials  
$P_{a,v}(q)$ for all  $a \in [u,v]$, $a \neq u$. This, by part iv) of 
Theorem \ref{8.1.2},  means that we can compute   
\begin{equation}  \label{8.1.2.2}  
q^{\LL(u,v)} \, P_{u,v} \left( \frac{1}{q} \right) -P_{u,v}(q)   
\end{equation}  
(recall that $R_{u,u}(q)=1$ by part ii) of Theorem \ref{8.1.1}).   
However,  by  part iii) of Theorem \ref{8.1.2}, the coefficient of $q^{i}$ in   
(\ref{8.1.2.2}) is the  same as the coefficient of $q^{i}$ in $-P_{u,v}(q)$ for 
all  $i =0,   \ldots , \left\lfloor \frac{1}{2}(\LL(u,v)-1) \right\rfloor$ 
(we  assume that $u<v$ for else we already know $P_{u,v}(q)$ by parts i)  
and ii) of Theorem \ref{8.1.2}) and thus we can compute $P_{u,v}(q)$ from   
(\ref{8.1.2.2}).  
We illustrate this procedure with an example.

\begin{exe}
\label{ex1}
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 \ref{8.1.2} and what we have just observed   
 we know that $P_{u,321}(q)   =1$ for all $u \in S_{3} \setminus \{ 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} (\LL(321)-\LL(123)) =\frac{3}{2}$, we deduce from this, 
by part iii) of Theorem \ref{8.1.2}, that   \[ P_{123,321}(q)=1 \, . \]  
\end{exe}


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. 

\begin{thm} \label{8.1.3} 
Let  $u,v \in S_{n}$, $u \leq v$, and $s \in D(v)$. 
Then \begin{equation} \label{8.1.3.1} 
P_{u,v}(q)  =  q^{1-c} P_{us,vs} (q) + q^{c} P_{u,vs} (q)  
- \sum _{\{ z : \; s \in D(z) \} } q^{\frac{\LL (z,v)}{2}} \overline{\mu }(z,vs) 
P_{u,z}(q) 
\end{equation} 
where $c = 1$ if $s \in D(u)$, and  $c =0$ otherwise, and
$\overline{\mu}(x,y)$ is the coefficient of  
$q^{\frac{1}{2}(\LL(x,y)-1)}$ in $P_{x,y}(q)$ 
(so $\overline{\mu}(x,y)=0$  if $\LL(x,y)$ is even).
\end{thm}  
A proof of the preceding  result can be found in \cite[\S 7.11]{Hum}.  

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

\begin{flushleft}
{\bf More properties of $KL$ and $R$-polynomials}
\end{flushleft}

\begin{itemize}
\item 
$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 \ldots 3 \; \;  2 \; \; 1$);
\item 
$P_{u,v}=P_{u^{-1},v^{-1}}=P_{w_{0}uw_{0},w_{0}vw_{0}}$;
\item 
$\overline{\mu}(u,v)=\overline{\mu}(w_{0}v,w_{0}u)=\overline{\mu}(vw_{0},uw_{0})$.
\end{itemize}

\noindent 
Proofs of these results can be found in \cite[Prop. 7.6 and \S 7.13]{Hum}
and \cite[\S 4]{Bre94}. 
   
\section{Problems}

\subsection{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 \S 1.3,
Kazhdan-Lusztig polynomials play a prominent
role in several branches of mathematics including representation theory (see, e.g., 
\cite{And}, and the references cited there),
 and the algebraic geometry and topology of Schubert varieties (see, e.g.,
\cite{K-L}, \cite{KL2}, and \cite{BL}).

Here are the main connections to Schubert varieties.
For a permutation $v \in S_{n+1}$ let $\Omega _{v}$ be the Schubert cell indexed by $v$,
and $\overline{\Omega}_{v}$  (Zariski closure) be the corresponding Schubert variety
(we refer the reader to, e.g., \cite{Mac}, \cite{Ful}, or \cite{BL} for the 
definition of, and further information about, Schubert cells and varieties).
It is well known (and not hard to see) that $\overline{\Omega}_{v}= \biguplus _{u \leq v}
\Omega _{u}$ so that 
\begin{equation}
\label{BS}
u \leq v \Leftrightarrow \overline{\Omega}_{u}
\subseteq \overline{\Omega}_{v}.
\end{equation}
Denote by $IH^{\ast}(\overline{\Omega}_{v}, {\bf C})_{\Omega _{u}}$ the (middle
perversity) local intersection cohomology of $\overline{\Omega}_{v}$ at a (equivalently,
any) point of $\Omega _{u}$. This is a graded vector space, and we denote by $IH^{i}
(\overline{\Omega}_{v}, {\bf C})_{\Omega _{u}}$ ($i \in {\bf N}$) its graded pieces
(we refer the reader to, e.g., \cite{GM}, or \cite{Kir}, 
for further information about intersection (co)homology).
The following result was first proved by Kazhdan and Lusztig in \cite[Theorem 4.3]{KL2}.
\begin{thm}
\label{2.6}
Let $u,v \in S_{n+1}$, $ u \leq v$. Then
\[ P_{u,v}(q) = \sum _{i \geq 0} q^{i} \; \mbox{dim}_{\bf C} (IH^{2i} (\overline{\Omega}
_{v}, {\bf C})_{\Omega _{u}}). \]
\end{thm}
Note that it is known that dim$_{\bf C}(IH^{i}(\overline{\Omega}_{v}, {\bf C})_{\Omega
_{u}})=0$ if $i \equiv 1 \pmod{2}$. 

Theorem \ref{2.6} implies that the coefficients
of $P_{u,v}(q)$ are nonnegative for all $u,v \in S_{n}$ (something that 
Kazhdan and Lusztig had conjectured in \cite{K-L}). 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., \cite{KL2},
and \cite{BL}).
\begin{cor}
Let $v \in S_{n}$. Then
\[ \sum _{u \leq v} q^{l(u)} P_{u,v}(q) = \sum _{i \geq 0} \mbox{dim}_{\bf C} (IH^{2i}
(\overline{\Omega_{v}}))q^{i} \]
\end{cor}
\begin{thm}
Let $v \in S_{n}$. Then the following are equivalent:
\begin{description}
\item[i)] $P_{e,v}(q)=1$; 
\item[ii)] $\overline{\Omega _{v}}$ is smooth.
\end{description}
\end{thm}
What about the $R$-polynomials? Do they have any connections to
geometry? The following result is a simple consequence of the main
theorem in \cite{Deo2}.
\begin{thm}
Let $\bf F$ be a finite field of order $q$ and $u,v \in S_{n}$. Then
\[ R_{u,v }(q) =| \Omega _{v} \cap \Omega _{u} ^{\ast} | \]
where $\Omega ^{\ast }_{v}$ is the Shubert cell opposite to $\Omega _{v}$.
\end{thm}

In their original paper Kazhdan and Lusztig also conjectured (\cite[Conj. 1.5]{K-L}) 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 \cite{BB}, and by Brylinski and
Kashiwara \cite{BK}, and has then been generalized in various different directions 
(see, e.g., \cite[\S 4]{And}). 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:
\begin{center}
{\em How to compute these polynomials?}
\end{center}

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., \cite{BW01}, \cite{BW02}, \cite{BP},
\cite{Boe88}, \cite{Bre98}, \cite{BreSim}, \cite{Bre02},
\cite{Car94}, \cite{Cas},
\cite{Deo2}, \cite{Deo3},
\cite{Dy}, \cite{Dye97}, \cite{Ki-La}, \cite{L-S}, \cite{Le-Th}, \cite{Mar},
\cite{Pol99}, \cite{SSV}, \cite{Tag94a}, \cite{Zel}), and my
choice here is entirely subjective. 

\subsection{$R$-polynomials and increasing subsequences}

Let's begin with the following  easy observation.
\begin{lem}
Let $u,v \in S_{n}$, $u \leq v$. Then there exists a unique polynomial
$\widetilde{R}_{u,v} (t) \in {\bf N}[t]$ such that $R_{u,v}(q)=q^{\frac{l(v)-l(u)}{2}}
\widetilde{R}_{u,v} (q^{\frac{1}{2}}-q^{-\frac{1}{2}})$.
\end{lem}
{\bf Proof. } Easy induction, using Theorem \ref{8.1.1}. $\Box$

The combinatorics that we are about to describe relates to these 
$\widetilde{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 $\widetilde{R}_{u,v}(q)$ as follows. We first check
(e.g., using Theorem \ref{u.2}) that $u<v$ (if $u \not \leq v$ then $\widetilde{R}
_{u,v}(q) \stackrel{\rm def}{=}
0$, if $u=v$ then $\widetilde{R} _{u,v}(q) \stackrel{\rm 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 \ref{u.2}
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 $\widetilde{R}_{u,v}(q)$
is given by 
\begin{equation}
\label{3.0.1a}
 \widetilde{R}_{u,v}(t) =t \widetilde{R} _{u^{(1)},v}(t) +t^{2} \widetilde{R}
_{u^{(2)}, v}(t)+t^{2} \widetilde{R} _{u^{(3)},v}(t) +t^{3} \widetilde{R}
_{u^{(4)},v} (t) \, ,  
\end{equation}
(where the exponent of the power of $t$ that multiplies 
$\widetilde{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
$$ \widetilde{R}_{1234,4321}=t^{2}+t^{4}+t^{4}+t^{6}+t^{4}=t^{6}+3t^{4}+t^{2}.$$
\[
\begin{picture}(120,120)(-60,-40)
\put(-25,-30){\line(-2,1){10}}
\put(-35,-25){\vector(-3,2){15}}
\put(-15,-30){\vector(-1,3){5}}
\put(0,-30){\vector(1,3){5}}
\put(10,-30){\vector(4,3){20}}
\put(-55,0){\vector(1,2){35}}
\put(-20,30){\vector(1,4){10}}
\put(0,0){\vector(0,1){70}}
\put(-20,0){\vector(0,1){15}}
\put(10,0){\vector(2,3){10}}
\put(35,0){\vector(2,3){10}}
\put(25,30){\vector(-1,2){20}}
\put(50,30){\vector(-1,1){40}}
\put(-8,-37){\makebox(0,0){$ \scriptstyle 1234$}}
\put(-55,-8){\makebox(0,0){$ \scriptstyle 4231$}}
\put(-20,-8){\makebox(0,0){$ \scriptstyle 4213$}}
\put(5,-8){\makebox(0,0){$ \scriptstyle 4123$}}
\put(35,-8){\makebox(0,0){$ \scriptstyle 4132$}}
\put(-20,23){\makebox(0,0){$ \scriptstyle 4312$}}
\put(25,23){\makebox(0,0){$ \scriptstyle 4312$}}
\put(48,23){\makebox(0,0){$ \scriptstyle 4312$}}
\put(-3,78){\makebox(0,0){$ \scriptstyle 4321$}}
\put(-43,35){\makebox(0,0){$\scriptstyle t$}}
\put(-12,45){\makebox(0,0){$\scriptstyle t$}}
\put(4,35){\makebox(0,0){$\scriptstyle t$}}
\put(23,45){\makebox(0,0){$\scriptstyle t$}}
\put(43,45){\makebox(0,0){$\scriptstyle t$}}
\put(-23,8){\makebox(0,0){$\scriptstyle t$}}
\put(20,8){\makebox(0,0){$\scriptstyle t^{2}$}}
\put(43,8){\makebox(0,0){$\scriptstyle t$}}
\put(-48,-23){\makebox(0,0){$\scriptstyle t$}}
\put(-11,-23){\makebox(0,0){$\scriptstyle t^{2}$}}
\put(8,-23){\makebox(0,0){$ \scriptstyle t^{3}$}}
\put(30,-23){\makebox(0,0){$ \scriptstyle t^{2}$}}
\end{picture}
\]
\begin{center}
Figure 4.
\end{center}

\begin{flushleft}
{\em What is going on?}
\end{flushleft}

For $u,v \in S_{n}$, $u < v$, let 
\[ \delta= \mbox{max} \{ i: \; v^{-1}(i) \neq u^{-1} (i) \}. \]
Then one has (see, e.g., \cite{Bre97}).
\begin{lem}
Let $u < v$ then $v^{-1}(\delta) < u^{-1} (\delta)$.
\end{lem}

Now let ${\cal C}(u,v)$ be the set of all the increasing subsequences of $u$ that begin
at position $v^{-1}(\delta)$ and end at position $u^{-1}(\delta)$.

For example, let $v=7356142$ and $u=1425736$, then 
$d=7$, $u^{-1}(7)=5$, $v^{-1}(7)=1$
and 
$${\cal 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 ${\cal C}(u,v)$ as a cycle.

Then we have (see \cite{Bre97}):

\begin{thm}
\label{3.1}
Let $u,v \in S_{n}$, $u <v$. Then
\begin{equation}
\label{3.1.1}
 \widetilde{R} _{u,v} (q) = 
{\displaystyle \sum _{
w \in {\cal C}(u,v)}}  q^{k(w)-1}
\widetilde{R} _{wu,v}(q) 
\end{equation}
where $k(w) \stackrel{\rm def}{=} n- |\{ i \in [n] : \; w(i)=i \}|$.
\end{thm}

Note that, unlike the original recursion given by Theorem \ref{8.1.1},
this recursion does not ``branch off'' in two cases, and is therefore
very easy to solve (see, \cite[Theorem 4.1]{Bre97}). Furthermore, it is much faster 
from a computational point of view.


\subsection{Kazhdan-Lusztig polynomials and rooted trees}

Let $\sigma \in S_{n}$. We say that $\sigma$ is {\em bigrassmannian} if and only if
$|D(\sigma )|=|D(\sigma^{-1} )|=1$. Note that $\sigma$ is bigrassmannian if and
only if 
\[ \sigma =12 \ldots a \underbrace{b+1 \ldots c} \underbrace{a+1 \ldots b}c+1 \ldots n \]
 for some $1 \leq a \leq b \leq c \leq n$ 
(i.e., if and only if $\sigma$ is obtained from the identity permutation
by switching two ``middle blocks''). 
Let
\[ B(u)= \{ \sigma \leq u : \; \; \sigma \; \; \mbox{is bigrassmannian} \} . \]
The following result was proved by Lascoux and Schutzenberger in \cite{LS}.
\begin{thm}
Let $u,v \in S_{n}$. Then 
$$u \leq v \Leftrightarrow B(u) \subseteq B(v).$$
\end{thm}

If $\sigma \in B(u)$ let 
\[ d(\sigma , u) \stackrel{\rm def}{=} \mbox{max}\{ i \in {\bf N}: \; 
12\ldots a-i \; b+1 \ldots c+i-1 \; a-i+1 \ldots b \; c+i \ldots n \leq u \} \]

Let $v \in S_{n}$. Say that $v$ {\em avoids 3412} if there are no indices 
$1 \leq a<b<c<d \leq 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.

\begin{exe}
Let $v=7541632$. Then $vw_{0}=2361457$ and $I(vw_{0})=(1,1,3,\break0,0,0,0)$ 
so we get the partition 
\begin{center}
\begin{picture}(15,15)
\put(0,0){\line(1,0){15}}
\put(0,5){\line(1,0){10}}
\put(0,0){\line(0,1){5}}
\put(10,15){\line(1,0){5}}
\put(10,5){\line(0,1){10}}
\put(15,0){\line(0,1){15}}
\put(5,0){\line(0,1){5}}
\put(10,0){\line(0,1){5}}
\put(10,5){\line(1,0){5}}
\put(10,10){\line(1,0){5}}
\end{picture}
\end{center}
\end{exe}
Associate to this partition a word in $\{ (,) \}$ by associating a 
\begin{center}
``$($'' to a vertical step
\end{center}
and a  
\begin{center}
``$)$'' to a horizontal step 
\end{center}
as you follow its boundary from SW to NE.

\begin{exe}
{}From the partition $(1,1,3)$ we get the word 
$$ ())(() $$
\end{exe}
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). 

\begin{exe}
For the word $))(())(())()$ we get 
\[ )) \underbrace{( \underbrace{()} )} \underbrace{( \underbrace{()} )} \underbrace{()} \]
and therefore
\[
\begin{picture}(20,20)(-10,-10)
\put(-10,-10){\line(0,1){10}}
\put(0,-10){\line(0,1){20}}
\put(-10,0){\line(1,1){10}}
\put(10,0){\line(-1,1){10}}
\put(-10,-10){\circle*{2}}
\put(0,-10){\circle*{2}}
\put(-10,0){\circle*{2}}
\put(0,0){\circle*{2}}
\put(10,0){\circle*{2}}
\put(0,10){\circle*{2}}
\end{picture}
\]
\end{exe}
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
$\lambda (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$).

\noindent 
Now label each leaf of the tree by 
$$ d(B_{i},uw_{0}) $$

\noindent 
Note that, since $u \leq v $ then $ B_{1}, B_{2} \leq vw_{0} \leq uw_{0}$.

Let $f: \{$ edges of tree $\} \rightarrow {\bf N}$ be such that: 
\begin{description}
\item[i)] $f$ increases weakly along any path from the root;
\item[ii)] the value of $f$ at a final edge is less than or equal to the label 
of that leaf.
\end{description}
Let $|f|=\sum_{e \in E} f(e)$. Then we have (Lascoux \cite{Las95a}):
\begin{thm}
\label{L}
Let $u,v \in S_{n}$, $u \leq v$, and $v$ be $3412$-avoiding. Then 
$$ P_{u,v}(q)= \sum_{f}q^{|f|} $$
where the sum is over all such functions $f$.
\end{thm}

We illustrate this theorem on an example. 

\begin{exe}
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 
\[
\lambda (vw_{0})= 
\begin{picture}(20,10)
\put(10,0){\line(1,0){10}}
\put(20,0){\line(0,1){10}}
\put(10,0){\line(0,1){5}}
\put(10,5){\line(1,0){5}}
\put(15,10){\line(1,0){5}}
\put(15,5){\line(0,1){5}}
\put(15,0){\line(0,1){5}}
\put(15,5){\line(1,0){5}}
\end{picture}
 \]
We get the word 
\[ ()() \]
and therefore
\begin{center}
\begin{picture}(20,10)(-10,-10)
\put(-10,0){\line(1,1){10}}
\put(10,0){\line(-1,1){10}}
\put(-10,0){\circle*{2}}
\put(10,0){\circle*{2}}
\put(0,10){\circle*{2}}
\end{picture}
\end{center}
\noindent 
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 $\lambda (vw_{0})$:
\begin{center}
\begin{picture}(20,10)
\put(15,5){\line(0,1){5}}
\put(20,5){\line(0,1){5}}
\put(15,10){\line(1,0){5}}
\thicklines
\put(10,0){\line(1,0){10}}
\put(10,0){\line(0,1){5}}
\put(20,0){\line(0,1){5}}
\put(10,5){\line(1,0){10}}
\end{picture}
\; \; \; \; \; \; \; \; 
\begin{picture}(20,10)
\put(10,0){\line(1,0){5}}
\put(10,0){\line(0,1){5}}
\put(10,5){\line(1,0){5}}
\thicklines
\put(15,0){\line(0,1){10}}
\put(20,0){\line(0,1){10}}
\put(15,0){\line(1,0){5}}
\put(15,10){\line(1,0){5}}
\end{picture}
\end{center}
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 \leq 1267345 \]
and for $i=1$
\[ 1456237 \not \leq 1267345 \]
hence 
$$ d(B_{1},uw_{0})=0. $$
Similarly 
\[ 1236457 \leq 1267345 \]
and
\[ 1267345 \leq 1267345 \]
so 
\[ d(B_{2},uw_{0})=1 . \]
Associate to the leaves of the tree these integers:
\begin{center}
\begin{picture}(20,10)(-10,0)
\put(-10,0){\line(1,1){10}}
\put(10,0){\line(-1,1){10}}
\put(-10,0){\circle*{2}}
\put(10,0){\circle*{2}}
\put(0,10){\circle*{2}}
\put(-10,-6){\makebox(0,0){$\scriptstyle 0$}}
\put(10,-6){\makebox(0,0){$\scriptstyle 1$}}
\end{picture}
\end{center}
(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:
\vspace{0.5cm}
\begin{center}
\begin{picture}(20,10)(-10,0)
\put(-10,0){\line(1,1){10}}
\put(10,0){\line(-1,1){10}}
\put(-10,0){\circle*{2}}
\put(10,0){\circle*{2}}
\put(0,10){\circle*{2}}
\put(-10,6){\makebox(0,0){$\scriptstyle 0$}}
\put(10,6){\makebox(0,0){$\scriptstyle 0$}}
\end{picture}
\; \; \; \; \; \; \; \;
\begin{picture}(20,10)(-10,0)
\put(-10,0){\line(1,1){10}}
\put(10,0){\line(-1,1){10}}
\put(-10,0){\circle*{2}}
\put(10,0){\circle*{2}}
\put(0,10){\circle*{2}}
\put(-10,6){\makebox(0,0){$\scriptstyle 0$}}
\put(10,6){\makebox(0,0){$\scriptstyle 1$}}
\end{picture}
\end{center}
so 
$$ P_{u,v}=1+q.$$ 
\end{exe}

The procedure described in the subsection can ``a priori'', be applied to any
two permutations $u,v \in 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)$).




\section{Combinatorial Invariance}

The main problem, namely:
\begin{center}
{\em How to compute these polynomials?}
\end{center}
has many related and subproblems.

One of them was posed by G. Lusztig in the early 1980's \cite{Lu}, 
and independently by M. Dyer in 1987 (\cite{Dye87}).

\begin{probl}
\label{prob} 
Let $u,v , \sigma , \tau \in S_{n}$ be such that $[u,v] \cong [\sigma
, \tau ]$ (as posets). Then $P_{u,v}(q) = P_{\sigma , \tau }(q)$.
\end{probl}

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 \ref{2.6},
a statement about the equality of certain intersection cohomology
vector spaces. The isomorphism of the posets is, by equation (\ref{BS}),
a statement that concerns exclusively the inclusion relations between
the Schubert subvarieties of $\overline{\Omega}_{v}$ and of 
$\overline{\Omega}_{\tau}$.

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 $\LL(u,v) \leq 4$.
In fact, we have already seen that 
\begin{center}
$P_{u,v}=1$ if $\LL(u,v) \leq 2$, 
\end{center} 
and it can be proved that
if  $\LL(u,v)=3$ then  
\[ P_{u,v}(q) = \left\{ \begin{array}{ll} 1, & \mbox{if $c(u,v)=2$,} \\ 
1+(c(u,v)-3)q, & \mbox{otherwise,} \end{array} \right.  \] 
where $c(u,v)$ denotes the number of coatoms of $[u,v]$. 
Furthermore, it can be shown that, if $\LL(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
\cite[Theorem 6.3]{Bre94}. 

\begin{thm}
Let $u,v \in S_{n}$, $u \leq 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]^{\ast}$).
\end{thm}

Also the property ``$P_{u,v}=1$'' is known to depend only on 
the poset $[u,v]$.

\noindent 
Given $u,v \in S_{n}$, $u \leq v$ let
\[ def(u,v) \stackrel{\rm def}{=} |\{(i,j) \in T: u<u(i,j) \leq 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 \cite[Theorem C]{Car94}. 
\begin{thm}
Let $u,v \in S_{n}$, $u \leq v$. Then the following are
equivalent:
\begin{description}
\item[i)] $P_{u,v}(q)=1$;
\item[ii)] $P_{x,v}(q)=1$ for all $x \in [u,v]$;
\item[iii)] $def(x,v)=\LL(v)-\LL(x)$ for all $x \in [u,v]$.
\end{description}
\end{thm}


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.



\subsection{Special matchings}

Let's go back at the beginning. Theorem \ref{8.1.2} implies that 
the Kazhdan-Lusztig polynomials
$\{ P_{x,y} \}_{x,y \in [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 \in [u,v]}$.  

\noindent 
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.

\noindent 
Let's take a second look at the fundamental recursion satisfied by these
polynomials, namely Theorem \ref{8.1.1}.
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 {\em impossible} even if u is the identity....

\begin{exe}

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

\begin{center}
\begin{picture}(50,50)(-20,0)
\put(-20,0){\line(0,1){20}}
\put(20,0){\line(-1,1){20}}
\put(0,-20){\line(-1,1){20}}
\put(20,20){\line(-1,1){20}}
\put(0,0){\line(-1,1){20}}
\put(0,20){\line(0,1){20}}
\put(0,-20){\line(0,1){20}}
\put(20,0){\line(0,1){20}}
\put(0,-20){\line(1,1){20}}
\put(0,0){\line(1,1){20}}
\put(-20,0){\line(1,1){20}}
\put(-20,20){\line(1,1){20}}
\put(-20,0){\circle*{2}}
\put(20,0){\circle*{2}}
\put(0,20){\circle*{2}}
\put(0,-20){\circle*{2}}
\put(0,0){\circle*{2}}
\put(-20,20){\circle*{2}}
\put(0,40){\circle*{2}}
\put(20,20){\circle*{2}}
\put(-30,0){\makebox(0,0){$\scriptstyle 1243$}}
\put(0,-25){\makebox(0,0){$\scriptstyle 1234$}}
\put(-30,20){\makebox(0,0){$\scriptstyle 1423$}}
\put(0,45){\makebox(0,0){$\scriptstyle 4123$}}
\put(30,20){\makebox(0,0){$\scriptstyle 3124$}}
\put(30,0){\makebox(0,0){$\scriptstyle 2134$}}
\put(0,23){\makebox(0,0){$\scriptstyle 2143$}}
\put(0,-5){\makebox(0,0){$\scriptstyle 1324$}}
\end{picture}
\end{center} 
\vspace{0.5cm}
\begin{center}
Figure 5: The interval $[1234,4123]$.
\end{center}
and $v$ has only one descent: $s=(1,2)$. This choice gives the two elements 
\begin{center}
\begin{picture}(20,20)(-10,0)
\put(-10,0){\line(0,1){10}}
\put(10,0){\line(0,1){10}}
\put(0,10){\line(0,1){10}}
\put(0,-10){\line(0,1){10}}
\put(-10,0){\line(1,1){10}}
\put(10,0){\line(-1,1){10}}
\put(0,-10){\line(-1,1){10}}
\put(0,-10){\line(1,1){10}}
\put(-10,10){\line(1,1){10}}
\put(10,10){\line(-1,1){10}}
\put(0,-0){\line(-1,1){10}}
\put(0,0){\line(1,1){10}}
\put(-10,0){\circle*{2}}
\put(10,0){\circle*{2}}
\put(0,10){\circle*{2}}
\put(0,-10){\circle*{2}}
\put(0,0){\circle*{2}}
\put(-10,10){\circle*{2}}
\put(0,20){\circle*{2}}
\put(10,10){\circle*{2}}
\put(-10,10){\circle{4}}
\put(10,0){\circle{4}}
\end{picture}
\end{center}
\noindent
However, this pair is combinatorially indistinguishible from the pair 
\begin{center}
\begin{picture}(20,20)(-10,0)
\put(-10,0){\line(0,1){10}}
\put(10,0){\line(0,1){10}}
\put(0,10){\line(0,1){10}}
\put(0,-10){\line(0,1){10}}
\put(-10,0){\line(1,1){10}}
\put(10,0){\line(-1,1){10}}
\put(0,-10){\line(-1,1){10}}
\put(0,-10){\line(1,1){10}}
\put(-10,10){\line(1,1){10}}
\put(10,10){\line(-1,1){10}}
\put(0,-0){\line(-1,1){10}}
\put(0,0){\line(1,1){10}}
\put(-10,0){\circle*{2}}
\put(10,0){\circle*{2}}
\put(0,10){\circle*{2}}
\put(0,-10){\circle*{2}}
\put(0,0){\circle*{2}}
\put(-10,10){\circle*{2}}
\put(0,20){\circle*{2}}
\put(10,10){\circle*{2}}
\put(0,0){\circle{4}}
\put(0,10){\circle{4}}
\end{picture}
\end{center}
and there is no $s \in S$ such that $y=vs$, $x=us$.
 
\end{exe}


Actually, for any $s \in D(v)$, the map $x \mapsto xs$ for $x \in [e,v]$ 
is a complete matching of the
Hasse diagram of the poset $[e,v]$. 
So the natural question is:
\begin{center}
{\em Do these matchings $x \mapsto xs$ have any special property?}
\end{center}
\noindent 
{}From known properties of the Bruhat order (see, e.g., \cite{Hum}), one
knows that:
\begin{center}
if $x \lhd y$
and $s \in S$ is such that $xs \neq y$ then $xs \leq ys$.
\end{center}

This motivates the following definition.

\noindent
Let $P$ be (any) poset, and $M$ be a complete matching of the
Hasse diagram of $P$. For $x \in P$ denote by $M(x)$ the match of
$x$. 
\begin{defi}
We say that $M$  is a {\em special matching} if, for all $x,y \in P$,
such that $M(x) \neq y$, we have that
\[ x \lhd y \Rightarrow M(x) \leq M(y) . \]
\end{defi}

\noindent
Note that this implies, in particular, that if  $x \lhd y$ and $M(x) \rhd
x$ then $M(y) \rhd y$ and $M(y) \rhd M(x)$, and dually that if $x \lhd y$
and $M(y) \lhd y$ then $M(x) \lhd x$ and $M(x) \lhd M(y)$ (see Figures 
8 and 9). This concept was first introduced in \cite{Bre}.

\begin{exe}
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.
\end{exe}

\begin{center}
\begin{picture}(20,20)(-10,0)
\put(-10,0){\line(0,1){10}}
\put(10,0){\line(-1,1){10}}
\put(0,-10){\line(-1,1){10}}
\put(10,10){\line(-1,1){10}}
\put(0,0){\line(-1,1){10}}
\put(0,10){\line(0,1){10}}
\put(0,-10){\line(0,1){10}}
\put(10,0){\line(0,1){10}}
\thicklines
\thicklines
\thicklines
\put(0,-10){\line(1,1){10}}
\put(0,0){\line(1,1){10}}
\put(-10,0){\line(1,1){10}}
\put(-10,10){\line(1,1){10}}
\put(-10,0){\circle*{2}}
\put(10,0){\circle*{2}}
\put(0,10){\circle*{2}}
\put(0,-10){\circle*{2}}
\put(0,0){\circle*{2}}
\put(-10,10){\circle*{2}}
\put(0,20){\circle*{2}}
\put(10,10){\circle*{2}}
\end{picture}
\end{center}
\begin{center}
Figure 6: A special matching.
\end{center}

\begin{center}
\begin{picture}(20,20)(-10,0)
\put(-10,0){\line(0,1){10}}
\put(10,0){\line(-1,1){10}}
\put(0,-10){\line(-1,1){10}}
\put(0,-10){\line(1,1){10}}
\put(10,10){\line(-1,1){10}}
\put(0,-0){\line(-1,1){10}}
\put(0,0){\line(1,1){10}}
\put(0,10){\line(0,1){10}}
\thicklines
\thicklines
\thicklines
\put(0,-10){\line(0,1){10}}
\put(10,0){\line(0,1){10}}
\put(-10,0){\line(1,1){10}}
\put(-10,10){\line(1,1){10}}
\put(-10,0){\circle*{2}}
\put(10,0){\circle*{2}}
\put(0,10){\circle*{2}}
\put(0,-10){\circle*{2}}
\put(0,0){\circle*{2}}
\put(-10,10){\circle*{2}}
\put(0,20){\circle*{2}}
\put(10,10){\circle*{2}}
\end{picture}
%\vspace{1cm}
\end{center}
\begin{center}
Figure 7: A matching that is not special.
\end{center}
\[ 
\begin{picture}(20,10)(-10,0)
\put(0,0){\line(1,1){10}}
\thicklines
\put(0,0){\line(-1,1){10}}
\put(-10,10){\circle*{2}}
\put(0,0){\circle*{2}}
\put(10,10){\circle*{2}}
\put(15,15){\makebox(0,0){$\scriptstyle y$}}
\put(0,-5){\makebox(0,0){$\scriptstyle x$}}
\put(-15,15){\makebox(0,0){$\scriptstyle M(x)$}}
\end{picture}
 \; \; \; \; \Rightarrow \hspace{1cm} 
\begin{picture}(30,40)(-10,0)
\put(-10,0){\line(1,1){10}}
\put(0,-10){\line(1,1){10}}
\thicklines
\put(10,0){\line(-1,1){10}}
\put(0,-10){\line(-1,1){10}}
\put(-10,0){\circle*{2}}
\put(0,-10){\circle*{2}}
\put(10,0){\circle*{2}}
\put(0,10){\circle*{2}}
\put(-22,0){\makebox(0,0){$\scriptstyle M(x)$}}
\put(0,-15){\makebox(0,0){$\scriptstyle x$}}
\put(15,0){\makebox(0,0){$\scriptstyle y$}}
\put(0,15){\makebox(0,0){$\scriptstyle M(y)$}}
\end{picture}
\vspace{0.3cm}
\]
\begin{center}
Figure 8.
\end{center}
\[ 
\begin{picture}(20,10)(-10,0)
\put(0,10){\line(-1,-1){10}}
\thicklines
\put(0,10){\line(1,-1){10}}
\put(-10,0){\circle*{2}}
\put(10,0){\circle*{2}}
\put(0,10){\circle*{2}}
\put(-10,-5){\makebox(0,0){$\scriptstyle x$}}
\put(0,15){\makebox(0,0){$\scriptstyle y$}}
\put(10,-5){\makebox(0,0){$\scriptstyle M(y)$}}
\end{picture}
 \hspace{0.5cm} \Rightarrow \hspace{1cm} 
\begin{picture}(30,40)(-10,0)
\put(-10,0){\line(1,1){10}}
\put(0,-10){\line(1,1){10}}
\thicklines
\put(10,0){\line(-1,1){10}}
\put(0,-10){\line(-1,1){10}}
\put(-10,0){\circle*{2}}
\put(0,-10){\circle*{2}}
\put(10,0){\circle*{2}}
\put(0,10){\circle*{2}}
\put(0,-15){\makebox(0,0){$\scriptstyle M(x)$}}
\put(-15,0){\makebox(0,0){$\scriptstyle x$}}
\put(0,15){\makebox(0,0){$\scriptstyle y$}}
\put(22,0){\makebox(0,0){$\scriptstyle M(y)$}}
\end{picture}
\vspace{0.3cm}
\]
\begin{center}
Figure 9.
\end{center}

\begin{center}
\begin{picture}(40,20)(-20,20)
\put(0,0){\line(1,1){10}}
\thicklines
\put(0,0){\line(0,-1){10}}
\put(10,10){\line(-1,1){10}}
\put(0,-10){\circle*{2}}
\put(0,0){\circle*{2}}
\put(10,10){\circle*{2}}
\put(0,20){\circle*{2}}
\put(0,-15){\makebox(0,0){$\scriptstyle M(x)$}}
\put(-5,0){\makebox(0,0){$\scriptstyle x$}}
\put(15,10){\makebox(0,0){$\scriptstyle y$}}
\put(0,25){\makebox(0,0){$\scriptstyle M(y)$}}
\end{picture}
\vspace{1cm}
\end{center}
\begin{center}
Figure 10: This configuration is always allowed in a special matching.
\end{center}

\begin{center}
\begin{picture}(20,10)(0,15)
\put(0,0){\line(1,1){10}}
\thicklines
\put(0,0){\line(-1,1){10}}
\put(20,0){\line(-1,1){10}}
\put(-10,10){\circle*{2}}
\put(0,0){\circle*{2}}
\put(10,10){\circle*{2}}
\put(20,0){\circle*{2}}
\put(15,15){\makebox(0,0){$\scriptstyle y$}}
\put(0,-5){\makebox(0,0){$\scriptstyle x$}}
\put(-15,15){\makebox(0,0){$\scriptstyle M(x)$}}
\put(25,-5){\makebox(0,0){$\scriptstyle M(y)$}}
\end{picture}
\vspace{0.5cm}
\end{center}
\begin{center}
Figure 11: This configuration is never allowed in a special matching.
\end{center}



\subsection{Combinatorial invariance}


The natural question now is:
\begin{center}
{\em Is any special matching of $[e,v]$ of the form 
$x \mapsto xs$ for some $s \in D(v)$ ?}
\end{center}

\noindent
Again, the answer is {\bf no}!

\begin{exe}
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 \mapsto 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 {\em combinatorially indistinguishable} 
from the first one!
\end{exe}

\begin{center}
\begin{picture}(50,50)(-20,0)
\put(-20,0){\line(0,1){20}}
\put(20,0){\line(-1,1){20}}
\put(0,-20){\line(-1,1){20}}
\put(20,20){\line(-1,1){20}}
\put(0,0){\line(-1,1){20}}
\put(0,20){\line(0,1){20}}
\put(0,-20){\line(0,1){20}}
\put(20,0){\line(0,1){20}}
\thicklines
\put(0,-20){\line(1,1){20}}
\put(0,0){\line(1,1){20}}
\put(-20,0){\line(1,1){20}}
\put(-20,20){\line(1,1){20}}
\put(-20,0){\circle*{2}}
\put(20,0){\circle*{2}}
\put(0,20){\circle*{2}}
\put(0,-20){\circle*{2}}
\put(0,0){\circle*{2}}
\put(-20,20){\circle*{2}}
\put(0,40){\circle*{2}}
\put(20,20){\circle*{2}}
\put(-30,0){\makebox(0,0){$\scriptstyle 1243$}}
\put(0,-25){\makebox(0,0){$\scriptstyle 1234$}}
\put(-30,20){\makebox(0,0){$\scriptstyle 1423$}}
\put(0,45){\makebox(0,0){$\scriptstyle 4123$}}
\put(30,20){\makebox(0,0){$\scriptstyle 3124$}}
\put(30,0){\makebox(0,0){$\scriptstyle 2134$}}
\put(0,23){\makebox(0,0){$\scriptstyle 2143$}}
\put(0,-5){\makebox(0,0){$\scriptstyle 1324$}}
\end{picture}
\end{center}
\vspace{0.5cm}
\begin{center}
Figure 12
\end{center}

\begin{center}
\begin{picture}(20,20)(-10,0)
\put(10,0){\line(-1,1){10}}
\put(0,-10){\line(-1,1){10}}
\put(0,-10){\line(1,1){10}}
\put(10,10){\line(-1,1){10}}
\put(0,-0){\line(-1,1){10}}
\put(0,0){\line(1,1){10}}
\put(-10,0){\line(1,1){10}}
\put(-10,10){\line(1,1){10}}
\thicklines
\put(-10,0){\line(0,1){10}}
\put(0,-10){\line(0,1){10}}
\put(10,0){\line(0,1){10}}
\put(0,10){\line(0,1){10}}
\put(-10,0){\circle*{2}}
\put(10,0){\circle*{2}}
\put(0,10){\circle*{2}}
\put(0,-10){\circle*{2}}
\put(0,0){\circle*{2}}
\put(-10,10){\circle*{2}}
\put(0,20){\circle*{2}}
\put(10,10){\circle*{2}}
\end{picture}
\hspace{1.5cm}
\begin{picture}(20,20)(-10,0)
\put(0,-10){\line(1,1){10}}
\put(0,-0){\line(-1,1){10}}
\put(0,0){\line(1,1){10}}
\put(-10,0){\line(1,1){10}}
\put(-10,10){\line(1,1){10}}
\put(-10,0){\line(0,1){10}}
\put(0,-10){\line(0,1){10}}
\put(10,0){\line(0,1){10}}
\put(0,10){\line(0,1){10}}
\thicklines
\put(10,0){\line(-1,1){10}}
\put(10,10){\line(-1,1){10}}
\put(0,-0){\line(-1,1){10}}
\put(0,-10){\line(-1,1){10}}
\put(-10,0){\circle*{2}}
\put(10,0){\circle*{2}}
\put(0,10){\circle*{2}}
\put(0,-10){\circle*{2}}
\put(0,0){\circle*{2}}
\put(-10,10){\circle*{2}}
\put(0,20){\circle*{2}}
\put(10,10){\circle*{2}}
\end{picture}
\vspace{0.5cm}
\end{center}
\begin{center}
Figure 13
\end{center}

Nonetheless, remarkably, the following holds (\cite[Theorem 5.2]{Bre}).

\begin{thm}
\label{4.2}
Let $v \in S_{n}$, and $M$ be a special matching of $[e,v]$. Then
\begin{equation} 
\label{4.2.0} 
R_{u,v}(q) = \left\{ \begin{array}{ll} R_{M(u),M(v)}(q), & 
\mbox{if $M(u) \lhd u$,} \\ qR_{M(u),M(v)}(q)+(q-1)R_{u,M(v)}(q), & 
\mbox{if $M(u) \rhd u$,} \end{array} \right.  
\end{equation} for all $u \in [e,v]$.
So the polynomials ${R_{x,y}(q)}_{x,y \in [e,v]}$ 
(and hence ${P_{x,y}(q)}_{x,y \in [e,v]}$, and hence the intersection
homology of the Schubert variety $\overline{\Omega}_{v}$ ) 
depend only on $[e,v]$ as an abstract poset. 
\end{thm}

We conclude this section by illustrating Theorem \ref{4.2} with an example.
\begin{center}
\begin{picture}(250,160)(-120,0)
\put(0,0){\line(-2,1){60}}
\put(0,0){\line(0,1){150}}
\put(0,0){\line(2,1){120}}
\put(-60,30){\line(6,1){180}}
\put(-60,30){\line(4,1){120}}
\put(-60,30){\line(2,1){120}}
\put(0,30){\line(-4,1){120}}
\put(0,30){\line(-2,1){60}}
\put(0,30){\line(2,1){60}}
\put(60,30){\line(-6,1){180}}
\put(60,30){\line(-4,1){120}}
\put(-120,60){\line(0,1){30}}
\put(-120,60){\line(2,1){120}}
\put(-120,60){\line(1,0){30}}
\put(-90,60){\line(6,1){180}}
\put(90,90){\line(1,0){30}}
\put(0,60){\line(2,1){60}}
\put(0,60){\line(4,1){120}}
\put(60,60){\line(-4,1){120}}
\put(60,60){\line(0,1){60}}
\put(120,60){\line(-6,1){180}}
\put(120,60){\line(-4,1){120}}
\put(120,60){\line(0,1){30}}
\put(-120,90){\line(2,1){120}}
\put(-120,90){\line(4,1){120}}
\put(-60,90){\line(4,1){120}}
\put(60,90){\line(-2,1){60}}
\put(120,90){\line(-6,1){180}}
\put(120,90){\line(-2,1){120}}
\put(-60,60){\line(-2,1){60}}
\put(-60,60){\line(2,1){60}}
\put(0,90){\line(-2,1){60}}
\put(0,0){\circle*{2}}
\put(0,-5){\makebox(0,0){$\scriptstyle 1$}}
\put(-60,30){\circle*{2}}
\put(-63,27){\makebox(0,0){$\scriptstyle 2$}}
\put(0,30){\circle*{2}}
\put(3,27){\makebox(0,0){$\scriptstyle 3$}}
\put(60,30){\circle*{2}}
\put(63,27){\makebox(0,0){$\scriptstyle 4$}}
\put(-120,60){\circle*{2}}
\put(-123,57){\makebox(0,0){$\scriptstyle 5$}}
\put(-60,60){\circle*{2}}
\put(-63,57){\makebox(0,0){$\scriptstyle 6$}}
\put(0,60){\circle*{2}}
\put(3,57){\makebox(0,0){$\scriptstyle 7$}}
\put(60,60){\circle*{2}}
\put(64,60){\makebox(0,0){$\scriptstyle 8$}}
\put(120,60){\circle*{2}}
\put(123,57){\makebox(0,0){$\scriptstyle 9$}}
\put(-120,90){\circle*{2}}
\put(-125,90){\makebox(0,0){$\scriptstyle 10$}}
\put(-60,90){\circle*{2}}
\put(-64,92){\makebox(0,0){$\scriptstyle 11$}}
\put(0,90){\circle*{2}}
\put(5,92){\makebox(0,0){$\scriptstyle 12$}}
\put(60,90){\circle*{2}}
\put(65,90){\makebox(0,0){$\scriptstyle 13$}}
\put(120,90){\circle*{2}}
\put(125,90){\makebox(0,0){$\scriptstyle 14$}}
\put(-60,120){\circle*{2}}
\put(-65,122){\makebox(0,0){$\scriptstyle 15$}}
\put(0,120){\circle*{2}}
\put(5,123){\makebox(0,0){$\scriptstyle 16$}}
\put(60,120){\circle*{2}}
\put(65,123){\makebox(0,0){$\scriptstyle 17$}}
\put(0,150){\circle*{2}}
\put(0,155){\makebox(0,0){$\scriptstyle 18$}}
\end{picture}
\end{center}
\vspace{0.5cm} 
\begin{center}
Figure 14: A lower interval in a symmetric group.
\end{center}


\begin{exe}
\label{4312} 
 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 \ref{4.2}, 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 \} , \break\{ 16,18 \} \}$. 

Applying Theorem \ref{4.2} we obtain that
\[
R_{1,18} = q \, R_{M(1),M(18)}+(q-1) R_{1,M(18)} = q R_{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 \leq 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) \in \{ 7,8 \}$, and $N(4) \in \{ 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 \cite[Prop. 4.1]{Bre},
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 \ref{4.2} we get
\begin{eqnarray*}
R_{1,16} & = & q \, R_{3,11}+(q-1)R_{1,11} , \\
R_{2,16} & = &  \, (q-1)R_{2,11},  \\
\end{eqnarray*}
(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 \in [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 \} ,\break \{ 5,11 \}
\} $. So by Theorem \ref{4.2} 
\begin{eqnarray*}
R_{1,11} & = & (q-1)R_{1,5} , \\
R_{2,11} & = & R_{1,5} , \\
R_{3,11} & = & (q-1)R_{3,5} , \\
\end{eqnarray*}
(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 \ref{4.2} 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 
\ref{4.2}
we obtain $R_{1,4} =(q-1)R_{1,1}$. Putting all these relations together we then get 
\begin{eqnarray*}
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} , 
\end{eqnarray*}
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 \in P$, $u \leq v$. The computation of the Kazhdan-Lusztig polynomials $P_{u,v}$
for $u,v \in P$, $u \leq v$, now proceeds using Theorem \ref{8.1.2} and induction on $l(u,v)$,
just as in Example \ref{ex1}.
\end{exe}



\subsection{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.

\begin{probl}
Which posets have special matchings?
\end{probl}

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.
\begin{center}
\begin{picture}(40,30)(-20,0)
\put(-15,-5){\line(0,1){10}}
\put(-5,-5){\line(0,1){10}}
\put(5,-5){\line(0,1){10}}
\put(15,-5){\line(0,1){10}}
\put(-5,-5){\line(-1,1){10}}
\put(5,-5){\line(-1,1){10}}
\put(15,-5){\line(-1,1){10}}
\put(-15,-5){\line(3,1){30}}
\put(0,20){\line(-1,-1){15}}
\put(0,20){\line(-1,-3){5}}
\put(0,20){\line(1,-3){5}}
\put(0,20){\line(1,-1){15}}
\put(0,-20){\line(-1,1){15}}
\put(0,-20){\line(-1,3){5}}
\put(0,-20){\line(1,3){5}}
\put(0,-20){\line(1,1){15}}
\put(0,-20){\circle*{2}}
\put(15,-5){\circle*{2}}
\put(5,-5){\circle*{2}}
\put(-5,-5){\circle*{2}}
\put(-15,-5){\circle*{2}}
\put(-15,5){\circle*{2}}
\put(-5,5){\circle*{2}}
\put(5,5){\circle*{2}}
\put(15,5){\circle*{2}}
\put(0,20){\circle*{2}}
\end{picture}
\vspace{0.5cm}
\end{center}
\begin{center}
Figure 15
\end{center}



Given a poset $P$ that has a special matching, it is clear 
that one could use Theorem \ref{4.2} to {\em 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.

\begin{probl}
For which posets does Theorem \ref{4.2} give a definition
that is independent of the choice of special matching?
\end{probl}

The answer to this problem is known to be yes if $P$ is an Eulerian lattice
(see \cite[Prop. 4.3]{Bre}), 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., \cite[\S\S 7.14-7.15]{Hum}) that the coefficient 
$\overline{\mu}(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.
\begin{con}
Let $u,v \in S_{n}$, $u \leq v$, be such that $\LL(u,v)$ is odd.
Then $\overline{\mu}(u,v) \neq 0$ if and only if $[u,v]$ does not have
a special matching.
\end{con} 

This conjecture has been verified for $\LL(u,v) \leq 5$.

Since the statement in Theorem \ref{4.2} makes sense verbatim for any
Coxeter group, one may conjecture the following.
\begin{con}
\label{con1} 
Theorem \ref{4.2} holds for any Coxeter group.
\end{con}

Finally, we conclude with a conjecture which has already been made in 
\cite{Bre}.

\begin{con}
Theorem \ref{4.2} holds for any element $u \in S_{n}$
(not just for $u$ equals the identity permutation).
\end{con}

In other words, I conjecture that if $u,v \in 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 \in [u,v]$ and any special matching $M$ of $[u,v]$, where $c
\stackrel{\rm def}{=} 1$ if $M(a) \lhd a$ and $c \stackrel{\rm def}{=} 0$ if
$M(a) \rhd a$.

Of course, not all reasonable conjectures turn out to be true 
(see, e.g., \cite{MW}). 

{\bf Note added in proof:} Conjecture \ref{con1} has been proved 
for all doubly laced Coxeter systems by F. Brenti, F. Caselli, M. Marietti,  
{\em Special matchings and Kazhdan-Lusztig 
polynomials for doubly laced Coxeter systems}, preprint. 
The second part of Theorem \ref{4.2} has also been proved, independently, 
by F. Du Cloux,
{\em Rigidity of Schubert closures and invariance of Kazhdan-Lusztig polynomials},
Advances in Math., to appear. 


\begin{thebibliography}{xx}

\bibitem{And}
H. H. Andersen,  {\em The irreducible characters for semi-simple algebraic 
groups and for quantum groups}, 
 Proceedings of the International Congress of Mathematicians,
 Z\"{u}rich, 1994, 
732-743, Birkh\"{a}user, Basel, Switzerland, 1995. 

\bibitem{BB}
A. Beilinson, J. Bernstein,
{\em Localisation de $g$-modules}, 
C. R. Acad. Sci. Paris, {\bf 292} (1981), 15-18. 

\bibitem{BL}
S. Billey, V. Lakshmibai,  {\em Singular loci of Schubert varieties}, 
Progress in Math., {\bf 182}, Birkh\"{a}user, Boston, MA, 2000. 

\bibitem{BP}
S. Billey, A. Postnikov, 
{\em A root system description of pattern avoidance with applications to G/B},  
preprint.

\bibitem{BW01}
S. Billey, G. Warrington, 
{\em Kazhdan-Lusztig polynomials for 321-hexagon-avoiding permutations},  
J. Algebraic Combin., {\bf 13} (2001), 111-136.

\bibitem{BW02}
S. Billey, G. Warrington, 
{\em Maximal singular loci for Schubert varieties in SL(n)/B},  
Trans. Amer. Math. Soc., to appear.

\bibitem{BW}
A. Bj\"{o}rner and  M. Wachs, {\em Bruhat order of Coxeter groups and
shellability}, Advances in Math. {\bf 43} (1982), 87--100.

\bibitem{Boe88}
B. D. Boe, 
{\em Kazhdan-Lusztig polynonomials for Hermitian symmetric spaces},
Trans. Amer. Math. Soc. {\bf 309} (1988), 279--294.

\bibitem{BrMa01}
T. Braden, R. MacPherson,  
{\em From moment graphs to intersection cohomology}, 
Math. Ann., {\bf 321} (2001), 533-551.

\bibitem{Bre97}
F. Brenti, {\em  Combinatorial properties of the Kazhdan-Lusztig $R$-polynomials
for $S_{n}$}, Adv. in Math., {\bf 126} (1997), 21-51.

\bibitem{Bre94}
F. Brenti, {\em A combinatorial formula for Kazhdan-Lusztig
polynomials}, Invent. Math., {\bf 118}
(1994), 371-394.

\bibitem{Bre98}
F. Brenti,  {\em Lattice paths and Kazhdan-Lusztig polynomials}, 
J. Amer. Math. Soc., {\bf 11} (1998), 229-259.

\bibitem{BreSim}
F. Brenti, R. Simion, {\em Explicit formulae for some Kazhdan-Lusztig polynomials}, 
J. Algebraic Combin., {\bf 11} (2000), 187-196.

\bibitem{Bre02}
F. Brenti, {\em Kazhdan-Lusztig and $R$-polynomials, Young's lattice, and
Dyck partitions}, Pacific J. Math., {\bf 207} (2002),  257-286.  

\bibitem{Bre} 
F. Brenti, 
{\em A combinatorial construction for the Kazhdan-Lusztig polynomials 
of the symmetric group}, 
preprint, available at http://www.mat.uniroma2.it/$\sim$brenti/papers.htm 

\bibitem{BK}
J.-L. Brylinski, M. Kashiwara, {\em Kazhdan-Lusztig conjecture and 
holonomic system}, Invent. Math. {\bf 64} (1981), 387-410.

\bibitem{Cas}
F. Caselli,
{\em Proof of two conjectures of Brenti-Simion on Kazhdan-Lusztig polynomials},
J. Algebraic Combin., to appear.

\bibitem{Car94}  
J. Carrell, {\em 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. {\bf 56},
Amer. Math. Soc., Providence, 1994.

\bibitem{Deo1}
V. V. Deodhar, {\em Some characterizations of Bruhat ordering 
on a Coxeter group and determination of the relative 
M\"{o}bius function}, Invent. Math., {\bf 39} (1977), 187-198.

\bibitem{Deo2}
V. V. Deodhar, {\em On some geometric aspects of Bruhat orderings.
I. A finer decomposition of Bruhat cells}, Invent. Math. {\bf 79}
(1985), 499-511.

\bibitem{Deo3}
V. V. Deodhar, {\em A combinatorial setting for questions in 
Kazhdan-Lusztig  Theory}, Geom. Dedicata, {\bf 36} (1990),
95-120.

\bibitem{Dye87}
M. Dyer, {\em Hecke algebras and reflections in Coxeter groups}, 
Ph. D. Thesis, University of Sydney, 1987.

\bibitem{Dy1}
M. Dyer, {\em On the ``Bruhat graph'' of a Coxeter system},
Comp. Math., {\bf 78} (1991), 185-191.

\bibitem{Dy}
M. Dyer, {\em Hecke algebras and shellings of Bruhat intervals},
Comp. Math., {\bf 89} (1993), 91-115.

\bibitem{Dye97}
M. J. Dyer, 
{\em On coefficients of $q$ in Kazhdan-Lusztig polynomials}, 
Algebraic groups and Lie groups, 
Austral. Math. Soc. Lect. Ser., {\bf 9}, 
Cambridge Univ. Press,
Cambridge, 1997, 189-194.

\bibitem{Ede}
P. H. Edelman, {\em The Bruhat order of the symmetric group is
lexicographically shellable}, Proc. Amer. Math. Soc., {\bf 82}
(1981), 355-358.

\bibitem{FKK}
I. Frenkel, M. Khovanov, A. Kirillov,  
{\em Kazhdan-Lusztig polynomials and canonical basis}, 
Transform. Groups, {\bf 3} (1998), 321-336. 

\bibitem{Ful}
W. Fulton, {\em Young tableaux. With applications to representation theory 
and geometry.} London Mathematical Society
Student Texts {\bf 35}, Cambridge University Press, Cambridge, 1997.

\bibitem{GM}
M. Goresky, R. MacPherson,  {\em Intersection homology theory}, 
Topology, {\bf 19} (1983), 135-162. 

\bibitem{Ha}
M. Haiman,  {\em Hecke algebra characters and immanant conjectures}, 
J. Amer. Math. Soc., {\bf 6} (1993), 569-595.

\bibitem{Hum} 
J. E. Humphreys, {\em Reflection Groups and Coxeter Groups},
Cambridge Studies in Advanced Mathematics, no.29,
Cambridge Univ. Press, Cambridge,  1990.

\bibitem{K-L}
D. Kazhdan, G. Lusztig, {\em Representations of Coxeter groups
and Hecke algebras}, Invent. Math. {\bf 53} (1979), 165-184.

\bibitem{KL2}
D. Kazhdan, G. Lusztig, {\em Schubert varieties and Poincar\'{e}
duality}, Geometry of the Laplace operator, Proc. Sympos. Pure
Math. 34, Amer. Math. Soc., Providence, RI, 1980, pp. 185-203.

\bibitem{Ki-La}
A. Kirillov, A. Lascoux,
{\em Factorization of Kazhdan-Lusztig elements for Grassmannians}, 
Adv. Studies in Pure Math., {\bf 28} (2000), 143-154. 

\bibitem{Kir}
F. Kirwan,  {\em An introduction to intersection homology theory}, 
Research Notes in Math., {\bf 187}, Pitman, 1988. 

\bibitem{La-Se}
V. Lakshmibai, B. Sandhya, {\em Criterion for smoothness
of Schubert varieties in $S_{l(n)/B}$}, Proc. Indian Acad. Sci.
Math. Sci.,
{\bf 100} (1990), 45-52.

\bibitem{Las95a}
A. Lascoux,
{\em Polyn\^{o}mes de Kazhdan-Lusztig pour les vari\'et\'es de Schubert vexillaires}, 
C. R. Acad. Sci. Paris Sér. I Math., {\bf 321} (1995), 667-670. 

\bibitem{L-S}
A. Lascoux, M.-P. Sch\"{u}tzenberger, {\em Polyn\^{o}mes de 
Kazhdan \& Lusztig pour les grassmanniennes}, Young tableaux
and Schur functions in algebra and geometry, Ast\'{e}risque,
{\bf 87}-{\bf 88} (1981), pp. 249-266.

\bibitem{LS}
A. Lascoux, M.-P. Sch\"{u}tzenberger,
{\em Treillis et bases des groupes de Coxeter},
Electron. J. Combin., {\bf 3}(1996), \#27, 35pp.

\bibitem{Le-Th}
B. Leclerc, J.-Y. Thibon,
{\em Littlewood-Richardson coefficients and Kazhdan-Lusztig polynomials}, 
Adv. Studies in Pure Math., {\bf 28} (2000), 155-220. 

\bibitem{Lu}
G. Lusztig, private communication, September 1993.

\bibitem{Mac}
I. G. Macdonald, {\em Notes on Schubert Polynomials},
Publ. du LACIM {\bf 6}, Univ. du Qu\'ebec, Montr\'eal, 1991.

\bibitem{Mar}
M. Marietti,
{\em Closed product formulas for certain $R$-polynomials},
Europ. J. Combinatorics, {\bf 23} (2002), 57-62.

\bibitem{MW} 
T. McLarnan, G. Warrington, 
{\em Counterexamples to the 0-1 conjecture}, 
Representation Theory, {\bf 7} (2003), 181-195. 

\bibitem{Pol99} 
P. Polo, {\em Construction of arbitrary Kazhdan-Lusztig 
polynomials in symmetric groups}, 
Representation Theory, {\bf 3} (1999), 90-104. 

\bibitem{Pro}
R. A. Proctor, {\em Classical Bruhat orders and lexicographic
shellability}, J. Algebra, {\bf 77} (1982), 104-126.

\bibitem{SSV}
B. Shapiro, M. Shapiro, A. Vainshtein, {\em Kazhdan-Lusztig polynomials 
for certain varieties of incomplete flags}, 
Discrete Math., {\bf 180} (1998), 345-355.

\bibitem{StaEC1}
 R. P. Stanley,
{\em Enumerative Combinatorics }, vol.1, Wadsworth and
Brooks/Cole, Monterey, CA, 1986. 

\bibitem{Tag94a}
H. Tagawa,
{\em On the non-negativity of the first coefficient of Kazhdan-Lusztig polynomials},
J. Algebra, {\bf 177} (1995), 698-707.

\bibitem{Ug}
D. Uglov, {\em Canonical bases of higher level $q$-deformed Fock spaces and
Kazhdan-Lusztig polynomials}, Physical Combinatorics, 
Progress in Math., {\bf 191}, Birkh\"{a}user, Boston, MA, 2000, 249-299.

\bibitem{Ver}
D.-N. Verma, {\em M\"{o}bius inversion for the Bruhat order on a Weyl 
group}, Ann. Sci. \'{E}cole Norm. Sup., {\bf 4} (1971), 393-398.

\bibitem{Zel}
A. Zelevinski, {\em Small resolutions of singularities of Schubert
varieties}, Funct. Anal.  Appl., {\bf 17} (1983), 142-144. 

\end{thebibliography} 





\end{document}