Séminaire Lotharingien de Combinatoire 58 (2008), Article B58e

DUALITY OF ANTIDIAGONALS AND PIPE DREAMS

NING JIA AND EZRA MILLER

The cohomology ring H^{∗}(F l_{n}) of the manifold of complete flags in a complex vector space ℂ^{n} has a basis consisting of the Schubert classes [X_{w}], the cohomology classes of the Schubert varieties X_{w} indexed by permutations w ∈ S_{n}. The ring H^{∗}(F l_{n}) is naturally a quotient of a polynomial ring in n variables; nonetheless, there are natural n-variate polynomials, the Schubert polynomials, representing the Schubert classes [LS82a]. The most widely used formulas [BJS93, FS94] for the Schubert polynomial 𝔖_{w} are stated in terms of combinatorial objects called reduced pipe dreams, which can be thought of as subsets of an n × n grid associated to w.

Reduced pipe dreams are special cases of curve diagrams invented by Fomin and Kirillov [FK96]. They were developed in a combinatorial setting by Bergeron and Billey [BB93], who called them rc-graphs, and ascribed geometric origins in [Kog00, KM05]. One of the main results in the latter is that the set RP_{w} of reduced pipe dreams is in a precise sense dual to a family A_{w} of simpler subsets of the n × n grid called antidiagonals (antichains in the product of two size n chains): every antidiagonal in A_{w} shares at least one element with every reduced pipe dream, and each antidiagonal and reduced pipe dream is minimal with this property [KM05, Theorem B]. The antidiagonals were identified there with the generators of a monomial ideal whose zero set corresponds to a certain flat degeneration of the Schubert variety X_{w}. Geometrically, the duality meant that the components in the special fiber are in bijection with the reduced pipe dreams in RP_{w}, which yield directly the monomial terms in 𝔖_{w}. It was pointed out in [KM05, Remark 1.5.5] that the proof of this duality was roundabout, relying on the recursive characterization of RP_{w} by “chute” and “ladder” moves [BB93], along with intricate algebraic structures on the corresponding monomial ideals; our purpose here is to give a direct combinatorial explanation.

Fix a permutation w ∈ S_{n}, and identify it with its permutation matrix, which has an entry 1 in row i and column j whenever w(i) = j, and zeros elsewhere. We write w_{p×q} for the upper left p × q rectangular submatrix of w and

r_{pq} = r_{pq}(w) = #{(i, j) ≤ (p, q) | w(i) = j}

for the rank of the matrix w_{p×q}. Let

l(w) = #{(i, j) | w(i) > j and w^{−1}(j) > i} = #{i < i′ | w(i) > w(i′)}

be the number of inversions of w, which is called the length of w.

Definition 1. A k × ℓ pipe dream is a tiling of the k × ℓ rectangle by crosses and elbows [figure] . A pipe dream is reduced if each pair of pipes crosses at most once.

EM was partially supported by NSF grants DMS-0304789 and DMS-0449102.

For examples as well as further background and references, see [MS05, Chapter 16]. Pipe dreams should be interpreted as “wiring diagrams” consisting of pipes entering from the west and south edges of a rectangle and exiting though the north and east edges, with the tiles and [figure] indicating intersections and bends of the pipes.

The set RP_{w} of reduced pipe dreams for a permutation w consists of those n × n pipe dreams with l(w) crosses such that the pipes entering row i from the west exit from column w(i). In such a pipe dream D, all of the tiles below the main southwestto-northeast (anti)diagonal are necessarily elbow tiles. We identify D with its set of crossing tiles, so that D ⊆ [n] × [n] is a subset of the n × n grid.

Definition 2. An antidiagonal is a subset A ⊆ [n] × [n] such that no element is (weakly) southeast of another: (i, j) ∈ A and (i, j) ≤ (p, q) ⇒ (p, q) ∉ A. Let A_{w} be the set of minimal elements (under inclusion) in the union over all 1 ≤ p, q ≤ n of the set of antidiagonals in [p] × [q] of size 1 + r_{pq}(w).

For example, when w = 2143 ∈ S_{4},

A_{2143} = {{(1, 1)}, {(1, 3), (2, 2), (3, 1)}}
and RP_{2143} = {{(1, 1), (1, 3)}, {(1, 1), (2, 2)}, {(1, 1), (3, 1)}}.

As another example, when w = 1432 ∈ S_{4},

A_{1432} = {{(1, 2), (2, 1)}, {(1, 2), (3, 1)}, {(1, 3), (2, 1)}, {(1, 3), (2, 2)}, {(2, 2), (3, 1)}}

and

RP_{1432} = {{(1, 2), (1, 3), (2, 2)}, {(1, 2), (2, 1), (3, 1)},
{(2, 1), (2, 2), (3, 1)}, {(1, 2), (2, 1), (2, 2)}}.

Given any collection C of subsets of [n] × [n], a transversal to C is a subset of [n] × [n] that meets every element of C at least once. The transversal dual of C is the set C^{∨} of all minimal transversals to C. (Our definition of transversal differs from that in matroid theory, where a transversal meets every subset only once. Here, our transversals do not give rise to matroids: the transversal duals need not have equal cardinality, so they cannot be the bases of a matroid.) When no element of C contains another, it is elementary that taking the transversal dual of C^{∨} yields C.

Our goal is a direct proof of the following, which is part of [KM05, Theorem B]; see also [MS05, Chapter 16] for an exposition, where it is isolated as Theorem 16.18.

Theorem 3. For any permutation w, the transversal dual of the set RP_{w} of reduced pipe dreams for w is the set A_{w} of antidiagonals for w; equivalently, RP_{w} = A_{w}^{∨}.

In other words, every antidiagonal shares at least one element with every reduced pipe dream, and it is minimal with this property.

Proof. We will show two facts.

Claim 1. D ∈ RP_{w} ⇒ D ⊇ E for some E ∈ A_{w}^{∨}.

Claim 2. E ∈ A_{w}^{∨} ⇒ E ∈ RP_{v} for some permutation v ≥ w in Bruhat order.

Assuming these, the result is proved as follows. First we show that A_{w}^{∨} ⊆ RP_{w}. To this end, suppose E ∈ A_{w}^{∨}. Then E ∈ RP_{v} for some v ≥ w by Claim 2, so E ⊇ D for some D ∈ RP_{w} by elementary properties of Bruhat order (use [MS05, Lemma 16.36], for example: reduced pipe dreams for v are certain reduced words for v, and each of these contains a reduced subword for w). Claim 1 implies that D ⊇ E′ for some E′ ∈ A_{w}^{∨}. We get E = E′ by minimality of E, so E = D and v = w.

To show that RP_{w} ⊆ A_{w}^{∨}, assume that D ∈ RP_{w}. Claim 1 implies that D ⊇ E for some E ∈ A_{w}^{∨}. But E ∈ RP_{w} by the previous paragraph, so D = E because all reduced pipe dreams for w have the same number of crossing tiles.

The remainder of this paper proves Claims 1 and 2. □

The key to proving Claims 1 and 2 is the combinatorial geometry of pipe dreams. For this purpose, we identify [n] × [n] with an n × n square tiled by closed unit subsquares, called boxes. This allows us to view pipes, crossing tiles, elbow tiles, and pieces of these as curves in the plane. We shall additionally need the following.

Definition 4. A northeast grid path is a connected arc whose intersection with each box is one of its four edges or else the rising diagonal ⧸ of the box.

Example 5. Fix an antidiagonal A in the k × ℓ rectangle [k] × [ℓ]. There exists a northeast grid path G, starting at the southwest corner of [k] × [ℓ] and ending at the northeast corner, whose sole ⧸ diagonals pass through the boxes in A. There might be more than one; a typical path G with k = 7, ℓ = 15, and |A| = 3 looks as follows:

PSfrag replacements

⇝

Example 6. Let P be a pipe in a pipe dream, or a connected part of a pipe. Define up(P) to be the northeast grid path consisting of the north edge of each box traversed horizontally by P, the west edge of each box traversed vertically by P, and the rising diagonal in each box through which P enters from the south and exits to the east. Dually, define dn(P) to consist of the south edge of each box traversed horizontally by P, the east edge of each box traversed vertically by P, and the rising diagonal in each box through which P enters from the west and exits to the north.

P with up(P) P with dn(P)

Whenever a northeast grid path is viewed as superimposed on a pipe dream, we always assume (either by construction or by fiat) that no pipe crosses it vertically through a diagonal ⧸ segment. This is especially important in the next two lemmas.

The arguments toward Claims 1 and 2 are based on two elementary principles for a region R bounded by northeast grid paths. Such a region has a lower (“southeast”) border SE = SE(R) and an upper (“northwest”) border NW = NW (R).

Lemma 7 (Incompressible flow). Fix a pipe dream. If k pipes enter R vertically through SE and none cross SE again, then NW has at least k horizontal segments.

Proof. Every pipe crossing SE vertically exits R vertically through NW . □

Thus the “flow” consisting of the pipes entering from the south is “incompressible”.

Lemma 8 (Wave propagation). If none of the pipes entering R vertically through SE cross SE again, then #{⧸ segments in SE} ≥ #{⧸ segments in NW}.

Proof. The sum of the numbers of horizontal and diagonal segments on NW equals the corresponding sum for SE since these arcs enclose a region. Now use Lemma 7. □

The “waves” here are formed by the northwest halves of elbow tiles, each viewed as being above a corresponding rising ⧸ diagonal; see also the proof of Lemma 11. In the proof of Proposition 12, the “flipped” version is applied: if none of the pipes entering the region R vertically (downward) through NW cross NW again, then #{⧸ segments in NW} ≥ #{⧸ segments in SE}.

Proposition 9. If D ∈ RP_{w} has no on an antidiagonal A ⊆ [p]×[q] then |A| ≤ r_{pq}.

Proof. The q pipes in D that exit to the north from columns 1, …, q are of two types: r_{pq} of them enter [p] × [q] horizontally into rows 1, …, p, and the other q − r_{pq} of them enter into [p] × [q] vertically from the south. Now simply apply the principle of incompressible flow to the region bounded by a northeast grid path as in Example 5 and the path consisting of the south and east edges of [p] × [q]. □

Corollary 10. Every pipe dream D ∈ RP_{w} is transversal to A_{w}, so Claim 1 holds.

Proof. If an antidiagonal A ⊆ [p] × [q] lies in A_{w}, then by definition A has size at least 1 + r_{pq}(w). Now use Proposition 9. □

Lemma 11. If D ∈ RP_{v} for some permutation v, then for every p, q ∈ {1, …, n}, there is an antidiagonal of size r_{pq}(v) in [p] × [q] on which D has only elbows.

Proof. Let I_{pq} be the set of all r_{pq} of the pipes in D that enter weakly above row p and exit weakly to the left of column q. For each k ≤ q, let b_{k} be the southernmost box (if it exists) in column k that intersects any P ∈ I_{pq}; otherwise, let b_{k} be the northernmost box in column k. Of the q pipes exiting to the north from columns 1, …, q, precisely q − r_{pq} of them cross some b_{k} vertically from the south. The remaining r_{pq} of the boxes b_{k} must be elbow tiles, and these form the desired antidiagonal. □

PSfrag replacements The pipes in I_{pq} and the boxes b_{1}, …, b_{q} in the proof of Lemma 11 Proposition 12. Every transversal E ∈ A_{w}^{∨}, thought of as a pipe dream, is reduced.

p, q

PSfrag replacements

1 2

P b Q

Illustration of the proof of Proposition 12

Proof. Fix a (not necessarily minimal) transversal E of A_{w} containing two pipes P and Q that cross twice, say at ⊞_{1} and ⊞_{2}, with ⊞_{2} northeast of ⊞_{1}. Assume that the pipes P and Q as well as the crosses ⊞_{1} and ⊞_{2} are chosen so that the taxicab distance (i.e., the sum of the numbers of rows and columns) between them is minimal. Then one of the pipes, say P, is northwest of the other on the boundary of this area. The minimality condition implies that no pipe in E crosses P or Q twice, so the principle of wave propagation holds for any region R such that SE(R) is part of up(Q), and the flipped version holds if NW (R) is part of dn(P).

Our goal is to show that if ⊞_{2} is replaced by an elbow tile in E, then E will still have a crossing tile on every antidiagonal A ∈ A_{w}, whence the transversal E is not minimal. The method: for any A ∈ A_{w} containing ⊞_{2}, we produce a new antidiagonal A′ ∈ A_{w} such that ⊞_{2} ∉ A′, and furthermore every box in A′ is either an elbow tile in E or a crossing tile of A. Since A′ contains a crossing tile of E other than ⊞_{2} (by construction and transversality of E), we conclude that A does, as well.

Assume that some box of A lies on ⊞_{2}. For notation, let □_{P} be the box containing the only elbow tile of P in the same row as ⊞_{2}, and □_{Q} the box containing the only elbow tile of Q in the same column as ⊞_{2}. Construct A′ from A using one of the following rules, depending on how A is situated with respect to P and Q. (Some cases are covered more than once; for example, if the next box of A strictly southwest of ⊞_{2} lies between P and Q but south of the row containing □_{Q}.)

• If the southwest box in A is on ⊞_{2}, or if A continues southwest with its next box in a column strictly west of □_{P}, then move A’s box on ⊞_{2} west to □_{P}.

• If A continues southwest of ⊞_{2} with its next box in a row strictly south of □_{Q},

then move A’s box on ⊞_{2} south to lie on □_{Q}. For the remaining cases, we can assume that A has a box strictly southwest of ⊞_{2} but between P and Q (lying on one of P or Q is allowed). Let b be the southwest-most such box of A, and let Ā consist of the boxes of A between ⊞_{2} and b.

• Assume that A continues to the west of P southwest of b. Let G be a northeast grid path passing through all the boxes in Ā as in Example 5, starting with the bottom edge of the box on P that is in the same row as b, and ending with the east edge of ⊞_{2}. Applying the flipped version of wave propagation to the region enclosed by G and dn(P), we conclude that we can define A′ by replacing Ā ∪ {⊞_{2}} with an equinumerous set of elbow tiles on P.

• If A continues to the south of Q after b, let G be a northeast grid path passing through all the boxes in Ā as in Example 5, starting with the west edge of the box on Q in the same column as b, and ending with the east edge of ⊞_{2}. Applying wave propagation to the region enclosed by G and up(Q), we conclude that we can define A′ by replacing Ā ∪ {⊞_{2}} with an equinumerous set of elbow tiles on Q. □

Corollary 13. Claim 2 holds: E ∈ A_{w}^{∨} ⇒ E ∈ RP_{v} for some v ≥ w in Bruhat order.

Proof. Bruhat order is characterized by v ≥ w ⇔ r_{pq}(v) ≤ r_{pq}(w) for all p, q. As E ∈ A_{w}^{∨} ⇒ E ∈ RP_{v} for some v by Proposition 12, we get v ≥ w by Lemma 11. □

References

[BB93] Nantel Bergeron and Sara Billey, RC-graphs and Schubert polynomials, Exp. Math. 2 (1993), no. 4, 257–269.

[BJS93] Sara C. Billey, William Jockusch, and Richard P. Stanley, Some combinatorial properties of Schubert polynomials, J. Algebraic Combin. 2 (1993), no. 4, 345–374.

[FK96] Sergey Fomin and Anatol N. Kirillov, The Yang–Baxter equation, symmetric functions, and Schubert polynomials, Discrete Math. 153 (1996), no. 1–3, 123–143.

[FS94] Sergey Fomin and Richard P. Stanley, Schubert polynomials and the nil-Coxeter algebra, Adv. Math. 103 (1994), no. 2, 196–207.

[Kog00] Mikhail Kogan, Schubert geometry of flag varieties and Gel′fand–Cetlin theory, Ph.D. thesis, Massachusetts Institute of Technology, 2000.

[KM05] Allen Knutson and Ezra Miller, Gröbner geometry of Schubert polynomials, Ann. Math. 161, 1245–1318.

[LS82a] Alain Lascoux and Marcel-Paul Schützenberger, Polynômes de Schubert, C. R. Acad. Sci. Paris Sér. I Math. 294 (1982), no. 13, 447–450.

[MS05] Ezra Miller and Bernd Sturmfels, Combinatorial commutative algebra, Graduate Texts in Mathematics Vol. 227, Springer-Verlag, New York, 2005.

School of Mathematics, University of Minnesota, MN

  E-mail address: njia@math.umn.edu

School of Mathematics, University of Minnesota, MN

  E-mail address: ezra@math.umn.edu