GRÖBNER GEOMETRY OF VERTEX DECOMPOSITIONS AND OF FLAGGED TABLEAUX

ALLEN KNUTSON, EZRA MILLER, AND ALEXANDER YONG

Abstract. We relate a classic algebro-geometric degeneration technique, dating at least to [Hodge 1941], to the notion of vertex decompositions of simplicial complexes. The good case is when the degeneration is reduced, and we call this a geometric vertex decomposition.

Our main example in this paper is the family of vexillary matrix Schubert varieties, whose ideals are also known as (one-sided) ladder determinantal ideals. Using a diagonal term order to specify the (Gröbner) degeneration, we show that these have geometric vertex decompositions into simpler varieties of the same type. From this, together with the combinatorics of the pipe dreams of [Fomin– Kirillov 1996], we derive a new formula for the numerators of their multigraded Hilbert series, the double Grothendieck polynomials, in terms of flagged set-valued tableaux. This unifies work of [Wachs 1985] on flagged tableaux, and [Buch 2002] on set-valued tableaux, giving geometric meaning to both.

This work focuses on diagonal term orders, giving results complementary to those of [Knutson–Miller 2005], where it was shown that the generating minors form a Gröbner basis for any antidiagonal term order and any matrix Schubert variety. We show here that under a diagonal term order, the only matrix Schubert varieties for which these minors form Gröbner bases are the vexillary ones, reaching an end toward which the ladder determinantal literature had been building.

Contents

1. Introduction and statement of results 2 1.1. Vertex decompositions of simplicial complexes 2 1.2. An analogue for affine schemes 2 1.3. Vexillary matrix Schubert varieties 4 1.4. Gröbner bases 5 1.5. Flagged set-valued tableaux 5 1.6. Schubert and Grothendieck polynomials 6 2. Geometric vertex decompositions 7 2.1. Algebraic aspects 7 2.2. Geometric aspects 8 2.3. Cohomological aspects 10 3. Vexillary matrix Schubert varieties 12 3.1. Matrix Schubert varieties 12 3.2. Vexillary permutations 13 3.3. Diagonal Gröbner bases 17 4. Stanley–Reisner ideals and subword complexes 18 5. Flagged set-valued tableaux 21 5.1. Set-valued tableaux and Grassmannian permutations 21 5.2. Flaggings 24 6. The diagonal Gröbner basis theorem for Schubert ideals is sharp 26 Acknowledgments 28 References 28

Date: 15 March 2005.

1. Introduction and statement of results

Fix an ideal I in a polynomial ring, or correspondingly, its zero scheme X inside a coordinatized vector space. Each term order yields a Gröbner basis for I, or geometrically, a Gröbner degeneration of X into a possibly nonreduced union of coordinate subspaces. Such a degeneration often creates too many pieces all at once, or spoils geometric properties like reducedness; it can be better to work instead with less drastic degenerations that take the limit of X under rescaling just one axis at a time. The limit X′ breaks into two collections of pieces: a projection part and a cone part. In cases where X′ is reduced, quantitative information such as multidegrees and Hilbert series of the original variety X can be derived separately from the parts of this geometric vertex decomposition of X and combined later. Reducing the computation of invariants of X to those of X′ can be especially helpful when the projection and cone parts of X′ are simpler than X.

Under suitable hypotheses, repeating the degeneration-decomposition procedure for each coordinate axis in turn eventually yields the Gröbner degeneration, but with extra inductive information. When the limit X′′ of this sequence is a union of coordinate subspaces, or equivalently, X′′ is defined by a squarefree monomial ideal, the inductive procedure corresponds exactly to the usual notion of vertex decomposition for simplical complexes, as defined in [BP].

Our goals in this paper are to introduce and develop foundations of geometric vertex decompositions, to apply these generalities to the class of vexillary matrix Schubert varieties, and to exhibit the resulting combinatorics on their Gröbner degenerations for diagonal term orders. In particular, through the notion of flagged set-valued tableaux, we unify the work of Wachs on flagged tableaux [Wac] and Buch on set-valued tableaux [Buc], giving geometric meaning to both. Moreover, using these tableaux, we obtain new formulae for homological invariants of the vexillary matrix Schubert varieties. Our results can be interpreted as providing a complete, general, combinatorially enriched development of the theory surrounding Gröbner bases for the extensively studied ladder determinantal ideals, which are the defining ideals of vexillary matrix Schubert varieties.

We begin in this section with a more precise overview, including statements of our main theorems.

1.1. Vertex decompositions of simplicial complexes. Let Δ be a simplicial complex, and l a vertex of Δ. Define two subcomplexes of Δ: the deletion of l is the union δ of faces of Δ not containing l, and the star of l is the union σ of the closed faces containing l. Then Δ equals the union of δ and σ along the link λ = δ ∩ σ of l. The expression Δ = δ ∪_{λ} σ of Δ as a union of the deletion and star of l glued along the link is called the vertex decomposition of the complex Δ at the vertex l. Note that σ is a cone, namely the cone on λ with cone point l.

Vertex decompositions allow for inductive calculations on simplicial complexes, deriving good properties of Δ from corresponding properties of δ and λ. One such property is shellability, as first related to vertex decompositions in [BP].

1.2. An analogue for affine schemes. Associated to a simplicial complex Δ with vertex set V is the Stanley–Reisner scheme Spec 𝕜[Δ], a reduced scheme in the vector space 𝔸^{V} over 𝕜 with basis V defined by

Spec 𝕜[Δ] = ⋃_{F ∈Δ} 𝔸^{F} ,

where 𝔸^{F} is the coordinate subspace of 𝔸^{V} with basis F. Starting from this perspective, the notion of vertex decomposition extends to any coordinatized affine scheme X, meaning a subscheme of the vector space H × L where L is a line with coordinate y. As X might be irreducible, part of the extension involves breaking X into pieces by degeneration.

On the vector space H×L we have an action of the algebraic torus 𝕜^{×} = 𝕜∖{0} by scaling the L coordinate: t · (x⃗, y) = (x⃗, ty). Consider the flat limit X′ = lim_{t)0} t · X, which is the result of a sort of gradual projection of X to H.

That X′ contains the closure Π of the actual projection of X to H is obvious; but there is usually more in X′. View L as the finite part of L ∪ { } ≅ ℙ^{1}, so H × L ⊂ H × ℙ^{1}, and we may take the closure \overline{X} of X inside H × ℙ^{1}. As we slow-motion project X to H × {0} by scaling the L coordinate, we pull it away from H = H × \{ \} without changing the intersection Λ = \overline{X} ∩ H . Consequently, the limit X′ must contain the cone Λ × L from the origin over Λ.

X′ ⊇ (Π × {0}) ∪_{Λ×{0}}(Λ × L)

By part of our first geometric result, Theorem 2.2, this lower bound correctly calculates X′ as a set. When X′ and this union are equal as schemes and not just as sets, such as when the ideal I(X′) is radical and hence the intersection P ∩ C of radical ideals P = I(Π) and C = I(Λ × L), we call this the geometric vertex decomposition of X along the splitting H ⊕ L. The letter P here stands for “projection”, while C stands for “cone”.

Example 1.1. Let I = ⟨xy − 1⟩, so X is a hyperbola. Its projection to the x-axis is dense, and its intersection with the line at infinity meeting the y-axis occurs at on the y-axis itself. Hence we expect the limit X′ to contain the x-axis and the yaxis. Calculating the limit using the 𝕜^{×} action t · I = ⟨xy − t⟩, we set t = 0 to get the ideal of X′, namely I′ = ⟨xy⟩. The equality I′ = P ∩ C holds here, as P = ⟨y⟩ and C = ⟨x⟩, so this example is a geometric vertex decomposition of the hyperbola. The ideal I′ is Stanley–Reisner, but fairly dull—the simplicial complex consists of two points.

Example 1.2. Let I = ⟨xy − 1⟩ ∩ ⟨x, y⟩, so X is now a hyperbola union a point at the origin. A Gröbner basis for I under either of the lexicographic term orders is given by {y^{2}x − y, yx^{2} − x}. Thus I′ = ⟨y^{2}x, yx^{2}⟩. As P = ⟨y⟩ and C = ⟨x⟩, we get I′ ≠ C∩P = ⟨xy⟩, so we do not have a geometric vertex decomposition in this case; the limit X′ contains more, scheme-theoretically, than just the union of two lines. Note that even though P, C are radical ideals, I′ is not radical.

Example 1.3. Let Δ be a simplicial complex and X = Spec 𝕜[Δ] be the associated Stanley–Reisner scheme. Let L be the line corresponding to a vertex l and H be the hyperplane defined by the sum of the other coordinates. Then the limiting process does not change X, i.e., X′ = X, and the geometric vertex decomposition

X′ = (Π × {0}) ∪_{Λ×{0}}(Λ × L)

is obtained by applying the Stanley–Reisner recipe to each of the subcomplexes of the vertex decomposition

Δ = δ ∪_{λ} σ.

The algebro-geometric degeneration technique investigated here is classical, see, e.g., [Hod]. However, our desire to explicate the analogy with vertex decompositions of simplicial complexes, and to put this story inside a general framework, was motivated by our work with vexillary matrix Schubert varieties, as detailed below. Actually, during the preparation of this text, further examples of geometric vertex decompositions and applications of the methods given below have been found, see, e.g., [KY1, KY2, K2, KMN, KZJ, PS] (see also [K1] for a summary of the first four of these papers). We believe that it would be very interesting to find more examples of schemes that can be profitably studied from the viewpoint suggested here.

1.3. Vexillary matrix Schubert varieties. To each permutation π ∈ S_{n}, there is an associated matrix Schubert variety \overline{X}_{π} ⊆ M_{n} living in the space M_{n} of n×n matrices, and also a set of accessible boxes in the diagram of π (these definitions appear in Sections 3.1–3.2). Each accessible box (l, m) yields a splitting M_{n} = H ⊕ L, where H consists of the matrices with entry 0 at (l, m), and L consists of those matrices with entries 0 everywhere else.

We are now ready to attempt a geometric vertex decomposition of \overline{X}_{π}. Things behave particularly well if π is vexillary, a condition with surprisingly many equivalent formulations, some of which are expounded in Section 3.2.^{1} Among the vexillary permutations, the simplest (and easiest to characterize) are the Grassmannian permutations, which are those with exactly one descent π(i) > π(i + 1). The following is stated more precisely in Lemma 3.7, Theorem 3.8, and Proposition 3.9.

Theorem. Fix a vexillary permutation π.

a) Let M_{n} = H ⊕ L be the decomposition at an accessible box. Set X′ = lim_{t)0} t · \overline{X}_{π}. Then X has a geometric vertex decomposition given by X′ = (Π × {0}) ∪_{Λ×{0}}(Λ × L), where Π × L and Λ × L are each again vexillary matrix Schubert varieties.

b) There is a sequence of permutations σ_{1}, …, σ_{t} with σ_{1} being Grassmannian and σ_{t} = π, such that each \overline{X}_{σ_{i}} for i > 1 arises as the cone part of a geometric vertex decomposition of the previous \overline{X}_{σ_{i−1}}.

One interpretation of these two statements is that, if we wish to inductively study Grassmannian matrix Schubert varieties via our degeneration technique, then the class of vexillary matrix Schubert varieties is a suitable one to work in. Another interpretation is that if we wish to answer questions about vexillary matrix Schubert varieties, then we should try to reduce these to questions about Grassmannian matrix Schubert varieties.

1See [KY2] for a treatment of the non-vexillary case.

1.4. Gröbner bases. The ideal I_{π} of any matrix Schubert variety \overline{X}_{π} is generated by certain minors in the n × n matrix of variables, namely Fulton’s essential minors [Ful]. In this paper we are concerned with diagonal term orders, which by definition choose from each minor its diagonal term as the largest. The following combines Theorem 3.8 and Theorem 6.1 into one statement.

Theorem. Let π be a permutation. The essential minors constitute a Gröbner basis for \overline{X}_{π} under some (and hence any) diagonal term order if and only if π is vexillary.

The commutative algebra literature has been for some time sneaking up on the “if” direction of this result: extensively studied classes of increasingly complex ladder determinantal ideals defined over the past decade are special cases of vexillary Schubert determinantal ideals; see, e.g., [KM1, Section 2.4] [Stu, Ful, GM] and the references therein. The most inclusive class of ladder determinantal ideals whose generating minors have been shown previously to form diagonal Gröbner bases appear in [GM] (which also contains a well-written exposition about past developments) and cover a substantial portion of the vexillary cases.

The “only if” direction is striking because the essential minors in I_{π} form a Gröbner basis for any antidiagonal term order, even if the permutation π is not vexillary [KM1]. Hence we push the diagonal term orders as far as they can go. The key point is that a permutation fails to be vexillary precisely when two of its essential rank conditions are nested, causing the diagonal terms of some essential minors to divide the diagonal terms of other (larger) essential minors.

1.5. Flagged set-valued tableaux. As promised earlier, the initial scheme that is produced in Section 1.4 by Gröbner-degenerating the matrix Schubert variety \overline{X}_{π} all at once exhibits inductive combinatorial structures inherited from stepwise geometric vertex decompositions.

In [KM1], the antidiagonal initial schemes of all matrix Schubert varieties were shown to be Stanley–Reisner schemes of certain subword complexes (whose definition from [KM2] we recall in Section 4, in a special case). The faces of the subword complexes in [KM1] corresponded naturally to the reduced pipe dreams of Fomin and Kirillov [FK2, BB].

Here, we again get subword complexes for the initial scheme, along with a geometric explanation for their vertex-decomposability. However, the combinatorics involves flagged set-valued tableaux, whose definition we introduce in Section 5, providing the natural common generalization of flagged tableaux [Wac] and set-valued tableaux [Buc].^{2} For the term order, pick a total ordering of the n^{2} matrix variables in which no variable appears earlier in the order than another one weakly to the southeast; the resulting lexicographic term order is easily seen to be a diagonal term order. The following theorem provides our Gröbner geometry explanation of the naturality of flagged set-valued tableaux.

Theorem. If π is a vexillary permutation, then the above lex ordering induces a sequence of degenerations of \overline{X}_{π}, each one a geometric vertex decomposition. The end result of these degenerations is a vertex decomposition of the initial scheme, the Stanley–Reisner scheme of a certain subword complex Γ_{π}, whose interior faces correspond in a natural way to flagged set-valued tableaux and whose maximal faces correspond to flagged tableaux.

2An alternative combinatorial approach to this simplicial complex structure on tableaux, logically independent of [KM2], is given in [KMY].

The first sentence of the above result was discussed in Section 1.3. To relate a geometric vertex decomposition along the way to an actual vertex decomposition at the end of the sequence we use Proposition 2.3. The rest is a combination of Theorem 4.4, where we identify the initial ideal, and Theorem 5.8, where we biject the flagged set-valued tableaux with special cases of combinatorial diagrams called pipe dreams. When the permutation π is Grassmannian, the interior faces correspond bijectively to the set-valued tableaux—with no flagging—for the associated partition (Theorem 5.5), and the facets correspond to the usual semistandard Young tableaux (Proposition 5.3). The subword combinatorics of diagonal initial ideals is new even for the ladder determinantal ideals whose Gröbner bases were already known from [GM].

1.6. Schubert and Grothendieck polynomials. The combinatorics of initial ideals yields formulae for homological invariants.

Geometrically, the space M_{n} of n × n matrices carries two actions of the group T of invertible diagonal matrices, by multiplication on the left and inverse multiplication on the right, each preserving every decomposition H ⊕ L along a matrix entry. The resulting Gröbner degenerations are therefore T ×T -equivariant, so they preserve the T × T -equivariant classes of \overline{X}_{π} in both cohomology and K-theory.

Equivalently (and more algebraically), the coordinate ring of \overline{X}_{π} carries a grading by ℤ^{2n} in which the variable z_{ij} has ordinary weight x_{i}−y_{j}. Under this grading, the variety \overline{X}_{π} has the same ℤ^{2n}-graded K -polynomial and multidegree (see [MS, Chapter 8] for definitions) as the Stanley–Reisner initial scheme from Section 1.5. Moreover, this K -polynomial and multidegree are known [KM1]: they are, respectively, the double Grothendieck polynomial and double Schubert polynomial associated by Lascoux and Schützenberger [LS] to π; see Section 5.2 for our conventions on Schubert and Grothendieck polynomials in this paper. The previous theorem implies the following.

Corollary. Let π ∈ S_{n} be a vexillary permutation. The double Schubert polynomial can be expressed as the positive sum

𝔖_{π}(x, y) = ∑_{τ∈FT(π)} ∏_{e∈τ} (x_{val(e)} − y_{val(e)+j(e)})

over the set FT (π) of flagged tableaux associated to π, all of which have shape λ(π). Each product is over the entries e of τ, whose numerical values are denoted val(e), and where j(e) = c(e) − r(e) is the difference of the row and column indices.

The double Grothendieck polynomial G_{π}(x, y) can be expressed as the sum

G_{π}(x, y) = ∑_{τ∈FSVT(π)}(−1)^{|τ|−|λ|} ∏_{e∈τ} (1 − \frac{x_{val(e)}}{y_{val(e)+j(e)}} )

over the set FSVT (π) of flagged set-valued tableaux associated to π. The sign (−1)^{|τ|−|λ|} alternates with the number of “excess” entries in the set-valued tableau.

This result appears as part of Theorem 5.8. It was already known in the case of single Schubert polynomials [Wac] and in the case of Grothendieck polynomials for Grassmannian permutations [Buc].

Since the paper [KM1] already provided a geometric explanation for a combinatorial formula for the Grothendieck and Schubert polynomials of any vexillary permutation—indeed, of any permutation—the reader may wonder why we have provided another one. There are three reasons. The primary reason is to show that the combinatorial trick we used in [KM2], vertex-decomposability, can have a transparent geometric origin. Another is to directly connect the Gröbner geometry to Young tableaux, rather than to the less familiar pipe dreams. Finally, the two formulae themselves are very different, as demonstrated in Example 5.10.

One of the satisfying aspects of the degenerations in this paper is that they stay within the class of (vexillary) matrix Schubert varieties. While one can view the antidiagonal degeneration used in [KM1] also in terms of geometric vertex decompositions, we don’t know what the cone and projection pieces look like along the way; they are no longer matrix Schubert varieties.

2. Geometric vertex decompositions

The main results on geometric vertex decompositions are most easily stated in algebraic language, so we do this first, in Theorem 2.1. Then, for ease of future reference, we make explicit in Section 2.2 the geometric interpretation of Theorem 2.1. Our choice of geometric language makes it clear that the description of geometric vertex decomposition already given in Section 1.2 does not really depend on the hyperplane H. We close Section 2.2 with a useful technique for working with (repeated) geometric vertex decompositions of reduced schemes.

2.1. Algebraic aspects. Let R = 𝕜[x_{1}, …, x_{n}, y] be a polynomial ring in n + 1 variables over an arbitrary field 𝕜. We shall be dealing with Gröbner bases, for which our basic reference is [Eis, Chapter 15]. Define the initial y-form in_{y}p of a polynomial p ∈ R to be the sum of all terms of p having the highest power of y. Fix a term order ≺ on R such that the initial term in p of any polynomial p is a term in the initial y-form: in p = in(in_{y}p). Let in J denote the initial ideal of J, generated by the initial terms in f of all f ∈ J, and let in_{y}J denote the ideal generated by the initial y-forms of the elements of J. Thus in ⟨g_{1}, …, g_{r}⟩ ⊇ ⟨in g_{1}, …, in g_{r}⟩, with equality if and only if {g_{1}, …, g_{r}} is a Gröbner basis under ≺. We automatically have in(in_{y}J) = in J, by our condition on ≺.

We say that I is homogeneous if it is ℤ-graded for the grading on R in which all of the variables have degree 1. When I is homogeneous, it has a Hilbert series h_{R/I}(s) = ∑ _{k∈ℤ} dim(R/I)_{k}·s^{k}. When h and h′ are two power series in the variable s with integer coefficients, we write h ≤ h′ if for all k, the coefficient on s^{k} in h is less than or equal to the coefficient on s^{k} in h′.

Theorem 2.1. Let I be an ideal in R, and {y^{d_{i}}q_{i} + r_{i}}_{i=1}^{m} a Gröbner basis for it, where y^{d_{i}}q_{i} is the initial y-form of y^{d_{i}}q_{i} + r_{i} and y does not divide q_{i}. Then the following statements hold for

I′ = ⟨y^{d_{i}}q_{i} | i = 1, …, m⟩, C = ⟨q_{i} | i = 1, …, m⟩, P = ⟨q_{i} | d_{i} = 0⟩ + ⟨y⟩.

a) The given generating sets of I′, C, and P are Gröbner bases, and I′ = in_{y}I.

b) If max_{i} d_{i} = 1, then I′ = C ∩ P and in(C + P ) = in C + in P.

c) \sqrt{I′} = \sqrt{C} ∩ \sqrt{P}.

d) C = (I′ : y ), which is by definition the ideal {f ∈ R | y^{j}f ∈ I′ for some j ≥ 0}.

e) If I is homogeneous, then h_{R/I}(s) ≥ h_{R/P} (s)+s·h_{R/C}(s), with equality if and only

if I′ = C ∩ P. When I′ = C ∩ P, we will call this decomposition of I′ a geometric vertex decomposition of I.

Proof.(a) These all follow from [Eis, Section 15.10.4 and 15.10.5].

(b) The hypothesis means that I′ = yC + ⟨q_{i} | d_{i} = 0⟩. As the generators of C do not involve the variable y, we have yC = C ∩ ⟨y⟩. Hence, using the modular law for ideals (that is, 𝔠 ∩ (𝔞 + 𝔟) = 𝔠 ∩ 𝔞 + 𝔠 ∩ 𝔟 if 𝔠 ⊇ 𝔟), we can conclude that I′ = C ∩ ⟨y⟩ + C ∩ ⟨q_{i} | d_{i} = 0⟩ = C ∩ P. For the equality involving initial ideals, observe that C + P = C + ⟨y⟩, so that in(C + P ) = in C + ⟨y⟩, and use part (a).

(c) Let Ĩ′ = ⟨yq_{i} | d_{i} ≥ 1⟩+⟨q_{i} | d_{i} = 0⟩. Then \sqrt{I′} ⊇ Ĩ′ ⊇ I′, so by the Nullstellensatz all three ideals have the same vanishing set. Part (b) implies Ĩ′ = C ∩ P.

(d) This is elementary, using the fact that I′ is homogeneous for the ℤ-grading in which y has degree 1 and all other variables have degree zero.

(e) It suffices to show that the sum of series on the right hand side of the inequality is the Hilbert series of R/(C ∩ P ), because (i) C ∩ P ⊇ I′ by our proof of (c), and (ii) the quotients R/I and R/I′ have the same Hilbert series. To complete the proof, use the exact sequence

0 ) R/(C + P ) ) R/C ⊕ R/P ) R/(C ∩ P ) ) 0

of R-modules. It implies that

h_{R/(C∩P )} = h_{R/P} + (h_{R/C} − h_{R/(C+P )}).

The equality C + P = C + ⟨y⟩ yields R/(C + P ) = (R/C)/y(R/C). Therefore h_{R/(C+P )}(s) = (1 − s)h_{R/C}(s), because the generators of C do not involve y. □

This inequality (e) is used in [KMN] to study schemes whose Hilbert functions are smallest, in various senses.

2.2. Geometric aspects. While the next theorem essentially recapitulates Theorem 2.1 in geometric language, it is not a verbatim translation. For example, we do not assume that coordinates x_{1}, …, x_{n}, y have been given. One of the purposes of Theorem 2.2 is to describe the flat limit X′ using schemes naturally determined by the subscheme X ⊆ V and the choice of the line L, namely Π and Λ, at least in the case where we have a geometric vertex decomposition.

Let V be a vector space over a field 𝕜, viewed as a scheme over 𝕜, and suppose that a 1-dimensional subspace L of V has been given. The projectivization \overline{V} = ℙ(V ⊕ 𝕜), which we view as the projective completion V ∪ ℙV of V, has a point ℙL ∈ ℙV. Denote by Bl_{L}\overline{V} the blow up of ℙ(V ⊕𝕜) at the point ℙL. The exceptional divisor is naturally identified with the projective completion of the quotient vector space V/L, and in particular contains a copy of V/L.

For each choice of a codimension 1 subspace H ⊆ V complementary to L, there is an action t · (h⃗, l) = (h⃗, tl) of 𝕜^{×} on V, which we call scaling L and fixing H.

Theorem 2.2. Let X be a closed subscheme of V and L a 1-dimensional subspace of V. Denote by Π the scheme-theoretic closure of the image of X in V/L, and by \overline{X} the closure of X in Bl_{L}\overline{V}. Set Λ = \overline{X} ∩ V/L, where the intersection of schemes takes place in Bl_{L}\overline{V}.

a) If H is a hyperplane complementary to L in V, and we identify H with V/L, then the flat limit X′ := lim_{t)0} t · X under scaling L and fixing H satisfies

X′ ⊇ (Π × {0}) ∪_{Λ×{0}}(Λ × L).

b) The scheme-theoretic containment in part (a) is an equality as sets.

c) If (the ideal of) X is homogeneous, then the same holds for Π as well as Λ, and we derive an inequality on Hilbert series of subschemes of V:

h_{X}(s) ≥ (1 − s)h_{Π×L}(s) + sh_{Λ×L}(s).

d) Parts (a) and (c) both become equalities if the flat limit X′ is reduced.

Proof.Pick coordinates x_{1}, …, x_{n} on H and a coordinate y on L, and choose a term order on R = 𝕜[x_{1}, …, x_{n}, y] such that in(in_{y} p) = in p for all polynomials p. Let I ⊆ R be the ideal defining X. Then there exists a Gröbner basis for I with respect to this term order, and we can apply Theorem 2.1 to study the associated ideals I′, C, and P. The ideal P cuts out the projection Π ⊆ H, while C cuts out the subscheme Λ × L ⊆ V. Our claims therefore follow from Theorem 2.1. □

Though it is very important in this paper, we did not see how to state Theorem 2.1 part (b) in a particularly geometric way. We expressed the Hilbert series in Theorem 2.2(c) in terms of X, Π × L, and Λ × L because all three occur in the same vector space (once H has been chosen).

The property of being a geometric vertex decomposition is preserved under (further) degeneration, so long as the schemes stay reduced:

Proposition 2.3. Let X ⊇ D be two reduced closed subschemes of H × L. Let M be a 1-dimensional vector space, and define Y ⊆ H × L × M as

Y = (X × {0}) ∪_{D×{0}}(D × M).

Use the action of 𝕜^{×} on H × L scaling L and fixing H to define two new flat limits X′ and D′. Assume that these are again reduced, so they are geometric vertex decompositions. Then the flat limit Y ′ of Y under the action of 𝕜^{×} on H × M × L scaling L and fixing H × M is again reduced, and hence it is a geometric vertex decomposition.

Proof.By Theorem 2.2, as subschemes of H × L we have

X′ = (Π × {0}) ∪ (Λ × L) and D′ = (Σ × {0}) ∪ (Γ × L).

Hence the projection and cone parts of Y ’ are, as subsets of H × M,

(Π × {0}) ∪_{Σ×{0}}(Σ × M) and (Λ × {0}) ∪_{Γ ×{0}}(Γ × M),

respectively. Again by Theorem 2.2 we get

Y ′ ⊇ (Π × {0} × {0}) ∪ (Σ × {0} × M) ∪ (Λ × L × {0}) ∪ (Γ × L × M).

Our goal is to prove the above containment to be an equality of schemes. Rearranging, we see that

Y ′ ⊇ (Π × {0} × {0}) ∪ (Λ × L × {0}) ∪ (Σ × {0} × M) ∪ (Γ × L × M)
= (X′ × {0}) ∪_{D′×{0}}(D′ × M).

Since X′ and D′ had geometric vertex decompositions, the right hand side has the same Hilbert series as (X × {0}) ∪_{D×{0}}(D × M) = Y, which matches that of Y ′, the left hand side. Therefore the containment is an equality. □

2.3. Cohomological aspects. Even if the degeneration by rescaling an axis is not a geometric vertex decomposition, the limit X′ can still be analyzed enough to give a useful positivity statement about (multi)degrees. Moreover, it is always an equality, not just an inequality like Theorem 2.2 part (c).

For X a T -invariant subscheme of a vector space V carrying an action of a torus T, there is an associated multidegree deg_{V} X living in the symmetric algebra Sym(T^{∗}), where T^{∗} is the weight lattice of T. Our general reference for multidegrees is [MS, Chapter 8], though this particular algorithm appears in [Jo]. Proposition 2.4. Three axioms suffice to characterize the assignment of multidegrees:

a) deg_{{0}}{0} = 1 for the zero vector space 0 and the trivial torus action.

b) If the components of X of top dimension are X_{1}, …, X_{k}, occurring in X with multiplicities m_{1}, …, m_{k}, then deg_{V} X = ∑ _{i} m_{i} deg_{V} X_{i}.

c) If H is a T -invariant hyperplane in V, and X is an irreducible variety, then (i) if X ⊈ H, then deg_{V} X = deg_{H}(X ∩ H). (ii) if X ⊆ H, then deg_{V} X = wt(V/H) deg_{H} X, where wt(V/H) ∈ Sym^{1}(T^{∗}) is the weight of the T -action on the 1-dimensional representation V/H.

Proof.That these properties are satisfied by multidegrees follows from [MS, Section 8.5 and Exercise 8.12]. These properties determine a unique assignment by induction on the dimension of V: the base case is the first axiom; the second axiom reduces the calculation of multidegrees from schemes to varieties; and the third axiom brings the dimension down by 1 for varieties. □

If T is 1-dimensional, then Sym^{codimX}(T^{∗}) ≅ ℤ, so deg_{V} X ∈ Sym^{codimX}(T^{∗}) is specified by a number. If in addition the torus action is by global rescaling on V, so X is an affine cone, then this number is the usual degree of the corresponding projective variety. This cohomological interpretation is related to the general fact that Sym(T^{∗}) is the equivariant cohomology ring, and equivariant Chow ring, of V. The theorem to follow is already interesting as a statement about usual degrees.

In an unfortunate collision of terminology, the degree of a morphism^{3} X ) Y of reduced irreducible schemes over a field 𝕜 is defined to be the degree of the extension 𝕜(X) ⊇ 𝕜(Y ) of their fraction fields (if this extension is finite) and zero otherwise. When 𝕜 is algebraically closed, the degree of X ) Y is simply the cardinality of a generic fiber, if this number is finite.

3Actually, the two are related. If W ≤ V is a generic subspace of codimension dim X, then the degree of the morphism X ) V/W is the usual degree of the affine cone X. Such genericity is unavailable for most bigger torus actions, and one may view Theorem 2.5 as a version of this statement for multidegrees.

Theorem 2.5. Let X, X′ ⊆ H × L and Π, Λ ⊆ H be as in Theorem 2.2. Assume that X is reduced, irreducible, and invariant under the action of a torus T on V, so its projection Π ⊂ H is, too. Let d be the degree of the projection morphism X ) Π. Then

deg_{V} X = d · deg_{V} Π + deg_{V} (Λ × L).

Moreover, deg_{V} Π = deg_{V} (Π ×L)·wt(V/H), where wt(V/H) ∈ Sym^{1}(T^{∗}) is the weight of the action of T on the one-dimensional representation V/H.

Proof.Let us assume that the morphism X ) Π has degree d > 0, for otherwise X = Π × L = X′, and the result is trivial. The stability of deg under Gröbner degeneration [MS, Corollary 8.47] implies that deg(X) = deg(X′). Additivity of deg on unions [MS, Theorem 8.53] therefore implies, by Theorem 2.2, that deg(X) = deg(Λ × L) + deg(Π′), where Π′ is the (possibly nonreduced) component of X′ supported on Π. It remains only to show that deg(Π′) = d · deg(Π). This will follow from the additivity of deg once we show that Π′—or equivalently, X′—has multiplicity d along Π.

Let K = 𝕜(Π), the fraction field of Π. Given a module M over the coordinate ring 𝕜[Π] of Π, denote by M_{Π} the localization M ⊗_{𝕜[Π]} K at the generic point of Π. The multiplicity of X′ along Π is the dimension of 𝕜[X′]_{Π} as a vector space over K. Now consider the flat degeneration X ⇝ X′ as a family over the line with coordinate ring 𝕜[t], and let M be the coordinate ring of the total space of this family. Thus M is flat as a module over 𝕜[t]; equivalently, M is torsion-free over 𝕜[t]. To prove the result it is enough to show that the localization M_{Π} is flat over K[t], since taking K-vector space dimensions of the fibers over t = 1 and t = 0 yields the degree d of X ) Π and the multiplicity of X′ along Π, respectively.

We know that M is flat over 𝕜[t], that 𝕜[Π][t] is flat over 𝕜[t], and that K[t] is flat over 𝕜[Π][t]. A routine calculation therefore shows that M_{Π} is flat over 𝕜[t]. On the other hand, M is the coordinate ring of the total space of a (partial) Gröbner degeneration, so M ⊗_{𝕜[t]} 𝕜[t, t^{−1}] is the coordinate ring of a family over 𝕜^{×} that is isomorphic to the trivial family 𝕜^{×} × X. Moreover, since the rescaling in our Gröbner degeneration commutes with the projection to Π, the coordinate ring M ⊗_{𝕜[t]} 𝕜[t, t^{−1}] is free over 𝕜[Π][t, t^{−1}]. It follows that M_{Π} ⊗_{K[t]}K[t, t^{−1}] is free over K[t, t^{−1}]. Consequently, the K[t]-torsion submodule of M_{Π} is supported at t = 0. The K[t]-torsion of M_{Π} is thus also 𝕜[t]-torsion, each element therein being annihilated by some power of t. Since M_{Π} has no 𝕜[t]-torsion, we conclude M_{Π} is torsion-free, and hence flat, over K[t].

The claim about deg_{V} Π in the final sentence follows from Proposition 2.4. □

We remark that in the setup of Theorem 2.5, d = 1 is necessary in order to have a geometric vertex decomposition. It is not sufficient, as seen in Example 1.2.

This theorem is applied in [K2] to affine patches on Schubert varieties.

For a subtorus S ⊆ T, there are two different multidegrees deg_{V}^{T} X ∈ Sym(T^{∗}) and deg_{V}^{S} X ∈ Sym(S^{∗}) one could assign to a T -invariant (hence also S-invariant) subscheme X ⊆ V. They are related by the natural map Sym(T^{∗}) ) Sym(S^{∗}) induced from the restriction of characters T^{∗} ) S^{∗}.

The map Sym(T^{∗}) ) Sym(S^{∗}) can be thought of as specialization of polynomials upon the imposition of linear conditions on the variables. The following consequence of Theorem 2.5 gives a criterion for one polynomial to be the specialization of another. In it, we do not assume any Gröbner properties of {y^{d_{i}}q_{i} + r_{i}}; hence the ideal J here is contained in the ideal C from Theorem 2.1, perhaps properly.

Corollary 2.6. Let X ⊆ H × L, where H has coordinates x_{1}, …, x_{n} and L has coordinate y. Assume that H and L are representations of a torus T, and X is a T -invariant subvariety. Let w ∈ T^{∗} = Sym^{1}(T^{∗}) be the weight of T on L, and S ⊆ T the stabilizer of L, so the map Sym(T^{∗}) ) Sym(S^{∗}) takes p ) p|_{w=0}.

Let the ideal I defining X be generated by {y^{d_{i}}q_{i} + r_{i} | i = 1, …, m}, where y^{d_{i}}q_{i} is the initial y-form of y^{d_{i}}q_{i} + r_{i} and y does not divide q_{i}. Let J = ⟨q_{1}, …, q_{m}⟩, and define Θ ⊆ H to be the zero scheme of J. If we know that

• Θ has only one component of dimension dim X − 1,

• that component is generically reduced, and

• X is not contained in a union of finitely many translates of H, then

(deg_{V} X)|_{w=0} = (deg_{H} Θ)|_{w=0}.

Proof.Let Θ′ be the reduced variety underlying the (dim X − 1)-dimensional component of Θ. By the conditions on Θ, deg_{H} Θ = deg_{H} Θ′.

Let Λ, Π, d be as in Theorem 2.5, whose conclusion specializes to

(deg_{V} X)|_{w=0} = (deg_{H} Λ)|_{w=0}

since setting w = 0 kills the contribution from Π.

Let C be the ideal defining Λ. Then C contains J, so Λ ⊆ Θ. The condition that X not be contained in a union of finitely many translates of H says that Λ is nonempty, and hence has dimension dim X − 1.

Hence Λ ⊇ Θ′, and being trapped between two schemes with the same multidegree, deg_{H} Λ = deg_{H} Θ. □

Essentially, this corollary replaces the difficulty of showing that a basis for an ideal is Gröbner with the difficulty of showing that Θ has only one big component. It is used in precisely this form in [KZJ].

3. Vexillary matrix Schubert varieties

3.1. Matrix Schubert varieties. In this subsection we review some definitions and results of Fulton on determinantal ideals [Ful]; an exposition of this material can be found in [MS, Chapter 15].

Let M_{n} be the variety of n × n matrices over 𝕜, with coordinate ring 𝕜[z] in indeterminates {z_{ij}}_{i,j=1}^{n}. We will let z denote the generic matrix of variables (z_{ij}) and let z_{p×q} denote the northwest p × q submatrix of z. More generally, if Z is any rectangular array of objects, let Z_{p×q} denote the northwest p × q subarray. In particular, identifying π ∈ S_{n} with the square array having blank boxes in all locations except at (i, π(i)) for i = 1, …, n, where we place dots, we define the rank π r_{pq} to be the number of dots in the subarray π_{p×q}. This yields the n × n rank array r^{π} = ( ^{π} r_{pq})_{p,q=1}^{n}. We can recover the dot-matrix for π from r^{π} by placing a dot at (p, q) whenever ^{π} r_{pq} − ^{π} r_{p−1,q} − ^{π} r_{p,q−1} + ^{π} r_{p−1,q−1} = 1 rather than 0 (by convention, we set ^{π} r_{0∗} = ^{π} r_{∗0} = 0).

For π ∈ S_{n}, the Schubert determinantal ideal I_{π} ⊆ 𝕜[z] is generated by all minors in z_{p×q} of size 1 + ^{π} r_{pq} for all p and q. It was proven in [Ful] to be prime. The matrix Schubert variety \overline{X}_{π} is the subvariety of M_{n} cut out by I_{π}; thus \overline{X}_{π} consists of all matrices Z ∈ M_{n} such that rank(Z_{p×q}) ≤ ^{π} r_{pq} for all p and q.

In fact, the ideal I_{π} is generated by a smaller subset of these determinants. This subset is described in terms of the diagram

D(π) = {(p, q) ∈ {1, …, n} × {1, …, n} | π(p) > q and π^{−1}(q) > p}.

of π. Pictorially, if we draw a “hook” consisting of lines going east and south from each dot, then D(π) consists of the squares not in the hook of any dot. The essential set is the set of southeast corners of the connected components of the diagram:

Ess(π) = {(p, q) ∈ D(π) | (p + 1, q), (p, q + 1) ∉ D(π)}.

Then with these definitions, we call a generator of I_{π} essential if it arises as a minor of size 1 + ^{π} r_{pq} in z_{p×q} where (p, q) ∈ Ess(π). The prime ideal I_{π} is generated by its set of essential minors.

Example 3.1. The dot-matrix for π = ( \begin{matrix}1 & 2 & 3 & 4 & 5 \\ 4 & 1 & 3 & 2 & 5 \end{matrix} ) ∈ S_{5} and the diagram D(π)

are combined below:

[figure: 1; 0]

The diagram consists of two connected components; we also record the value of the rank array r(π) on the essential set.

The matrix Schubert variety \overline{X}_{π} is the set of 5×5 matrices Z such that z_{11} = z_{12} = z_{13} = 0 and whose upper left 3×2 submatrix Z_{3×2} has rank at most 1; all other rank conditions on Z ∈ \overline{X}_{π} follow from these. Using only the essential minors,

I_{π} = ⟨z_{11}, z_{12}, z_{13}, z_{11}z_{22} − z_{21}z_{12}, z_{11}z_{32} − z_{31}z_{12}, z_{21}z_{32} − z_{31}z_{22}⟩.

These generators form a Gröbner basis under any diagonal term order, i.e., one that picks z_{11}, z_{12}, z_{13}, z_{11}z_{22}, z_{11}z_{32}, and z_{21}z_{32} as the leading terms. This statement is an instance of the main result of this section, Theorem 3.8.

3.2. Vexillary permutations. Since we shall be interested in vexillary matrix Schubert varieties, we collect in this subsection some results on vexillary permutations.

A permutation π is called vexillary or 2143-avoiding if there do not exist integers a < b < c < d such that π(b) < π(a) < π(d) < π(c). Fulton characterized these permutations in terms of their essential sets: no element (p, q) of the essential set is strictly northwest of another element (i, j), meaning p < i and q < j. To each vexillary permutation π ∈ S_{n} we associate the partition λ(π) whose parts are the numbers of boxes in the rows of D(π), sorted into weakly decreasing order. For example, the permutation π in Example 3.1 is vexillary, and λ(π) = (3, 1).

Every Grassmannian permutation (see the Introduction) is vexillary; in fact, a permutation is Grassmannian if and only if its essential set is contained in one row, necessarily the last nonempty row of the diagram. In this case, λ(π) simply lists the number of boxes in the rows of D(π), read bottom-up.

In Corollary 3.3, we will collect the characterizations of vexillary permutations that we will need, one based on this.

Lemma 3.2. Let π ∈ S_{n} and (i, j) ∈ D(π). There exists (p, q) ∈ Ess(π) with p < i and q < j if and only if the ^{π} r_{ij} dots of π_{(i−1)×(j−1)} do not form a diagonal of size ^{π} r_{ij}.

Proof.This is straightforward from the definition of essential set. □

Corollary 3.3 ([Ful]). The following are equivalent for a permutation π ∈ S_{n}. a) π is vexillary.

b) There do not exist (p, q) ∈ Ess(π) and (i, j) ∈ Ess(π) with p < i and q < j.

c) For all (p, q) ∈ D(π), the ^{π} r_{pq} dots of π_{(p−1)×(q−1)} form a diagonal of size ^{π} r_{pq}.

Proof.The equivalence of (a) and (b) comes from [Ful, Section 9]. Since every element of D(π) has an element of Ess(π) to the southeast of it in its connected component, the equivalence of (b) and (c) comes from Lemma 3.2. □

For any permutation π, call a box (p, q) ∈ D(π) accessible if ^{π} r_{pq} ≠ 0 and no boxes other than (p, q) itself lie weakly to its southeast in D(π). In particular, (p, q) ∈ Ess(π). Our next goal is to define, for a vexillary π and an accessible box (p, q), two new vexillary permutations π_{P} and π_{C}.

For any permutation π, each connected component of D(π) has a unique northwest corner (a, b). If π is vexillary and (a, b) ≠ (1, 1), then there is a dot of π at (a − 1, b − 1), because Corollary 3.3 prevents pairs of dots of π weakly northwest of (i, j) from forming antidiagonals. Let (t, π(t)) = (a − 1, b − 1) be the dot of π adjacent to the northwest corner of the connected component of D(π) containing (p, q). Now set

(1)  π_{P} = π ∘ (p, π^{−1}(q)) and π_{C} = π_{P} ∘ (t, p),

where the composition ∘ (i, j) with the transposition (i, j) results in switching rows i and j. Denote the corresponding rank matrices by r^{P} = r^{π_{P}} and r^{C} = r^{π_{C}}.

Example 3.4. The permutation π = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 8 & 7 & 1 & 6 & 2 & 9 & 5 & 3 & 4 \end{matrix} ) is vexillary. Its

dot-matrix and diagram are combined below:

[figure: 2]

The box (p, q) = (7, 4), which is marked with ^{π} r_{74} = 2, is accessible, and the dot immediately northwest of its connected component is (t, π(t)) = (5, 2). Therefore

π_{P} = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 8 & 7 & 1 & 6 & 2 & 9 & 4 & 3 & 5 \end{matrix} ) and π_{C} = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 8 & 7 & 1 & 6 & 4 & 9 & 2 & 3 & 5 \end{matrix} ) .

These correspond respectively to

[figure]

Lemma 3.5. Let π be a vexillary permutation, r^{π} its rank matrix, and (p, q) an accessible box for π. Then the following hold.

a) D(π_{P} ) = D(π) ∖ {(p, q)}.

b) D(π_{C}) is obtained by moving diagonally northwest by one step the rectangle consisting of boxes of D(π) weakly northwest of (p, q) and in its connected component.

c) ^{P} r_{ij} = | \begin{matrix}^{π} r_{ij} + 1 & if p ≤ i ≤ π^{−1}(q) − 1 andq ≤ j ≤ π(p) − 1 \\ ^{π} r_{ij} & otherwise. \end{matrix}

d) ^{C} r_{ij} = \{ \begin{matrix}^{π} r_{ij} − 1 & if t ≤ i ≤ p − 1 andπ(t) ≤ j ≤ q − 1 \\ ^{π} r_{ij} + 1 & if p ≤ i ≤ π^{−1}(q) − 1 andq ≤ j ≤ π(p) − 1 \\ ^{π} r_{ij} & otherwise. \end{matrix}

e) Ess(π) ∖ {(p, q)} ⊆ Ess(π_{P} ) and Ess(π_{P} ) ∖ Ess(π) ⊆ {(p − 1, q), (p, q − 1)}.

f) Ess(π_{C}) = (Ess(π) ∖ {(p, q)}) ∪ {(p − 1, q − 1)}.

g) π_{P} and π_{C} are vexillary permutations.

Proof.Parts (a)–(f) are straightforward to check from the definitions. Part (g) follows easily from parts (a) and (b) combined with the equivalence of Corollary 3.3(a) and Corollary 3.3(b). □

Example 3.6. Continuing Example 3.4, omitting the 2’s to better see the shapes, and omitting the 5’s, 6’s, 7’s, 8’s, and 9’s (which don’t change), we have

r^{π} = (\begin{matrix}0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & . & . \\ 1 & 1 & 1 & 1 & 1 & 1 & . & 3 & 3 \\ 1 & 1 & 1 & 1 & 1 & . & 3 & 4 & 4 \\ 1 & . & . & . & . & 3 & 4 & . & . \\ 1 & . & . & . & . & 3 & 4 & . & . \\ 1 & . & . & . & 3 & 4 & . & . & . \\ 1 & . & 3 & 3 & 4 & . & . & . & . \\ 1 & . & 3 & 4 & . & . & . & . & . \end{matrix}) ,

r^{P} = (\begin{matrix}0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & . & . \\ 1 & 1 & 1 & 1 & 1 & 1 & . & 3 & 3 \\ 1 & 1 & 1 & 1 & 1 & . & 3 & 4 & 4 \\ 1 & . & . & . & . & 3 & 4 & . & . \\ 1 & . & . & . & . & 3 & 4 & . & . \\ 1 & . & . & 3 & 3 & 4 & . & . & . \\ 1 & . & 3 & 4 & 4 & . & . & . & . \\ 1 & . & 3 & 4 & . & . & . & . & . \end{matrix}) , and r^{C} = (\begin{matrix}0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & . & . \\ 1 & 1 & 1 & 1 & 1 & 1 & . & 3 & 3 \\ 1 & 1 & 1 & 1 & 1 & . & 3 & 4 & 4 \\ 1 & 1 & 1 & . & . & 3 & 4 & . & . \\ 1 & 1 & 1 & . & . & 3 & 4 & . & . \\ 1 & . & . & 3 & 3 & 4 & . & . & . \\ 1 & . & 3 & 4 & 4 & . & . & . & . \\ 1 & . & 3 & 4 & . & . & . & . & . \end{matrix}) .

These rank arrays r^{P} and r^{C} are in agreement with Lemma 3.5.

Finally, we see how to get vexillary permutations from Grassmannian ones.

Lemma 3.7. Let π ∈ S_{n} be vexillary permutation with largest descent position k. Then there exists some N ≥ n and a sequence of vexillary permutations

σ_{1}, σ_{2}, …, σ_{t} = π

in S_{N}, all with largest descent position k, such that σ_{1} is Grassmannian and σ_{i+1} = (σ_{i})_{C} for 1 ≤ i ≤ t − 1. The permutation π̃ = σ_{1} is uniquely determined by π; in fact,

Ess(π̃) = {(k, k − p + q) | (p, q) ∈ Ess(π)} and π̃ r_{k,k−p+q} = k − p + ^{π} r_{pq}.

Proof.There is nothing to prove if π is Grassmannian. Otherwise we construct a vexillary permutation σ as follows. Find the second largest descent i < k of π. Hence the rightmost box (i, j) of D(π) in row i lies in Ess(π). Since π is assumed to be vexillary, all boxes of Ess(π) to the north of (i, j) are weakly to the east of column j. Find the northmost box in Ess(π) that is in column j, say (h, j).

Since (h, j) ∈ Ess(π), there are dots (h + 1, q) and (p, j + 1) of π satisfying q ≤ j and p ≤ h. Since π is vexillary, there are no boxes of the diagram D(π) strictly southeast of (h, j). This implies that there is a unique northwestmost dot (c, π(c)) of π strictly southeast of (h, j); that is, no two dots of π strictly southeast of (h, j) form an antidiagonal.

Now let σ = π ∘ (p, h + 1) ∘ (h + 1, c). Then one checks that D(σ) is obtained from D(π) by moving the boxes in the rectangle in row p to h and columns q and j southeast by one unit. Our choices guarantee that σ is still vexillary, by looking at Ess(σ) and using Corollary 3.3. Moreover, λ(σ) = λ(π) because the number of rows with any given number of boxes of the diagram is the same for both π and σ. Also, σ still has its last descent at position k. Most importantly, (h + 1, j + 1) ∈ Ess(σ) is accessible, and π = σ_{C}.

Note in particular that the boxes of σ are further south than those of π (and strictly so in at least one case). Therefore, repeated application of the above construction successively moves the boxes of D(π) south, but always above row k. So this gives a chain of permutations starting with π and eventually ending with a Grassmannian permutation in some S_{N} with N ≥ n.

The final sentence of the lemma follows from parts (d) and (f) of Lemma 3.5. □

3.3. Diagonal Gröbner bases. In [KM1] it was proved that for any permutation π, the essential minors form a Gröbner basis of the Schubert determinantal ideal I_{π} under any antidiagonal term order. We prove here a complementary result for diagonal term orders, assuming that the permutation π is vexillary (Theorem 3.8); in Section 6 we explain the sense in which this diagonal Gröbner basis result is sharp. Our proof will be an application of Theorem 2.1.

Theorem 3.8. If π ∈ S_{n} is a vexillary permutation, then the essential minors of I_{π} constitute a Gröbner basis with respect to any diagonal term order.

The proof will be by an induction based on Lemma 3.7 and the following, which connects the notation of Theorem 2.1 with Eq. (1). Geometrically, Proposition 3.9 concerns the decomposition M_{n} = H⊕L where H consists of all matrices satisfying z_{pq} = 0 for some fixed accessible box (p, q) ∈ Ess(π), and L is the 1-dimensional space of matrices with all z_{ij} vanishing except z_{pq}.

Proposition 3.9. Let π be a vexillary permutation and (p, q) ∈ Ess(π) an accessible box. Fix a diagonal term order ≺ on 𝕜[z]. Suppose that the essential minors generating I = I_{π} form a Gröbner basis with respect to ≺, set z_{pq} = y, and let I′, C, P, and their respective generators be as in Theorem 2.1. Then the following hold.

a) C = I_{π_{C}} and P = I_{π_{P}} + ⟨z_{pq}⟩, where π_{C} and π_{P} are defined by Eq. (1).

b) The generators of C and P are Gröbner bases for these ideals under ≺.

c) The essential minors generating I_{π_{C}} form a Gröbner basis under ≺.

d) I′ = C ∩ P is a geometric vertex decomposition.

Proof.Separate the set of essential minors generating I into sets V and U according to whether they do or do not involve z_{pq}. Since (p, q) is accessible, the array of zvariables appearing in an essential minor that involves z_{pq} has southeast corner z_{pq}.

For each minor in V, put into a new set V ′ the one-smaller minor obtained by removing the last row and column. Define z_{pq}V ′ by multiplying all elements of V ′ by z_{pq}. Then, by definition of Gröbner basis, I′ is generated by U ∪(z_{pq}V ′), whereas C is generated by U ∪ V ′ and P is generated by U ∪ {z_{pq}}.

It follows from parts (c) and (e) of Lemma 3.5 that the essential minors for π_{P} are precisely the determinants in U. Hence the statement about P in part (a) follows.

Next we check that C ⊆ I_{π_{C}}. Each minor in U comes from a (possibly inessential) rank condition from r^{π} corresponding to either

(i) a box of D(π) ∖ {(p, q)} in the same connected component as (p, q) and in row p or column q, or

(ii) a box in Ess(π) ∖ {(p, q)}. In either case, Lemma 3.5(d) shows that r^{π_{C}} and r^{π} are equal at these positions. Hence each minor in U lies in I_{π_{C}}. Also, any minor in V arises from the rank condition corresponding to (p, q) ∈ Ess(π), and the associated minor in V ′ is an essential minor corresponding to ^{C} r_{p−1,q−1}, by parts (d) and (f) of Lemma 3.5. Thus we obtain V ′ ⊆ I_{π_{C}}, and so U ∪ V ′ ⊆ I_{π_{C}}. Therefore C ⊆ I_{π_{C}}.

To show the other inclusion, one checks from Lemma 3.5 that if an essential minor comes from (p − 1, q − 1) ∈ Ess(π_{C}) then it lies in V ′; otherwise, it lies in U. This concludes the proof of part (a).

Theorem 2.1 guarantees that the generating sets for C and P are again Gröbner bases. Since minors have only squarefree terms, the power of z_{pq} in each generator is at most 1, so the theorem also tells us we have a geometric vertex decomposition. This proves parts (b) and (d).

It remains to check part (c). Although I_{π_{C}} = C, there are minors in U ∪V ′ that are not essential minors for I_{π_{C}}. These are exactly those minors in U arising from (i) above. Thus we wish to show that we can remove these inessential minors and still have a Gröbner basis. Since I_{π_{C}} is generated by its essential minors, it suffices to check that the leading term of each minor from (i) is divisible by the leading term of an essential minor in I_{π_{C}}. For this, note that removing the last row and column from one of these inessential minors yields a minor of smaller degree that is an essential minor of I_{π_{C}} arising from ^{C} r_{p−1,q−1}. □

Proof of Theorem 3.8. Construct a chain of vexillary permutations as in Lemma 3.7. If π = σ_{1}, so π is Grassmannian, then the result is proved in [CGG, Stu]. This case can also be derived from [KM1, Theorem B], which proves the Gröbner basis property for antidiagonal term orders, because the set of essential minors for a Grassmannian permutation with unique descent k is invariant under the permutation of the variables induced by reversing the top k rows of z (since the essential set of π lies entirely in the k^{th} row of D(π)). If π ≠ σ_{1} then the desired statement holds by induction on the length of the sequence in Lemma 3.7, using Proposition 3.9(c). □

4. Stanley–Reisner ideals and subword complexes

Theorem 3.8 shows that for a vexillary permutation π ∈ S_{n}, the initial ideal in I_{π} is a squarefree monomial ideal; this makes it the Stanley–Reisner ideal of a simplicial complex whose vertices are [n]^{2} = {(p, q) | 1 ≤ p, q ≤ n} and whose faces consist of those subsets F such that no monomial from in I_{π} has support F.

In this section we prove this complex to be a subword complex [KM2]; besides its intrinsic interest, we apply this fact toward combinatorial formulae in the next section. Without introducing subword complexes, though, our geometric technology is already sufficient to prove that this complex is shellable.

Theorem 4.1. Let π be a vexillary permutation, and Γ the simplicial complex whose Stanley–Reisner ideal is in I_{π}. Then Γ is shellable.

Proof.If J is a Stanley–Reisner ideal in 𝕜[z], let Γ (J) denote the corresponding simplicial complex on the vertex set [n]^{2}, so Γ = Γ (in I_{π}).

By Proposition 3.9 part (d), \overline{X}_{π} has a geometric vertex decomposition into \overline{X}_{π_{P}} ∩ \{z_{pq} = 0\} and \overline{X}_{π_{C}}, where (p, q) is an accessible box of π. By Proposition 2.3, this geometric vertex decomposition of \overline{X}_{π} degenerates to a geometric vertex decomposition of in I_{π} into in I_{π_{P}} +⟨z_{pq}⟩ and in I_{π_{C}}. As explained in Example 1.3, this gives an ordinary vertex decomposition of Γ (in I_{π}) at the vertex (p, q) into the deletion Γ (in I_{π_{P}} + ⟨z_{pq}⟩) and the cone Γ (in I_{π_{C}}) on the link.

Since the ideal in I_{π_{P}} doesn’t involve the generator z_{pq}, the complex Γ (in I_{π_{P}} ) is the cone on Γ (in I_{π_{P}} + ⟨z_{pq}⟩) at the vertex (p, q). In particular, one is shellable if and only if the other is.

Using induction on the position of the most southeastern box in the diagram, Γ (in I_{π_{C}}) and Γ (in I_{π_{P}} ) are both shellable; hence Γ (in I_{π_{P}} + ⟨z_{pq}⟩) is also. As noted in [BP], one can concatenate a shelling of the deletion Γ (in I_{π_{P}} +⟨z_{pq}⟩) and a shelling of the cone Γ (in I_{π_{C}}) on the link to make a shelling of Γ (in I_{π}). □

We review some definitions about subword complexes from [KM2]; see also [MS, Section 16.5], which covers the generality here. A word of size t is an ordered sequence Q = (s_{i_{1}}, …, s_{i_{t}}) of simple reflections s_{i} = (i, i + 1) ∈ S_{m}. An ordered subsequence P of Q is a subword of Q. In addition, P represents ρ ∈ S_{m} if the ordered product of the simple reflections in P is a reduced decomposition of ρ. We say that P contains ρ ∈ S_{m} if some subsequence of P represents ρ. Let Δ(Q, ρ) denote the subword complex with vertex set the simple reflections in Q and with faces given by the subwords Q ∖ P whose complements P contain ρ.

Using the above setup, we now define the subword complex Γ_{π} for a given vexillary permutation π ∈ S_{n}. Let μ(π) = (μ_{1} ≥ μ_{2} ≥ … ≥ μ_{k} > 0) be the partition with the smallest Ferrers shape (in English notation, i.e. the largest part along the top row) containing all of the boxes of D(π); thus the shape of μ(π) is the union over (p, q) ∈ Ess(π) of the northwest p × q rectangles in the n × n grid. Fill each box (p, q) in the shape of μ(π) with the reflection s_{k−p+q}. Reading each row of μ(π) from right to left, starting with the bottom row and ending with the top row yields the word

Q = (\underbrace{s_{μ_{k}}, …, s_{1}}_{row k}, \underbrace{s_{1+μ_{k−1}}, …, s_{2}}_{row k−1}, …, \underbrace{s_{i+μ_{i}}, …, s_{i+1}}_{row k−i}, …, \underbrace{s_{k−1+μ_{1}}, …, s_{k}}_{top row}).

Let π̃ be the Grassmannian permutation from Lemma 3.7, and set Γ_{π} = Δ(Q, π̃).

Example 4.2. The vexillary permutation π = ( \begin{matrix}1 & 2 & 3 & 4 & 5 \\ 4 & 1 & 3 & 2 & 5 \end{matrix} ) ∈ S_{5} from Exam-

ple 3.1 has μ(π) = (3, 2, 2) and π̃ = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 3 & 6 & 2 & 4 & 5 \end{matrix} ) ∈ S_{N} for N = 6. The

ambient word for Γ_{π} is Q = (s_{2}, s_{1}, s_{3}, s_{2}, s_{5}, s_{4}, s_{3}).

Lemma 4.3. Identify μ(π) with its Ferrers shape. Setting to 1 ∈ 𝕜 all variables z_{pq} for (p, q) outside of μ(π) takes any generating set for in Iπ̃ to a generating set for in I_{π}.

Proof.It suffices to check that (i) every diagonal generator of in I_{π} can be obtained from some diagonal in in Iπ̃ by setting the variables outside of μ(π) to 1, and (ii) setting the given variables to 1 in any diagonal from in Iπ̃ yields an element inside in I_{π}. For (i), if δ is a diagonal generator of I_{π}, say of degree 1 + ^{π} r_{pq} using the variables z_{p×q} for (p, q) ∈ Ess(π), then simply multiply δ by the diagonal z_{1+p,1+q} ⋯ z_{k,k−p+q} to get a diagonal generator of in Iπ̃. For (ii), observe that any diagonal of size at least j + 1 + ^{π} r_{pq} using the variables z_{(j+p)×(j+q)} has at least 1 + ^{π} r_{pq} of its variables weakly northwest of z_{pq}, and take j = k − p for (p, q) ∈ Ess(π). □

Theorem 4.4. Let π ∈ S_{n} be a vexillary permutation. With respect to any diagonal term order, the initial ideal of I_{π} is the Stanley–Reisner ideal for the subword complex Γ_{π}.

Proof.Let π̃ be the Grassmannian permutation defined in Lemma 3.7. If π = π̃ then the result follows from [KM1, Theorem B and Example 1.8.3], which proves the corresponding result for the antidiagonal initial ideal of Iπ̃, because the set of essential minors for Iπ̃ is invariant under the permutation of the variables induced by reversing the top k rows of z.

For general vexillary π, let us write Γπ̃ = Δ(Q̃, π̃), to distinguish the word Q̃ from Q. Given a subword P of Q̃, denote by z_{P} the set of variables corresponding to the locations of the boxes occupied by P. The previous paragraph yields the minimal prime decomposition in Iπ̃ = ⋂_{P} ⟨z_{P} ⟩, the intersection being over subwords P of Q̃ representing π̃. Since in Iπ̃ is a monomial ideal, setting the variables outside of μ(π) to 1 ∈ 𝕜 and omitting those intersectands ⟨z_{P} ⟩ that become the unit ideal yields a prime decomposition, and it is a decomposition of in I_{π} by Lemma 4.3. (The intersections for in Iπ̃ and in I_{π} are taken in different polynomial rings, but this is irrelevant here.) The intersectand ⟨z_{P} ⟩ for a subword P ⊆ Q̃ representing π̃ survives the process of setting the variables outside of μ(π) to 1 if and only if P is actually a subword of Q. □

In the next section, we will use a pictorial description of Γ_{π}, developed in [FK2, BB, KM1] (see [MS, Chapter 16] for an exposition). Let π be vexillary, and again consider the Grassmannian permutation π̃ ∈ S_{N} with descent at k. A tiling of the k×N rectangle by crosses and elbows [figure] is called a pipe dream. (Warning: the elbow tile here is mirror-reflected top-to-bottom from the above references. This is traceable to our use of diagonal, rather than antidiagonal, term orders.) It is often convenient to identify a pipe dream with its set of tiles, and to identify each subword P of Q with the pipe dream whose crosses lie at the positions occupied by P. When P represents π̃, so the number of crosses equals the length of π̃, then P is a reduced pipe dream (or an “rc-graph”) for π̃. In this language, the initial ideal in I_{π} is described as follows, by [KM1, Example 1.8.3].

Corollary 4.5. Q ∖ P is a face of Γ_{π} if and only if (i) the crosses in the pipe dream P lie in the Ferrers shape μ(π), and (ii) P contains some reduced pipe dream representing π̃.

Example 4.6. Recall the situation from Example 4.2. The following pipe dream P corresponds to the subword (s_{2}, · , · , · , s_{5}, s_{4}, s_{3}) of Q, and Q ∖ P is a facet of Γ_{π}.

P = [figure: 1; 2; 3; 1 2 3 4 5 6] ()  \begin{matrix}1 \\ 2 \\ 3 \\ & 1 & 2 & 3 & 4 & 5 & 6 \end{matrix}

By Example 3.1, in I_{π} = ⟨z_{11}, z_{12}, z_{13}, z_{21}z_{32}⟩ = ⟨z_{11}, z_{12}, z_{13}, z_{21}⟩ ∩ ⟨z_{11}, z_{12}, z_{13}, z_{32}⟩. Thus there is only one remaining facet Q∖P′ of Γ_{π}, corresponding to the (reduced) pipe dream P′ obtained by moving the at (3, 2) diagonally northwest to (2, 1).

If we follow the three pipes from the left side to the bottom, they come out in positions 1, 3, 6. These are the positions of the “up” moves in the word “up, right, up, right, right, up” describing a walk around the partition (3, 1, 0) from the southwest corner to the northeast.

We could have waited to prove Theorem 4.1 until after proving that the initial complex is a subword complex, and then using the combinatorially proven fact from [KM2] that subword complexes are shellable, instead of using geometric vertex decompositions. In [K2] we will reverse this argument, and use geometric vertex decompositions to prove once more that subword complexes are shellable.

5. Flagged set-valued tableaux

5.1. Set-valued tableaux and Grassmannian permutations. Formulae for certain Grothendieck polynomials associated to a partition λ were given by Buch [Buc] (see Corollary 5.9, below). Naturally generalizing the tableau formula for Schur polynomials, he gave his formula in terms of (semistandard) set-valued tableaux with shape λ. These are fillings τ : λ ) P owerSet(ℕ) of the boxes in the shape of λ (in English notation, the largest part along the top row) with nonempty sets of natural numbers satisfying the following “semistandardness” conditions:

• if box b ∈ λ lies above box c ∈ λ, then each element of τ(b) is strictly less than each element of τ(c); and

• if box b ∈ λ lies to the left of box c ∈ λ, then each element of τ(b) is less than or equal to each element of τ(c).

Let SVT (λ) denote the collection of all such tableaux for a partition λ, as the nonsemistandard ones will be of little interest in this paper. (They are more pertinent in [KMY].) For τ ∈ SVT (λ), let |τ| denote the number of entries, so |τ| ≥ |λ| with equality exactly for ordinary (non-set-valued) tableaux.

Example 5.1. The following is a set-valued tableau τ ∈ SVT (λ) for the partition λ = (7, 6, 4, 3, 1):

\begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 2 & 2 & 2 & 2 & 2 \\ 3, 4 & 4 & 4 & 4 \\ 5 & 5, 6 & 6 \\ 6, 7 & 7 \end{matrix} = τ.

The goal of this section is to generalize and refine Buch’s formula by way of a Gröbner geometry explanation in terms of Theorem 3.8. The combinatorial aspect of this story consists of a bijection between a certain set of pipe dreams and a certain collection of set-valued tableau. This generalizes the bijection between (ordinary) semistandard Young tableaux and reduced pipe dreams for Grassmannian permutations (Proposition 5.3, below), which we learned from Kogan [Kog] (on the other hand, see Example 5.10).

We begin with the bijection Ω from tableaux to pipe dreams. Since its definition is just as easy to state for set-valued tableaux, we work in that generality from the outset. Define Ω by associating to every τ ∈ SVT (λ) a pipe dream as follows:

For each integer i that τ assigns to the box b, place a in row i so that it lies on the diagonal containing the box b.

Example 5.2. The set-valued tableaux τ in Example 5.1 maps to

\begin{aligned}& 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \end{aligned} = Ω(τ).

Proposition 5.3. If π̃ ∈ S_{N} is a Grassmannian permutation with descent at k and associated partition λ = λ(π̃), then Ω induces a bijection from the set of (ordinary) semistandard tableaux of shape λ with entries at most k to the set of k × N reduced pipe dreams for π̃. Moreover, in each k × N reduced pipe dream for π̃, the following hold.

a) No pipe passes horizontally through one tile and vertically through another.

b) The row indices of the tiles on the i^{th} horizontal pipe from the top in Ω(τ) are the values assigned by τ to the boxes in row i of λ.

c) The tile in Ω(τ) corresponding to the box b of λ lies on the same diagonal as b.

d) The box in row p and column q of λ corresponds to the in Ω(τ) at the intersection of the p^{th} horizontal pipe from the top with the q^{th} vertical pipe from the left.

Example 5.4. Consider the ordinary semistandard Young tableaux \overline{τ} obtained from the set-valued tableaux τ in Example 5.1 by taking only the smallest entry in each box. Then, drawing the horizontal pipes (with small bits of their crossings through vertical pipes to make the picture easier to parse), Ω sends \overline{τ} to

Ω ( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 2 & 2 & 2 & 2 & 2 \\ 3 & 4 & 4 & 4 \\ 5 & 5 & 6 \\ 6 & 7 \end{matrix} ) = [figure: 1 2 3 4 5 6 7 8 9 10 11 12 13 14; 1; 2; 3; 4; 5; 6; 7]

The three boxes containing elbow tiles will be explained in Example 5.6.

Proof of Proposition 5.3. Let τ be a semistandard tableau of shape λ with entries at most k. Construct a new tableau T (of shape λ + ρ, where ρ = (k, k − 1, …, 2, 1)) by adding to the i^{th} row an extra box filled with j for each j = i, …, k (and arranged to be increasing along each row). The map τ ) Ω(τ) factors as τ ) T ) Ω(τ), where each box (p, q) of T filled with j corresponds to a tile at (j, q): the tile is a if (p, q + 1) is filled with j and a [figure] otherwise. The tiles in Ω(τ) not assigned by T are all [figure] tiles.

The semistandard condition on T guarantees that each [figure] arising from the last j in a row of T has another [figure] due south of it. Hence there is a single pipe such that the numbers in row i of T list the row indices of the tiles in Ω(τ) entered from the left by that pipe. As every in Ω(τ) arises from T, this proves parts (a) and (b). Part (c) follows easily from (b) by considering each row of T separately and using induction on the number of boxes in any fixed row. Part (d) follows from part (a), since the horizontal pipes can’t cross one another, and nor can the vertical pipes.

It remains only to show that Ω induces the claimed bijection. As the numbers of the indicated tableaux and reduced pipe dreams are equal (both agree with the evaluation at (1, …, 1) of the Schur polynomial s_{λ}(x_{1}, …, x_{k}), which equals the Schubert polynomial 𝔖π̃(x_{1}, …, x_{k})), it is enough to show that Ω(τ) is a reduced pipe dream for π̃. This follows because Ω(τ) has |λ| = length(π̃) crossing tiles, and the pipe entering horizontally into row i exits vertically out of row k through column k − i + λ_{i} = π̃(i), as can be seen by counting its tiles. □

Subword complexes are homeomorphic to balls or spheres, as shown in [KM2, Theorem 3.7], where the interior and boundary faces were characterized. Here, the subword complex is Γπ̃ = Δ(Q, π̃) for the full k × N rectangular word Q.

Theorem 5.5. If π̃ ∈ S_{N} is Grassmannian with descent at k and partition λ = λ(π̃), then Ω bijects the set SVT_{k}(λ) of set-valued tableaux of shape λ with entries at most k to the set of k × N pipe dreams P whose elbow tiles form the vertex sets of interior faces of Γπ̃.

Proof.The pipe dream Ω(τ) for τ ∈ SVT_{k}(λ) has crosses in at most k rows because the entries are at most k, and Ω(τ) has at most N columns because λ fits in a rectangle of size k × (N − k). No entry appears twice in τ along any diagonal of λ. This together with semistandardness implies that Ω is injective into its image. What remains is to show that the image of Ω consists precisely of the interior faces of Γπ̃.

For ordinary tableaux τ and facets Ω(τ) of Γπ̃, this is Proposition 5.3. For arbitrary τ ∈ SVT_{k}(λ), there is an associated ordinary tableau \overline{τ} obtained (as in Example 5.4) by taking only the smallest entry in each box. We will show that, similarly, for each subword P of Q such that Q ∖ P is an interior face of Γπ̃, there is an associated reduced subword \overline{P} representing π̃. To complete the proof, we will then construct the set-valued tableau τ satisfying Ω(τ) = P starting from the ordinary tableau \overline{τ} satisfying Ω(\overline{τ}) = \overline{P}.

For a reduced pipe dream \overline{P}, say that a [figure] tile in \overline{P} is absorbable into \overline{P} if the two pipes passing through it intersect in a tile to its northwest (see Example 5.6, below). It is immediate from the definition that a tile is absorbable if and only if the corresponding reflection in Q∖\overline{P} is absorbable in the sense of [KM2, Section 4]. Therefore it follows from [KM2, Theorem 3.7] that a pipe dream P is the complement of an interior face Q ∖ P of Γπ̃ if and only if P is obtained from a reduced pipe dream \overline{P} for π̃ by changing some of its absorbable [figure] tiles into at will.

Proposition 5.3(a) allows us to distinguish between horizontal and vertical pipes in any reduced pipe dream \overline{P} for π̃. We claim that if a horizontal and vertical pipe cross at and pass through a [figure] tile southeast of it, then the [figure] lies on the same diagonal as the and occurs in a row that is strictly north of the next down (if there is one) on the vertical pipe. This suffices because altering such [figure] tiles to tiles corresponds, by defintion of Ω, to inserting extra entries in the box of \overline{τ} corresponding to the original tile of \overline{P}. The claim holds because once the vertical pipe passes downward through the next horizontal pipe, that next horizontal pipe separates the vertical pipe from the original horizontal pipe. □

Example 5.6. The shape λ in Examples 5.1 and 5.4 is λ(π̃) for a Grassmannian permutation π̃ ∈ S_{N=14} with descent at k = 7. The absorbable tiles in Example 5.4 lie in the boxes at (4, 2), (6, 4), and (7, 3). Altering these to tiles yields the nonreduced pipe dream in Example 5.2; as in the proof of Theorem 5.5, these absorbable tiles also correspond to the extra entries needed to make the set-valued tableau in Example 5.1 from the ordinary tableau in Example 5.4.

5.2. Flaggings. Given a partition λ, a flagging f of λ is a natural number assigned to each row of λ. Suppose that λ = λ(π) for some vexillary permutation π, and recall the partition μ(π) from Section 4. The flag f_{π} assigns to row i of λ the row index of the southeastern box of μ(π) that lies on the same diagonal as the last box (i, λ_{i}) in row i of λ.

If f is a flagging of λ, call a set-valued tableau τ flagged by f if each box b in the i^{th} row of λ satisfies max τ(b) ≤ f(i). In particular, if τ is an ordinary tableau (each set a singleton), this definition of flagged tableaux is the usual one, in [Wac], for example. Let FSVT (π) denote the collection of set-valued tableaux of shape λ(π) flagged by f_{π}. Also, let FT (π) denote the subset consisting of flagged semistandard (ordinary) tableaux, in which, by definition, all the sets are singletons.

Example 5.7. If π is the vexillary permutation from Example 3.4, then λ(π) is the partition from Example 5.1, and the tableau τ in Example 5.1 obeys the flagging f_{π} = (1, 2, 4, 6, 7); that is, τ lies in FSVT (π). In general, the flag of a vexillary permutation need not list the indices of the nonempty rows of D(π); indeed, for the permutation π_{C} in Example 3.4, the flagging is f_{π_{C}} = (1, 2, 4, 6, 6).

Let x = (x_{1}, x_{2}, …) and y = (y_{1}, y_{2}, …) be two collections of commuting indeterminates. To any permutation π ∈ S_{n}, Lascoux and Schützenberger associated a (double) Grothendieck polynomial G_{π}(x, y) [LS]. Our convention here is that G_{π}(x, y) means the same thing as in [KM1], which would be called G_{π}(x, y^{−1}) in [KM2], and is obtained from the polynomial called 𝔏\begin{matrix}(−1) \\ π \end{matrix}(y, x) in [FK1] by replacing each x and y variable there with 1−x and \frac{1}{1−y}, respectively. Let 𝔖_{π}(x, y) denote the (double) Schubert polynomial, which is the lowest homogeneous degree component of G_{π}(1 − x, 1 − y) when this rational function is expressed as a series in positive powers of x and y. These double Schubert polynomials are the same as those in [KM1]. Combinatorial formulae for Schubert and Grothendieck polynomials are known in terms of pipe dreams [FK2], and Gröbner geometry explanations of these formulae were given in [KM1, KM2]. However, the approach given there does not explain the tableau formulae given here, which are different and only apply when π is vexillary. Hence we now give a Gröbner geometry explanation of these tableau formulae.

Theorem 5.8. If π ∈ S_{n} is a vexillary permutation, then Ω bijects the facets and interior faces of Γ_{π} with FT (π) and FSVT (π), respectively. Consequently, we have the following formulae for the double Schubert and double Grothendieck polynomials associated to π:

𝔖_{π}(x, y) = ∑_{τ∈FT(π)} ∏_{e∈τ} (x_{val(e)} − y_{val(e)+j(e)})

G_{π}(x, y) = ∑_{τ∈FSVT(π)}(−1)^{|τ|−|λ|} ∏_{e∈τ} (1 − \frac{x_{val(e)}}{y_{val(e)+j(e)}} )

where each product is over each entry e of τ, whose numerical value is denoted val(e), and where j(e) = c(e) − r(e) is the difference of the row and column indices. The sign (−1)^{|τ|−|λ|}alternates with the number of “excess” entries in the set-valued tableau.

Proof.Let π̃ be the Grassmannian permutation of descent k associated to π by Lemma 3.7. The image under Ω of FSVT (π) consists exactly of the pipe dreams in Ω(SVT_{k}) whose tiles all lie inside the Ferrers shape μ(π). Therefore the first sentence follows immediately from [KM2, Theorem 3.7] and Theorem 5.5.

Consider the ℤ^{2n}-grading on 𝕜[z] from Section 1.6. The desired double Grothendieck polynomial equals the ℤ^{2n}-graded K -polynomial of the quotient 𝕜[z]/I_{π} by [KM1, Theorem A]. This statement holds for 𝕜[z]/in I_{π}, too, since K -polynomials are invariant under taking initial ideals [MS, Theorem 8.36]. On the other hand, the ℤ^{2n}-graded K -polynomial of 𝕜[z]/in I_{π} is obtained from its ℤ^{n^{2}}-graded counterpart by replacing z_{pq} with x_{p}/y_{q}. Using the definition of Γ_{π} as a subword complex, one calculates the ℤ^{n^{2}}-graded K -polynomial of 𝕜[z]/in I_{π} as in [KM2, Theorem 4.1]: it is, by [KM2, Theorem 3.7], the sum over the pipe dreams P corresponding to interior faces Q ∖ P of Γ_{π} of products (−1)^{|P |−ℓ}∏ _{(p,q)∈P}(1 − z_{pq}), where ℓ = |D(π)| is the length of π. The formula for G_{π}(x, y) results because, by definition of Ω, the summand ∏ _{b∈λ(π)} wt_{x,y}^{τ}(b) for τ ∈ FSVT (π) equals the appropriately signed product of factors (1 − x_{p}/y_{q}) over all (p, q) such that Ω(τ) has a tile at (p, q).

Substituting 1 − x_{p} for x_{p} and 1 − y_{q} for y_{q} in wt_{x,y}^{τ}(b) results in a power series whose lowest term has degree equal to the cardinality of τ(b). Taking the lowest degree terms in G_{π}(1 − x, 1 − y) therefore yields a sum over honest (that is, not set-valued) tableaux, and the formula for 𝔖_{π}(x, y) follows. □

In particular, we obtain a Gröbner geometry explanation of the following result due to Buch [Buc, Theorem 3.1].

Corollary 5.9 ([Buc]). If π is a Grassmannian permutation and λ = λ(π), then

G_{λ}(1 − x) = ∑_{τ∈SVT(λ)}(−1)^{|τ|−|λ|} ∏_{e∈τ(b)}x_{val(e)},

where G_{λ}(1 − x) is obtained from G_{λ}(x, y) by replacing each x_{p} and y_{q} with 1 − x_{p} and 1.

Example 5.10. We emphasize that our proof of Theorem 5.8 is a consequence of the Gröbner geometry, but it is not a direct combinatorial consequence of the Fomin– Kirillov formulae [FK1, FK2]. We leave it as a challenge to find such an explanation, even in the case of double Schubert polynomials. For example, let π =

( \begin{matrix}1 & 2 & 3 & 4 \\ 1 & 4 & 3 & 2 \end{matrix} ). Then λ(π) = (2, 1) and f_{π} = (2, 3). Theorem 5.8 computes

𝔖_{π}(x, y) = (x_{2} − y_{2})(x_{2} − y_{3})(x_{3} − y_{2}) + (x_{1} − y_{1})(x_{2} − y_{3})(x_{3} − y_{2})
+ (x_{1} − y_{1})(x_{1} − y_{2})(x_{3} − y_{2}) + (x_{1} − y_{1})(x_{2} − y_{1})(x_{2} − y_{3})
+ (x_{1} − y_{1})(x_{1} − y_{2})(x_{2} − y_{1}).

On the other hand, using the formula of [FK2] gives

𝔖_{π}(x, y) = (x_{1} − y_{3})(x_{2} − y_{1})(x_{3} − y_{1}) + (x_{1} − y_{2})(x_{1} − y_{3})(x_{3} − y_{1})
+ (x_{2} − y_{1})(x_{2} − y_{2})(x_{3} − y_{1}) + (x_{1} − y_{2})(x_{2} − y_{1})(x_{2} − y_{2})
+ (x_{1} − y_{2})(x_{1} − y_{3})(x_{2} − y_{2}).

One approach to relating these two formulae would be to prove that after any permutation of the rows, the essential minors remain a Gröbner basis for any diagonal term order. Then each permutation of the rows would give a different formula, and one might be able to relate the formulae associated to permutations that are adjacent in Bruhat order. The two formulae above correspond to the identity and long-word permutations of the rows.

6. The diagonal Gröbner basis theorem for Schubert ideals is sharp

Our goal in this section is to prove the converse of Theorem 3.8.

Let A_{π} denote the union over all (p, q) ∈ Ess(π) of the sets of minors of size 1+ ^{π} r_{pq} in the northwest p×q corner z_{p×q} of the generic matrix z. Define B_{π} similarly, except take the union over all (p, q) in the n × n grid. Both sets generate I_{π}, as shown in

[Ful] (see also [MS, Chapter 15] for an exposition).

Theorem 6.1. If π ∈ S_{n} is a permutation that is not vexillary, then neither A_{π} nor B_{π} is a Gröbner basis of I_{π} under any diagonal term order.

In what follows, we say that a pipe dream P poisons a diagonal or a minor if at least one member of the diagonal (or the diagonal term of the minor) coincides with a in P. We will also say that P is a poisoning of a set of diagonals or minors if it poisons each element in the set. The poisoning of a set is minimal if by removing any cross from P, some element in the set is no longer poisoned. Recall the diagram D(π) from Section 3.1, and let C(π) denote the n×n pipe dream formed by placing tiles in the boxes of D(π).

Our proof of Theorem 6.1 is based on the following.

Proposition 6.2. The cross diagram C(π) is a poisoning of A_{π}. Moreover, C(π) is a minimal poisoning of A_{π} if and only if π is vexillary.

The proof of this proposition requires a number of intermediate results. As in Section 3, identify each permutation π with its dot-matrix.

Lemma 6.3. For any diagonal δ not poisoned by C(π), the following holds.

a) Each element of δ is either south of a dot of π in the same column, or east of a dot of π in the same row. b) No dot of π has an element of δ south of it in the same column and a different element

of δ east of it in the same row.

Proof.These statements are immediate consequences of the definitions. □

We identify diagonals with the products of the corresponding variables in the array z. Recall that z_{p×q} denotes the northwest p × q submatrix of z.

Corollary 6.4. The following hold for any (p, q) ∈ D(π).

a) Any diagonal in z_{p×q} that is not poisoned by C(π) has size at most ^{π} r_{pq}.

b) If (p, q) is any maximally northwest box in D(π) with the property that at least two of the ^{π} r_{pq} = ^{π} r_{p−1,q−1} dots in π_{(p−1)×(q−1)} do not lie on a diagonal, then any diagonal in z_{(p−1)×(q−1)} not poisoned by C(π) has size at most ^{π} r_{pq} − 1.

Proof.Part (a) follows immediately from the definition of r^{π} and Lemma 6.3.

Our hypotheses in part (b) imply that some pair of dots in π_{(p−1)×(q−1)}, say at (i, j) and (k, ℓ), forms an antidiagonal (where, say (i, j) occurs to the southwest of (k, ℓ)). Additionally, in z_{(p−1)×(q−1)}, every column from ℓ through q − 1 has a dot of π: if not, some box of D(π) in row p strictly west of (p, q) would contradict our assumptions on (p, q). Similarly, every row from i through p − 1 has a dot of π.

Assume that some diagonal δ in z_{(p−1)×(q−1)} not poisoned by C(π) has maximal length ^{π} r_{pq}. Suppose that for some h satisfying ℓ ≤ h ≤ q − 1, no element of δ lies in column h weakly south of the dot of π there, and choose h maximal with this property. It follows that if • is the dot of π in column h, then any element of δ in the hook of • lies in the hook of some other dot of π (by maximality of h), and δ is forced to have size less than ^{π} r_{pq} by Lemma 6.3. Therefore, every column from ℓ through q−1 has an element of δ weakly south of the dot of π there. Similarly, every row from i through p − 1 has an element of δ weakly east of the dot of π there.

Where is the element of δ in column ℓ? If it is weakly north of row i, then any element of δ east of (i, j) in row i also lies south of some other dot of π (in a column from ℓ to q − 1). On the other hand, if the element of δ in column ℓ is weakly south of row i, then it lies east of some other dot of π (in a row from i to p − 1). In both cases, δ is forced to have size less than ^{π} r_{pq} by Lemma 6.3, a contradiction. □

Proof of Proposition 6.2. Part (a) of Corollary 6.4 proves the first assertion. For the remaining assertion, suppose first that π is vexillary. Pick any (p, q) ∈ Ess(π). Corollary 3.3 shows that the diagonal formed by the dots of π_{(p−1)×(q−1)} together with (p, q) form a diagonal of size 1+ ^{π} r_{pq}. Hence we cannot remove (p, q) from C(π) and remain a poisoning. Thus C(π) is a minimal poisoning.

Conversely, suppose that π is not vexillary. By Corollary 3.3, we find can find (p, q) ∈ D(π) that is maximally northwest with the property that at least two dots of π_{(r−1)×(s−1)} are in antidiagonal position. We claim that removing the cross of C(π) from (p, q) results in a smaller poisoning. If this is not true, we can find (i, j) ∈ Ess(π) to the southeast of (p, q) and a diagonal of size 1 + ^{π} r_{ij} in z_{i×j} unpoisoned by C(π) ∖ (p, q) but containing (p, q). By Corollary 6.4(b) the part of this diagonal in z_{p×q} (including (p, q) itself) has size at most ^{π} r_{pq}. The rest of this diagonal, which lies strictly south and strictly east of (p, q), has size at most ^{π} r_{ij} − ^{π} r_{pq} by Lemma 6.3, because this rank difference equals the number of dots of π_{i×j} in the union of all rows > p and columns > q. Hence the maximal size of our unpoisoned diagonal is ^{π} r_{ij}, a contradiction. This completes the proof of Proposition 6.2. □

For the proof of Theorem 6.1 we will also need the following.

Proposition 6.5. For any permutation π, the diagonal term of each minor in B_{π} is divisible by the diagonal term of some minor in A_{π}.

Proof.Fix a minor in B_{π} of size 1 + ^{π} r_{ij} in z_{i×j}. If (i, j) ∈ D(π) then the result follows by definition, so assume otherwise.

As the minor’s diagonal δ is larger than the number of dots in π_{i×j}, Lemma 6.3 implies that some element in δ must lie in D(π). Let (p, q) be the coordinates of the most southeast such occurrence. If at least 1 + ^{π} r_{pq} elements of δ are northwest of (p, q), we are done. On the other hand, if this does not occur, at least ^{π} r_{ij} − ^{π} r_{pq} + 1 elements of δ are strictly to the southeast of (p, q). By our choice of (p, q), this part of the diagonal misses D(π). Hence we obtain a contradiction in view of Lemma 6.3 (use the same argument as the one ending the proof of Proposition 6.2). □

Proof of Theorem 6.1. Assume that π is not vexillary. As the ideals in(A_{π}) and in(B_{π}) generated by the diagonal terms of all minors in A_{π} and B_{π} coincide by Proposition 6.5, it suffices to prove that in(A_{π}) ≠ in(I_{π}). The zero set of in(I_{π}) has the same dimension as the zero set of I_{π}, so it is enough to show that the dimension of the zero set of in(A_{π}) exceeds that of I_{π}. Equivalently, it suffices to prove that in(A_{π}) has a component whose codimension is strictly less than the length of π.

The variables corresponding to the tiles in any pipe dream P that poisons A_{π} generate an ideal J_{P} that contains in(A_{π}) by definition. The codimension of J_{P} equals the number of tiles in P. The theorem now follows from Proposition 6.2, because the number of tiles in C(π) is the length of π. □

Acknowledgments

We would like to thank David Eisenbud, Vic Reiner, Bernd Sturmfels and Alex Woo for helpful conversations. We thank Frank Sottile for directing us to the reference [Hod]. AK was supported by an NSF grant and EM was supported by NSF grant DMS-0304789. This work was partially completed while AY was an NSERC supported visitor at the Fields Institute in Toronto, during the 2005 program “The Geometry of String Theory”.

References

[BB] N. Bergeron and S. Billey, RC-graphs and Schubert polynomials, Experimental Math. 2 (1993), no. 4, 257–269.

[BP] L. J. Billera and J. S. Provan, A decomposition property for simplicial complexes and its relation to diameters and shellings, Second International Conference on Combinatorial Mathematics (New York, 1978), New York Acad. Sci., New York, 1979, pp. 82–85.

[Buc] A. S. Buch, A Littlewood-Richardson rule for the K-theory of Grassmannians, Acta. Math. 189 (2002), no. 1, 37–78.

[CGG] L. Caniglia, J. A. Guccione, and J. J. Guccione, Ideals of generic minors, Comm. Algebra 18 (1990), no. 8, 2633–2640.

[Eis] D. Eisenbud, Commutative algebra with a view toward algebraic geometry, Springer–Verlag, New York 1995.

[FK1] S. Fomin and A. N. Kirillov, Grothendieck polynomials and the Yang–Baxter equation, 1994, Proceedings of the Sixth Conference in Formal Power Series and Algebraic Combinatorics, DIMACS, pp. 183–190.

[FK2] , The Yang-Baxter equation, symmetric functions, and Schubert polynomials, Discrete Math. 153 (1996), no. 1-3, 123–143, Proceedings of the 5th Conference on Formal Power Series and Algebraic Combinatorics (Florence, 1993).

[Ful] W. Fulton, Flags, Schubert polynomials, degeneracy loci, and determinantal formulae, Duke Math. J. 65 (1992), no. 3, 381–420.

[GM] N. Gonciulea and C. Miller, Mixed ladder determinantal varieties, J. Algebra 231 (2000), no. 1, 104–137.

[Hod] W. V. D. Hodge, The base for algebraic varieties of given dimension on a Grassmannian variety, J. London Math. Soc. 16 (1941), 245–255.

[Jo] A. Joseph, Orbital varieties, Goldie rank polynomials and unitary highest weight modules, Algebraic and analytic methods in representation theory (Sønderborg, 1994), 53–98, Perspect. Math., 17, Academic Press, San Diego, CA, 1997.

[K1] A. Knutson, Geometric vertex decompositions, FPSAC lecture notes, file available online at http://www.math.berkeley.edu/∼allenk.

[K2] , Subword complexes and local equations for Schubert varieties, in preparation.

[KMN] A. Knutson, J. Migliore, U. Nagel, A lower bound on Hilbert functions of polynomial ideals, in preparation.

[KM1] A. Knutson and E. Miller, Gröbner geometry of Schubert polynomials, Ann. Math., to appear, 2005.

[KM2] , Subword complexes in Coxeter groups, Adv. Math. 184 (2004), 161–176.

[KMY] A. Knutson, E. Miller and A. Yong, A ball of semistandard Young tableaux, in preparation.

[KY1] A. Knutson and A. Yong, A formula for K-theory truncation Schubert calculus, Internat. Math. Res. Notices 70 (2004), 3741–3756.

[KY2] , Gröbner geometry of Schubert and Grothendieck transition formulae, in preparation.

[KZJ] A. Knutson and P. Zinn-Justin, A scheme related to the Brauer loop model, in preparation.

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

[LS] A. Lascoux and M.-P. Schützenberger, Structure de Hopf de l’anneau de cohomologie et de l’anneau de Grothendieck d’une variété de drapeaux, C. R. Acad. Sci. Paris Sér. I Math. 295 (1982), 629–633.

[MS] E. Miller and B. Sturmfels, Combinatorial commutative algebra, Graduate Texts in Mathematics Vol. 227, Springer–Verlag, New York, 2004.

[PS] N. Proudfoot and D. Speyer, A broken circuit ring, math.CO/0410069.

[Stu] B. Sturmfels, Gröbner bases and Stanley decompositions of determinantal rings, Math. Z. 205 (1990), no. 1, 137–144.

[Wac] M. Wachs, Flagged Schur functions, Schubert polynomials, and symmetrizing operators, J. Combin. Theory Ser. A, 40 (1985), no. 2, 276–289.

Department of Mathematics, University of California, Berkeley, CA 94720, USA

  E-mail address: allenk@math.berkeley.edu

School of Mathematics, University of Minnesota, Minneapolis, MN 55455, USA

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

Department of Mathematics, University of California, Berkeley, CA 94720, USA and The Fields Institute, 222 College Street, Toronto, Ontario, M5T 3J1, Canada

  E-mail address: ayong@math.berkeley.edu