Last update: 2 July 2013
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.
Here a "diagram" will be any finite non empty set of lattice points in the positive quadrant For example the diagram of a permutation is a diagram in the above sense. Let be any diagram. We denote by the diagram restricted to the row and Let be the columns of in which there is exactly one element of per column. Choose a column Assume first that If or if let be the diagram obtained from by replacing the element by Now suppose instead that We say that the point is with respect to if the number of elements of in the column and in the rows is equal to the number of elements of in the same area. Now if (and if there is no r-fixed element with respect to in or if let be the diagram obtained from by replacing the element by In both cases we say that the diagram is obtained from by a (with respect to For example let be such that is the following:
For this case 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 Let denote the set of all diagrams (including obtainable from by any sequence of B-moves.
Next for let denote the monomial where is the number of elements of in the row. For any permutation we shall have the following theorem:
To prove this we will proceed by reverse induction on If (the longest element of then (B.1) holds since contains only the element and On the other hand from (4.3), Now if then let From (4.2) we have
Let By the induction hypothesis equation (B.1) holds for The induction step will be to "apply" the operator to the diagrams in To this end we need more tools.
For the moment let us fix Let and be respectively the number of elements of in the and rows. We have
This suggests we define the operator directly on the diagram For this we need only to concentrate our attention on the rows and of Let Notice that in all columns of there are exactly two elements and in column of there is exactly one element in position We shall now reduce the sequence of indices according to the following rule. Let Remove from all pairs for which and Let us denote the resulting sequence by Repeat recursively this process on until no such pair can be found. Let us denote by the final sequence. From construction, the sequence is such that if then Let be the minimal such that If then set We are now in a position to define the operation of on the diagram To this end let us first assume that This means that we have more elements. in row then in row Hence for the length of The equality holds if and only if In the case the operator on the diagram is defined by the map
where is identical to except that we remove the element in position and for we successively set to be identical to except that the element is replaced by Now if we have (with equality iff So In this case the operator on the diagram is defined by the map
where is identical to except that we remove the element in position and the element is replaced by For we successively set to be identical to except that the element is replaced by Finally if then
With this definition of we have that
with the positive sign in case (B.4a), and the negative sign in case (B.4b). For (B.4c) the result of (B.5) is zero.
We shall now show that
The reader will notice that in the rectangle defined by the rows and the columns is filled with elements. None of these elements can B-move. Hence these elements are fixed in any diagram The same applies to all elements in column they are packed in the smallest rows and there are no elements in the rows strictly greater than Now let be a diagram in and assume that is non-empty. The remark above implies that the element in position does not affect the sequence of B-moves from to Hence we can apply the same sequence of B-moves to and obtain Moreover is obtainable from by a simple sequence of B-moves in rows for this one successively B-moves all the elements in row and columns given by This gives that is obtainable from by a sequence of B-moves, that is Now from the construction of is obtained from by exactly one B-move. Hence
It is appropriate at this point to give an example. Let Hence and We have depicted below the diagrams and In our example the fixed elements described above are colored in grey and the element in position is colored black.
Now let be the following diagram of
Here, and The reduced sequence is and Hence where
To prove (B.1) the first step is to find a subset of such that when we operate with we obtain To this end let
It is clear from construction that the subsets are disjoint when From (B.6) we only have to prove that for any there is a such that To see that, reduce the sequence by removing recursively all pairs for which and Denote the final sequence by Let be the bubble diagram obtained from by adding an element in position and successively B-moving all elements in positions We have that To see this one applies to the sequence of B-moves from to Of course one should ignore any B-move in rows performed on the original elements of in row But by the choice of the other B-moves apply almost directly and the resulting diagram is precisely Moreover since and we have and
We shall now investigate the effect of on More precisely we have
There are two classes of diagrams in The first class contains the diagrams for which In this case it is trivial that The other class is formed by the diagrams such that and In this case we shall construct an involution, such that Let and We first define the involution for the case Since we must have So let be identical to except that the elements in positions are B-moved to the positions It is clear that But and hence Moreover we have and hence The case is similar to the previous one.
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
Let be any diagram. Choose such that for all Let us suppose that there is a point with Then let be the largest integer such that and let denote the diagram obtained from by replacing by We say that is obtained from by a "K-move". Now let denote the set of all diagrams (including itself) obtainable from by any sequence of K-moves. Kohnert's conjecture states that for any permutation we have
A. Kohnert has proved (B.9) for the case where 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 The idea then is to show both inclusions by induction. The inclusion is the easiest one. We only have to show that any K-move of an element to can be simulated using B-moves. For this we proceed by induction on If then the K-move is simply one B-move. Now if we first perform the sequence of B-moves in row necessary to B-move the element to Then using the induction hypothesis we can K-move to Finally we reverse the first sequence of B-moves in rows That shows
The other inclusion needs a lot more work. For and any row of let denote the set of all diagrams (including obtainable from by any sequence of B-moves in the rows only. It is clear that if is big enough then We may then proceed by reverse induction on Now for a fixed notice that is obtainable from using only K-moves. Let denote the set of all diagrams obtainable from by any sequence of K-moves for which no elements crosses the border between the rows and A simple inductive algorithm may be used here to show that for any we have Next let denote the set of all diagrams of which have more elements than in the rows For almost all the cases it is fairly easy to show (using induction on and the induction hypothesis on that for we have But some of the cases are really hard to formalize! Now this completed would show that since
This is a typed excerpt of the book Notes on Schubert Polynomials by I. G. Macdonald.