%This is an AMS-Latex1.2 file
\documentclass[12pt]{amsart} 
\usepackage{amssymb,amsmath}
\pagestyle{plain}   
\textwidth 444pt \oddsidemargin 20pt \evensidemargin 20pt 
\headsep 0pt \flushbottom  \textheight 630pt 
\theoremstyle{plain} 
\theoremstyle{plain} 
\newtheorem{Lem}{Lemma}                    \newtheorem{Thm}[Lem]{Theorem} 
\newtheorem{Cor}[Lem]{Corollary}           \newtheorem{Def}[Lem]{Definition}         
\theoremstyle{definition} 
\newtheorem{Rem}[Lem]{Remark}              \newtheorem{Ex}[Lem]{Example}
\theoremstyle{remark} 
\newtheorem*{Ack}{Acknowledgement}         \errorcontextlines=0   
\newcommand{\C}{\mathbb C}                 \newcommand{\R}{\mathbb R} 
\newcommand{\Q}{\mathbb Q}                 \newcommand{\Z}{\mathbb Z} 
\newcommand{\N}{\mathbb N}                 \newcommand{\LL}{\mathbb L}
\newcommand{\X}{\mathbb X}                 \newcommand{\D}{\mathbb D} 
\newcommand{\B}{\mathbb B}                 \newcommand{\K}{\mathbb K}  
\newcommand{\PP}{\mathbb P}                \newcommand{\lcal}{\mathcal L}
\newcommand{\bcal}{\mathcal B}             \newcommand{\dcal}{\mathcal D} 
\newcommand{\scal}{\mathcal S}             \newcommand{\sch}{\mathfrak S}
\newcommand{\bbb}{_{\bullet}}              \newcommand{\id}{\mathbf 1} 
\newcommand{\gdw}{\Leftrightarrow}         \newcommand{\lra}{\longrightarrow} 
\newcommand{\Lra}{\Longrightarrow}         \newcommand{\lla}{\longleftarrow} 
\newcommand{\oo}{\overline}                \newcommand{\uu}{\underline}
\newcommand{\tin}{\vDash}                  \newcommand{\ntin}{\nvDash}                        
\newcommand{\cc}[1]{\put(1,1){\framebox(8,8){\scriptsize #1}}}
\newcommand{\ccc}[1]{\put(.5,.5){\framebox(4,4){\tiny #1}}}
\newcommand{\ccd}{\makebox(10,10){$\cdot$}}
\newcommand{\bpi}{\begin{picture}}         \newcommand{\epi}{\end{picture}}   
%\renewcommand{\baselinestretch}{1.6}

\begin{document} 
\title[A derivation of Kohnert's algorithm]{A derivation of Kohnert's algorithm from Monk's rule} 
\date{November 29th, 2000; revised: March 2nd and November 21th, 2002} 
\author[R. Winkel] {Rudolf Winkel}
\address{Institut f\"ur Reine und Angewandte Mathematik \\  RWTH Aachen \\ 
D-52056 Aachen \\ Germany\\ \hfill  {\it papers/preprints}: 
http://www.iram.rwth-aachen.de/ $\sim$winkel/} 
\email{winkel@iram.rwth-aachen.de}  
\subjclass[2000]{05E05, 05E10, 05E15, 14M15}
\begin{abstract} Kohnert's algorithm for the generation of Schubert polynomials is 
derived from Monk's rule for the multiplication of Schubert polynomials.   
\end{abstract}
\maketitle 

%First page headline in 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 48 \rms (2003), Article~B48f\hfill}
\def\thepage{}
%
%

\section{Introduction}

The theory of Schubert polynomials is a beautiful blend of geometric, algebraic and 
combinatorial ideas: on one hand Schubert polynomials faithfully represent the cohomology 
calculus of Schubert varieties of flag manifolds;  on the other hand Schubert polynomials
are a generalization of the classical Schur polynomials and can be studied in a
purely algebraic and combinatorial setting.  The primary references for Schubert
calculus and Schubert polynomials are the papers of Borel [Bo], Bernstein, Gelfand, and 
Gelfand [BGG], Demazure [D1,D2] and Lascoux and Sch\"utzenberger [LS] (see also [L]).
Introductory and comprehensive accounts of both the ``classical'' theory and newer research
are [F,FP] (for the algebraic-geometrical side) and  [M1,M2,W3] (for the 
algebraic-combinatorial side). 

The purpose of the present paper is to give a short and
natural proof of a combinatorial rule for the generation of Schubert polynomials which 
was conjectured first by Kohnert in his Ph. D. dissertation [K]
and subsequently proven in [W1]. The proof in [W1] has two advantages: 
\begin{itemize} 
\item It is the first and only one so far.
\item It incorporates as an intermediary step the proof of two other (more complicated) 
rules for the generation of Schubert polynomials, namely the rules given by Ber\-ge\-ron [B] 
and Magyar [Ma]. \end{itemize}
The proof in [W1] has also two disadvantages: 
\begin{itemize} 
\item It is the first and only one so far --- and first proofs are rarely the most simple
and elegant ones.
\item It incorporates as an intermediary step the proof of two other (more complicated) 
rules for the generation of Schubert polynomials, namely the rules given by Bergeron [B] and
Magyar  [Ma] --- and (as we will make more precise below) these two rules do not provide a 
natural context for the proof of  Kohnert's algorithm thus severely complicating matters.
\end{itemize}

Subsequently in this introduction we collect the basic necessary information about 
Schubert polynomials, describe Kohnert's algorithm and introduce some useful notation.
In Section 2 the proof is outlined and illustrated in two simple special cases, 
whereas Section 3 deals with the general case.

To every permutation $\pi$ on numbers $1,\dots,n$ contained in the symmetric 
group $S_{n}$  one can associate a multivariate polynomial with non-negative 
integer coefficients $X_{\pi}\in \Z[x_{1},\dots,x_{n}]$ as follows: Let 
$\omega_{n}:=n\, (n-1) \dots 1 \in S_{n}$ be the permutation of maximal length, i.e., with
the maximum number of inversions. Every other permutation $\pi\in S_{n}$ can then be 
reached from $\omega_{n}$ by going down in (right) {\em weak Bruhat order} 
where $\pi'$ covers $\pi$  in weak Bruhat order, if $\pi'=\pi\circ \sigma_{k}$ with 
$\sigma_{k}$ the elementary transposition $(k,k+1)$ and  $\pi(k)<\pi(k+1)$. 
In other words: $\pi$ results from $\pi'$ by removing the inversion of numbers on 
adjacent places $k$ and $k+1$. If for all such pairs $\pi, \pi'$ with 
$\pi'=\pi\circ \sigma_{k}$ one defines recursively $X_{\pi}:=\partial_{k} X_{\pi'}$ 
where $\partial_{k}$ is the divided difference operator acting on the 
variables $x_{k}$ and $x_{k+1}$ and if one starts at 
$X_{\omega_{n}}:=x_{1}^{n-1} x_{n}^{n-2}\dots x_{n-1}$ then this leads to  
well defined polynomials $X_{\pi}$ for all $\pi\in S_{n}$, the 
Schubert polynomials. It is interesting to note that this (classical) approach to 
Schubert polynomials by 
divided difference operators reflects the relative geometric positions of 
Schubert varieties in a flag manifold where one variety lies on the boundary of another. 

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL RUDOLF WINKEL}{\SMALL A DERIVATION OF KOHNERT'S ALGORITHM}
%
%

Alternatively, one can compute the Schubert polynomials without divided differences
by going down from $\omega_{n}$ in (right strong) {\em Bruhat order} where $\pi'$ covers
$\pi$  in Bruhat order, if $\pi'=\pi\circ (k,j)$ and 
$j\in J^{>k}(\pi)$ for any fixed $k$ with $J^{>k}(\pi):=$ \begin{multline} 
\{ j \mid k<j ,\ \pi(k)<\pi(j), \text{ and } 
|\{ \nu \mid k<\nu<j,\ \pi(k)<\pi(\nu)<\pi(j) \}|=0\ \}\ . \end{multline}
Then for every $\pi\neq \omega_{n}$ in $S_{n}$ and $k:=\pi^{-1}(1)$ one has \begin{equation} 
X_{\pi}=\frac{1}{x_{k}}\left( \sum_{j\in  J^{>k}(\pi)}  X_{\pi\circ (k,j)} \right)\ ,
\end{equation} i.e., if $k$ is chosen such that $\pi(k)=1$ then $x_{k} X_{\pi}$ equals 
the sum of $X_{\pi'}$ where $\pi'$ runs through certain $\pi'$ covering $\pi$ in  
Bruhat order. This formula has
been noted first in [W2, Sec. 6] as a simple consequence of Monk's rule [Mo] for the 
multiplication of an arbitrary Schubert polynomial by any of the polynomials 
$X_{\sigma_{k}}=x_{1}+\dots + x_{k}$. Since (2) is essential for our new proof of
Kohnert's algorithm we explain this point a bit more thoroughly:  Monk's rule is
\begin{equation*} 
X_{\sigma_{k}} X_{\pi}=  \sum_{(i,j)\in  J(k,\pi)}  X_{\pi\circ (i,j)}\ 
\end{equation*} where $J(k,\pi):=$  \begin{multline*}
\{ (i,j) \mid i\leq k < j ,\ \pi(i)<\pi(j), \text{ and } 
|\{ \nu \mid i<\nu<j,\ \pi(i)<\pi(\nu)<\pi(j) \}|=0\ \}\ .  \end{multline*} 
(Concise and simple proofs of Monk's rule can be found in each of [M1,M2,W2,W3].) From this formula
one easily derives that the product $x_{k}  X_{\pi}$ is of the form 
``sum on the r.h.s. of (2) minus a similar sum''; but the subtracted sum is zero, 
if for example $k=\pi^{-1}(1)$ (see [W2] or [W3] for details). 

Note that formula (2) relates the calculation of Schubert polynomials
directly to their multiplicative properties, respectively, the intersection calculus of 
Schubert varieties. \\

It is time now to describe the diagram rule for the generation of Schubert 
polynomials previously conjectured by Kohnert [K].

A (box) {\em diagram} is a finite collection of  unit squares or boxes with vertices
in the integer lattice $\Z\times\Z$; the diagram $D(\pi)$ of a permutation  
$\pi \in S_{n}$  is the diagram that originates from the set of boxes 
$\{ [i,j] \mid 1\leq i,j \leq n\}$ by cancellation of the `hooks'  
\begin{equation*} 
\{ [\pi (j),j'] \mid j'\geq j \}\cup \{ [i',j] \mid i'\geq \pi (j) \} 
\end{equation*} for $j=1,\dots,n$. For example,  if $\pi=263154\in S_{6}$, then 
$D(\pi)\ =$\\ \begin{center} \bpi(60,60)(0,0) 
  \put(0,0){\line(0,1){60}} \put(0,0){\line(1,0){60}}  
  \put(0,60){\line(1,0){60}} \put(60,0){\line(0,1){60}}  
    \put(0,0){\cc{}} \put(10,0){\cc{}} \put(10,20){\cc{}} 
	\put(10,30){\cc{}} \put(10,40){\cc{}} \put(20,0){\cc{}} 
	\put(40,30){\cc{}}  
    \put(0,10){\ccd}  \put(5,15){\line(1,0){55}}  \put(5,15){\line(0,1){45}}
    \put(10,50){\ccd} \put(15,55){\line(1,0){45}} \put(15,55){\line(0,1){5}}
    \put(20,20){\ccd} \put(25,25){\line(1,0){35}} \put(25,25){\line(0,1){35}}
    \put(30,0){\ccd}  \put(35,5){\line(1,0){25}}  \put(35,5){\line(0,1){55}}
    \put(40,40){\ccd} \put(45,45){\line(1,0){15}} \put(45,45){\line(0,1){15}}
    \put(50,30){\ccd} \put(55,35){\line(1,0){5}}  \put(55,35){\line(0,1){25}}
  \put(-7,3){\scriptsize{1}} \put(-7,13){\scriptsize{2}} 
  \put(-7,23){\scriptsize{3}} \put(-7,33){\scriptsize{4}} 
  \put(-7,43){\scriptsize{5}} \put(-7,53){\scriptsize{6}}  
   \put(2,-8){\scriptsize{1}} \put(12,-8){\scriptsize{2}} 
  \put(22,-8){\scriptsize{3}} \put(32,-8){\scriptsize{4}} 
  \put(42,-8){\scriptsize{5}} \put(52,-8){\scriptsize{6}}  
\epi  \end{center} \vspace{11pt} 
where we have added hooks in the positions $(\pi(j),j)$, row numbers  
$i=1,\dots,6$ at the left and column numbers $j=1,\dots,6$ 
at the bottom of the diagram. Kohnert's algorithm says that all monomials 
occurring in a Schubert polynomial $X_{\pi}$ can be found by looking at the 
set $K(D(\pi))$ of box diagrams derivable from $D(\pi)$ by (repeated) application of 
K-moves:
 
\begin{Def} {\bf (K-moves)} \  
Let $[i,j]\in D$ with $\{ (i',j) \mid i'> i\} \cap D=\emptyset$, 
i.e., there is no box above $[i,j]$ in $D$, and assume that \begin{equation*}  
M_{D} (i,j):=\{ (i,j') \mid j'<j,\ [i,j'] \notin D \} \neq \emptyset\ .
\end{equation*}  
Then $[i,j]$ is allowed to move to the position in $M_{D} (i,j)$ with  
the greatest column number $j'$, i.e., the closest empty position left 
to $[i,j]$ in row $i$ of $D$. A K-move of the box $[i,j]$ will be called {\em free}, 
if $(i,j-1)\in M_{D} (i,j)$, and a {\em tunnelling move} 
(through the boxes $[i,j-1], [i,j-2], \dots \in D$) otherwise. 
\end{Def} 

For any diagram $D$ let $D^{[j,j']}$, $D_{[i,i']}$ and
$D^{[j,j']}_{[i,i']}$ denote the sub diagrams (``minors'')
of $D$ that contain only the boxes in the intervals of columns 
$[j,j']$, rows $[i,i']$ and in both columns $[j,j']$
and rows $[i,i']$, respectively. A special case of this notation can be
used to associate a monomial to a diagram $D$ by 
$x^{D} := x_{1}^{\beta _{1}} x_{2}^{\beta _{2}} \dots\ $ where $\beta_{j}:=|D^{[j]}|$
and $D^{[j]}:=D^{[j,j]}$.
The purpose of the present paper is to give a simple and natural proof of

\begin{Thm} For any natural number $n\in \N$ and permutation $\pi \in S_{n}$ let
$K:=K(D(\pi))$ be the set of diagrams derivable from $D(\pi)$ by repeated application
of K-moves. Then \begin{equation*} 
 X_{\pi}=\sum_{D\in K} x^{D}\ . \end{equation*}
\end{Thm} 
 
\begin{Ex} For the permutation $\pi=31542$ one computes algebraically $X_{\pi}=   
x_{1}^{2} x_{3}^{2} x_{4} + x_{1}^{2} x_{2} x_{3} x_{4} 
+ x_{1}^{3} x_{3} x_{4} + x_{1}^{2} x_{2}^{2} x_{4} 
+ x_{1}^{2} x_{2} x_{3}^{2} + x_{1}^{3} x_{2} x_{4} 
+ x_{1}^{2} x_{2}^{2} x_{3} + x_{1}^{3} x_{2} x_{3} $. And indeed, the set
 $K$ for this permutation contains all elements of the following poset:
\begin{center}
\setlength{\unitlength}{1.4pt} 
\bpi(200,230)(0,0) 
 \put(50,0){\ccc{}} \put(50,5){\ccc{}} \put(50,10){\ccc{}} 
     \put(55,5){\ccc{}} \put(60,5){\ccc{}}
 \put(50,150){\ccc{}} \put(50,155){\ccc{}} \put(55,160){\ccc{}} 
     \put(60,155){\ccc{r}} \put(65,155){\ccc{r}}
 \put(0,100){\ccc{}} \put(0,105){\ccc{}} \put(0,110){\ccc{}} 
     \put(10,105){\ccc{r}} \put(15,105){\ccc{r}}
 \put(50,100){\ccc{}} \put(50,105){\ccc{}} \put(55,110){\ccc{}} 
     \put(55,105){\ccc{}} \put(65,105){\ccc{}}
 \put(100,100){\ccc{}} \put(100,105){\ccc{}} \put(110,110){\ccc{r}} 
     \put(105,105){\ccc{}} \put(110,105){\ccc{}}
 \put(0,50){\ccc{}} \put(0,55){\ccc{}} \put(0,60){\ccc{}} 
     \put(5,55){\ccc{}} \put(15,55){\ccc{}}
 \put(50,50){\ccc{}} \put(50,55){\ccc{}} \put(55,60){\ccc{}} 
     \put(55,55){\ccc{}} \put(60,55){\ccc{}}
 \put(50,200){\ccc{}} \put(50,205){\ccc{}} \put(60,210){\ccc{}} 
     \put(60,205){\ccc{r}} \put(65,205){\ccc{r}}
  \multiput(65,195)(3,-5){15}{\circle*{1}} 
 \put(60,195){\line(0,-1){25}}
 \put(45,145){\line(-1,-1){29}}  \put(60,145){\line(0,-1){25}} 
 \put(10,95){\line(0,-1){25}} \put(60,95){\line(0,-1){25}}
 \put(15,49){\line(1,-1){30}}  \put(60,45){\line(0,-1){25}}
 \put(45,95){\line(-1,-1){29}} \put(105,98){\line(-1,-1){30}}
\epi \end{center} 
where $D(\pi)$ is the top element and all K-derived diagrams are ordered such that
$D'$ covers $D$, if $D$ originates from $D'$ by an {\em irreducible} (or minimal) K-move.
We have used straight lines for the free K-moves and a dotted line for the tunnelling move.
More information about these posets can be found in [W1] where they form an
integral part of the proof. Here we have exhibited the partial order only as a means
to make the process of successive generation of diagrams more transparent. Note that 
the two boxes in the first column of  $D(\pi)$ never move; such boxes are called
{\em inertial}. (Why certain boxes are marked with an `$r$' will become apparent 
later in Section 3.) 
\hfill $\square$ 
\end{Ex}

A ``natural'' proof of Kohnert's algorithm is one that ``explains'' the definition 
of K-moves and in particular the occurrence of tunnelling moves. Since Schur polynomials
are special Schubert polynomials, the definition of K-moves must include  moves 
which guarantee the realization of all monomials of Schur polynomials by box diagrams. 
But as already observed and proven by Kohnert in [K] the free K-moves
are in fact in natural correspondence to the columnstrict numbering of semistandard
Young tableaux which are used in the well known combinatorial definition of 
Schur polynomials (see also [W1, Section 4]). 
On the other hand free K-moves alone are obviously not sufficient
to generate the monomials of general Schubert polynomials. Therefore Bergeron has 
included in his rule certain ``backward'' moves, i.e., moves of boxes from the left 
to the right; these backward moves were used to model in a combinatorial fashion the 
divided differences used in the classical approach to Schubert polynomials.
Similarly Magyar's rule, which is a simplification of 
Bergeron's rule, has the divided difference approach as its starting point 
(cf. [W1, Section5]). Whereas the proof of these rules in [W1] with the help of the poset
structure on the sets  $K(D(\pi))$ and a suitable recursion argument is relatively 
transparent and easy, the subsequent derivation of Kohnert's rule is done by an 
exhaustive study of cases which establishes correctness without leading to a deeper
understanding. 

In the next section we will see that the generation of Schubert polynomials
via formula (2) (without divided differences) makes the use of tunnelling moves 
virtually inevitable thereby suggesting the possibility of finding analogs of
Kohnert's rule in more general settings: since the symmetric groups are Coxeter
(and Weyl) groups of type $A$, one could use the generalization of Monk's (or "Pieri's")
rule as the starting point for such an investigation.  
\vspace{21pt}





\section{Outline of the proof and two special examples}

The proof proceeds by induction over $n$ and $k$. It is not hard to verify Theorem 2 for 
$n=1,\, 2$ and $3$ and as induction hypothesis we assume that it is true for all 
permutations $\pi\in S_{n-1}$. Setting
\begin{equation} S_{n,k}:=\{ \pi\in S_{n} \mid \pi(k)=1 \}
\end{equation} one can define a bijection between $S_{n-1}$ and $S_{n,n}$ 
with the help of the mapping
\begin{equation} \pi \mapsto 1_{+}(\pi)\,  1 := (\pi(1)+1) \dots (\pi(n-1)+1)\  1\ .
\end{equation} But because the diagram $D(1_{+}(\pi)\,  1)_{[2,n]}$ has the same shape as
$D(\pi)$ and the $n-1$ boxes in the row $D(1_{+}(\pi)\,  1)_{[1]}$ are inertial, 
the formula \begin{equation} 
X_{1_{+}(\pi)\,  1} = x_{1}\cdot\dots\cdot x_{n-1}\,  X_{\pi}
\end{equation} from [W2, Prop. 3.3] (or [W3, Prop. 4.3.3]) shows that Theorem 2 is
valid also for all $\pi\in S_{n,n}$. 

Subsequently we will assume that $\pi$ is contained in some $S_{n,k}$ with $1\leq k <n$ 
and that the assertion of Theorem 2 is true for all $\pi'\in S_{n,n}, \dots, S_{n,k+1}$.
Moreover, let \begin{equation} 
J^{>k}(\pi)=\{k_{0}, k_{1}, \dots, k_{q}\} \ \text{ with } \ 
k+1=k_{0}< k_{1} < \dots < k_{q}\leq n  
\end{equation} and  for $\nu=0,\dots, q$ set $\pi_{\nu}:=\pi\circ (k,k_{\nu})$, 
$B_{\nu}:=D(\pi_{\nu})$, $K_{\nu}:=K(B_{\nu})$ and $i_{\nu}:=\pi(k_{\nu})$. 
Recall also that $K:=K(D(\pi))$. \\

In view of formula (2) the following steps will constitute a proof of Theorem 2:
\begin{enumerate} \item There is a bijection between the sets $K_{\nu}$ and certain
subsets $H_{\nu}$ of $K$ that is {\em faithful with respect to columns}. By this we 
mean that the image $D\in H_{\nu}\
 K$ of some diagram $B\in K_{\nu}$ 
has the same number of boxes in every column as $B$ except for column $k$ where 
$|D^{[k]}|=|B^{[k]}-1|$.  
\item $H_{\nu}\cap H_{\nu'}=\emptyset$, if $\nu\neq \nu'$.
\item $K\subset \bigcup_{\nu=0}^{q} H_{\nu}$.
\end{enumerate} 

Since  $K\supset \bigcup_{\nu=0}^{q} H_{\nu}$ by 1, points 2 and 3 show that
 $K=\biguplus_{\nu=0}^{q} H_{\nu}$; and since the bijections of step 1 are 
faithful w.r.t. columns, one gets the desired conclusion by induction: 
\begin{equation*} 
X_{\pi} \stackrel{(2)}{=} \frac{1}{x_{k}} \sum_{\nu=0}^{q}  X_{\pi_{\nu}} =
 \frac{1}{x_{k}} \sum_{\nu=0}^{q} \sum_{B\in K_{\nu}} x^{B} =
 \sum_{\nu=0}^{q} \sum_{D\in H_{\nu}} x^{D} = \sum_{D\in K} x^{D}\ .
\end{equation*}  \vspace{17pt} 

To carry out the above steps we compare first of all the diagrams of $\pi$ and
any of the $\pi_{\nu}$:
\begin{center} $D(\pi)\ =\ $
 \bpi(110,60)(0,0) 
  \put(0,0){\line(1,0){110}} 
  \put(40,0){\ccd}  \put(45,5){\line(1,0){50}}  \put(45,5){\line(0,1){40}}
  \put(80,30){\ccd} \put(85,35){\line(1,0){10}} \put(85,35){\line(0,1){10}}  
  \put(51,11){\dashbox{7}(28,18){}}
  \put(50,30){\cc{s}} \put(60,30){\cc{s}} \put(70,30){\cc{s}} 
	              \put(80,10){\cc{t}} \put(80,20){\cc{t}}  
  \put(33,3){\scriptsize{$1$}}  \put(33,33){\scriptsize{$i_{\nu}$}} 
  \put(42,-8){\scriptsize{$k$}} \put(82,-8){\scriptsize{$k_{\nu}$}}  
\epi \quad \quad \quad \quad   $B_{\nu}:=D(\pi_{\nu})\ =\ $
 \bpi(110,60)(0,0) 
  \put(0,0){\line(1,0){110}} 
  \put(80,0){\ccd}  \put(85,5){\line(1,0){10}}  \put(85,5){\line(0,1){40}}
  \put(40,30){\ccd} \put(45,35){\line(1,0){50}} \put(45,35){\line(0,1){10}}  
  \put(51,11){\dashbox{7}(28,18){}}
  \put(50,0){\cc{s}} \put(60,0){\cc{s}}  \put(70,0){\cc{s}} 
  \put(40,0){\cc{ }} \put(40,10){\cc{t}} \put(40,20){\cc{t}}  
  \put(33,3){\scriptsize{$1$}}  \put(33,33){\scriptsize{$i_{\nu}$}} 
  \put(42,-8){\scriptsize{$k$}} \put(82,-8){\scriptsize{$k_{\nu}$}}  
\epi \end{center} \vspace{21pt} 

The diagrams of $D(\pi)$ and $B_{\nu}$ are identical outside of the array of boxes 
formed by the intersection of rows $1,\dots, i_{\nu}$ with columns $k,\dots , k_{\nu}$ 
where the dashed rectangle is completely filled with boxes except for possibly 
empty rows on levels $\pi(1),\dots,\pi(k-1)$. (These levels are of course also empty in 
the columns containing the t-boxes for both $D(\pi)$ and $B_{\nu}$.) 
Note the additional box $[1,k]\in B_{\nu}$ corresponds to the fact that
$\pi_{\nu}$ covers $\pi$ in Bruhat order thereby having exactly one more inversion than
$\pi$. 

The diagram  in $K$ that corresponds faithfully w.r.t. columns and ``naturally'', i.e., 
with a minimal number of differences to $B_{\nu}$, is the diagram $D_{\nu}$ that results
from $D(\pi)$ by ``swapping'' the boxes (marked with a `t') in column $k_{\nu}$ to
column $k$. By the recursiveness inherent in our induction this ``swapping'' is
therefore a necessary supplement of the free moves.
In fact, it is a sequence of valid tunnelling moves in the sense of Definition 1, because
column $k_{\nu}$ is empty above level $i_{\nu}$ and because of the structure of the 
dashed rectangle.  
  
\begin{center} $D_{\nu}\ =\ $
 \bpi(110,60)(0,0) 
  \put(0,0){\line(1,0){110}} 
  \put(40,0){\ccd}  \put(45,5){\line(1,0){50}}  \put(85,35){\line(0,-1){35}}
  \put(80,30){\ccd} \put(85,35){\line(1,0){10}} \put(85,35){\line(0,1){10}}  
  \put(51,11){\dashbox{7}(28,18){}}
  \put(50,30){\cc{s}} \put(60,30){\cc{s}} \put(70,30){\cc{s}} 
  \put(40,10){\cc{t}} \put(40,20){\cc{t}}  
  \put(33,3){\scriptsize{$1$}}  \put(33,33){\scriptsize{$i_{\nu}$}} 
  \put(42,-8){\scriptsize{$k$}} \put(82,-8){\scriptsize{$k_{\nu}$}}  
\epi  \end{center} \vspace{21pt}

In Example 3 we have introduced already the notion of {\em inertial} boxes. They were 
defined as the boxes in $D(\pi)$ that can never K-move. Equivalently, they could be
defined as the boxes that are not in the upper right area included by any of 
the hooks that were removed for the generation of the diagram $D(\pi)$. Clearly, the inertial
boxes form a "partition" (with respect to columns or rows) in the lower left corner of 
$D(\pi)$ since there are no empty positions available. All other boxes can move 
(column wise from left to right) at least one position to the left. Below we will use the 
notion of inertial boxes in a slightly more general form, namely, a box is called 
{\it inertial} in an arbitrary diagram $D$, if it can not K-move relative to this diagram,
and {\it movable} otherwise. Therefore the 
set of inertial boxes increases monotonically with every K-move executed on a diagram 
until all boxes are inertial (compare again the poset of Example 3). Furthermore, every
rectangle of positions in $D$ formed by the origin as lower left and an inertial box as 
upper right corner contains only inertial boxes (or empty positions).

Observe now that the s-boxes  of $B_{\nu}$ above, i.e., the boxes marked with an `$s$', 
are inertial (in $B_{\nu}$) so that all diagrams of $K_{\nu}=K(B_{\nu})$ can be derived ``as if 
the s-boxes were not there''. Since we want to represent  $K_{\nu}$ faithfully 
w.r.t. columns by a set $H_{\nu}\subset K$ the following definition is natural:

\begin{Def} For $\pi$, $\pi_{\nu}$ and $D_{\nu}$ as above let  
$S(D_{\nu}):= \{ [i_{\nu},k_{0}] , [i_{\nu},k_{0}+1] , \dots, [i_{\nu},k_{\nu}-1] \}$ 
denote the set of s-boxes of $D_{\nu}$. Let $K_{S}(D_{\nu})$ denote the set of all 
diagrams in $K(D_{\nu})$ which can be derived without moving any s-box $S(D_{\nu})$.
Then $D_{\nu}$ is called {\em s-independent}, if 
\begin{equation*} 
K_{S}(D_{\nu})= K( D_{\nu}\setminus S(D_{\nu})) \cup S(D_{\nu})\ ,
\end{equation*} where the union with the set $S(D_{\nu})$ is of course taken for 
every diagram in $K( D_{\nu}\setminus S(D_{\nu}))$.  
$D_{\nu}$ is called {\em s-dependent}, if it is not s-independent.  
\end{Def}

Note that $(D_{\nu})$ is s-independent iff all boxes below $S(D_{\nu})$ in $D_{\nu}$ are inertial.

Moreover, we remark that similarly to the notation $S(D_{\nu})$ of Definition 4 one defines 
the sets of s-boxes $S(B_{\nu}):= \{ [1,k_{0}],\dots , [1,k_{\nu}-1] \}$ and  the sets of t-boxes 
$T(B_{\nu}):=(B_{\nu})^{[k]}\setminus \{[1,k]\}$,   $T(D_{\nu}):= T(B_{\nu})$, 
$T_{\nu}(D(\pi)):=D(\pi)^{[k_{\nu}]}$.

\begin{Lem} For every  $\pi\in S_{n,k}$ with $k <n$ and $J^{>k}(\pi)$ as in (6)
the diagrams $D_{0}$ and $D_{q}$ are s-independent. 
\end{Lem}\begin{proof} For $D_{0}$ this is trivial, because $ S(D_{0})=\emptyset$.
For $D_{q}$ one observes that $(D_{q})^{[k_{0}, n]}_{[1, i_{q}-1]}$ and
 $(D_{q})^{[k_{q} , n]}_{[i_{q},i_{q}]}$ are empty so that no boxes in  
$D_{q}\setminus S(D_{q})$ can be obstructed in their movability by the boxes in $S(D_{q})$.
(Compare $D_{3}$ in Examples 6 and 11.) 
\end{proof}

If for some $\pi$ {\em all} diagrams $D_{\nu}$ are s-independent then it is easy to 
carry out the steps 1, 2 and 3 of the proof:

\begin{Ex} Let $\pi=15432\in S_{5}$. Then
$D(\pi)= $ \bpi(50,40)(0,10) 
  \put(0,0){\line(1,0){50}}  \put(0,0){\line(0,1){40}} 
  \put(10,10){\cc{}}  \put(20,10){\cc{}}  \put(30,10){\cc{}} 
  \put(10,20){\cc{}} \put(20,20){\cc{}} \put(10,30){\cc{}} 
\epi \  and  \vspace{21pt}
 
\begin{center}   
$D_{0}= $ \bpi(50,40)(0,10) 
  \put(0,0){\line(1,0){50}}  \put(0,0){\line(0,1){40}} 
  \put(0,10){\cc{t}}  \put(20,10){\cc{}}  \put(30,10){\cc{}} 
  \put(0,20){\cc{t}} \put(20,20){\cc{}} \put(0,30){\cc{t}} 
\epi \ , \quad 
$D_{1}= $ \bpi(50,40)(0,10) 
  \put(0,0){\line(1,0){50}}  \put(0,0){\line(0,1){40}} 
  \put(10,10){\cc{}}  \put(0,10){\cc{t}}  \put(30,10){\cc{}} 
  \put(10,20){\cc{}} \put(0,20){\cc{t}} \put(10,30){\cc{s}} 
\epi \ , \quad  
$D_{2}= $ \bpi(50,40)(0,10) 
  \put(0,0){\line(1,0){50}}  \put(0,0){\line(0,1){40}} 
  \put(10,10){\cc{}}  \put(20,10){\cc{}}  \put(0,10){\cc{t}} 
  \put(10,20){\cc{s}} \put(20,20){\cc{s}} \put(10,30){\cc{}} 
\epi \ , \quad  
$D_{3}= $ \bpi(50,40)(0,10) 
  \put(0,0){\line(1,0){50}}  \put(0,0){\line(0,1){40}} 
  \put(10,10){\cc{s}}  \put(20,10){\cc{s}}  \put(30,10){\cc{s}} 
  \put(10,20){\cc{}} \put(20,20){\cc{}} \put(10,30){\cc{}} 
\epi \quad  . 
\end{center} \vspace{21pt}

Clearly, all $D_{\nu}$ are s-independent, because the boxes below the sets $S(D_{\nu})$ 
are inertial. Hence the faithful w.r.t. columns bijection of step 1 is simply given by setting 
$H_{\nu}:=K(D_{\nu}\setminus S(D_{\nu})) \cup  S(D_{\nu})$ (remember the removal 
of $[1,k]$).

For any finite permutation $\pi$ the number of boxes in $S(D_{\nu})$ is $k_{\nu}-k-1$
by definition. For any diagram $D\in K(D(15432))$ in our example (or more generally any
$D$ contained in a s-independent $D_{\nu}$) set
\begin{equation*} \mu(D):= \max\ \{\nu \mid S(D_{\nu})\subset D \}\ .
\end{equation*}
Since for all $\nu$ the s-boxes of $D_{\nu}$ are fixed for the $D\in H_{\nu}$ and 
since all boxes in rows below level $i_{\nu}$ are inertial, one has  
$D\in H_{\nu} \gdw \mu(D)=\nu$. This shows both step 2 and step 3.
\hfill $\square$ \end{Ex}

The case that for given $\pi$ all $D_{\nu}$ are s-independent is of course a rare one.
To get a first idea about how to deal with a $D_{\nu}$ that
is s-dependent, we close this section with another simple example.
  
\begin{Ex} Let $\pi=21543\in S_{5}$. Then
$D(\pi)= $ \bpi(50,40)(0,10) 
  \put(0,0){\line(1,0){50}}  \put(0,0){\line(0,1){40}} 
  \put(0,0){\cc{}}   \put(20,20){\cc{}} \put(30,20){\cc{}} \put(20,30){\cc{}} 
\epi \quad  and (omitting the empty second row)  \vspace{21pt}
 
\begin{center}   
$D_{0}= $ \bpi(50,30)(0,0) 
  \put(0,0){\line(1,0){50}}  \put(0,0){\line(0,1){30}} 
  \put(0,0){\cc{}} \put(10,10){\cc{t}} \put(30,10){\cc{}} \put(10,20){\cc{t}} 
\epi \ , \quad  
$D_{1}= $ \bpi(50,30)(0,0) 
  \put(0,0){\line(1,0){50}}  \put(0,0){\line(0,1){30}} 
  \put(0,0){\cc{}} \put(20,10){\cc{r}} \put(10,10){\cc{t}} \put(20,20){\cc{s}} 
\epi \ , \quad 
$D_{2}= $ \bpi(50,30)(0,0) 
  \put(0,0){\line(1,0){50}}  \put(0,0){\line(0,1){30}} 
  \put(0,0){\cc{}} \put(20,10){\cc{s}} \put(30,10){\cc{s}} \put(20,20){\cc{}} 
\epi \quad  . 
\end{center} \vspace{21pt}

By Lemma 5 (or direct inspection) one sees that $D_{0}$ and $D_{2}$ are s-independent. 
But $D_{1}$ is s-dependent. If one K-moves the boxes of $D_{1}$ as if the s-box were 
not there, one would get

\begin{center}    
\bpi(50,30)(0,10) 
  \put(0,0){\line(1,0){50}}  \put(0,0){\line(0,1){30}} 
  \put(0,0){\cc{}} \put(20,10){\cc{}} \put(10,10){\cc{}} \put(20,20){\cc{s}} 
\epi \quad\quad  \quad\quad  
\bpi(50,30)(0,10) 
  \put(0,0){\line(1,0){50}}  \put(0,0){\line(0,1){30}} 
  \put(0,0){\cc{}} \put(20,10){\cc{}} \put(0,10){\cc{}} \put(20,20){\cc{s}} 
\epi \quad\quad \quad\quad   
\bpi(50,30)(0,10) 
  \put(0,0){\line(1,0){50}}  \put(0,0){\line(0,1){30}} 
  \put(0,0){\cc{}} \put(0,10){\cc{}} \put(10,10){\cc{}} \put(20,20){\cc{s}} 
\epi \quad . 
\end{center} \vspace{21pt}

But then the second move would not be a valid K-move. The way out is to fix the r-box of 
$D_{1}$ (marked with an `$r$') instead of the s-box. Then the above diagrams
are faithfully w.r.t. columns represented by:   \vspace{11pt}

\begin{center}    
\bpi(50,30)(0,0) 
  \put(0,0){\line(1,0){50}}  \put(0,0){\line(0,1){30}} 
  \put(0,0){\cc{}} \put(20,10){\cc{r}} \put(10,10){\cc{}} \put(20,20){\cc{}} 
\epi \quad\quad  \quad\quad   
\bpi(50,30)(0,0) 
  \put(0,0){\line(1,0){50}}  \put(0,0){\line(0,1){30}} 
  \put(0,0){\cc{}} \put(20,10){\cc{r}} \put(0,10){\cc{}} \put(20,20){\cc{}} 
\epi \quad\quad  \quad\quad   
\bpi(50,30)(0,0) 
  \put(0,0){\line(1,0){50}}  \put(0,0){\line(0,1){30}} 
  \put(0,0){\cc{}} \put(20,10){\cc{r}} \put(0,10){\cc{}} \put(10,20){\cc{}} 
\epi \ .
\end{center} \vspace{21pt}

It is very important to note that simply fixing the r-box in $D_{1}$ allows 
for more K-derived diagrams than just the two depicted above, namely:  \vspace{11pt}

\begin{center}    
\bpi(50,30)(0,0) 
  \put(0,0){\line(1,0){50}}  \put(0,0){\line(0,1){30}} 
  \put(0,0){\cc{}} \put(20,10){\cc{r}} \put(10,10){\cc{}} \put(10,20){\cc{}} 
\epi \quad\quad  \quad\quad   
\bpi(50,30)(0,0) 
  \put(0,0){\line(1,0){50}}  \put(0,0){\line(0,1){30}} 
  \put(0,0){\cc{}} \put(20,10){\cc{r}} \put(10,10){\cc{}} \put(0,20){\cc{}} 
\epi \quad\quad  \quad\quad   
\bpi(50,30)(0,0) 
  \put(0,0){\line(1,0){50}}  \put(0,0){\line(0,1){30}} 
  \put(0,0){\cc{}} \put(20,10){\cc{r}} \put(0,10){\cc{}} \put(0,20){\cc{}} 
\epi \ .
\end{center} \vspace{21pt}

But these three diagrams are already contained in $K_{S}(D_{0})=K(D_{0})$! 
The key to distinguish between the ``right'' three the ``wrong'' three diagrams which 
fix the r-box is to maintain the order of the two moving boxes
``as if they were on the same level''. The sub diagrams 
\ \bpi(20,20)(0,5)   \put(0,0){\cc{}} \put(10,10){\cc{}}  \epi\  , 
\ \bpi(30,20)(0,5)   \put(0,0){\cc{}} \put(20,10){\cc{}}  \epi\  , etc. where
the boxes are in {\em ascending order} or form an {\em ascending step} are 
the ``right'' one's in  $K_{S}(D_{1})$. The subdiagrams \vspace{5pt} 
\ \bpi(10,20)(0,5)   \put(0,0){\cc{}} \put(0,10){\cc{}}  \epi\  , 
\ \bpi(20,20)(0,5)   \put(10,0){\cc{}} \put(0,10){\cc{}}  \epi\ ,  etc. (the latter 
being in {\em descending order} or forming a {\em descending step}) 
are the ``wrong'' one's. 

It is clear by the forgoing discussion that $H_{2}$ contains all diagrams derivable
from $D_{2}$ with the two s-boxes fixed, that $H_{1}$ contains the diagrams derivable
from $D_{1}$ with the r-box fixed and the two movable boxes maintaining ascending order,
that $D_{0}$ contains all remaining diagrams of $K$  and that the $H_{\nu}$ thus defined
form a partition of $K$. (For a similar situation examine again the poset of Example 3.)
\hfill $\square$ \end{Ex}
\vspace{21pt}



\section{The general case}

Since the discussion of Example 6 (and in particular the equivalence 
$D\in H_{\nu} \gdw \mu(D)=\nu$) applies to all s-independent diagrams $D_{\nu}$, the work 
in the general case has to focus on the s-dependent $D_{\nu}$. Example 7 pointed out
how to proceed: In case of an s-dependent diagram $D_{\nu}$ one must choose
r-boxes as substitutes for the s-boxes. They must be below the s-boxes in the same 
columns (because of faithfulness w.r.t. columns) and the must guarantee optimal
movability of the other boxes (``as if they were not there'') without being inertial
themselves (because the original s-boxes in $B_{\nu}$ are not inertial, too). 
These requirements solicit the following definition:

\begin{Def} Let the permutation $\pi$ be element of some $S_{n,k}$ with $k <n$ and 
with $J^{>k}(\pi)$ as in (6). For any diagram $D_{\nu}$ the set of r-boxes 
$R(D_{\nu})\subset (D_{\nu})^{[k_{0} , k_{\nu}-1]}$  contains the unique box in 
every column in question that is directly above the highest inertial box.
\end{Def} 

\begin{Lem} Let $\pi$, $J^{>k}(\pi)$ and the sets  $R(D_{\nu})$ be given as in 
Definition 8 above. Then: \\ 
a) No r-box is above an s-box.\\
b) If a diagram $D_{\nu}$ is s-independent, then the r-boxes of $D_{\nu}$ are
identical to the s-boxes:  $R(D_{\nu}) = S(D_{\nu})$. Otherwise the r-boxes are
strictly below the s-boxes.\\
c) All r-boxes of an s-dependent $D_{\nu}$ are in the same row.\\
d) If not all $D_{\nu}$ are s-dependent, then \begin{equation} 
\rho:=\max\ \{ \nu \mid D_{\nu}\ \text{\rm is s-dependent }\}
\end{equation} exists and $D_{0}, D_{\rho +1},\dots ,D_{q}$ are s-independent,
whereas $D_{1},\dots ,D_{\rho}$ are s-dependent. Moreover, the r-boxes of the 
s-dependent $D_{\nu}$ are all on level $i_{\rho}$.
\end{Lem}\begin{proof} a) follows from the definition of r-boxes, the fact 
that the s-boxes $S(D_{\nu}) \subset (D_{\nu})^{[k_{0} , k_{\nu}-1]}$ are 
never inertial and that inertial boxes can not be above movable boxes. 

b) After Definition 4 we remarked that $D_{\nu}$ is s-independent iff all boxes 
below $S(D_{\nu})$ in $D_{\nu}$ are inertial. Hence b) is a consequence of a).

c) Suppose that $[i,j]\in R(D_{\nu})$ has minimal column index $j$ and that $[i',j']$
is a different box in $R(D_{\nu})$, which means $j<j'$. Then by Definition 8 the next 
box $[i'',j']$ below $[i',j']$ is inertial and consequently every box in 
$(D_{\nu})^{[1, j']}_{[1,i'']}$ is inertial, whence $i\geq i'$.

It remains to show that $i>i'$ is excluded, too.
But since $[i',j']$ is movable, there must be an empty position $(i',j'')$ in
$D_{\nu}$ with $j''<j'$. In fact, even $j''<j$ because $k<j<j'<k_{\nu}$ and all rows
below $S(D_{\nu})$ are either completely filled with boxes or completely empty.
If now the position  $(i',j'')$ with $j''<j$ is empty in $D_{\nu}$, then the assumption
  $i>i'$ forces an empty position  $(i-1,j'')$ in $D_{\nu}$ and $[i-1,j]$ would be
movable instead of being inertial. Hence all r-boxes are in the same row. 

d) Assume that $D_{\nu}$ is s-independent for some $\nu>0$. Then the boxes below 
$S(D_{\nu})$ in the interval of columns $[k_{0}, k_{\nu-1}]$ are inertial in $D_{\nu}$.
In particular the boxes below $[i_{\nu+1}, k_{0}], \dots, [i_{\nu+1}, k_{\nu-1}]$ are 
inertial $D_{\nu}$. Comparison of $D_{\nu}$ and $D_{\nu+1}$ then shows that consequently
the boxes below $[i_{\nu+1}, k_{0}], \dots, [i_{\nu+1}, k_{\nu}]$ are inertial in 
$D_{\nu+1}$. Hence $D_{\nu+1}$ is s-independent by Definition 4. 

This proves the first part of d). That the r-boxes of the s-dependent $D_{\nu}$ are 
all on level $i_{\rho}$ follows by an analogous argument that proceeds from the s-boxes 
of $D_{\rho+1}$ to the r-boxes of $D_{\rho}, D_{\rho-1}, \dots, D_{1}$ using 
Definition 8. 
\end{proof}

The next problem is to define the sets $H_{\nu}\subset K$ for the $D_{\nu}$ as required
by step 1 in Section 2. For s-independent  $D_{\nu}$ this is done by setting 
 $H_{\nu}:=K(D_{\nu}\setminus S(D_{\nu})) \cup  S(D_{\nu})$. But for  s-dependent 
$D_{\nu}$ it is not possible to simply substitute the s-boxes by the r-boxes. 
The K-derived set fixing the r-boxes would be too big in general. It is necessary to 
apply the notions of ascending and descending orders of boxes from Example 7 to suitable 
subdiagrams. This is done by generalizing the notion of a row or level by a ``line'':

\begin{Def} a) Let $\pi$, $J^{>k}(\pi)$,  $S(D_{\nu})$ and  $R(D_{\nu})$ as in Definition 
{\rm 8} and $\rho$ as in {\rm (7)}.
Then the {\em lines} of an s-independent $D_{\nu}$ are identical to the rows of $D_{\nu}$;
and the  {\em lines} of an s-dependent $D_{\nu}$ are identical to the rows of 
$D_{\nu}$ outside of
\begin{equation} \dcal_{\nu}:=
(D_{\nu})^{[k_{0} , k_{\nu}-1]}_{[i_{\rho}+1, i_{\nu}]}\  
\end{equation}
 whereas each row $i$ with $i_{\rho}\leq i < i_{0}$ is continued inside $\dcal_{\nu}$ 
by the next higher non-empty row of boxes.\\ 
b) The lines that have a non-empty intersection with
$\dcal_{\nu}$ are called {\em proper lines}. The intersection with $\dcal_{\nu}$ is called
the {\em middle part} of the line and the parts left and right of $\dcal_{\nu}$ the {\em left} 
and {\em right part}, respectively. The step from the left to the middle part of a proper line
is called an {\em ascending step} and the step from the middle part to the right part of a 
proper line a {\em descending step}. Alternatively, one could say that the two boxes involved 
in both kinds of steps are in {\em ascending order} respective {\em descending order}.\\
c) The number of boxes contained in the left, middle and 
right part of the $l$-th proper line (counted from bottom to top) of $D_{\nu}$ form the 
first, second and third entry of a vector $\chi_{\nu}^{l}\in \N_{0}^{3}$ called the 
{\em characteristic} of that proper line.     
\end{Def}

\begin{Ex}  Let $\pi=31864752\in S_{8}$. Then (without the empty third row)\\
\begin{center} $D(\pi)= $ \bpi(70,60)(0,10) 
  \put(0,0){\line(1,0){70}}  \put(0,0){\line(0,1){60}} 
  \put(0,0){\cc{}}    \put(0,10){\cc{}}   \put(20,10){\cc{}} 
  \put(30,10){\cc{}}  \put(40,10){\cc{}}  \put(50,10){\cc{}}  \put(60,10){\cc{}} 
  \put(20,20){\cc{}}  \put(30,20){\cc{}}  
  \put(20,30){\cc{}}  \put(30,30){\cc{}} \put(50,30){\cc{}}
  \put(20,40){\cc{}}  \put(20,50){\cc{}} 
\epi \quad\quad  and \quad 
$D_{0}= $ \bpi(70,60)(0,10) 
  \put(0,0){\line(1,0){70}}  \put(0,0){\line(0,1){60}} 
  \put(0,0){\cc{}}    \put(0,10){\cc{}}   \put(10,10){\cc{t}} 
  \put(30,10){\cc{}}  \put(40,10){\cc{}}  \put(50,10){\cc{}}  \put(60,10){\cc{}} 
  \put(10,20){\cc{t}}  \put(30,20){\cc{}}  
  \put(10,30){\cc{t}}  \put(30,30){\cc{}} \put(50,30){\cc{}}
  \put(10,40){\cc{t}}  \put(10,50){\cc{t}} 
\epi \ , \quad \end{center} \vspace{21pt}
\begin{center}
$D_{1}= $ \bpi(70,60)(0,10) 
  \put(0,0){\line(1,0){70}}  \put(0,0){\line(0,1){60}} 
  \put(0,0){\cc{}}    \put(0,10){\cc{}}   \put(20,10){\cc{}} 
  \put(10,10){\cc{t}} \put(40,10){\cc{}}  \put(50,10){\cc{}}  \put(60,10){\cc{}} 
  \put(20,20){\cc{r}}  \put(10,20){\cc{t}}  
  \put(20,30){\cc{}}  \put(10,30){\cc{t}} \put(50,30){\cc{}}
  \put(20,40){\cc{s}}  \put(20,50){\cc{}} 
\epi \ , \quad
$D_{2}= $ \bpi(70,60)(0,10) 
  \put(0,0){\line(1,0){70}}  \put(0,0){\line(0,1){60}} 
  \put(0,0){\cc{}}    \put(0,10){\cc{}}   \put(20,10){\cc{}} 
  \put(30,10){\cc{}}  \put(10,10){\cc{t}} \put(50,10){\cc{}}  \put(60,10){\cc{}} 
  \put(20,20){\cc{s}} \put(30,20){\cc{s}}  
  \put(20,30){\cc{}}  \put(30,30){\cc{}}  \put(50,30){\cc{}}
  \put(20,40){\cc{}}  \put(20,50){\cc{}} 
\epi \ , \quad
$D_{3}= $ \bpi(70,60)(0,10) 
  \put(0,0){\line(1,0){70}}  \put(0,0){\line(0,1){60}} 
  \put(0,0){\cc{}}    \put(0,10){\cc{}}   \put(20,10){\cc{s}} 
  \put(30,10){\cc{s}} \put(40,10){\cc{s}} \put(50,10){\cc{s}}  \put(60,10){\cc{s}} 
  \put(20,20){\cc{}}  \put(30,20){\cc{}}  
  \put(20,30){\cc{}}  \put(30,30){\cc{}} \put(50,30){\cc{}}
  \put(20,40){\cc{}}  \put(20,50){\cc{}} 
\epi \quad . \end{center}  \vspace{21pt}
Therefore $\rho=1$ and the lines of $D_{1}$ are \\
\begin{center}
$D_{1}= $ \bpi(70,60)(0,10) 
  \put(0,0){\line(1,0){70}}   \put(0,0){\line(0,1){60}}    \put(5,5){\line(1,0){20}} 
  \put(5,15){\line(1,0){60}}  \put(15,25){\line(1,1){10}}  \put(15,55){\line(1,0){30}} 
  \put(15,35){\line(1,1){10}} \put(25,45){\line(3,-1){30}} \put(25,35){\line(3,-1){30}}  
  \put(0,0){\cc{}}    \put(0,10){\cc{}}   \put(20,10){\cc{}} 
  \put(10,10){\cc{}}  \put(40,10){\cc{}}  \put(50,10){\cc{}}  \put(60,10){\cc{}} 
  \put(20,20){\cc{r}} \put(10,20){\cc{}}  
  \put(20,30){\cc{}}  \put(10,30){\cc{}} \put(50,30){\cc{}}
  \put(20,40){\cc{}}  \put(20,50){\cc{}} 
\epi  \end{center} \vspace{14pt}
with the characteristics $\chi_{1}^{1}=(1,1,0)$ and $\chi_{1}^{2}=(1,1,1)$. 
\hfill $\square$ \vspace{12pt}
 
\end{Ex}
 
It is useful to think about the lines of an  s-dependent $D_{\nu}$ as the rows 
of $B_{\nu}$  being ``pushed up'' locally by the upward move of the s-boxes of  
$B_{\nu}$ to the position of the r-boxes of  $D_{\nu}$ while at the same time removing
the s-boxes of  $D_{\nu}$. (Note that the removal of  $S(D_{\nu})$ in the process of
pushing up guarantees that the lines modify the original rows only inside $\dcal_{\nu}$
and that all lines are disjoint.) 

\begin{Def}  Let $\pi$ be as in Definition 8. For s-independent $D_{\nu}$ 
set $H_{\nu}:=K(D_{\nu}\setminus S(D_{\nu})) \cup  S(D_{\nu})$. For s-dependent 
$D_{\nu}$ let $H_{\nu}$ be the set of all diagrams in $K(D_{\nu})$ that fix
 $R(D_{\nu})$ and which respect lines in the following sense: there are never boxes
of the same line on top of each other (except in a transitory way during tunnelling). 
\end{Def}  

In other words: The boxes in a proper line move as if they were on one level.
Since all $D\in H_{\nu}$ are derived by K-moves that respect lines, it is possible to 
extend the notions of proper lines and characteristics of Definition 10 to all such $D$:  

\begin{Def}  Let $\pi$ be as in Definition 8 and $H_{\nu}$ as in Definition 12 for 
any s-dependent $D_{\nu}$ and $D \in H_{\nu}$ arbitrary. Then the proper lines of 
some $D$ can be derived recursively from the proper lines of $D_{\nu}$ by a sequence 
of K-move that respect lines.

Accordingly, the notions of left, middle and right parts, of ascending and descending steps
and of a characteristics from Definition 10 b)-c) apply to the proper lines in $D$.
Again the middle part is exactly the elevated portion of the proper line and Again the 
number of boxes contained in the left, middle and right part of the $l$-th proper line 
(counted from bottom to top) of $D$ form the {\em characteristics} $\chi_{\nu}^{l}(D)$ of $D$.     
\end{Def}  
 
Note that $\chi_{\nu}^{l}(D)$ can be differ from $\chi_{\nu}^{l}$ in a certain way: 
the number of boxes in the left part of a proper line can increase at the cost of the right 
part through tunnelling of a box.\\ 

We are now prepared to carry out the steps 1 -- 3 of the proof of Kohnert's algorithm (recall 
Section 2) also for the s-dependent $D_{\nu}$ where $1\leq \nu \leq \rho$. 
For step 1 observe that for every diagram $D\in H_{\nu}$
there is clearly some counterpart $D'\in K_{\nu}=K(B_{\nu})$ that is faithful w.r.t. columns, 
because the K-moves in $H_{\nu}$ respect lines. But conversely there is also for every 
$D'\in K_{\nu}$ a counterpart $D\in H_{\nu}$: any K-move $K_{\nu}$ can be imitated by a sequence 
of one or more K-moves in $H_{\nu}$ that respect lines. The "obstacle" $R(D_{\nu})$ can be 
overcome by tunnelling.\\ 
 
For steps 2 and 3 it is sufficient to show that every diagram $D\in K$ is contained in exactly one 
$H_{\nu}$. If $S(D_{\nu})\subset D$ for any $\nu\in \{\rho+1, \dots, q \}$, then necessarily
$D\in H_{\nu}$ for exactly that $\nu$. (Also the reversal is true.) If this is not the case, 
then we have to show that $D\in H_{\nu}$ for exactly one $\nu\in \{0,1, \dots, \rho \}$. 
The idea how to proceed is as follows:

For all $\nu$ with $1\leq \nu \leq \rho$ try to construct proper lines in $D$ in a way 
that is consistent with the different characteristics $\chi_{\nu}^{l}$ 
-- we will describe an appropriate algorithm below --. 
If this is possible, we write $D\tin H_{\nu}$, and $D\ntin H_{\nu}$ otherwise.
Clearly, $D\in H_{\nu} \Lra D\tin H_{\nu}$ but not necessarily conversely. 
The desired conclusion "$D\in H_{\nu}$ for exactly one $\nu$" is then implied by the two claims\\
a)\quad   $D\tin H_{\nu} \ \Lra\ D\notin H_{\nu'} \quad \forall \nu'<\nu$ and \\
b)\quad   $D\ntin H_{\nu},\ \forall \nu\geq 1 \ \Lra\ D\in H_{0}$. \\
In fact a) and b) together say that the (existing) maximal $\nu\leq \rho$ with 
$D\tin H_{\nu}$ is the unique $\nu$ for which $D\in H_{\nu}$.\\
  
Note that for fixed $\nu\in \{1,\dots,\rho \}$ 
\begin{equation*}  \chi_{\nu}^{l}(2)=r_{\nu}:=|R(D_{\nu})|,\ \forall\ l\ ,
\end{equation*} 
i.e., the middle parts of all proper lines in $D_{\nu}$ have the same cardinality $r_{\nu}$.
Recall further that by tunnelling of boxes $\chi_{\nu}^{l}(1)$ may increase 
at the cost of $\chi_{\nu}^{l}(3)$ and that on levels $i_{\nu}$ no $D\in K$ has any 
boxes right to column $k_{\nu}$. 
\begin{Lem}{\rm (Non-crossing Condition)} Let $D\in K$ be a diagram with more than one
proper line. Then no box from the middle part of a proper line can be left to (in the same row)
any box from the left part of the next proper line above. (It is however possible that 
a box from the right part of a proper line is left to a box from the middle part of the next
proper line below.) \end{Lem}
\begin{proof} A box from the middle part of any proper line can be moved to the left only 
after the corresponding boxes from the middle parts of higher proper lines have been moved 
to the left. But Definition 12 says that moving boxes from the middle part of a proper line
results in "pushing" the boxes from its left part father to the left. \end{proof}

Given any $D\notin H_{\nu}$ for $\rho +1 \leq \nu \leq q$ we discuss now how to construct 
proper lines for given characteristics. Since $R(D_{\rho+1})\nsubseteq D$ by assumption, 
there exists (recall Lemma 9 d) ) a $k'$:
$k_{0}\leq k' < k_{ \rho+1 }$ with $\{[i_{\rho+1 },k_{0}], \dots , [i_{\rho+1 },k']\}\subset D$ 
but $[i_{q},k'+1]\notin D$. Hence it is possible that $D\tin H_{\nu}$ for some 
$\nu$ with $k_{\nu}\leq k'$ and we begin by checking the maximal $\nu$ first, 
than the next smaller $\nu$, etc. .

Assuming that $D\in H_{\nu}$ (for $1\leq \nu \leq \rho$) the positions of the boxes 
$R(D_{\nu})\subset D$ are known and the first proper line can be determined using the characteristic 
$\chi_{\nu}^{1}$. If there are less than $\chi_{\nu}^{1}(3)$ boxes right to $R(D_{\nu})$ in the
first proper line then the missing boxes must have tunnelled to the left part of the line 
(and possibly higher boxes must have tunnelled, too). 
Observing the non-crossing condition of Lemma 14 and using the characteristics 
$\chi_{\nu}^{2},\chi_{\nu}^{3}, \dots$ it can be checked one line after the other, whether it is 
possible to construct all proper lines bottom up in a consistent manner, i.e., 
whether $D\tin H_{\nu}$.
 
\begin{Ex}  Consider the permutation $\pi=$ 3 6 2 1 8 7 10 5 9 4 $\in S_{10}$ with 
(relevant rows only)  \vspace{11pt}
 
\begin{center} 
$D_{0}= $ \bpi(90,30)(0,0) 
  \put(0,0){\line(1,0){90}}  \put(0,0){\line(0,1){30}} 
  \put(10,0){\cc{}}   \put(10,10){\cc{}}  \put(30,0){\cc{t}}  \put(30,10){\cc{t}}  
  \put(50,0){\cc{}}   \put(50,10){\cc{}}  \put(30,20){\cc{t}}
  \put(60,0){\cc{}}   \put(60,10){\cc{}}  \put(70,0){\cc{}}  \put(80,0){\cc{}}
\epi \ , \quad 
$D_{1}= $ \bpi(90,30)(0,0) 
  \put(0,0){\line(1,0){90}}  \put(0,0){\line(0,1){30}} 
  \put(10,0){\cc{}}   \put(10,10){\cc{}}  \put(30,0){\cc{t}}  \put(30,10){\cc{t}}  
  \put(40,0){\cc{r}}  \put(40,10){\cc{}}  \put(40,20){\cc{s}}
  \put(60,0){\cc{}}   \put(60,10){\cc{}}  \put(70,0){\cc{}}  \put(80,0){\cc{}}
\epi \ , \quad \vspace{11pt} \\
$D_{2}= $ \bpi(90,30)(0,0) 
  \put(0,0){\line(1,0){90}}  \put(0,0){\line(0,1){30}} 
  \put(10,0){\cc{}}   \put(10,10){\cc{}}  \put(30,0){\cc{t}}  
  \put(40,0){\cc{r}}  \put(40,10){\cc{s}} \put(40,20){\cc{}}  \put(80,0){\cc{}}
  \put(50,0){\cc{r}}  \put(50,10){\cc{s}} \put(60,0){\cc{r}}  \put(60,10){\cc{s}}
\epi \ , \quad 
$D_{3}= $ \bpi(90,30)(0,0) 
  \put(0,0){\line(1,0){90}}  \put(0,0){\line(0,1){30}} 
  \put(10,0){\cc{}}   \put(10,10){\cc{}}  \put(50,0){\cc{s}}  \put(50,10){\cc{}}  
  \put(40,0){\cc{s}}  \put(40,10){\cc{}}  \put(40,20){\cc{}}
  \put(60,0){\cc{s}}  \put(60,10){\cc{}}  \put(70,0){\cc{s}}  \put(80,0){\cc{s}}
\epi \ . \end{center}  \vspace{11pt}

$D_{0}$ and $D_{3}$ have of course no proper lines whereas $D_{1}$ has two of them with 
characteristics $\chi_{1}^{1}=(2,1,3)$, $\chi_{1}^{2}=(2,1,1)$ and $D_{2}$ has one with 
characteristic $\chi_{2}^{1}=(2,3,1)$. Accordingly, $r_{0}=0$, $r_{1}=1$, $r_{2}=3$ and
$r_{3}=5$. 

Investigation of the following four diagrams \vspace{11pt}

\begin{center} 
$D= $ \bpi(90,30)(0,0) 
  \put(0,0){\line(1,0){90}}  \put(0,0){\line(0,1){30}}  
  \put(0,0){\cc{}}    \put(0,10){\cc{}}   \put(0,20){\cc{}}  \put(20,0){\cc{}}  
  \put(40,0){\cc{?}}  \put(40,10){\cc{}}  \put(30,10){\cc{}}
  \put(50,0){\cc{?}}  \put(50,10){\cc{}}  \put(60,0){\cc{?}} \put(70,0){\cc{}}
\epi\ ,  \quad\ 
$D'= $ \bpi(90,30)(0,0) 
  \put(0,0){\line(1,0){90}}  \put(0,0){\line(0,1){30}}    
  \put(10,0){\cc{}}   \put(10,10){\cc{}}  \put(20,10){\cc{}}  \put(30,10){\cc{}}  
  \put(40,0){\cc{?}}  \put(40,10){\cc{}}  \put(40,20){\cc{}}
  \put(50,0){\cc{?}}  \put(30,0){\cc{}}   \put(60,0){\cc{?}}  \put(70,0){\cc{}}
\epi \quad  \end{center} \vspace{11pt} 
\begin{center} 
$D''= $ \bpi(90,30)(0,0) 
  \put(0,0){\line(1,0){90}}  \put(0,0){\line(0,1){30}}   \put(25,5){\line(1,1){10}} 
  \put(10,0){\cc{}}   \put(10,10){\cc{}}  \put(20,0){\cc{}}  \put(30,10){\cc{}}  
  \put(40,0){\cc{?}}  \put(40,10){\cc{}}  \put(40,20){\cc{}}
  \put(50,0){\cc{?}}  \put(50,10){\cc{}}  \put(60,0){\cc{?}} \put(70,0){\cc{}}
\epi\ ,  \quad\ 
$D'''= $ \bpi(90,30)(0,0) 
  \put(0,0){\line(1,0){90}}  \put(0,0){\line(0,1){30}}  
  \put(0,0){\cc{}}    \put(0,10){\cc{}}   \put(0,20){\cc{}}   \put(20,0){\cc{}}  
  \put(40,0){\cc{?}}  \put(40,10){\cc{}}  \put(30,0){\cc{}}   \put(30,10){\cc{}}
  \put(50,0){\cc{?}}  \put(50,10){\cc{}}   \put(60,0){\cc{?}}  
\epi \quad  \end{center} \vspace{11pt} 

shows that none of them is an element of $H_{3}$, but all of them contain boxes in the
positions $R(D_{1})$ and $ R(D_{2})$ indicated by the question marks. Moreover, it is not hard to
verify that $D\tin H_{2}$ and $D\ntin H_{1}$, $D'\tin H_{1}$ (with tunnelling in the second 
proper line) and $D'\ntin H_{2}$, $D''\tin H_{1}$ and $D''\tin H_{2}$ whereas 
$D'''\ntin H_{1}$ and $D'''\ntin H_{2}$ (watch the necessity of a ascending step!). 

Indeed, $D\in H_{2}$, $D'\in H_{1}$, $D''\in H_{2}$ and $D'''\in H_{0}$ in accordance with
the claims a) and b) to be shown next.    
\hfill $\square$ \end{Ex}

\begin{proof} (of a)) \  Let $D\tin H_{\nu}$ with $\nu \leq \rho$ maximal. Then all middle
parts of the proper lines may be in their original position (forming a "rectangle" of 
boxes with possibly some empty rows) or may not. 

For the first case recall that $\nu'<\nu$ implies $k_{\nu'}< k_{\nu}$, 
$i_{\nu'}>i_{\nu}$ and $r_{\nu'}<r_{\nu}$ whence row $i_{\nu}$ contains more boxes 
right to column $k$ than possible for a $D\in H_{\nu'}$.

For the second case Definition 12 shows that moving a box from the middle part of
a proper lines causes the boxes of its left part to move, too, such that the ascending step
from left to middle part is retained. But since $i_{\nu'}>i_{\nu}$ for $\nu'<\nu$ in case of
$D\in H_{\nu'}$ this would mean an ascending step among the t-boxes of $D$ which is impossible.
(For an illustration examine again $D''$ of Example 15 where the crucial ascending 
step is marked by a line segment). 
\end{proof}
\begin{proof} (of b)) \ Assume $D\ntin H_{\nu},\ \forall \nu\geq 1$. Then for all 
$\nu \geq 1$ the number of boxes right to column $k$ in row $i_{\nu}$ must be less than 
$r_{\nu}$ by the arguments in the proof of a). Clearly, $D_{0}$ obeys this condition and 
at the same time it is the maximal element of the sub poset $H_{0}$ of $K$. 
In other words: every $D\in K$ obeying the 
mentioned condition can be derived by a sequence of K-moves from $D_{0}$ whence 
$D\in H_{0}$. (For an illustration examine again $D'''$ of Example 15.) 
\end{proof}

\vspace{21pt}
\begin{Ack} The valuable remarks and hints of the referees helped much to improve 
the presentation. \end{Ack}

%\vfill \pagebreak

\begin{thebibliography}{9}
\bibitem[B]{B} {\sc N. Bergeron}, A combinatorial construction of the 
Schubert polynomials, {\it J. Comb. Th. A} {\bf 60} (1992), 168-182.
\bibitem[BGG]{BGG} {\sc I.N. Bernstein, I.M. Gelfand, S.I. Gelfand}, 
 Schubert Cells and cohomology of the spaces $G/B$, {\it Russian Math. 
Surveys} {\bf 28} (1973), 1-26. 
\bibitem[Bo]{Bo} {\sc A. Borel},  Sur la cohomologie des espaces fibr\'{e}
principaux et des espaces homog\`{e}nes des groupes Lie compacts, 
{\it Ann. Math.} {\bf 57} (1953), 115 - 207. 
\bibitem[D1]{D1} {\sc M. Demazure}, Invariants sym\'etriques des groups de 
Weyl et torsion, {\it inventiones math.} {\bf 21} (1973), 287 - 301.
\bibitem[D2]{D2} {\sc M. Demazure}, D\'esingularisation des vari\'et\'es
de Schubert g\'en\'eralis\'es, {\it Ann. Scient. Ec. Norm. Sup.} {\bf 7} 
(1974), 53 - 88.
\bibitem[F]{F} {\sc W. Fulton}, ``Young tableaux'', 
Cambridge University Press, Cambridge, 1997.
\bibitem[FP]{FP} {\sc W. Fulton, P. Pragacz}, ``Schubert Varieties and Degeneracy Loci'', 
{\it Lecture Notes in Mathematics} {\bf 1689}, Springer, Berlin, 1998.
\bibitem[K]{K} {\sc A. Kohnert}, ``Weintrauben, Polynome, Tableaux", 
{\it Bayreuther Mathematische Schriften} {\bf 38} (1991), 1 - 97.
\bibitem[L]{L} {\sc A. Lascoux},
 Polyn\^{o}mes de Schubert. Une approache historique, 
{\it Discrete Math.} {\bf 139} (1995), 303 - 317.
\bibitem[LS]{LS} {\sc A. Lascoux, M.-P. Sch\"{u}tzenberger}, 
Polynomes de Schubert, {\it C.R.Acad.Sci.Paris} 
{\bf 294} (1982), 447 - 450.
\bibitem[M1]{M1} {\sc I.G. Macdonald}, Schubert polynomials, {\it in}: 
{\sf A.D. Kendwell (ed.)}, ``Surveys in Combinatorics", {\it London Math. 
Soc. Lec. Notes Ser.} {\bf 166}, 73 - 99, Cambridge University Press, Cambridge 
1991. 
\bibitem[M2]{M2} {\sc I.G. Macdonald}, ``Notes on Schubert 
polynomials", Publications du L.A.C.I.M., vol. 6, Universit\'{e} du  
Qu\'{e}bec, Montr\'{e}al, 1991.
\bibitem[Ma]{Ma} {\sc P. Magyar}, Four new formulas for Schubert polynomials,
 preprint (1995).
\bibitem[Mo]{Mo} {\sc D. Monk}, The geometry of flag manifolds, 
{\it Proc. London Math. Soc. (3)} {\bf 9} (1959), 253-286. 
\bibitem[W1]{W1} {\sc R. Winkel},  Diagram rules for the generation of 
Schubert polynomials, {\it J. Combin. Theory A}  {\bf 86} (1999), 14 - 48.   
\bibitem[W2]{W2} {\sc R. Winkel},  Recursive and combinatorial 
properties of Schubert polynomials, 
{\it Sem. Loth. Comb.} {\bf B38c} (1996),  29 pp.
\bibitem[W3]{W3} {\sc R. Winkel},  ``On algebraic and combinatorial properties of Schur 
and Schubert polynomials'', 
{\it Bayreuther Mathematische Schriften} {\bf 59} (2000), 225 pp.
\end{thebibliography} 
\end{document}
