Using a formula of {\it S. C. Billey}, {\it W. Jockusch} and {\it R. P. Stanley} [Some combinatorial properties of Schubert polynomials, J. Algebr. Comb. 2, No. 4, 345-374 (1993; Zbl 0790.05093)], {\it S. Fomin} and {\it A. N. Kirillov} [Yang-Baxter equation, symmetric functions, and Schubert polynomials, Proceedings of the conference on power series and algebraic combinatorics, Firenze (1993)] have introduced a new set of diagrams that encode the Schubert polynomials. In this paper, these objects are called rc-graphs. Here, two variants of an algorithm for constructing the set of all rc-graphs for a given permutation are defined and proved. This construction makes many of the identities known for Schubert polynomials more apparent, and yields new ones. In particular, we find a new proof of Monk’s rule using an insertion algorithm on rc- graphs. This insertion rule is a generalization of the Schensted insertion for tableaux. We find two conjectures of analogs of Pieri’s rule for multiplying Schubert polynomials. The authors also extend the algorithm to generate the double Schubert polynomials.
Reviewer: N.Bergeron (North York)