Diagram rules for the generation of Schubert polynomials (Q1284466)

The author considers the Schubert polynomials \(X_{\pi}\in {\mathbb{Z}}[x_1,x_2,\ldots]\) associated with the permutations \(\pi\) contained in the symmetric groups \(S_n\). There are many possible ways to introduce the Schubert polynomials via divided difference operators, recursive generation without divided differences based on the Monk rule and the Bruhat order on permutations, via nil-Coxeter relations, the formula of Billey-Jockusch-Stanley, via sums of mixed shift and multiplication operators, via balanced labeled tableaux, via configurations of labeled pseudo-lines, via flagged Schur modules associated to a Rothe diagram, etc. The theme of the paper is the combinatorial generation of Schubert polynomials via sets of box diagrams. The main reasons to expect a combinatorial rule in terms of box diagrams are: the coefficients in \(X_{\pi}\) are non-negative integers and should count some discrete objects; in the special case of Grassmannian permutations the Schubert polynomial is equal to a Schur function in a finite number of variables and the well-known combinatorial properties of Schur functions should extend to Schubert polynomials. The main result of the paper is the proof of a very elegant and easily applicable combinatorial rule for the generation of Schubert polynomials conjectured in 1990 in the thesis by Kohnert. A similar type of combinatorial rule was given by Bergeron. As an intermediate step in the proof of the Kohnert conjecture the author also obtains a simplified proof of the Bergeron rule. In particular, he shows that the Bergeron rule may be also simplified to a version which is very similar to the recent combinatorial rule of Magyar proved with algebro-geometric methods. The author obtains a direct combinatorial proof of the Magyar rule as well. This shows that there is an algebro-geometric meaning of the Bergeron rule. On the other hand it makes apparent the possibility to give fully combinatorial proofs of other results concerning, e.g., the fact that the Schubert polynomial is the character of the flagged Schur module associated to a Rothe diagram.