%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 kk}(\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 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'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 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 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 $ji'$ is excluded, too. But since $[i',j']$ is movable, there must be an empty position $(i',j'')$ in $D_{\nu}$ with $j''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'}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}