## Notes on Schubert PolynomialsAppendix

Last update: 2 July 2013

## A Combinatorial Construction of the Schubert Polynomials

### by Nantel Bergeron

In this appendix, we shall give a combinatorial rule based on diagrams for the construction of the Schubert polynomials. A different algorithm had been conjectured (and proved in the case of vexillary permutations) by A. Kohnert. We shall give, at the end of this appendix, a sketch of how one can show the equivalence of the two rules. I wish to acknowledge my indebtedness to Mark Shimozono for the stimulating exchanges regarding this work.

### Combinatorial construction

Here a "diagram" will be any finite non empty set of lattice points $\left(i,j\right)$ in the positive quadrant $\left(i\ge 1,j\ge 1\right)\text{.}$ For example the diagram $D\left(w\right)$ of a permutation $w$ is a diagram in the above sense. Let $D$ be any diagram. We denote by ${D}_{\left(r,r+1\right)}$ the diagram $D$ restricted to the row $r$ and $r+1\text{.}$ Let $j\left(r,D\right)=\left({j}_{1},{j}_{2},\dots ,{j}_{k}\right)$ be the columns of $D$ in which there is exactly one element of ${D}_{\left(r,r+1\right)}$ per column. Choose a column ${j}_{i}\in j\left(r,D\right)\text{.}$ Assume first that $\left(r+1,{j}_{i}\right)\in {D}_{\left(r,r+1\right)}\text{.}$ If $i=k$ or if $\left(r,{j}_{i+1}\right)\in {D}_{\left(r,r+1\right)},$ let ${D}_{1}$ be the diagram obtained from $D$ by replacing the element $\left(r+1,{j}_{i}\right)$ by $\left(r,{j}_{i}\right)\text{.}$ Now suppose instead that $\left(r,{j}_{i}\right)\in {D}_{\left(r,r+1\right)}\text{.}$ We say that the point $\left(r,{j}_{i}\right)$ is $r\text{-fixed}$ with respect to $D\left(w\right)$ if the number of elements of $D$ in the column ${j}_{i}$ and in the rows $r\prime >r$ is equal to the number of elements of $D\left(w\right)$ in the same area. Now if $i=1$ (and if there is no r-fixed element with respect to $D\left(w\right)$ in $D\text{)}$ or if $\left(r+1,{j}_{i-1}\right)\in {D}_{\left(r,r+1\right)},$ let ${D}_{1}$ be the diagram obtained from $D$ by replacing the element $\left(r,{j}_{i}\right)$ by $\left(r+1,{j}_{i}\right)\text{.}$ In both cases we say that the diagram ${D}_{1}$ is obtained from $D$ by a $\text{"}B\text{-move}\text{"}$ (with respect to $D\left(w\right)\text{).}$ For example let $D$ be such that ${D}_{\left(r,r+1\right)}$ is the following:

$1 2 3 4 5 6 7 8 9 r r+1$

For this case $j\left(r,D\right)=\left(2,5,8,9\right)\text{.}$ We can perform on this diagram a B-move in column 2, 5 or 9 and obtain, respectively, the following diagrams:



The element in column 8 is not allowed to move since $\left(r+1,5\right)\notin {D}_{\left(r,r+1\right)}\text{.}$ Let $\Omega \left(w\right)$ denote the set of all diagrams (including $D\left(w\right)\text{)}$ obtainable from $D\left(w\right)$ by any sequence of B-moves.

Next for $D\in \Omega \left(w\right)$ let ${x}^{D}$ denote the monomial ${x}_{1}^{{a}_{1}}{x}_{2}^{{a}_{2}}{x}_{3}^{{a}_{3}}\dots$ where ${a}_{i}$ is the number of elements of $D$ in the ${i}^{\text{th}}$ row. For any permutation $w$ we shall have the following theorem:

$(B.1) 𝔖w=∑D∈Ω(w) xD.$

To prove this we will proceed by reverse induction on $\ell \left(w\right)\text{.}$ If $w={w}_{0}$ (the longest element of ${S}_{n}\text{)}$ then (B.1) holds since $\Omega \left({w}_{0}\right)$ contains only the element $D\left({w}_{0}\right)$ and ${x}^{D\left({w}_{0}\right)}={x}^{\delta }\text{.}$ On the other hand from (4.3), ${𝔖}_{{w}_{0}}={x}^{\delta }\text{.}$ Now if $w\ne {w}_{0}$ then let $r=\text{min}\left\{i:w\left(i\right) From (4.2) we have

$(B.2) 𝔖w=∂r 𝔖wsr.$

Let $v=w{s}_{r}\text{.}$ By the induction hypothesis equation (B.1) holds for ${𝔖}_{v}\text{.}$ The induction step will be to "apply" the operator ${\partial }_{r}$ to the diagrams in $\Omega \left(v\right)\text{.}$ To this end we need more tools.

For the moment let us fix $D\in \Omega \left(v\right)\text{.}$ Let $a={a}_{r}\left(D\right)$ and $b={a}_{r+1}\left(D\right)$ be respectively the number of elements of $D$ in the $r\text{th}$ and $r+1\text{st}$ rows. We have

$(B.3) ∂rxD=∂r… xraxr+1b…= { ∑k=0a-b-1 …xra-r-1 xr+1b+r… if a>b, 0 if a=b, -∑k=0a-b-1 …xra+r xr+1b-r-1… if a

This suggests we define the operator ${\partial }_{r}$ directly on the diagram $D\text{.}$ For this we need only to concentrate our attention on the rows $r$ and $r+1$ of $D\text{.}$ Let $j\left(r,D\right)=\left({j}_{1},{j}_{2},\dots ,{j}_{p}\right)\text{.}$ Notice that in all columns $j of ${D}_{\left(r,r+1\right)}$ there are exactly two elements and in column $w\left(r\right)={j}_{1}$ of ${D}_{\left(r,r+1\right)}$ there is exactly one element in position $\left(r,{j}_{1}\right)\text{.}$ We shall now reduce the sequence of indices $j\left(r,D\right)$ according to the following rule. Let ${J}_{\left(0\right)}=\left({j}_{2},{j}_{3},\dots ,{j}_{p}\right)\text{.}$ Remove from ${J}_{\left(0\right)}$ all pairs ${j}_{k},{j}_{k+1}$ for which $\left(r,{j}_{k}\right)\in D$ and $\left(r+1,{j}_{k+1}\right)\in D\text{.}$ Let us denote the resulting sequence by ${J}_{\left(1\right)}\text{.}$ Repeat recursively this process on ${J}_{\left(1\right)}$ until no such pair can be found. Let us denote by $f\left(r,D\right)=\left({f}_{1},{f}_{2},\dots ,{f}_{q}\right)$ the final sequence. From construction, the sequence $f\left(r,D\right)$ is such that if $\left(r,{f}_{k}\right)\in D$ then $\left(r,{f}_{k+1}\right)\in D\text{.}$ Let $\text{up}\left(r,D\right)$ be the minimal $k$ such that $\left(r,{f}_{k}\right)\in D\text{.}$ If $\left(r+1,{f}_{q}\right)\in D$ then set $\text{up}\left(r,D\right)=q+1\text{.}$ We are now in a position to define the operation of ${\partial }_{r}$ on the diagram $D\text{.}$ To this end let us first assume that $a>b\text{.}$ This means that we have $a-b$ more elements. in row $r$ then in row $r+1\text{.}$ Hence $q-\text{up}\left(r,D\right)+1\ge a-b-1$ for $q$ the length of $f\left(r,D\right)\text{.}$ The equality holds if and only if $\text{up}\left(r,D\right)=1\text{.}$ In the case $a>b$ the operator ${\partial }_{r}$ on the diagram $D$ is defined by the map

$(B.4a) ∂rD→ { D0,D1,D2, …,Da-b-1 }$

where ${D}_{0}$ is identical to $D$ except that we remove the element in position $\left(r,w\left(r\right)\right)$ and for $k=1,2,\dots ,a-b-1$ we successively set ${D}_{k}$ to be identical to ${D}_{k-1}$ except that the element $\left(r,{f}_{\text{up}\left(r,D\right)+k-1}\right)$ is replaced by $\left(r+1,{f}_{\text{up}\left(r,D\right)+k-1}\right)\text{.}$ Now if $a we have $\text{up}\left(r,D\right)-1\ge b-a+1$ (with equality iff $\text{up}\left(r,D\right)=q+1\text{).}$ So $\text{up}\left(r,D\right)-1>b-a\text{.}$ In this case the operator ${\partial }_{r}$ on the diagram $D$ is defined by the map

$(B.4b) ∂rD→ { D0,D1,D2, …,Db-a-1 }$

where ${D}_{0}$ is identical to $D$ except that we remove the element in position $\left(r,{w}_{r}\right)$ and the element $\left(r+1,{f}_{\text{up}\left(r,D\right)-1}\right)$ is replaced by $\left(r,{f}_{\text{up}\left(r,D\right)-1}\right)\text{.}$ For $k=1,2,\dots ,b-a-1$ we successively set ${D}_{k}$ to be identical to ${D}_{k-1}$ except that the element $\left(r+1,{f}_{\text{up}\left(r,D\right)-k-1}\right)$ is replaced by $\left(r,{f}_{\text{up}\left(r,D\right)-k-1}\right)\text{.}$ Finally if $a=b$ then

$(B.4c) ∂rD→{}.$

With this definition of ${\partial }_{r}$ we have that

$(B.5) ∂rxD=± ∑Di∈∂rD xDi,$

We shall now show that

$(B.6) ∂r maps Ω(v) into Ω(w).$

 Proof. The reader will notice that in $D\left(v\right)$ the rectangle defined by the rows $1,2,\dots ,r+1$ and the columns $1,2,\dots ,w\left(r\right)-1$ is filled with elements. None of these elements can B-move. Hence these elements are fixed in any diagram $D\in \Omega \left(v\right)\text{.}$ The same applies to all elements in column $w\left(r\right)\text{;}$ they are packed in the smallest rows and there are no elements in the rows strictly greater than $r\text{.}$ Now let $D$ be a diagram in $\Omega \left(v\right)$ and assume that ${\partial }_{r}D=\left\{{D}_{0},{D}_{1},\dots ,{D}_{m}\right\}$ is non-empty. The remark above implies that the element in position $\left(r,w\left(r\right)\right)$ does not affect the sequence of B-moves from $D\left(v\right)$ to $D\text{.}$ Hence we can apply the same sequence of B-moves to $D\left(v\right)-\left\{\left(r,w\left(r\right)\right)\right\}$ and obtain ${D}_{0}\text{.}$ Moreover $D\left(v\right)-\left\{\left(r,w\left(r\right)\right)\right\}$ is obtainable from $D\left(w\right)$ by a simple sequence of B-moves in rows $r,r+1,$ for this one successively B-moves all the elements in row $r+1$ and columns given by $j\left(r,D\left(w\right)\right)\text{.}$ This gives that ${D}_{0}$ is obtainable from $D\left(w\right)$ by a sequence of B-moves, that is ${D}_{0}\in \Omega \left(w\right)\text{.}$ Now from the construction of ${\partial }_{r}D,$ ${D}_{k}$ $\left(k>0\right)$ is obtained from ${D}_{k-1}$ by exactly one B-move. Hence ${\partial }_{r}D\subset \Omega \left(w\right)\text{.}$ $\square$

It is appropriate at this point to give an example. Let $w=\left(6,3,9,5,1,2,11,8,4,7,10\right)\text{.}$ Hence $r=2$ and $v=\left(6,9,3,5,1,2,11,8,4,7,10\right)\text{.}$ We have depicted below the diagrams $D\left(w\right)$ and $D\left(v\right)\text{.}$ In our example the fixed elements described above are colored in grey and the element in position $\left(r,w\left(r\right)\right)$ is colored black.

$1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11 D(w)D(v)$

Now let $D$ be the following diagram of $\Omega \left(v\right)\text{.}$

$D=$

Here, ${a}_{r}\left(D\right)=7,$ ${a}_{r+1}\left(D\right)=4$ and $j\left(r,D\right)=\left(3,5,7,8,10\right)\text{.}$ The reduced sequence $f\left(r,D\right)$ is $\left(8,10\right)$ and $\text{up}\left(r,D\right)=1\text{.}$ Hence ${\partial }_{r}D=\left\{{D}_{0},{D}_{1},{D}_{2}\right\}$ where

$D0D1D2$

To prove (B.1) the first step is to find a subset of $\Omega \left(v\right)$ such that when we operate with ${\partial }_{r}$ we obtain $\Omega \left(w\right)\text{.}$ To this end let

$Ω0(v)= { D∈Ω(v): ar(D)> ar+1(D) and up(r,D) =1 } .$

We have

$(B.7) Ω(w)= ⋃D∈Ω0(v) ∂rD(disjoint union).$

 Proof. It is clear from construction that the subsets ${\partial }_{r}D$ are disjoint when $D\in {\Omega }_{0}\left(v\right)\text{.}$ From (B.6) we only have to prove that for any $D\prime \in \Omega \left(w\right)$ there is a $D\in {\Omega }_{0}\left(v\right)$ such that $D\prime \in {\partial }_{r}D\text{.}$ To see that, reduce the sequence $j\left(r,D\prime \right)=\left({j}_{1},\dots ,{j}_{p}\right)$ by removing recursively all pairs ${j}_{k},{j}_{k+1}$ for which $\left(r,{j}_{k}\right)\in D\prime$ and $\left(r+1,{j}_{k+1}\right)\in D\prime \text{.}$ Denote the final sequence by $f\prime \left(r,D\prime \right)\text{.}$ Let $D$ be the bubble diagram obtained from $D\prime$ by adding an element in position $\left(r,w\left(r\right)\right)$ and successively B-moving all elements in positions $\left(r+1,{f}_{i}\right)\in D\prime \text{.}$ We have that $D\in \Omega \left(v\right)\text{.}$ To see this one applies to $D\left(v\right)$ the sequence of B-moves from $D\left(w\right)$ to $D-\left\{\left(r,w\left(r\right)\right)\right\}\text{.}$ Of course one should ignore any B-move in rows $r,r+1$ performed on the original elements of $D\left(v\right)$ in row $r\text{.}$ But by the choice of $r,$ the other B-moves apply almost directly and the resulting diagram is precisely $D\text{.}$ Moreover since $f\left(r,D\right)=f\prime \left(r,D\prime \right)$ and $\text{up}\left(r,D\right)=1$ we have $D\in {\Omega }_{0}\left(v\right)$ and $D\prime \in {\partial }_{r}D\text{.}$ $\square$

We shall now investigate the effect of ${\partial }_{r}$ on ${\Omega }_{1}\left(v\right)=\Omega \left(v\right)-{\Omega }_{0}\left(v\right)\text{.}$ More precisely we have

$(B.8) ∑D∈Ω1(v) ∂rxD=0.$

 Proof. There are two classes of diagrams in ${\Omega }_{1}\left(v\right)\text{.}$ The first class contains the diagrams $D$ for which ${a}_{r}\left(D\right)={a}_{r+1}\left(D\right)\text{.}$ In this case it is trivial that ${\partial }_{r}{x}^{D}=0\text{.}$ The other class is formed by the diagrams $D$ such that ${a}_{r}\left(D\right)\ne {a}_{r+1}\left(D\right)$ and $\text{up}\left(r,D\right)>1\text{.}$ In this case we shall construct an involution, $D\to D\prime ,$ such that ${\partial }_{r}{x}^{D}+{\partial }_{r}{x}^{D\prime }=0\text{.}$ Let $f\left(r,D\right)=\left({f}_{1},{f}_{2},\dots ,{f}_{q}\right),$ $a={a}_{r}\left(D\right)$ and $b={a}_{r+1}\left(D\right)\text{.}$ We first define the involution for the case $a>b\text{.}$ Since $\text{up}\left(r,D\right)>1$ we must have $q-\text{up}\left(r,D\right)+1\ge a-b\text{.}$ So let $D\prime$ be identical to $D$ except that the elements in positions $\left(r,{f}_{\text{up}\left(r,D\right)}\right),\left(f,{f}_{\text{up}\left(r,D\right)+1}\right),\dots ,\left(r,{f}_{\text{up}\left(r,D\right)+a-b-1}\right)$ are B-moved to the positions $\left(r+1,{f}_{\text{up}\left(r,D\right)}\right),\left(r+1,{f}_{\text{up}\left(r,D\right)+1}\right),\dots ,\left(r,{f}_{\text{up}\left(r,D\right)+a-b-1}\right)\text{.}$ It is clear that $D\prime \in \Omega \left(v\right)\text{.}$ But $f\left(r,D\prime \right)=f\left(r,D\right)$ and $\text{up}\left(r,D\prime \right)>\text{up}\left(r,D\right)>1,$ hence $D\prime \in {\Omega }_{1}\left(v\right)\text{.}$ Moreover we have ${a}_{r}\left(D\right)=b$ and ${a}_{r+1}\left(D\right)=a,$ hence ${\partial }_{r}{x}^{D}+{\partial }_{r}{x}^{D\prime }=0\text{.}$ The case $a is similar to the previous one. $\square$

A proof of (B.1) is now completed combining (B.2), (B.5), (B.7) and (B.8). More precisely using the induction hypothesis, we have

$𝔖w = ∂r𝔖v (B.2) = ∑D∈Ω(v) ∂rxD = ∑D∈Ω0(v) ∂rxD (B.8) = ∑D∈Ω0(v) ∑Di∈∂rD xDi (B.5) = ∑D′∈Ω(w) xD′. (B.7)$

### Kohnert's construction

Let $D$ be any diagram. Choose $\left(i,j\right)\in D$ such that $\left(i,j\prime \right)\notin D$ for all $j\prime Let us suppose that there is a point $\left(i\prime ,j\right)\notin D$ with $i\prime Then let $h be the largest integer such that $\left(h,j\right)\notin D$ and let ${D}_{1}$ denote the diagram obtained from $D$ by replacing $\left(i,j\right)$ by $\left(h,j\right)\text{.}$ We say that ${D}_{1}$ is obtained from $D$ by a "K-move". Now let $K\left(D\left(w\right)\right)$ denote the set of all diagrams (including $D$ itself) obtainable from $D$ by any sequence of K-moves. Kohnert's conjecture states that for any permutation $w$ we have

$(B.9) 𝔖w=∑D∈K(D(w)) xD.$

A. Kohnert has proved (B.9) for the case where $w$ is a vexillary permutation but the general case was still open. For the interested reader here is a sketch of how one may prove (B.9).

We have noticed by computer that $\Omega \left(w\right)=K\left(D\left(w\right)\right)\text{.}$ The idea then is to show both inclusions by induction. The inclusion $K\left(D\left(w\right)\right)\subset \Omega \left(w\right)$ is the easiest one. We only have to show that any K-move of an element $\left(i,j\right)$ to $\left(h,j\right)$ can be simulated using B-moves. For this we proceed by induction on $i-h\text{.}$ If $i-h=1$ then the K-move is simply one B-move. Now if $i-h>1,$ we first perform the sequence of B-moves in row $h,h+1$ necessary to B-move the element $\left(h+1,j\right)$ to $\left(h,j\right)\text{.}$ Then using the induction hypothesis we can K-move $\left(i,j\right)$ to $\left(h+1,j\right)\text{.}$ Finally we reverse the first sequence of B-moves in rows $h,h+1\text{.}$ That shows $K\left(D\left(w\right)\right)\subset \Omega \left(w\right)\text{.}$

The other inclusion needs a lot more work. For $D\in K\left(D\left(w\right)\right)$ and $i$ any row of $D$ let ${B}_{i}\left(D\right)$ denote the set of all diagrams (including $D\text{)}$ obtainable from $D$ by any sequence of B-moves in the rows $i,i+1$ only. It is clear that if $i$ is big enough then ${B}_{i}\left(D\right)\subset K\left(D\left(w\right)\right)\text{.}$ We may then proceed by reverse induction on $i\text{.}$ Now for a fixed $i,$ notice that ${B}_{i}\left(D\left(w\right)\right)$ is obtainable from $D\left(w\right)$ using only K-moves. Let ${\Omega }_{0}$ denote the set of all diagrams obtainable from ${B}_{i}\left(D\left(w\right)\right)$ by any sequence of K-moves for which no elements crosses the border between the rows $i+1$ and $i+2\text{.}$ A simple inductive algorithm may be used here to show that for any $D\in {\Omega }_{0}$ we have ${B}_{i}\left(D\right)\subset {\Omega }_{0}\text{.}$ Next let ${\Omega }_{k}$ denote the set of all diagrams of $K\left(D\left(w\right)\right)$ which have $k$ more elements than $D\left(w\right)$ in the rows $1,2,\dots ,i+1\text{.}$ For almost all the cases it is fairly easy to show (using induction on $k$ and the induction hypothesis on $i\text{)}$ that for $D\in {\Omega }_{k}$ we have ${B}_{i}\left(D\right)\subset {\Omega }_{k}\text{.}$ But some of the cases are really hard to formalize! Now this completed would show that $\Omega \left(w\right)\subset K\left(D\left(w\right)\right)$ since $K\left(D\left(w\right)\right)=\cup {\Omega }_{k}\text{.}$

## Notes and References

This is a typed excerpt of the book Notes on Schubert Polynomials by I. G. Macdonald.