A GEOMETRIC LITTLEWOOD-RICHARDSON RULE

RAVI VAKIL

Abstract. We describe a geometric Littlewood-Richardson rule, interpreted as deforming the intersection of two Schubert varieties into the union of Schubert varieties. There are no restrictions on the base field, and all multiplicities arising are 1; this is important for applications. This rule should be seen as a generalization of Pieri’s rule to arbitrary Schubert classes, by way of explicit homotopies. It has straightforward bijections to other Littlewood-Richardson rules, such as tableaux, and Knutson and Tao’s puzzles. This gives the first geometric proof and interpretation of the Littlewood-Richardson rule. Geometric consequences are described here and in [V2, KV1, KV2, V3]. For example, the rule also has an interpretation in K-theory, suggested by Buch, which gives an extension of puzzles to K-theory.

Contents

1. Introduction 1 2. The statement of the rule 7 3. First applications: Littlewood-Richardson rules 17 4. Bott-Samelson varieties 23 5. Proof of the Geometric Littlewood-Richardson rule (Theorem 2.13) 25 References 40 Appendix A. The bijection between checkergames and puzzles (with A. Knutson) 41 Appendix B. Combinatorial summary of the rule 44

1. Introduction

A Littlewood-Richardson rule is a combinatorial interpretation of the Littlewood-Richardson numbers. These numbers have a variety of interpretations, most often in terms of symmetric functions, representation theory, and geometry. In each case they appear as structure coefficients of rings. For example, in the ring of symmetric functions they are the structure coefficients with respect to the basis of Schur polynomials.

In geometry, Littlewood-Richardson numbers are structure coefficients of the cohomology ring of the Grassmannian with respect to the basis of Schubert cycles (see Section 1.4;

Date: Saturday, February 22, 2003. Revised version: Tuesday, February 15, 2005. 1991 Mathematics Subject Classification. Primary 14M15, 14N15; Secondary 05E10, 05E05. Partially supported by NSF Grant DMS–0228011, an AMS Centennial Fellowship, and an Alfred P. Sloan

Research Fellowship.

Schubert cycles generate the cohomology groups of the Grassmannian). Given the fundamental role of the Grassmannian in geometry, and the fact that many of the applications and variations of Littlewood-Richardson numbers are geometric in origin, it is important to have a good understanding of the geometry underlying these numbers. Our goal here is to prove a geometric version of the Littlewood-Richardson rule, and to present applications, and connections to both past and future work.

The Geometric Littlewood-Richardson rule can be interpreted as deforming the intersection of two Schubert varieties (with respect to transverse flags M_{·} and F_{·}) so that it breaks into Schubert varieties. It is important for applications that there are no restrictions on the base field, and that all multiplicities arising are 1. The geometry of the degenerations are encoded in combinatorial objects called checkergames; solutions to “Schubert problems” are enumerated by checkergame tournaments.

Checkergames have straightforward bijections to other Littlewood-Richardson rules, such as tableaux (Theorem 3.2) and puzzles [KTW, KT] (Appendix A). Algebro-geometric consequences are described in [V2]. The rule should extend to equivariant K-theory [KV2], and suggests a conjectural geometric Littlewood-Richardson rule for the equivariant K-theory of the flag variety [V3].

Degeneration methods are of course a classical technique. See [Kl2] for a historical discussion. Sottile suggests that [P] is an early example, proving Pieri’s formula using such methods; see also Hodge’s proof [H]. More recent work by Sottile provided inspiration for this work.

1.1. Remarks on positive characteristic. The rule we describe works over arbitrary base fields. The only characteristic-dependent statements in the paper are invocations of the Kleiman-Bertini theorem [Kl1, Section 1.2]. The application of the Kleiman-Bertini theorem that we use is the following. Over an algebraically closed field of characteristic 0, if X and Y are two subvarieties of G(k, n), and σ is a general element of GL(n), then X intersects σY transversely. Kleiman gives a counterexample to this in positive characteristic [Kl1]. Kleiman-Bertini is not used for the proof of the main theorem (Theorem 2.13). All invocations here may be replaced by a characteristic-free generic smoothness theorem [V2, Theorem 1.6] proved using the Geometric Littlewood-Richardson rule.

1.2. Summary of notation and conventions. If X ⊂ Y, let Cl_{Y} X denote the closure in Y of X. Span is denoted by ⟨·⟩. Fix a base field K (of any characteristic, not necessarily algebraically closed), and non-negative integers k ≤ n. We work in G(k, n), the Grassmannian of dimension k subspaces of K^{n}. Let F l(a_{1}, …, a_{s}, n) be the partial flag variety parameterizing {V_{a_{1}} ⊂ ⋯ ⊂ V_{a_{s}} ⊂ V_{n} = K^{n}}. Our conventions follow those of [F], but we have attempted to keep this article self-contained. Table 1 is a summary of important notation introduced in the article.

1.3. Acknowledgments. The author is grateful to A. Buch and A. Knutson for patiently explaining the combinatorial, geometric, and representation-theoretic ideas behind this problem, and for comments on earlier versions. The author also thanks S. Billey, L. Chen,

Section  Notation

introduced

1.2; 1.4; 1.5 Cl, K, k < n, F l(a_{1}, …, a_{s}, n), ⟨·⟩; Rec_{k,n−k}; Moving flag M_{·}, Fixed flag F_{·}
2.1 ; 2.2  checker configuration, dominate, ≺; •, X_{•}
2.3  specialization order, •_{init}, •_{final}, •_{next}, descending checker (r, c),

rising checker, critical row r, critical diagonal

2.5–2.8  happy, ∘•, ∘, universal two-flag Schubert varieties X_{∘•} and \overline{X}_{∘•},

two-flag Schubert varieties Y_{∘•} and \overline{Y}_{∘•}, ∘_{A,B}, mid-sort ∘

2.9; 2.10  D ⊂ Cl_{G(k,n)×(X_{•}∪X_{•_{next}})} X_{∘•}; phase 1, swap, stay, blocker, phase 2, ∘_{stay}, ∘_{swap}
2.16; 2.18 checkergame; Schubert problem, checkergame tournament
4  quilt Q, dim, quadrilateral, southwest and northeast borders,

Bott-Samelson variety BS(Q) = {V_{m} : m ∈ Q}, stratum BS(Q)_{S}, Q_{∘}, 0

5.1  π, D_{Q} ⊂ Cl_{BS(Q_{∘})×(X_{•}∪X_{•_{next}})} X_{∘•}
5.4; 5.6  label, content; a, a′, a′′, d
5.7–5.9  W_{a}, W_{••_{next}}, W_{•_{next}} ⊂ ℙ(F_{c}/V_{inf(a,a′′)})^{∗} → T
5.9  b, b′, western and eastern good quadrilaterals, D_{S}

Table 1. Important notation and terminology

W. Fulton, and F. Sottile, and especially H. Kley, D. Davis, and I. Coskun for comments on the manuscript.

1.4. The geometric description of Littlewood-Richardson coefficients. (For more details and background, see [F].) Given a flag F_{·} = {F_{0} ⊂ F_{1} ⊂ ⋯ ⊂ F_{n}} in K^{n}, and a k-plane V, define the rank table to be the data dim V ∩ F_{j} (0 ≤ j ≤ n). An example for n = 5, k = 2 is:

\begin{matrix}j & 0 & 1 & 2 & 3 & 4 & 5 \\ dim V ∩ F_{j} & 0 & 0 & 1 & 1 & 1 & 2 \end{matrix}

If α is a rank table, then the locally closed subvariety of G(k, n) consisting of those kplanes with that rank table is denoted Ω_{α}(F_{·}), and is called the Schubert cell corresponding to α (with respect to the flag F_{·}). The bottom row of the rank table is a sequence of integers starting with 0 and ending with k, and increasing by 0 or 1 at each step; each such rank table is achieved by some V. This data may be summarized conveniently in two other ways. First, it is equivalent to the data of a size k subset of {1, …, n}, consisting of those integers where the rank jumps by 1 (those j for which dim V ∩ F_{j} > dim V ∩ F_{j−1}, sometimes called “jumping numbers”). The set corresponding to the example above is {2, 5}. Second, it is usually represented by a partition that is a subset of a k × (n − k) rectangle, as follows. (Denote such partitions by Rec_{k,n−k} for convenience.) Consider a path from the northeast corner to the southwest corner of such a rectangle consisting of n segments (each the side of a unit square in the rectangle). On the j^{th} step we move south if j is a jumping number, and west if not. The partition is the collection of squares northwest of the path, usually read as m = λ_{1} + λ_{2} + ⋯ + λ_{k}, where λ_{j} is the number of boxes in row j; m is usually written as |λ|. The (algebraic) codimension of Ω_{α}(F_{·}) is |λ|. The example above corresponds to the partition 2 = 2 + 0, as can be seen in Figure 1.

k = 2  ^{n − k = 3}  ^{⟺}  {2, 5}^{⟺}^{5} ^{4} ^{3} ^{2}^{1}

Figure 1. The bijection between Rec_{k,n−k} and size k subsets of {1, …, n}

The Schubert classes [\overline{Ω}_{α}] (as α runs over Rec_{k,n−k}) are a ℤ-basis of A_{∗}(G(k, n), ℤ), or (via Poincaré duality) A^{∗}(G(k, n), ℤ); we will sloppily consider these as classes in homology or cohomology depending on the context. (We use Chow groups and rings A_{∗} and A^{∗}, but the complex-minded reader is welcome to use H_{2∗} and H^{2∗} instead.) Of course there is no dependence on F_{·}. Hence

[\overline{Ω}_{α}] ∪ [\overline{Ω}_{β}] = ∑_{γ∈Rec_{k,n−k}} c_{αβ}^{γ}[\overline{Ω}_{γ}]

for some integers c_{αβ}^{γ}; these are the Littlewood-Richardson numbers. The Chow (or cohomology) ring structure may thus be recovered from the Littlewood-Richardson numbers.

1.5. A key example of the rule. It is straightforward to verify (and we will do so) that if M_{·} and F_{·} are transverse flags, then \overline{Ω}_{α}(M_{·}) intersects \overline{Ω}_{β}(F_{·}) transversely, so [\overline{Ω}_{α}] ∪ [\overline{Ω}_{β}] = [\overline{Ω}_{α}(M_{·}) ∩ \overline{Ω}_{β}(F_{·})]. We will deform M_{·} (the “Moving flag”) through a series of oneparameter degenerations. In each degeneration, M_{·} will become less and less transverse to the “Fixed flag” F_{·}, until at the end of the last degeneration they will be identical. We start with the cycle [\overline{Ω}_{α}(M_{·}) ∩ \overline{Ω}_{β}(F_{·})], and as M_{·} moves, we follow what happens to the cycle. At each stage the cycle will either stay irreducible, or will break into two pieces, each appearing with multiplicity 1. If it breaks into two components, we continue the degenerations with one of the components, saving the other for later. At the end of the process, the final cycle will be visibly a Schubert variety (with respect to the flag M_{·} = F_{·}). We then go back and continue the process with the pieces left behind. Thus the process produces a binary tree, where the bifurcations correspond to when a component breaks into two; the root is the initial cycle at the start of the process, and the leaves are the resulting Schubert varieties. The Littlewood-Richardson coefficient c_{αβ}^{γ} is the number of leaves of type γ, which will be interpreted combinatorially as checkergames (Section 2.16). The deformation of M_{·} will be independent of the choice of α and β.

Before stating the rule, we give an example. Let n = 4 and k = 2, i.e. we consider the Grassmannian G(2, 4) = 𝔾(1, 3) of projective lines in ℙ^{3}. (We use the projective description in order to better draw pictures.) Let α = β = □ = \{2, 4\}, so \overline{Ω}_{α} and \overline{Ω}_{β} both correspond to the set of lines in ℙ^{3} meeting a fixed line. Thus we seek to deform the locus of lines meeting two (skew) fixed lines into a union of Schubert varieties.

The degenerations of M_{·} are depicted in Figure 2. (The checker pictures will be described in Section 2. They provide a convenient description of the geometry in higher dimensions, when we can’t easily draw pictures.) In the first degeneration, only the moving plane ℙM_{3} moves, and all other ℙM_{i} (and all ℙF_{j}) stay fixed. In that pencil of planes, there is one special position, corresponding to when the moving plane contains the fixed flag’s point ℙF_{1}. Next, the moving line ℙM_{2} moves (and all other spaces are fixed), to the unique “special” position, when it contains the fixed flag’s point ℙF_{1}. Then the moving plane ℙM_{3} moves again, to the position where it contains the fixed flag’s line ℙF_{2}. Then the moving point ℙM_{1} moves (until it is the same as the fixed point), and then the moving line ℙM_{2} moves (until it is the same as the fixed line), and finally the moving plane ℙM_{3} moves (until it is the same as the fixed plane, and both flags are the same).

point  ^{line}  ^{plane} 4123  1423  1243^{12}  ^{23}  ^{34}^{M·} 4321^{F·}  ^{plane}^{34}^{line}  ^{plane} 4312  4132^{23}  ^{34}  1234

Figure 2. The specialization order for n = 4, visualized in terms of flags in ℙ^{3}. The checker configurations will be defined in Section 2.2.

In Figure 3 we will see how this sequence of deformations “resolves” (or deforms) the intersection \overline{Ω}_{α}(M_{·}) ∩ \overline{Ω}_{β}(F_{·}) into the union of Schubert varieties. (We reiterate that this sequence of deformations will “resolve” any intersection in 𝔾(k, 3) in this way, and the analogous sequence in ℙ^{n} will resolve any intersection in 𝔾(k, n).)

To begin with, \overline{Ω}_{α}(M_{·})∩\overline{Ω}_{β}(F_{·}) ⊂ 𝔾(1, 3) is the locus of lines meeting the two lines ℙM_{2} and ℙF_{2}, as depicted in the first panel of Figure 3. After the first degeneration, in which the moving plane moves, the cycle in question has not changed (the second panel). After the second degeneration, the moving line and the fixed line meet, and there are now two irreducible two-dimensional loci in 𝔾(1, 3) of lines meeting both the moving and fixed line. The first case consists of those lines meeting the intersection point ℙM_{2} ∩ ℙF_{2} = ℙF_{1} (the third panel in the top row). The second case consists of those lines contained in the plane spanned by ℙM_{2} and ℙF_{2} (the first panel in the second row). After the next degeneration in this second case, this condition can be restated as the locus of lines contained in the moving plane ℙM_{3} (the second panel of the second row), and it is this description that we follow thereafter. The remaining pictures should hopefully be clear. At the end of both cases, we see Schubert varieties. In the first case we have the locus of lines through a fixed point (corresponding to partition 2 = 2 + 0, or {1, 4}, see the panel in the lower right). In the second case we have the locus of lines contained in the fixed plane (corresponding to partition 2 = 1 + 1, or the subset {2, 3}, see the second-last panel in the final row). Thus we see that

c_{(1),(1)}^{(2)} = c_{(1),(1)}^{(1,1)} = 1.

We now abstract from this example the essential features that will allow us to generalize this method, and make it rigorous. We will see that the analogous sequence of \binom{n}{2} degenerations in K^{n} will similarly resolve any intersection \overline{Ω}_{α}(M_{·})∩\overline{Ω}_{β}(F_{·}) in any G(k, n). The explicit description of how it does so is the geometric Littlewood-Richardson rule.

1. Defining the relevant varieties. Given two flags M_{·} and F_{·} in given relative position (i.e. part way through the degeneration), we define varieties (called closed two-flag Schubert varieties, Section 2.5) in the Grassmannian G(k, n) = {V ⊂ K^{n}} that are the closure of the locus with fixed numerical data dim V ∩ M_{i} ∩ F_{j}. In the case where M_{·} and F_{·} are transverse, we verify that \overline{Ω}_{α}(M_{·}) ∩ \overline{Ω}_{β}(F_{·}) is such a variety.

2. The degeneration, inductively. We degenerate M_{·} in the specified manner. Each component of the degeneration is parameterized by ℙ^{1}; over 𝔸^{1} = ℙ^{1} − {∞}, M_{·} meets F_{·} in the same way (i.e. the rank table dim M_{i} ∩F_{j} is constant), and over one point their relative position “jumps”. Hence any closed two-flag Schubert variety induces a family over 𝔸^{1} (in G(k, n) × 𝔸^{1}). We take the closure in G(k, n) × ℙ^{1}. We show that the fiber over ∞ consists of one or two components, each appearing with multiplicity 1, and each a closed two-flag Schubert variety (so we may continue inductively).

3. Concluding. After the last degeneration, the two flags M_{·} and F_{·} are equal. Then the two-flag Schubert varieties are by definition Schubert varieties with respect to this flag.

The key step is the italicized sentence in Step 2, and this is where the main difficulty lies. In fact, we have not proved this step for all two-flag Schubert varieties; but we can

input: ×  output: {2, 3} =  output: {1, 4} = ** * † (α = β = {2, 4})  †

Figure 3. A motivating example of the rule (compare to Figure 2). Checker configurations * and ** are discussed in Caution 2.20, and the degenerations labeled † are discussed in Sections 2.11 and 3.1.

do it with all two-flag Schubert varieties inductively produced by this process. (These are the two-flag Schubert varieties that are mid-sort, see Definition 2.8.) A proof avoiding this technical step, but assuming the usual Littlewood-Richardson rule and requiring some tedious combinatorial work, is outlined in Section 2.19.

2. The statement of the rule

2.1. Preliminary definitions. Geometric data will be conveniently summarized by the data of checkers on an n × n board. The rows and columns of the board will be numbered in “matrix” style: (r, c) will denote the square in row r (counting from the top) and column c (counting from the left), e.g. see Figure 4. A set of checkers on the board will be called a configuration of checkers. We say a square (i_{1}, j_{1}) dominates another square (i_{2}, j_{2}) if it is weakly southeast of (i_{2}, j_{2}), i.e. if i_{1} ≥ i_{2} and j_{1} ≥ j_{2}. Domination induces a partial order ≺ on the plane.

2.2. Double Schubert cells, and black checkers. Suppose {v_{ij}} is an achievable rank table dim M_{i} ∩ F_{j} where M_{·} and F_{·} are two flags in K^{n}. This data will be conveniently summarized by the data of n black checkers on the n × n board, no two in the same row or column, as follows. There is a unique way of placing black checkers so that the entry dim M_{i} ∩ F_{j} is given by the number of black checkers dominated by square (i, j). (To obtain the inverse map we proceed through the columns from left to right and place a checker in the first box in each column where the number of checkers that box dominates is less than the number written in the box. The checker positions are analogs of the “jumping numbers” of 1.4.) An example of the bijection is given in Figure 4. Each square on the board corresponds to a vector space, whose dimension is the number of black checkers dominated by that square. This vector space is the span of the vector spaces corresponding to the black checkers it dominates. The vector spaces of the right column (resp. bottom row) correspond to the Moving flag (resp. Fixed flag).

3^{4}^{2}  ^{2}^{1}^{1}^{1}  ⟺^{1}  ^{3}^{0}  ^{2}^{1}^{0}  ^{0}^{0}^{0}^{M_{1}}^{M_{2}}^{M_{3}}^{M_{4}}  ^{F_{1}} ^{F_{2}} ^{F_{3}} ^{F_{4}}  ^{dim M_{2} ∩ F_{4}}

Figure 4. The relative position of two flags, given by a rank table, and by a configuration of black checkers

A configuration of black checkers will often be denoted •. If • is such a checker configuration, define X_{•} to be the corresponding locally closed subvariety of F l(n) × F l(n) (where the first factor parameterizes M_{·} and the second factor parameterizes F_{·}). The variety X_{•} is smooth, and its codimension in F l(n) × F l(n) is the number of pairs of distinct black checkers a and b such that a ≺ b. (This is a straightforward exercise; it also follows quickly from Section 4.) This sort of construction is common in the literature.

The X_{•} are sometimes called “double Schubert cells”. They are the GL(n)-orbits of F l(n) × F l(n), and the fibers over either factor are Schubert cells of the flag variety. They stratify F l(n)×F l(n). The fiber of the projection X_{•} → F l(n) given by ([M_{·}], [F_{·}]) ↦ [F_{·}] is the Schubert cell Ω_{σ(•)}, where the permutation σ(•) sends r to c if there is a black checker at (r, c). (Schubert cells are usually indexed by permutations [F, Section 10.2]. Caution: some authors use other bijections to permutations than that of [F].) For example, the permutation corresponding to Figure 4 is 4231; for more examples, see Figure 2.

2.3. The specialization order (in the weak Bruhat order), and movement of black checkers. We now define a specialization order of such data, a particular sequence, starting with the transverse case •_{init} (corresponding to the longest word w_{0} in 𝔖_{n}) and ending with •_{final} (the identity permutation in 𝔖_{n}), corresponding to when the two flags are identical. If • is one of the configurations in the specialization order, then •_{next} will denote the next configuration in the specialization order.

The intermediate checker configurations correspond to partial factorizations from the left of w_{0}:

w_{0} = e_{n−1} ⋯ e_{2}e_{1} ⋯ e_{n−1}e_{n−2}e_{n−3} e_{n−1}e_{n−2} e_{n−1}.

(Note that this word neither begins nor ends with the corresponding word for n − 1, making a naive inductive proof of the rule impossible.) For example, Figure 2 shows the six moves of the black checkers for n = 4, along with the corresponding permutations:

w_{0} = e_{3}e_{2}e_{1}e_{3}e_{2}e_{3}, e_{3}e_{2}e_{1}e_{3}e_{2}, e_{3}e_{2}e_{1}e_{3}, e_{3}e_{2}e_{1}, e_{3}e_{2}, e_{3}, e.

In the language of computer science, the specialization order may be interpreted as a bubble-sort of the black checkers.

Figure 5 shows a typical checker configuration in the specialization order. Each move involves moving one checker one row down (call this the descending checker), and another checker one row up (call this the rising checker), as shown in the figure. The notions of critical row and critical diagonal will be useful later; see Figure 5 for a definition. Hereafter let r be the row of the descending checker, and c the column.

rising checker critical diagonal descending checker (r, c) critical row r

Figure 5. The critical row and the critical diagonal

2.4. An important description of X_{•} and X_{•_{next}} for • in the specialization order. Here is a convenient description of X_{•} and X_{•_{next}}. Define

P = {M_{0} ⊂ M_{1} ⊂ ⋯ ⊂ M_{n−1} ⊂ M_{n} = K^{n}, F_{c} ⊂ F_{c+1} ⊂ ⋯ ⊂ F_{n−1} ⊂ F_{n} = K^{n},
M_{·} is transverse to the partial flag F_{c} ⊂ ⋯ ⊂ F_{n} }
⊂ F l(n) × F l(c, …, n).

Over P consider the projective bundle ℙF_{c}^{∗} = {(p ∈ P, F_{c−1} ⊂ F_{c})} of hyperplanes in F_{c}. Then X_{•} is isomorphic to the locus

{F_{c−1} : F_{c−1} ⊃ M_{r−1} ∩ F_{c}, F_{c−1} ⊉ M_{r} ∩ F_{c}} :

to recover F_{1}, …, F_{c−2}, for r + c − n ≤ j ≤ c − 2, take F_{j} = M_{n−c+j+1} ∩ F_{c−1}, and for j ≤ r + c − n − 1 take F_{j} = M_{n−c+j} ∩ F_{c−1}. (Figure 6 may be helpful for understanding the geometry.) More concise (but less enlightening) is the description of F_{0}, …, F_{c−1} by the equality of sets

{F_{0}, …, F_{c−1}} = {M_{0} ∩ F_{c−1}, M_{1} ∩ F_{c−1}, … M_{n} ∩ F_{c−1}} ⊂ ℙF_{c}^{∗}.

Mr ∩ Fc Fr+c−n = Mr+1 ∩ Fc−1 F1 = Mn−c+1 ∩ Fc−1 Fr+c−n−1 = Mr−1 ∩ Fc−1 ⋮  M1 ⋮ Mn−c Mn−c+1 ⋮ Mr Mr−1 Mr+1 Fc−1  Mn = Fn Fc Fc+1

Figure 6. A convenient description of a double Schubert cell in the specialization order in terms of transverse {F_{c}, …, F_{n}} and M_{·}, and F_{c−1} in given position with respect to M_{·}. Some squares of the checkerboard are labeled with their corresponding vector space.

Similarly, X_{•_{next}} is isomorphic to

{F_{c−1} : F_{c−1} ⊃ M_{r} ∩ F_{c}, F_{c−1} ⊉ M_{r+1} ∩ F_{c}} ⊂ ℙF_{c}^{∗}.

2.5. Two-flag Schubert varieties, and white checkers. Suppose {v_{ij}}, {w_{ij}} are achievable rank tables dim M_{i} ∩ F_{j} and dim V ∩ M_{i} ∩ F_{j} where M_{·} and F_{·} are two flags in K^{n} and V is a k-plane. This data may be summarized conveniently by a configuration of n black checkers and k white checkers on an n×n checkerboard as follows. The meaning of the black checkers is the same as above; they encode the relative position of the two flags. There is a unique way to place the k white checkers on the board such that dim V ∩M_{i}∩F_{j} is the number of white checkers in squares dominated by (i, j). See Figure 3 for examples. It is straightforward to check that (i) no two white checkers are in the same row or column, and (ii) each white checker must be placed so that there is a black checker weakly to its north (i.e. either in the same square, or in a square above it), and a black checker weakly to its west. We say that white checkers satisfying (ii) are happy. Such a configuration of black and white checkers will often be denoted ∘•; a configuration of white checkers will often be denoted ∘.

If ∘• is a configuration of black and white checkers, let X_{∘•} be the corresponding locally closed subvariety of G(k, n) × F l(n) × F l(n); call this an open universal two-flag Schubert variety. Call \overline{X}_{∘•} := Cl_{G(k,n)×X_{•}} X_{∘•} a closed universal two-flag Schubert variety. (Notational caution: \overline{X}_{∘•} is not closed in G(k, n) × F l(n) × F l(n).)

If M_{·} and F_{·} are two flags whose relative position is given by •, let the open two-flag Schubert variety Y_{∘•} = Y_{∘•}(M_{·}, F_{·}) ⊂ G(k, n) be the set of k-planes whose position relative to the flags is given by ∘•; define the closed two-flag Schubert variety \overline{Y}_{∘•} to be Cl_{G(k,n)} Y_{∘•}.

Note that (i) X_{∘•} → X_{•} is a Y_{∘•}-fibration; (ii) \overline{X}_{∘•} → X_{•} is a \overline{Y}_{∘•}-fibration, and is a projective morphism; (iii) G(k, n) is the disjoint union of the Y_{∘•} (for fixed M_{·}, F_{·}); (iv) G(k, n) × F l(n) × F l(n) is the disjoint union of the X_{∘•}. Caution: the disjoint unions of (iii) and (iv) are not in general stratifications; see Caution 2.20(a) for a counterexample for (iv).

The proof of the following Lemma is straightforward by constructing Y_{∘•} as an open subset of a tower of projective bundles (one for each white checker) and hence omitted.

2.6. Lemma. — The variety Y_{∘•} is irreducible and smooth; its dimension is the sum over all white checkers w of the number of black checkers w dominates minus the number of white checkers w dominates (including itself).

Suppose that A = {a_{1}, …, a_{k}} and B = {b_{1}, …, b_{k}} are two subsets of {1, …, n}, where a_{1} < ⋯ < a_{k} and b_{1} < ⋯ < b_{k}. Denote by ∘_{A,B} the configuration of k white checkers in the squares (a_{1}, b_{k}), (a_{2}, b_{k−1}), …, (a_{k}, b_{1}). (Informally: the white checkers are arranged from southwest to northeast, such that they appear in the rows corresponding to A and the columns corresponding to B. No white checker dominates another.)

2.7. Proposition (initial position of white checkers). — Suppose M_{·} and F_{·} are two transverse flags (i.e. with relative position given by •_{init}). Then (the scheme-theoretic intersection) \overline{Ω}_{A}(M_{·}) ∩ \overline{Ω}_{B}(F_{·}) is the closed two-flag Schubert variety \overline{Y}_{∘_{A,B}•_{init}}.

In the literature, these intersections are known as Richardson varieties [R]; see [KL] for more discussion and references. They are also called skew Schubert varieties by Stanley [St].

In particular, if (and only if) any of these white checkers are not happy (or equivalently if a_{i} + b_{k+1−i} ≤ n for some i), then the intersection is empty. For example, this happens if n = 2 and A = B = {1}, corresponding to the intersection of two distinct points in ℙ^{1}.

Proof. Assume first that the characteristic is 0. By the Kleiman-Bertini theorem (Section 1.1), \overline{Ω}_{A}(M_{·}) ∩ \overline{Ω}_{B}(F_{·}) is reduced of the expected dimension. The generic point of any of its components lies in Y_{∘•_{init}} for some configuration ∘ of white checkers, where the first coordinates of the white checkers of ∘ are given by the set A and the second coordinates are given by the set B. A short calculation using Lemma 2.6 yields dim Y_{∘•_{init}} ≤ dim Y_{∘_{A,B}•_{init}}, with equality holding if and only if ∘ = ∘_{A,B}. (Reason: the sum over all white checkers w in ∘ of the number of black checkers w dominates is ∑_{a∈A} a + ∑_{b∈B} b − kn, which is independent of ∘, so dim Y_{∘•_{init}} is maximized when no white checker dominates another, which is the definition of ∘_{A,B}.) Then it can be checked directly that dim Y_{∘_{A,B}•_{init}} = dim \overline{Ω}_{A}∩\overline{Ω}_{B}. As Y_{∘_{A,B}•_{init}} is irreducible, the result in characteristic 0 follows.

In positive characteristic, the same argument shows that the cycle \overline{Ω}_{A}(M_{·}) ∩ \overline{Ω}_{B}(F_{·}) is some positive multiple of the the cycle \overline{Y}_{∘_{A,B}•_{init}}. It is an easy exercise to show that the intersection is transverse, i.e. that this multiple is 1. It will be easier still to conclude the proof combinatorially; we will do this — and finish the proof — in Section 2.18. □

We will need to consider a particular subset of the possible ∘•, which we define now.

2.8. Definition. Suppose ∘• is a configuration of black and white checkers such that • is in the specialization order, and the descending checker is in column c. Suppose the white checkers are at (r_{1}, c_{1}), …, (r_{k}, c_{k}) with c_{1} < ⋯ < c_{k}. If (r_{i}, …, r_{k}) is decreasing when c_{i} ≥ c, then we say that ∘• is mid-sort. For example, the white checkers of Figure 7 are mid-sort. As the black checkers in columns up to c − 1 are arranged diagonally, the “happy” condition implies that (r_{1}, …, r_{j}) is increasing when c_{j} < c, as may be seen in Figure 7. Any initial configuration is clearly mid-sort. Other examples of mid-sort highlighting the overall shape of the white checkers’ placement are given in Figures 18 and 19.

diagonally here white checkers arranged:  anti-diagonally here

Figure 7. An example of mid-sort checkers

2.9. The degenerations. Suppose now that ∘• is mid-sort. Consider the diagram:

(1)  \xymatrix{\overline{X}_{∘•} := Cl_{G(k,n)×X_{•}} X_{∘•} \ar[d] \ar@{^{(}->}[r]^{open} & Cl_{G(k,n)×(X_{•}∪X_{•_{next}})} X_{∘•} \ar[d] & D \ar@{^{(}->}[l]_{Cartier} \ar[d] \\ X_{•} \ar@{^{(}->}[r]^{open} & X_{•} ∪ X_{•_{next}} & X_{•_{next}}. \ar@{^{(}->}[l]_{Cartier}}

The Cartier divisor D on Cl_{G(k,n)×(X_{•}∪X_{•_{next}})} X_{∘•} is defined by pullback; both squares in (1) are fibered squares. The vertical morphisms are projective, and the vertical morphism on the left is a \overline{Y}_{∘•}-fibration. We will identify the irreducible components of D as certain \overline{X}_{∘′•_{next}}, each appearing with multiplicity 1.

2.10. Description of the movement of the white checkers. The movement of the white checkers takes place in two phases. Phase 1 depends on the answers to two questions: Where (if anywhere) is the white checker in the critical row? Where (if anywhere) is the highest white checker in the critical diagonal? Based on the answers to these questions, these two white checkers either swap rows (i.e. move from (r_{1}, c_{1}) and (r_{2}, c_{2}) to (r_{2}, c_{1}) and (r_{1}, c_{2})), or they stay where they are, according to Table 2. (The pictorial examples of Figure 8 may be helpful.) The central entry of the table is the only time when there is a possibility for choice: the pair of white checkers can stay, or if there are no white checkers in the rectangle

White checker in critical row?

yes, in descending yes, elsewhere no

checker’s square

Top white yes, in rising swap swap stay^{†}
checker checker’s square
in  yes,  swap  swap if no blocker stay
critical  elsewhere  or stay
diagonal?  no  stay  stay  stay

Table 2. Phase 1 of the white checker moves (see Figure 8 for a pictorial description)

between them they can swap. Call white checkers in this rectangle blockers. Figure 9 gives an example of a blocker.

or^{no}  ^{no} White checker in critical row?^{elsewhere} ^{checker’s square}^{moves:}^{phase 1:}^{phase 2:} Legend:  ^{yes, in descending}^{yes, in}^{rising}^{checker’s}^{square}^{yes,} Top white checker in critical diagonal?^{black checker}^{white checker}^{white checker}  ^{yes, elsewhere}  ^{†}

Figure 8. Examples of the entries of Table 2 (case † is discussed in Section 3.1)

white checker in critical row

blocker

top white checker in critical diagonal

Figure 9. Example of a blocker

After phase 1, at most one white checker is unhappy. Phase 2 is a “clean-up” phase: if a white checker is not happy, then move it either left or up so that it becomes happy. This is always possible, in a unique way. Afterwards, no two white checkers will be in the same row or column.

The resulting configuration is dubbed ∘_{stay}•_{next} or ∘_{swap}•_{next} (depending on which option we chose in phase 1).

(A more concise — but less useful — description of the white checker moves, not requiring Table 2 or the notion of blockers, is as follows. In phase 1, we always consider the stay option, and we always consider the swap option if the critical row and the critical diagonal both contain white checkers. After phase 1, there are up to two unhappy white checkers. We “clean up” following phase 2 as before, making all white checkers happy. Then we have one or two possible configurations. If one of the configurations has two white checkers in the same row or column, we discard it. If one of the configurations ∘′•_{next} has dimension less than desired — i.e. dim X_{∘′•_{next}} < dim D = dim X_{∘•} − 1, or equivalently dim Y_{∘′•_{next}} < dim Y_{∘•}, see Lemma 2.6 — we discard it.)

The geometric meaning of each case in Table 2 is straightforward; we have already seen seven of the cases in Figure 3. For example, in the bottom-right case of Table 2/Figure 8, the k-plane V continues to meet flags M_{·} and F_{·} in the same way, although they are in more special position (as in the first degeneration of Figure 3). In the top-right case of Table 2/Figure 8, V meets F_{·} in the same way, and is forced to meet M_{·} in a more special way (see the degenerations marked † in Figure 3). The reader is encouraged to compare more degenerations of Figure 3 to Table 2/Figure 8 to develop a sense for the geometry behind the checker moves.

2.11. The cases where there is no white checker in the critical row r (the third column of Table 2) are essentially trivial; in this case the moving subspace M_{r} imposes no condition on the k-plane (see Figure 3 for numerous examples). This will be made precise in Section 5.2. Even the case where a checker moves (the top right entry in Figure 8), there is no corresponding change in the position of the k-plane (see the degenerations marked † in Figure 3 for examples).

The following may be shown by a straightforward induction.

2.12. Lemma. — If ∘• is mid-sort, then ∘_{stay}•_{next}and ∘_{swap}•_{next}(if they exist) are mid-sort.

We now state the main result of this paper, which will be proved in Section 5. (A different proof, assuming the combinatorial Littlewood-Richardson rule, is outlined in Section 2.19.)

2.13. Theorem (Geometric Littlewood-Richardson rule). —

D = \overline{X}_{∘_{stay}•_{next}}, \overline{X}_{∘_{swap}•_{next}}, or \overline{X}_{∘_{stay}•_{next}} ∪ \overline{X}_{∘_{swap}•_{next}}.

Note: Throughout this paper, the meaning of or in such a context will always be depending on which checker movements are possible according to Table 2.

2.14. Interpretation of the rule in terms of deforming cycles in the Grassmannian. From Theorem 2.13 we obtain the deformation description given in Section 1.5, as follows. Given a point p of F l(n) (parameterizing M_{·}) in the dense open Schubert cell (with respect to a fixed reference flag F_{·}), there is a chain of \binom{n}{2} ℙ^{1}’s in F l(n), starting at p and ending with the “most degenerate” point of F l(n) (corresponding to M_{·} = F_{·}). This chain corresponds to the specialization order; each ℙ^{1} is a fiber of the fibration of the appropriate X_{•} ∪ X_{•_{next}} → X_{•_{next}}. All but one point of the fiber lies in X_{•}. The remaining point ∞ (where the ℙ^{1} meets the next component of the degeneration) lies on a stratum X_{•_{next}} of dimension one lower. If the move corresponds to the descending checker in critical row r dropping one row, then all components of the flags F_{·} and M_{·} except M_{r} are held fixed (as shown in Figure 2).

Given such a ℙ^{1} ↪ X_{•} ∪ X_{•_{next}} in the degeneration, we obtain the following by pullback from (1)(introducing temporary notation Y_{∘•} and D_{Y}):

(2)  \xymatrix{Y_{∘•} \ar[d] \ar@{^{(}->}[r]^{open} & Cl_{G(k,n)×ℙ^{1}} Y_{∘•} \ar[d] & D_{Y} \ar@{^{(}->}[l]_{Cartier} \ar[d] \\ 𝔸^{1} \ar@{^{(}->}[r]^{open} & ℙ^{1} & \{∞\}. \ar@{^{(}->}[l]_{Cartier}}

Again, the vertical morphisms are projective and the vertical morphism on the left is a \overline{Y}_{∘•}-fibration.

By applying base change from (1)to (2)to Theorem 2.13, we obtain:

2.15. Theorem (Geometric Littlewood-Richardson rule, degeneration version). —

D_{Y} = \overline{Y}_{∘_{stay}•_{next}}, \overline{Y}_{∘_{swap}•_{next}}, or \overline{Y}_{∘_{stay}•_{next}} ∪ \overline{Y}_{∘_{swap}•_{next}}.

(The notation Y_{∘•} and D_{Y} will not be used hereafter.)

We use this theorem to compute the class (in H_{∗}(G(k, n))) of the intersection of two Schubert cycles as follows. By the Kleiman-Bertini theorem (Section 1.1), or the Grassmannian Kleiman-Bertini theorem [V2, Theorem 1.6] in positive characteristic, this is the class of the intersection of two Schubert varieties with respect to two general (transverse) flags, which by Proposition 2.7 is [\overline{Y}_{∘_{A,B}•_{init}}]. We use Theorem 2.15 repeatedly to break the cycle inductively into pieces. We conclude by noting that each \overline{Y}_{∘•_{final}} is a Schubert variety; the corresponding subset of {1, …, n} is precisely the set of black checkers sharing a square with a white checker (as in Figure 3).

2.16. Littlewood-Richardson coefficients count checkergames. A checkergame with input α and β and output γ is defined to be a sequence of moves ∘_{α,β}•_{init}, …, ∘_{γ}•_{final}, as described by the Littlewood-Richardson rule (i.e. the position after ∘• is ∘_{stay}•_{next} or ∘_{swap}•_{next}).

2.17. Corollary. — The Littlewood-Richardson coefficient c_{αβ}^{γ} is the number of checkergames with input α and β and output γ.

2.18. Enumerative problems and checkergame tournaments. Suppose [\overline{Ω}_{α_{1}}], …, [\overline{Ω}_{α_{ℓ}}] are Schubert classes on G(k, n) of total codimension dim G(k, n). Then the degree of their intersection — the solution to an enumerative problem by the Kleiman-Bertini theorem (Section 1.1), or the Grassmannian Kleiman-Bertini theorem [V2, Theorem 1.6] in positive characteristic) — can clearly be inductively computed using the Geometric Littlewood-Richardson rule. (Such an enumerative problem is called a Schubert problem.) Hence Schubert problems can be solved by counting checkergame tournaments of ℓ − 1 games, where the input to the first game is α_{1} and α_{2}, and for i > 1 the input to the i^{th} game is α_{i+1} and the output of the previous game. (The outcome of each checkergame tournament will always be the same — the class of a point.)

Conclusion of proof of Proposition 2.7 in positive characteristic. We will show that the multiplicity with which \overline{Y}_{∘_{A,B}•_{init}} appears in \overline{Ω}_{A}(M_{·}) ∩ \overline{Ω}_{B}(F_{·}) is 1. We will not use the Grassmannian Kleiman-Bertini Theorem [V2, Theorem 1.6] as its proof relies on Proposition 2.7.

Choose C = \{c_{1}, …, c_{k}\} such that dim[\overline{Ω}_{A}] ∪ [\overline{Ω}_{B}] ∪ [\overline{Ω}_{C}] = 0 (where ∪ is the cup product in cohomology) and deg[\overline{Ω}_{A}] ∪ [\overline{Ω}_{B}] ∪ [\overline{Ω}_{C}] > 0. In characteristic 0, the above discussion shows that deg[\overline{Ω}_{A}] ∪ [\overline{Ω}_{B}] ∪ [\overline{Ω}_{C}] is the number of checkergame tournaments with inputs A, B, C. In positive characteristic, the above discussion shows that if the multiplicity is greater than one, then deg[\overline{Ω}_{A}] ∪ [\overline{Ω}_{B}] ∪ [\overline{Ω}_{C}] is strictly less than the same number of checkergames. But deg[\overline{Ω}_{A}] ∪ [\overline{Ω}_{B}] ∪ [\overline{Ω}_{C}] is independent of characteristic, yielding a contradiction. □

2.19. A second proof of the rule (Theorem 2.13), assuming the combinatorial Littlewood-Richardson rule. We now outline a second proof of the Geometric Littlewood-Richardson rule that bypasses almost all of Sections 4 and 5. Proposition 5.15 shows that X_{∘_{stay}•_{next}} and/or X_{∘_{swap} •_{next}} are contained in D with multiplicity 1. (It may be rewritten without the language of Bott-Samelson varieties.) We seek to show that there are no other components. The semigroup consisting of effective classes in H^{∗}(G(k, n), ℤ) is generated by the Schubert classes; this semigroup induces a partial order on H^{∗}(G(k, n), ℤ). Let d_{αβ}^{γ} be the number of checkergames with input α and β, and output γ. Then at each stage of the degeneration, [D] − [\overline{X}_{∘_{stay}•_{next}}], [D] − [\overline{X}_{∘_{swap} •_{next}}], or [D] − [\overline{X}_{∘_{stay}•_{next}}] − [\overline{X}_{∘_{swap} •_{next}}] (depending on the case) is effective, and hence

[\overline{Ω}_{α}] ∪ [\overline{Ω}_{β}] − ∑_{γ} d_{αβ}^{γ}[\overline{Ω}_{γ}] ≥ 0

with equality holding if and only if the Geometric Littlewood-Richardson rule Theorem 2.13 is true at every stage in the degeneration. But by the combinatorial Littlewood-Richardson rule,

[\overline{Ω}_{α}] ∪ [\overline{Ω}_{β}] = ∑_{γ} c_{αβ}^{γ}[\overline{Ω}_{γ}].

Theorem 3.2 gives a bijection between checkergames and tableaux. The proof uses the bijection between checkergames and puzzles of Appendix A. This in turn was proved by giving an injection from checkergames to puzzles, and using the Geometric Littlewood-Richardson rule to show bijectivity. However, as described there, it is possible to show bijectivity directly (by an omitted tedious combinatorial argument). Thus c_{α,β}^{γ} = d_{α,β}^{γ}, so Theorem 2.13 is true for every ∘• that arises in the course of a checkergame.

Finally, one may show by induction on • that every ∘• (with ∘ mid-sort) does arise in the course of a checkergame: It is clearly true for mid-sort ∘•_{init}. Given a mid-sort ∘′•_{next}, one may easily verify using Figure 8 that there is some ∘• such that ∘′•_{next} = ∘_{stay}•_{next} or ∘_{swap}•_{next}. □

2.20. Cautions. (a) The specialization order may not be replaced by an arbitrary path through the weak Bruhat order. For example, if ∘• is as shown on the left of Figure 10, then X_{∘•} parameterizes: distinct points p_{1} and p_{2} in ℙ^{3}; lines ℓ_{1} and ℓ_{2} through p_{1} such that ℓ_{1}, ℓ_{2}, and p_{2} span ℙ^{3}; and a point q ∈ ℓ_{1} − p_{1}. Then the line corresponding to the white checkers (a point of 𝔾(1, 3)) is ⟨q, p_{2}⟩. The degeneration shown in Figure 10 (• → •′, say) corresponds to letting p_{2} tend to p_{1}, and remembering the line ℓ_{3} of approach. Then the divisor on Cl_{G(k,n)×(X_{•}∪X_{•′})} X_{∘•} corresponding to X_{•′} parameterizes lines through p_{1} contained in ⟨ℓ_{1}, ℓ_{3}⟩. This is not of the form X_{∘′•′} for any ∘′.

p_{1}  ^{ℓ_{3}}^{ℓ_{2}}^{ℓ_{1}}  ^{F_{4}}^{F_{3}}^{F_{2}}^{F_{1}}^{M_{1}}^{M_{2}}^{M_{3}}^{M_{4}}^{p_{2}}^{p_{1}}  ^{q} ^{ℓ_{2}}^{ℓ_{1}}  ? ⟹^{F_{1}}  ^{F_{4}}^{F_{3}}^{F_{2}}^{M_{1}}^{M_{2}}^{M_{3}}^{M_{4}}

Figure 10. The dangers of straying from the specialization order

(b) Unlike the variety \overline{X}_{•} = Cl_{F l(n)×F l(n)} X_{•}, the variety \overline{X}_{∘•} cannot be defined numerically, i.e. in general \overline{X}_{∘•} will be only one irreducible component of

\overline{X}′_{∘•} := \{(V, M_{·}, F_{·}) ∈ G(k, n) × X_{•} ⊂ G(k, n) × F l(n) × F l(n) : dim V ∩ M_{i} ∩ F_{j} ≥ γ_{∘}^{i,j}\}

where γ_{∘}^{i,j} is the number of white checkers dominated by (i, j). For example, in Figure 3, if ∘• is the configuration marked “*” and ∘′• is the configuration marked “**”, then \overline{X}′_{∘•} = \overline{X}_{∘•} ∪ \overline{X}_{∘′•}.

3. First applications: Littlewood-Richardson rules

In this section, we discuss bijections between checkers, the classical Littlewood-Richardson rule involving tableaux, and puzzles. We extend the checker and puzzle rules to K-theory, proving a conjecture of Buch. We conclude with open questions. We assume familiarity with the following Littlewood-Richardson rules: tableaux [F], puzzles [KTW, KT], and Buch’s set-valued tableaux [B1].

3.1. Checkers, puzzles, tableaux. We now give a bijection between tableaux and checkergames. We use the tableaux description of [F, Corollary 5.1.2]. More precisely, given three partitions α, β, γ, construct a skew partition δ from α and β, with α in the upper right and β in the lower left. Then c_{αβ}^{γ} is the number of Littlewood-Richardson skew tableaux [F, p. 63] on δ with content γ. In any such tableau on δ, the i^{th} row of α must consist only of i’s. Thus γ can be recovered from the induced tableaux on β: γ_{i} is α_{i} plus the number of i’s in the tableaux on β.

The bijection to such tableaux (on β) is as follows. Whenever there is a move described by a † in Figure 8 (see also Table 2), where the “rising” white checker is the r^{th} white checker (counting by row) and the c^{th} (counting by column), place an r in row c of the tableau.

The geometric interpretation of the bijection is simple. In each step of the degeneration, some intersection M_{r} ∩ F_{c} jumps in dimension. If in this step the k-plane V changes its intersection with M_{·} (or equivalently, V ∩ M_{r} jumps in dimension), then we place the final value of dim V ∩ M_{r} in row dim V ∩ F_{c} of the tableau (in the rightmost square still empty). In other words, given a sequence of degenerations, we can read off the tableau, and each tableau gives instructions as to how to degenerate.

For example, in Figure 3, the left-most output corresponds to the tableau 2 , and the right-most output corresponds to the tableau 1 . The moves where the tableaux are filled are marked with †. (In the left case, at the crucial move, the rising white checker is the second white checker counting by row and the first white checker counting by column, so a “2” is placed in the first row of the diagram.)

3.2. Theorem (bijection from checkergames to tableaux). — The construction above gives a bijection from checkergames to tableaux.

Proof. A bijection between checkergames and puzzles is given in Appendix A. Combining this with Tao’s “proof-without-words” of a bijection between puzzles and tableaux (given in Figure 11) yields the desired bijection between checkergames and tableaux. I am grateful to Tao for telling me his bijection. □

(There is undoubtedly a simpler direct proof, given the elegance of this map, and the inelegance of the bijection from checkergames to puzzles.)

Hence checkergames give the first geometric interpretation of tableaux and puzzles; indeed there is a bijection between tableaux/puzzles and solutions of the corresponding three-flag Schubert problem, once branch paths are chosen [V2, Section 2.10], [SVV].

u  ^{s}  ^{p}  ^{h}^{m}^{q}^{t}  ^{r}  ^{n}^{o}^{a}  ^{b}  ^{c}  ^{d}  ^{e}  ^{f}  ^{g}  ^{h}^{l}^{k}^{j}^{i}^{1}^{2}^{3}^{4}  ^{u}  ^{t}  ^{r}^{s}  ^{q}  ^{n}^{p}^{h}  ^{g}  ^{f}  ^{e}^{1}  ^{2}  ^{3}  ^{4}^{2}  ^{3}  ^{4}^{3}  ^{4}^{4}  ^{o}^{m}^{2}^{3}^{4}  ^{j}^{a}^{b}^{c}^{d}  ^{k}^{l}  ^{i}^{1} α  β γ

Figure 11. Tao’s “proof without words” of the bijection between puzzles and tableaux (1-triangles are depicted as black, regions of 0-rectangles are grey, and regions of rhombi are white)

Note that to each puzzle, there are three possible checkergames, depending on the orientation of the puzzle. These correspond to three degenerations of three general flags. A. Knutson points out that it would be interesting to relate these three degenerations.

3.3. K-theory: checkers, puzzles, tableaux. Buch [B2] has conjectured that checkergame analysis can be extended to K-theory or the Grothendieck ring (see [B1] for background on the K-theory of the Grassmannian). Precisely, the rules for checker moves are identical, except there is a new term in the middle square of Table 2 (the case where there is a choice of moves), of one lower dimension, with a minus sign. As with the swap case, this term is included only if there is no blocker. If the two white checkers in question are at (r_{1}, c_{1}) and (r_{2}, c_{2}), with r_{1} > r_{2} and c_{1} < c_{2}, then they move to (r_{2}, c_{1}) and (r_{1} − 1, c_{2}) (see Figure 12). Call this a sub-swap, and denote the resulting configuration ∘_{sub}•_{next}. By Lemma 2.6, dim \overline{Y}_{∘_{sub}•_{next}} = dim \overline{Y}_{∘•} − 1.

3.4. Theorem (K-theory Geometric Littlewood-Richardson rule). — Buch’s sub-swap rule describes multiplication in the Grothendieck ring of G(k, n).

Sketch of Proof. We give a bijection from K-theory checkergames to Buch’s “set-valued tableaux” (certain tableaux whose entries are sets of integers, [B1]), generalizing the bijection of Theorem 3.2. To each checker is attached a set of integers, called its “memory”. At the start of the algorithm, every checker’s memory is empty. Each time there is a subswap, where a checker rises from being the r^{th} white checker to being the (r−1)^{st} (counting

(−1)×

Figure 12. Buch’s “sub-swap” case for the K-theory Geometric Littlewood-Richardson rule (cf. Figure 8)

by row), that checker adds to its memory the number r. (Informally, the checker remembers that it had once been the r^{th} checker counting by row.) Whenever there is a move described by a † in Figure 8, where the white checker is the r^{th} counting by row and the c^{th} counting by column, in row c of the tableau place the set consisting of r and the contents of its memory (all remembered earlier rows). (Place the set in the rightmost square still empty.) Then erase the memory of that white checker. The reader may verify that in Figure 3, the result is an additional set-valued tableau, with a single cell containing the set {1, 2}.

The proof that this is a bijection is omitted. □

This result suggests that Buch’s rule reflects a geometrically stronger fact, extending the Geometric Littlewood-Richardson rule (Theorem 2.13).

3.5. Conjecture (K-theory Geometric Littlewood-Richardson rule, geometric form, with A. Buch). —

(a) In the Grothendieck ring, [X_{∘•}] = [\overline{X}_{∘_{stay}•_{next}}], [\overline{X}_{∘_{swap}•_{next}}], or [\overline{X}_{∘_{stay}•_{next}}] + [\overline{X}_{∘_{swap}•_{next}}] − [\overline{X}_{∘_{sub}•_{next}}].

(b) Scheme-theoretically, D = \overline{X}_{∘_{stay}•_{next}}, \overline{X}_{∘_{swap}•_{next}}, or \overline{X}_{∘_{stay}•_{next}} ∪ \overline{X}_{∘_{swap}•_{next}}. In the latter case, the scheme-theoretic intersection \overline{X}_{∘_{stay}•_{next}} ∩ \overline{X}_{∘_{swap}•_{next}} is a translate of \overline{X}_{∘_{sub}•_{next}}.

Part (a) clearly follows from part (b).

Knutson has speculated that the total space of each degeneration is Cohen-Macaulay; this would imply the conjecture.

The K-theory Geometric Littlewood-Richardson rule 3.4 can be extended to puzzles.

3.6. Theorem (K-theory Puzzle Littlewood-Richardson rule). — The K-theory Littlewood-Richardson coefficient corresponding to subsets α, β, γ is the number of puzzles with sides given by α, β, γ completed with the pieces shown in Figure 13. There is a factor of −1 for each K-theory piece in the puzzle.

0 0 0  1 1 1  1 0 1 0  1 0 1 0 0  1 K

Figure 13. The K-theory puzzle pieces

The first three pieces of Figure 13 are the usual puzzle pieces of [KTW, KT]; they may be rotated. The fourth K-theory piece is new; it may not be rotated. Tao had earlier, independently, discovered this piece.

Theorem 3.6 may be proved via the K-theory Geometric Littlewood-Richardson rule 3.4 (and extending Appendix A), or by generalizing Tao’s proof of Figure 11. Both proofs are omitted.

As an immediate consequence, using the cyclic symmetry of K-theory puzzles:

3.7. Corollary (triality of K-theory Littlewood-Richardson coefficients). — If K-theory Littlewood-Richardson coefficients are denoted C_{··}^{·}, C_{αβ}^{γ^{∨}} = C_{βγ}^{α^{∨}} = C_{γα}^{β^{∨}}.

This is immediate in cohomology, but not obvious in the Grothendieck ring. The following direct proof is due to Buch (cf. [B1, p. 30]).

Proof. Let ρ : G(k, n) → pt be the map to a point. Define a pairing on K_{0}(X) by (a, b) := ρ_{∗}(a · b). This pairing is perfect, but (unlike for cohomology) the Schubert structure sheaf basis is not dual to itself. However, if t denotes the top exterior power of the tautological subbundle on G(k, n), then the dual basis to the structure sheaf basis is {tO_{Y} : Y is a Schubert variety}. More precisely, the structure sheaf for a partition λ = (λ_{1}, …, λ_{k}) is dual to t times the structure sheaf for λ^{∨}. (For more details, see [B1, Section 8]; this property is special for Grassmannians.) Hence ρ_{∗}(tO_{α}O_{β}O_{γ}) = C_{αβ}^{γ^{∨}} = C_{βγ}^{α^{∨}} = C_{γα}^{β^{∨}}. □

3.8. Questions. One motivation for the Geometric Littlewood-Richardson rule is that it should generalize well to other important geometric situations (as it has to K-theory). We briefly describe some potential applications; some are work in progress.

(a) Knutson and the author have extended these ideas to give a Geometric Littlewood-Richardson rule in equivariant K-theory (most conveniently described by puzzles), which is not yet proved [KV2]. As a special case, equivariant Littlewood-Richardson coefficients may be understood geometrically; equivariant puzzles [KT] may be translated to checkers, and partially-completed equivariant puzzles may be given a geometric interpretation.

(b) These methods may apply to other groups where Littlewood-Richardson rules are not known. For example, for the symplectic (type C) Grassmannian, there are only rules in the Lagrangian and Pieri cases. L. Mihalcea has made progress in finding a Geometric Littlewood-Richardson rule in the Lagrangian case, and has suggested that a similar algorithm should exist in general.

(c) The specialization order (and the philosophy of this paper) leads to a precise conjecture about the existence of a Littlewood-Richardson rule for the (type A) flag variety, and indeed for the equivariant K-theory of the flag variety. This conjecture will be given and discussed in [V3]. The conjecture unfortunately does not seem to easily yield a combinatorial rule, i.e. an explicit combinatorially described set whose cardinality is the desired coefficient. However, (i) in any given case in cohomology, the conjecture may be checked in cohomology, and the combinatorial object described, using methods from [BV]; (ii) the conjecture is true in cohomology in for n ≤ 5; (iii) the conjecture is true in K-theory for Grassmannian classes by Theorem 3.4; and (iv) the conjecture should be true in equivariant K-theory for Grassmannian classes by [KV2]. Note that understanding the combinatorics underlying the geometry in the case of cohomology will give an answer to the important open question of finding a Littlewood-Richardson rule for Schubert polynomials (see for example [Mac, Man, BJS, BB] and [F, p. 172]).

(d) An intermediate stage between the Grassmannian and the full flag manifold is the two-step partial flag manifold F l(k, l, n). This case has applications to Grassmannians of other groups, and to the quantum cohomology of the Grassmannian [BKT]. Buch, Kresch, and Tamvakis have suggested that Knutson’s proposed partial flag rule (which Knutson showed fails for flags in general) holds for two-step flags, and have verified this up to n = 16 [BKT, Section 2.3]. A geometric explanation for Knutson’s rule (as yet unproved) will be given in [KV1].

(e) The quantum cohomology of the Grassmannian can be translated into classical questions about the enumerative geometry of surfaces. One may hope that degeneration methods introduced here and in [V1] will apply. This perspective is being pursued (with different motivation) by I. Coskun (for rational scrolls) [Co]. I. Ciocan-Fontanine has suggested a different approach (to the three-point invariants) using Quot schemes, following [C-F]: one degenerates two of the three points together, and then uses the Geometric Littlewood-Richardson rule.

(f) D. Eisenbud and J. Harris [EH] describe a particular (irreducible, one-parameter) path in the flag variety, whose general point is in the large open Schubert cell, and whose special point is the smallest stratum: consider the osculating flag M_{·} to a point p on a rational normal curve, as p tends to a reference point q with osculating flag F_{·}. Eisenbud has asked if the specialization order is some sort of limit (a “polygonalization”) of such a path. This would provide an irreducible path that breaks intersections of Schubert cells into Schubert varieties. (Of course, the limit cycles could not have multiplicity 1 in general.) Eisenbud and Harris’ proof of the Pieri formula is evidence that this could be true.

Sottile has a precise conjecture generalizing Eisenbud and Harris’ approach to all flag manifolds [S3, Section 5]. He has generalized this further: one replaces the rational normal curve by the curve e^{tη}X_{u}(F_{·}), where η is a principal nilpotent in the Lie algebra of the appropriate algebraic group, and the limit is then lim_{t→0} e^{tη}X_{u}(F_{·}) ∩ X_{w}, where X_{w} is given by the flag fixed by lim_{t→0} e^{tη}, [S4]. Eisenbud’s question in this context then involves polygonalizing or degenerating this path.

(g) If the specialization order is indeed a polygonalization of the path corresponding to the osculating flag, then the Geometric Littlewood-Richardson rule would imply that the Shapiro-Shapiro conjecture is “asymptotically true” (via [V2, Proposition 1.4]). Currently the conjecture is known only for G(2, n) [EG]. Could the Geometric Littlewood-Richardson rule yield a proof in some cases for general G(k, n)?

4. Bott-Samelson varieties

4.1. Definition: Quilts and their Bott-Samelson varieties. We will associate a variety to the following data (Q, dim, n); n is the integer fixed throughout the paper.

(1) Q is a finite subset of the plane, with the partial order ≺ given by domination (defined in Section 2.1). We require Q to have a maximum element and a minimum element. (We visualize the plane so that downwards corresponds to increasing the first coordinate and rightwards corresponds to increasing the second coordinate, in keeping with the labeling convention for tables.)

(2) dim : Q → {0, 1, 2, …, n} is an order-preserving map, denoted dimension.

(3) If [a, b] is a covering relation in Q (i.e. minimal interval: a ≺ b, and there is no c ∈ Q such that a ≺ c ≺ b), then we require that dim a = dim b − 1.

(4) If straight edges are drawn corresponding to the covering relations, then we require the interior of the graph to be a union of quadrilaterals, with 4 elements of Q as vertices, and 4 edges of Q as boundary. (Figure 14 shows two ways in which this condition can be violated. Note that the closure of the interior need not be the entire graph, e.g. Figure 19(b).)

We call this data a quilt, and abuse notation by denoting it by Q and leaving dim implicit. For example, the quilt of Figure 15 has 10 elements and 5 quadrilaterals.

Note that the poset Q must be a lattice, i.e. any two elements x, y have a unique minimal element dominating both (denoted sup(x, y)), and a unique maximal element dominated by both (denoted inf(x, y)). An element of Q at (i, j) is said to be on the southwest border (resp. northeast border) if there are no other elements (i′, j′) of Q such that i′ > i and j′ < j (resp. i′ < i and j′ > j); see Figure 15. Thus every element on the boundary is on the southwest border or the northeast border. The maximum and minimum elements are on both.

Define the Bott-Samelson variety BS(Q) associated to a quilt Q to be the variety parameterizing a (dim s)-plane V_{s} in K^{n} for each s ∈ Q, with V_{s} ⊂ V_{t} for s ≺ t. It is a closed subvariety of ∏_{s∈Q} G(dim s, n). Elements s of Q will be written in bold-faced font, and corresponding vector spaces will be denoted V_{s}.

4.2. Lemma. — The Bott-Samelson variety BS(Q) is smooth.

Figure 14. Two planar posets (elements are grey dots). Neither is a quilt, as they both violate condition (4).

Proof. The variety parameterizing the subspaces corresponding to the southwest border of the graph is a partial flag variety (and hence smooth). The Bott-Samelson variety BS(Q) can be expressed as a tower of ℙ^{1}-bundles over the partial flag variety by inductively adding the data of V_{s} for s ∈ S corresponding to “new” (northeast) vertices of quadrilaterals. □

For example, Figure 15 illustrates that one particular Bott-Samelson variety is a tower of five ℙ^{1}-bundles over F l(4); the correspondence of the ℙ^{1}-bundles with quadrilaterals is illustrated by the numbered arrows.

3^{4}^{1}  ^{2} ^{5} configuration •  northeast border southwest border 0  quilt Q_{•}

Figure 15. The northeast and southwest borders of a quilt generated by a black checker configuration; description of a Bott-Samelson variety as a tower of five ℙ^{1}-bundles over F l(4)

4.3. Strata of Bott-Samelson varieties BS(Q)_{S}. Any set S of quadrilaterals of a quilt determines a stratum of the Bott-Samelson variety. The closed stratum corresponds to requiring the spaces corresponding to the northeast and southwest vertices of each quadrilateral in S to be the same. The open stratum corresponds to also requiring the spaces of the northeast and southwest vertices of each quadrilateral not in S to be distinct. Denote the open stratum by BS(Q)_{S}, so the dense open stratum is BS(Q)_{∅}. By the construction in the proof of Lemma 4.2, (i) the open strata give a stratification, (ii) the closed strata are smooth, and (iii) codim_{BS(Q)} BS(Q)_{S} = |S|. We depict a stratum by placing an “=” in the quadrilaterals of S, indicating the pairs of spaces that are required to be equal.

4.4. Example: quilts generated by a set of checkers. Given a checker configuration, define the associated quilt as follows. Include the squares of the table where there is a checker above (or possibly in the same square), and a checker to the left (or in the same square); include also a “zero element” 0 above and to the left of the checkers. For s ∈ Q, let dim s be the number of checkers s dominates, so dim 0 = 0, and dim s is the edge-distance from s to 0.

As a warm-up example, if • is a configuration of black checkers, let Q_{•} be the associated quilt (as in Figure 15). Then the definition of happy in Section 2.5 can be rephrased as: a white checker w is happy if w ∈ Q_{•}. The southwest border of Q_{•} corresponds to F_{·}, and the northeast border corresponds to M_{·}; BS(Q_{•}) is a tower of ℙ^{1}-bundles over F l(n) = {F_{·}}, and the fiber is a Bott-Samelson resolution of the corresponding Schubert variety. The morphism BS(Q_{•}) → \overline{X}_{•} is a resolution of singularities of the double Schubert variety, e.g. Figure 15 describes a Bott-Samelson resolution of the double Schubert variety corresponding to 1324. This morphism restricts to an isomorphism of the dense open stratum BS(Q_{•})_{∅} of BS(Q_{•}) with X_{•}.

If ∘ is a configuration of white checkers, let Q_{∘} be the associated quilt. The structure of Q_{∘} for mid-sort ∘ will be central to the proof. See Figures 18 and 19 for important examples that we will refer to repeatedly.

5. Proof of the Geometric Littlewood-Richardson rule (Theorem 2.13)

5.1. Strategy of proof. The strategy is as follows. Instead of considering the divisor D on the closure of X_{∘•} in G(k, n) × (X_{•} ∪ X_{•_{next}}), we consider the corresponding divisor D_{Q} on the closure of X_{∘•} in BS(Q_{∘}) × (X_{•} ∪ X_{•_{next}}), see (3)below. Here the bottom two rows are diagram (1). The vertical morphisms from the top row to the middle row (denoted π) are projective. The top row is obtained from the bottom row by fibered product.

(3)  \xymatrix{Cl_{BS(Q_{∘})×X_{•}} X_{∘•} \ar[d] \ar@{^{(}->}[r]^{open} & Cl_{BS(Q_{∘})×(X_{•}∪X_{•_{next}})} X_{∘•} \ar[d]^{π} & D_{Q} \ar@{^{(}->}[l]_{Cartier} \ar[d] \\ \overline{X}_{∘•} := Cl_{G(k,n)×X_{•}} X_{∘•} \ar[d] \ar@{^{(}->}[r]^{open} & Cl_{G(k,n)×(X_{•}∪X_{•_{next}})} X_{∘•} \ar[d] & D \ar@{^{(}->}[l]_{Cartier} \ar[d] \\ X_{•} \ar@{^{(}->}[r]^{open} & X_{•} ∪ X_{•_{next}} & X_{•_{next}} \ar@{^{(}->}[l]_{Cartier}}

(i) In Section 5.2, we show that the result holds in the “trivial case” where there are no white checkers in the critical row. We assume thereafter that the critical row is non-empty.

(ii) We describe Cl_{BS(Q_{∘})×(X_{•}∪X_{•_{next}})} X_{∘•} more explicitly, giving it a modular interpretation rather than merely describing it as a closure (Theorem 5.8). (As a byproduct, we show Cl_{BS(Q_{∘})×(X_{•}∪X_{•_{next}})} X_{∘•} is Cohen-Macaulay.)

(iii) We identify the irreducible components {D_{S}} of D_{Q} (Theorem 5.10). (Steps (ii) and

(iii) are the crux of the proof.) (iv) We show that all but one or two D_{S} are contracted by π (Proposition 5.13), so their

image is not a divisor on Cl_{G(k,n)×(X_{•}∪X_{•_{next}})} X_{∘•}. We do this by exhibiting a oneparameter family through a general point of such a D_{S} contracted by π.

(v) In Proposition 5.15, we show that in the one or two remaining cases the multiplicity of D_{Q} along D_{S} is 1.

(vi) Finally, these one or two D_{S} map birationally to (i.e. map with degree 1 to) X_{∘_{stay}•_{next}} or X_{∘_{swap} •_{next}} (Proposition 5.16), ensuring that the multiplicity with which X_{∘_{stay}•_{next}} or X_{∘_{swap} •_{next}} appears in D is indeed 1.

5.2. Proof of the rule in the case where there is no white checker in the critical row. As pointed out in Section 2.11, this case is geometrically straightforward. Let X′_{∘•} be the projection of X_{∘•} to

G(k, n) × F l(1, …, r − 1, r + 1, …, n) × F l(n)

“forgetting” M_{r}. Then \overline{X}_{∘•} is the ℙ^{1}-bundle over X′_{∘•} corresponding to choosing M_{r} freely, and \overline{X}_{∘_{stay}•_{next}} is the section given by the Cartier divisor D_{Q} = \{M_{r} : M_{r} ∩ F_{c} ⊂ F_{c−1}\} (see Section 2.4). Hence D_{Q} = \overline{X}_{∘_{stay}•_{next}}, so we have completed the proof in the case where there is no white checker in the critical row.

5.3. For the rest of Section 5, we assume that there is a white checker in the critical row. We will need two preparatory lemmas.

Suppose we are given 1 ≤ a_{1} < a_{2} < ⋯ < a_{k} ≤ n (with the convention a_{0} = 0, a_{k+1} = ∞), and integers j and R such that a_{j} ≤ R < a_{j+1}. Consider the closed subvariety

(4)  T′ ⊂ F l(1, …, k, n) × F l(n) = {((V_{i})_{i≤k}, M_{·})}

defined by V_{i} ⊂ M_{a_{i}}. Then we may construct T′ as a tower of projective bundles over F l(1, …, k, n) by inductively choosing M_{n−1}, …, M_{1} with M_{j} a hyperplane in M_{j+1} containing V_{max_{a_{i}≤j} i}. Let B be a variety, B → F l(1, …, k, n) a morphism, and T′′ the pullback of T′ to B (i.e. T′′ := B ×_{F l(1,...,k,n)} T′).

5.4. Lemma. — For any δ, if Q is an irreducible subvariety of T′′ where dim V_{δ} ∩ M_{R} = j + ℓ_{2}, then codim_{T′′} Q ≥ ℓ_{2}. Equality holds only if

(i) ℓ_{2} = 0, or (ii) ℓ_{2} = 1, a_{j} < R, a_{j+1} = R + 1, and V_{j+1} ⊂ M_{R} for all points of Q.

Proof. It suffices to prove the result for δ = k, and B →^{∼} F l(1, …, k, n) (i.e. T′′ = T). We follow the spirit of the construction of double Schubert cells (Section 2.2). We stratify F l(1, …, k, n) × F l(n) by the numerical data dim V_{i_{2}} ∩ M_{i_{1}} (1 ≤ i_{2} ≤ k). The strata correspond to checkerboards with k columns and n rows, with k checkers, no two in the same row or column, such that dim V_{i_{2}} ∩ M_{i_{1}} is the number of checkers dominated by (i_{1}, i_{2}). See Figure 16 for an example. By building the stratum as an open subset of a tower of projective bundles over F l(n), we observe that the dimension of this stratum is

dim F l(n) + ∑_{checker c at (i_{1}, i_{2})} (i_{1} − #{checkers dominated by c }) .

Then T′ corresponds to configurations where there are at least i checkers in the first a_{i} rows, and the dense open stratum of T′ corresponds to the configuration {(a_{i}, i) : 1 ≤ i ≤ k}, so in particular there are j checkers in the first R rows. A dense open set of Q lies in some stratum where there are at least j +ℓ_{2} checkers in the first R rows. We are reduced to the following combinatorial question (left to the reader): suppose k checkers are placed so that there are i checkers in the first a_{i} rows (1 ≤ i ≤ k) and there are j + ℓ_{2} checkers in the first R rows. Then the sum of the rows in which the checkers appear is at most ∑ a_{i} − ℓ_{2}, and inequality is strict unless (i) or (ii) holds. (Informally, at least ℓ_{2} checkers must be in a higher — i.e. lower-numbered — row than they would be for the general point of T′, and if neither (i) nor (ii) hold, one checker must be at least 2 rows higher. See Figure 16 for an example of case (ii).) □

a_{1} = 1

a_{2} = a_{j} = 3
R = 4
a_{3} = a_{j+1} = 5
j = 2

Figure 16. n × k checker configuration in proof of Lemma 5.4 (n = 5, k = 3)

Suppose we are given a vector space Z ⊂ K^{n} and an element (V_{m})_{m∈Q_{∘}} of BS(Q_{∘}), and each element m of Q_{∘} is labeled with label(m) := dim V_{m} ∩ Z. If (V_{m}) ∈ BS(Q_{∘})_{S} then mark the quadrilaterals of S with “=”. To each quadrilateral of Q_{∘} we attach a content of

label(m_{ne}) + label(m_{sw}) − label(m_{nw}) − label(m_{se})

where m_{ne}, m_{sw}, m_{nw}, m_{se} are the northeast, southwest, northwest, southeast vertices of the quadrilateral respectively. The total content of a region of quadrilaterals is a linear combination of the labels of all vertices which appear. By inspection of all possible labeled quadrilaterals (Figure 17), every quadrilateral with positive content is marked with “=”.

5.5. Lemma. — Suppose we are given a locally closed subvariety

U ⊂ F l(1, …, k, n) × G(R, n) = {((V_{j}), M_{R})}

m + 1 m  m m + 1  m + 1 mm  m + 1 mm  m m mm  m m  m  m + 1 m + 1  m + 2  m  m + 1 m + 1  m + 1 m  m m  m + 1 m m + 1 mm  m  m + 1 m + 2 m + 1  content 1 content 0 content −1  ∗

Figure 17. Possible labeled quadrilaterals, where c is labeled with dim V_{c}∩ Z for some fixed vector space Z. Quadrilateral ∗ arises in Lemma 5.5.

where the rank data (V_{j} ∩M_{R})_{1≤j≤k} is constant, and (V_{j})_{1≤j≤k} corresponds to the northeast border of some given Q_{∘}. Define P via the pullback diagram

\xymatrix{P \ar[d] \ar@{^{(}->}[r] & BS(Q_{∘})_{S} × G(R, n) \ar[d] \\ U \ar@{^{(}->}[r] & F l(1, …, k, n) × G(R, n)}

where BS(Q_{∘})_{S} is a given open stratum of BS(Q_{∘}) (and elements of S are marked with “=”). Let ((V_{m})_{m∈Q_{∘}}, M_{R}) be a general point of P. Label m with dim V_{m} ∩ M_{R}.

(a) Then no quadrilaterals of type ∗ in Figure 17 appear.

(b) Assume furthermore that no negative-content quadrilaterals appear, and all quadrilaterals marked “=” have positive content.

(i) If the northern two vertices of a quadrilateral are labeled m, then the southern two vertices are also labeled m, and the quadrilateral is not marked “=”.

(ii) If the western two vertices of a quadrilateral are labeled m, then the eastern two edges are labeled the same (both m or m + 1), and the quadrilateral is not marked “=”.

Proof. (a) By the proof of Lemma 4.2 (with the role of southwest border now played by the northeast border), P → U is a tower of ℙ^{1}-bundles corresponding to the quadrilaterals of BS(Q_{∘}) not in S. Suppose for a general point of P we had a quadrilateral of type ∗, with vertices m_{nw}, m_{ne}, m_{sw}, m_{se}. Consider the ℙ^{1}-bundle associated to this quadrilateral, corresponding to letting V_{m_{sw}} be any subspace (of dimension dim m_{sw}) containing V_{m_{nw}} and contained in V_{m_{se}}; as dim V_{m_{ne}} ∩ M_{R} = m, for general V_{m_{sw}} in the pencil dim V_{m_{sw}} ∩ M_{R} ≤ m as well, so the label on m_{sw} for a general point of the stratum cannot be m + 1, yielding a contradiction.

(b) follows from (a) by inspection of Figure 17. □

5.6. Modular description of Cl_{BS(Q_{∘})×(X_{•}∪X_{•_{next}})} X_{∘•}. We describe a closed subscheme of BS(Q_{∘})×(X_{•}∪X_{•_{next}}) and show it is Cl_{BS(Q_{∘})×(X_{•}∪X_{•_{next}})} X_{∘•} (Theorem 5.8). The subscheme will be constructed as an intersection of two subvarieties of an open subset of a tower of projective bundles over BS(Q_{∘}). We are working harder than necessary to prove the Geometric Littlewood-Richardson rule; it would suffice to show that Cl_{BS(Q_{∘})×(X_{•}∪X_{•_{next}})} X_{∘•} is contained in this intersection (see the preprint version of this paper). However, we expect that the Cohen-Macaulayness of this variety (shown en route) will be important in understanding the K-theory of the Grassmannian (see Knutson’s remark after Conjecture 3.5, and [KV2]). In any case, ideas from the proof of Theorem 5.8 will be used later in Theorem 5.10.

Let m(M_{i}) (1 ≤ i ≤ n) be the maximum element m of Q_{∘} such that m ≺ (i, n), i.e. the maximum element of Q_{∘} in the rows up to i. Thus V_{m(M_{i})} is the largest vector space of BS(Q_{∘}) required to be contained in M_{i}. Define m(F_{j}) similarly, to be the maximum element m ∈ Q_{∘} with m ≺ (n, j), so V_{m(F_{j})} is the largest vector space of BS(Q_{∘}) required to be contained in F_{j}.

We name important elements of Q_{∘} (see Figures 18 and 19).

• Let a = m(F_{c−1}), the lowest (or equivalently, rightmost) white checker appearing in the first c − 1 columns (or 0 if there are none).

• Let a′ = m(M_{r}) and a′′ = m(M_{r−1}).

• Let d be the white checker in the critical row (if there is one).

Then the reader should quickly check that: (i) inf(a, a′′) is the maximal element in columns up to c−1 and rows up to r−1. (ii) inf(a, a′′) = inf(a, a′). (iii) The critical diagonal contains no white checkers if and only if a is in row less than r, i.e. a = inf(a, a′′) (Figure 19(a)). (iv) There are no white checkers directly north of the critical row (at (i, j) with i < r and j > c) if and only if a′′ is in column less than c, i.e. a′′ = inf(a, a′′) (Figure 19(b)).

critical row  a′ a′′ inf(a, a′′)  d a 0  sup(a, a′)

Figure 18. An example of Q_{∘} for mid-sort ∘. The internal diagonal edges of the region inf(a, a′′)a′′ sup(a, a′)a are thickened.

a′ = d^{a′′ = inf(a, a′′)}^{a}^{critical row}  ^{0} (b) no white checkers directly above the critical row^{a′ = sup(a, a′)} (a) no white checkers in critical diagonal^{critical row}  ^{a′}^{d}^{0}^{a = inf(a, a′′)}  ^{a′′}^{critical diagonal}

Figure 19. Two more examples of Q_{∘} for mid-sort ∘

5.7. Construct an open subvariety T of a tower of projective bundles over BS(Q_{∘})

T ⊂ BS(Q_{∘}) × F l(n) × F l(c, …, n) = {V_{m} : m ∈ Q_{∘}} × {M_{·}} × {F_{≥c}}

as follows.

Step A. First, for i = n − 1, n − 2, …, 1, inductively choose M_{i} in M_{i+1} containing V_{m(M_{i})}.

Step B. Then, for j = n−1, …, c, inductively choose F_{j} in F_{j+1} containing V_{m(F_{j})}, satisfying the open condition that F_{j} is transverse to the flag M_{·}.

Over T we have inclusions of vector bundles V_{inf(a,a′′)} ⊂ V_{a} ⊂ V_{m(F_{c})} ⊂ F_{c}. Consider the projective bundle over T

ℙ(F_{c}/V_{inf(a,a′′)})^{∗} = {(t ∈ T, F_{c−1})}

parameterizing hyperplanes F_{c−1} in F_{c} containing V_{inf(a,a′′)}. Define two smooth subvarieties of ℙ(F_{c}/V_{inf(a,a′′)})^{∗}:

W_{a} := {(t ∈ T, F_{c−1}) : V_{a} ⊂ F_{c−1}}

W_{••_{next}} := {(t ∈ T, F_{c−1}) : M_{r−1} ∩ F_{c} ⊂ F_{c−1}, M_{r+1} ∩ F_{c} ⊈ F_{c−1}}.

Then W_{a} is a closed subvariety and W_{••_{next}} is a locally closed subvariety. There is a natural closed immersion W_{••_{next}} ↪ BS(Q_{∘}) × (X_{•} ∪ X_{•_{next}}), cf. Section 2.4.

The codimension in ℙ(F_{c}/V_{inf(a,a′′)})^{∗} of every irreducible component of W_{••_{next}} ∩ W_{a} is bounded above by the “expected codimension”

expcod(W_{••_{next}} ∩ W_{a}) := codim_{ℙ(F_{c}/V_{inf(a,a′′)})^{∗}} W_{••_{next}} + codim_{ℙ(F_{c}/V_{inf(a,a′′)})^{∗}} W_{a}
(5)  = (dim M_{r−1} ∩ F_{c} − dim inf(a, a′′)) + (dim V_{a} − dim inf(a, a′′))

and W_{••_{next}} ∩ W_{a} is a local complete intersection if equality holds.

5.8. Theorem (modular description of Cl_{BS(Q_{∘})×(X_{•}∪X_{•_{next}})} X_{∘•}). — We have a (scheme-theoretic) equality

W_{••_{next}} ∩ W_{a} = Cl_{BS(Q_{∘})×(X_{•}∪X_{•_{next}})} X_{∘•},

and the variety is a local complete intersection and hence Cohen-Macaulay.

Note that X_{∘•} ⊂ W_{••_{next}} and X_{∘•} ⊂ W_{a}, so the inclusion Cl_{BS(Q_{∘})×(X_{•}∪X_{•_{next}})} X_{∘•} ⊂ W_{••_{next}}∩ W_{a} is clear.

If there is no white checker in the critical row, the theorem may be false, which is why that case was dealt with earlier in Section 5.2. But even in that case: (i) the proof below shows that the intersection has the expected dimension. There may be other components, however; Caution 2.20(b) gives such an example. (ii) Cl_{BS(Q_{∘})×(X_{•}∪X_{•_{next}})} X_{∘•} is still Cohen-Macaulay: by Section 5.2, Cl_{BS(Q_{∘})×(X_{•}∪X_{•_{next}})} X_{∘•} is a ℙ^{1}-bundle over Cl_{BS(Q_{∘})×X_{•_{next}}} X_{∘_{stay}•_{next}}, so it suffices to show the latter variety is Cohen-Macaulay. Hence by induction (using the Geometric Littlewood-Richardson rule) it suffices to show the result when ∘• has a white checker in the critical row (Theorem 5.8), or to show that Cl_{BS(Q_{∘})×X_{•_{final}}} X_{∘•_{final}} is Cohen-Macaulay (but this is the smooth variety T′ of (4)).

Proof. Fix an irreducible component Z of W_{••_{next}} ∩ W_{a}, necessarily of codimension at most expcod(W_{••_{next}} ∩ W_{a}). We will show that (a) there is only one possibility for Z, and codim_{ℙ(F_{c}/V_{inf(a,a′′)})^{∗}} Z = expcod(W_{••_{next}} ∩ W_{a}). (b) We then observe that Z is generically reduced, and the general point of Z lies in X_{∘•}. Hence Z is a local complete intersection, thus Cohen-Macaulay, and thus has no non-trivial associated points, so Z = Cl_{Z} X_{∘•} = Cl_{BS(Q_{∘})×(X_{•}∪X_{•_{next}})} X_{∘•}, and we are done.

(a) Z is unique, and codim_{ℙ(F_{c}/V_{inf(a,a′′)})^{∗}} Z = expcod(W_{••_{next}} ∩ W_{a}). We consider three cases, depending on whether inf(a, a′′) = a, or inf(a, a′′) ≠ a, a′′, or inf(a, a′′) = a′′. (These cases correspond to Figures 19(a), 18, and 19(b) respectively. The first and third cases may hold simultaneously.) The first case inf(a, a′′) = a is straightforward: W_{a} is codimension 0, so Z = W_{••_{next}}.

We next deal with the second case. (The reader may wish to refer repeatedly to Figure 18.) We will construct a dense open subscheme of Z following Steps A and B (Section 5.7). Let Z_{BS(Q_{∘})} (resp. Z_{Step A}, Z_{Step B}) be the image of Z in BS(Q_{∘}) (resp. BS(Q_{∘}) × {M_{·}}, T ⊂ BS(Q_{∘}) × {M_{·}} × {F_{≥c}}).

Let ℓ_{1} = codim_{BS(Q_{∘})} Z_{BS(Q_{∘})}. Z_{BS(Q_{∘})} is contained in some closed stratum of codimension at most ℓ_{1}, which corresponds to a set S of at most ℓ_{1} quadrilaterals of Q_{∘}. If |S| = ℓ_{1}, then Z_{BS(Q_{∘})} is this stratum BS(Q_{∘})_{S}.

We next consider M_{·} (following Step A). Let ℓ_{4} be the codimension of Z_{Step A} in the fibration

{(V_{·}, M_{·}) : (V_{·}) ∈ Z_{BS(Q_{∘})}, V_{m(M_{i})} ⊂ M_{i}} → Z_{BS(Q_{∘})}.

Suppose that for a general point in Z,

dim V_{sup(a,a′)} ∩ M_{r−1} − dim V_{a′′} = ℓ_{2}.

By Lemma 5.4 (taking R = r − 1, j = dim a′′, δ = dim sup(a, a′), B = Z_{BS(Q_{∘})}, and B → F l(1, …, k, n) the map giving the spaces of the northeast border of BS(Q_{∘})), ℓ_{4} ≥ ℓ_{2}.

Let ℓ_{5} be the codimension of Z_{Step B} in the fibration

{(V_{·}, M_{·}, F_{≥c}) : (V_{·}, M_{·}) ∈ Z_{Step A}, V_{m(F_{j})} ⊂ F_{j} for j ≥ c} → Z_{Step A}.

Then codim_{T} Z_{Step B} = ℓ_{1} + ℓ_{4} + ℓ_{5}.

For a general point {(V_{·}, M_{·}, F_{≥c})} of Z_{Step B}, the choice of F_{c−1} in F_{c} containing V_{a} and M_{r−1} ∩ F_{c} is of codimension (in ℙ(F_{c}/V_{inf(a,a′′)})^{∗})

dim ⟨\frac{V_{a}}{V_{inf(a,a′′)}} , \frac{M_{r−1} ∩ F_{c}}{V_{inf(a,a′′)}} ⟩
= dim V_{a} + dim M_{r−1} ∩ F_{c} − dim V_{a} ∩ M_{r−1} ∩ F_{c} − dim V_{inf(a,a′′)}
= dim a + dim M_{r−1} ∩ F_{c} − dim V_{a} ∩ M_{r−1} − dim inf(a, a′′)
= expcod(W_{••_{next}} ∩ W_{a}) + dim inf(a, a′′) − dim V_{a} ∩ M_{r−1}

from (5). Let ℓ_{3} = dim V_{a} ∩ M_{r−1} − dim inf(a, a′′) (non-negative as V_{inf(a,a′′)} ⊂ V_{a} ∩ M_{r−1}). Thus this step contributes a (negative) codimension of −ℓ_{3} compared to the expected codimension. Let ℓ_{6} be the codimension of Z in

{(V_{·}, M_{·}, F_{≥c−1}) : (V_{·}, M_{·}, F_{≥c}) ∈ Z_{Step B}, ⟨V_{a}, M_{r−1} ∩ F_{c}⟩ ⊂ F_{c−1}}.

Summing the boxed codimensional contributions,

(6)  codim Z − expcod(W_{••_{next}} ∩ W_{a}) = ℓ_{1} + ℓ_{4} + ℓ_{5} − ℓ_{3} + ℓ_{6} ≥ ℓ_{1} + ℓ_{2} − ℓ_{3}.

At (5)we observed that the left side is nonpositive.

We now show that the right side of (6)is nonnegative. Label vertex m of Q_{∘} with the value dim V_{m}∩M_{r−1} for a general point of Z. For example, V_{inf(a,a′′)} is labeled dim inf(a, a′′), and V_{a′′} is labeled dim a′′. We consider the region inf(a, a′′)a′′ sup(a, a′)a of vertices dominating inf(a, a′′) and dominated by sup(a, a′). The total content of the quadrilaterals in this region is a linear combination of the labels of the vertices. The net contribution of a vertex m ∈ Q_{∘} is the number of quadrilaterals in region inf(a, a′′)a′′ sup(a, a′)a of which it is the northeast or southwest corner, minus the number of which it is the northwest or southeast corner (all multiplied by the label dim V_{m} ∩ M_{r−1} of m). Hence the only vertices with a non-zero net contribution are the following. (The reader may wish to consult Figure 18.)

• Each diagonal edge (i.e. non-horizontal and non-vertical edge, see Figure 18) internal to region inf(a, a′′)a′′ sup(a, a′)a contributes the label of its larger vertex minus the label of its smaller vertex, a non-negative contribution.

• In addition, a and a′′ contribute their labels, and inf(a, a′′) and sup(a, a′) contribute the negative of their labels.

Thus the total content of region inf(a, a′′)a′′ sup(a, a′)a is

(internal diag. contribution ) + dim V_{a} ∩ M_{r−1} + dim V_{a′′} ∩ M_{r−1}
− dim V_{inf(a,a′′)} ∩ M_{r−1} − dim V_{sup(a,a′′)} ∩ M_{r−1}
(7)  ≥ (dim V_{a′′} − dim V_{sup(a,a′)} ∩ M_{r−1}) + (dim V_{a} ∩ M_{r−1} − dim V_{inf(a,a′′)})
= −ℓ_{2} + ℓ_{3}.

However, the content is bounded above by ℓ_{1} with equality only if no negative-content quadrilaterals appear: from Figure 17 each content 1 quadrilateral gives an element of our set S of quadrilaterals, and |S| ≤ ℓ_{1}. Thus ℓ_{1} +ℓ_{2} −ℓ_{3} ≥ 0, so we must have ℓ_{1} +ℓ_{2} −ℓ_{3} = 0, and equality must hold in all inequalities above. In particular, ℓ_{5} = ℓ_{6} = 0, ℓ_{4} = ℓ_{2}; from equality in Lemma 5.4, ℓ_{2} = 0 or 1 (and if ℓ_{2} = 1 then V_{a′} ⊂ M_{r−1}); Z_{BS(Q_{∘})} = BS(Q_{∘})_{S}; and no quadrilaterals with negative content appear.

By equality in (7), any internal diagonal edge must have the same labels on both vertices. Now inf(a, a′′)d is an internal diagonal edge (see Figure 18), so both vertices must be labeled the same (dim inf(a, a′′)). By Lemma 5.5(b)(ii), if the western two vertices of a quadrilateral have the same label, then the eastern two vertices have the same label (possibly different from the western vertices). Repeated application of this observation to the quadrilaterals in the region inf(a, a′′)a′′a′d (inductively from left to right) yields that the labels on a′′ and a′ are the same, so

dim V_{a′} ∩ M_{r−1} = dim V_{a′′} ∩ M_{r−1} = dim V_{a′′} < dim V_{a′},

so V_{a′} ⊈ M_{r−1}, so (from the last sentence of the previous paragraph) ℓ_{2} = 0.

By Lemma 5.5(b)(i), any quadrilateral whose northern two vertices are labeled m must have all four vertices labeled m. By repeated application of this observation to the region south of edge inf(a, a′′)d (inductively from top to bottom), all vertices in this region (and in particular, a) must be labeled dim inf(a, a′′) as well (see Figure 18). Thus ℓ_{1} = 0, and hence ℓ_{3} = 0 from ℓ_{1} + ℓ_{2} − ℓ_{3} = 0.

We have completed part (a) in the case where inf(a, a′′) ≠ a, a′′ by describing an open subscheme of Z explicitly as an open subscheme of a tower of projective bundles over BS(Q_{∘})_{∅}, and showing that it has the expected codimension.

The third case a′′ = inf(a, a′′) is similar. (The reader may wish to refer repeatedly to Figure 19(b).) The previous argument applies verbatim until (6)to yield

0 ≥ codim Z − expcod(W_{••_{next}} ∩ W_{a}) ≥ ℓ_{1} + ℓ_{2} − ℓ_{3}.

We show the right side is non-negative by again labeling vertex m of Q_{∘} with dim V_{m} ∩ M_{r−1}. As V_{a′′} is a hyperplane in V_{a′},

dim V_{a′} ∩ M_{r−1} − dim V_{a′′} ∩ M_{r−1} = 0 or 1.

Call this value ϵ.

This time we consider the region a′′a′ sup(a, a′)a. Summing the content of the region we obtain ϵ + ℓ_{3} − ℓ_{2} plus a non-negative contribution from internal diagonal edges; this is again bounded above by ℓ_{1}. Then 0 ≥ ℓ_{1} + ℓ_{2} − ℓ_{3} gives ϵ = 0, and equality holds in all previous inequalities. In particular, Lemma 5.4 (taking R = r−1 and B = BS(Q_{∘})) implies ℓ_{2} = 0 or 1, and ℓ_{2} = 1 only if ϵ = 1; but we have established ϵ = 0, so ℓ_{2} = 0. Also, a′′ and a′ have the same label dim a′′ (again as ϵ = 0), so by repeated use of Lemma 5.5(b)(i), all vertices south of edge a′′a′ have label dim a′′ as well. In particular, both a and sup(a, a′) have this label, so ℓ_{1} = ℓ_{3} = 0. We have completed part (a) in the third case where inf(a, a′′) = a′′.

(b) Rest of proof. In each of the three cases, there is one possibility for Z, and we have described the construction of an open subscheme explicitly: take the open stratum BS(Q_{∘})_{∅}, take all M_{·} so that M_{i} ⊃ V_{m(M_{i})}, then take all F_{n−1}, …, F_{c} transverse to M_{·} so that F_{j} ⊃ V_{m(F_{j})}, then take the open subset where V_{a} ∩ M_{r−1} ∩ F_{c} = V_{inf(a,a′′)}, then take all F_{c−1} containing both M_{r−1} ∩ F_{c} and V_{a} but not containing M_{r+1} ∩ F_{c}. By construction Z is generically reduced, and also by construction the general point of Z lies in X_{∘•}. □

5.9. We will identify the components of D_{Q}, in terms of strata on BS(Q_{∘}). Define the western good quadrilaterals of Q_{∘} to be those quadrilaterals with eastern two vertices dominating d, and the western two dominated by a. Let the eastern good quadrilaterals be those quadrilaterals whose vertices all dominate d, and to the east of a western good quadrilateral. Let b (resp. b′) be the bottom left (resp. right) corner of the region of good quadrilaterals. See Figure 20 for an explanatory picture, and note that the good quadrilaterals are arranged in a grid. If there is a blocker, there are no western good quadrilaterals and hence no eastern good quadrilaterals (see Figure 21). In this case let b = inf(a, a′) and b′ = a′, so in all cases the region of good quadrilaterals is inf(a, a′)a′b′b (possibly empty).

= eastern good quadrilaterals = western good quadrilaterals a′′ a′ b′ =  = = sup(a, a′) inf(a, a′)  b b′′  a 0  d

Figure 20. Good quadrilaterals. Three are marked with “=” so that none is weakly southeast of another (Theorem 5.10). Both b′′ and the set E of thickened edges arise in the proof of Theorem 5.10.

Following Section 2.4, define

W_{•_{next}} := {F_{c−1} : M_{r} ∩ F_{c} ⊂ F_{c−1}, M_{r+1} ∩ F_{c} ⊈ F_{c−1}} ⊂ ℙ(F_{c}/V_{inf(a,a′′)})^{∗},

a divisor on the smooth variety W_{••_{next}}. The divisor D_{Q} is the pullback of X_{•_{next}} ⊂ X_{•}∪X_{•_{next}}, from which D_{Q} = W_{•_{next}} ∩ W_{a} ⊂ W_{••_{next}} ∩ W_{a} (cf. Section 2.4).

b′ = a′ a′′ 0  a b = inf(a, a′)  d

Figure 21. If there is a blocker, there are no good quadrilaterals

Suppose S is a set of good quadrilaterals, with none weakly southeast (i.e. south or east or southeast) of another. Such a set is shown (marked with “=”) in Figure 20. Define a subvariety D_{S} of W_{•_{next}} ∩ W_{a} as follows. Over the stratum BS(Q_{∘})_{S}, choose M_{·} and F_{≥c} following Steps A and B. Over the open set of the resulting variety where V_{a} ∩ M_{r} is constant, let F_{c−1} be the set of hyperplanes of F_{c} containing both V_{a} and M_{r} ∩ F_{c}. Let D_{S} be the closure (in W_{•_{next}} ∩ W_{a}) of this locus.

5.10. Theorem. — The irreducible components of D_{Q} are a subset of the D_{S} described above.

Proof. We parallel the proof of Theorem 5.8; the roles of r − 1 and a′′ are here played by r and a′. The case inf(a, a′) = a is again immediate: W_{•_{next}} ∩ W_{a} = W_{•_{next}} = D_{∅}. (In this case there are no good quadrilaterals.) We assume inf(a, a′) ≠ a for the rest of the proof.

Let Z be an irreducible component of D_{Q}, so

codim_{ℙ(F_{c}/V_{inf(a,a′′)})^{∗}} Z = codim_{ℙ(F_{c}/V_{inf(a,a′′)})^{∗}} W_{••_{next}} ∩ W_{a} + 1.

Let Z_{BS(Q_{∘})} (resp. Z_{Step A}, Z_{Step B}) be the image of Z in BS(Q_{∘}) (resp. BS(Q_{∘}) × {M_{·}}, T ⊂ BS(Q_{∘}) × {M_{·}} × {F_{≥c}}).

Let ℓ_{1} = codim_{BS(Q_{∘})} Z_{BS(Q_{∘})}, and S the set of (at most ℓ_{1}) quadrilaterals corresponding to the smallest stratum of BS(Q_{∘}) in which Z_{BS(Q_{∘})} is contained. Let ℓ_{4} be the codimension of Z_{Step A} in {(V_{·}, M_{·}) : (V_{·}) ∈ Z_{BS(Q_{∘})}, V_{m(M_{i})} ⊂ M_{i}}, and suppose that for a general point in Z,

dim V_{sup(a,a′)} ∩ M_{r} − dim V_{a′} = ℓ_{2}.

By Lemma 5.4 (taking R = r, j = dim a′, and B = Z_{BS(Q_{∘})}), ℓ_{4} ≥ ℓ_{2}. If equality holds then ℓ_{2} = 0 (as Lemma 5.4(ii) cannot occur: α_{j} = R, as we have a white checker in the critical row r = R). Let ℓ_{5} be the codimension of Z_{Step B} in {(V_{·}, M_{·}, F_{≥c}) : (V_{·}, M_{·}) ∈ Z_{Step A}, V_{m(F_{j})} ⊂ F_{j} for j ≥ c}, so as before codim_{T} Z_{Step B} = ℓ_{1} + ℓ_{4} + ℓ_{5}. For a general point of Z_{Step B} = {(V_{·}, M_{·}, F_{≥c})}, the choice of F_{c−1} in F_{c} containing V_{a} and M_{r} ∩ F_{c} is of codimension (in ℙ(F_{c}/V_{inf(a,a′′)})^{∗})

dim ⟨\frac{V_{a}}{V_{inf(a,a′′)}} , \frac{M_{r} ∩ F_{c}}{V_{inf(a,a′′)}} ⟩
= dim V_{a} + dim M_{r} ∩ F_{c} − dim V_{a} ∩ M_{r} ∩ F_{c} − dim V_{inf(a,a′′)}
= dim a + (r + c − n) − dim V_{a} ∩ M_{r} − dim inf(a, a′′)
= codim_{ℙ(F_{c}/V_{inf(a,a′′)})^{∗}}(W_{••_{next}} ∩ W_{a}) + 1 + dim inf(a, a′′) − dim V_{a} ∩ M_{r}.

Let ℓ_{3} = dim V_{a} ∩ M_{r} − dim inf(a, a′′) ≥ 0 so this step contributes a codimension of 1 − ℓ_{3} compared to codim(W_{••_{next}} ∩ W_{a}). Let ℓ_{6} be the codimension of Z in

{(V_{·}, M_{·}, F_{≥c−1}) : (V_{·}, M_{·}, F_{≥c}) ∈ Z_{Step B}, ⟨V_{a}, M_{r−1} ∩ F_{c}⟩ ⊂ F_{c−1}}.

Summing the boxed contributions,

1 = codim Z − codim(W_{••_{next}} ∩ W_{a}) = 1 + ℓ_{1} + ℓ_{4} + ℓ_{5} − ℓ_{3} + ℓ_{6} ≥ 1 + ℓ_{1} + ℓ_{2} − ℓ_{3}.

We again show that ℓ_{1} + ℓ_{2} − ℓ_{3} is nonnegative. Label vertex m of Q_{∘} with dim V_{m} ∩ M_{r}. We compute the content of the region inf(a, a′)a′ sup(a, a′)a. As before, each internal diagonal edge contributes the label of its larger vertex minus the label of its smaller vertex, a non-negative contribution. Also, a and a′ contribute their labels, and inf(a, a′) and sup(a, a′) contribute the negative of their labels. Thus the total content of region inf(a, a′)a′′ sup(a, a′)a is

(internal diag. contribution ) + dim V_{a} ∩ M_{r} + dim V_{a′} ∩ M_{r}
− dim V_{inf(a,a′)} ∩ M_{r} − dim V_{sup(a,a′)} ∩ M_{r}
(8)  ≥ (dim V_{a′} − dim V_{sup(a,a′)} ∩ M_{r}) + (dim V_{a} ∩ M_{r} − dim V_{inf(a,a′)})
= −ℓ_{2} + ℓ_{3}.

But the content is again bounded above by ℓ_{1} (using Figure 17), so ℓ_{1} + ℓ_{2} − ℓ_{3} ≥ 0, hence ℓ_{1} + ℓ_{2} − ℓ_{3} = 0, and equality must hold in all inequalities above. In particular, ℓ_{5} = ℓ_{6} = ℓ_{2} = ℓ_{4} = 0; ℓ_{1} = ℓ_{3} (not necessarily zero!); Z_{BS(Q_{∘})} is the stratum corresponding to S; and all quadrilaterals have content 0 except for ℓ_{1} quadrilaterals with content 1 in region inf(a, a′)a′ sup(a, a′)a.

If b = a, then region inf(a, a′)a′′ sup(a, a′)a is precisely the region of good quadrilaterals; proceed to 5.11. Otherwise, let b′′ ∈ Q_{∘} be be the other end of the northernmost diagonal edge emanating southeast from b (see Figure 20). By equality in (8), b and b′′ have the same label. By repeated application of Lemma 5.5(b)(i) to the region below edge bb′′, all vertices below b and b′′ have the same label too. In particular, the labels of b and a are the same. Let E be set of edges due south of b′′, union the edge bb′′, shown in Figure 20. The region directly to the east of E consists of a grid of quadrilaterals, as it contains no white checkers (see Figure 20). By repeated application of Lemma 5.5(b)(ii) to this region, any two vertices east of E in the same column have the same label. Hence the labels of b′ and sup(a, a′) are the same. Thus the content of the region of good quadrilaterals inf(a, a′)a′b′b is the same as the content of the region inf(a, a′)a′ sup(a, a′)a considered earlier, which is ℓ_{1}. Thus the ℓ_{1} positive-content quadrilaterals S are a subset of the good quadrilaterals.

5.11. We conclude by showing that no element of S is weakly southeast of another. Fix a positive-content quadrilateral. Then its northeast, southeast, and southwest vertices have the same label. Thus by repeated application of Lemma 5.5(b)(i), all vertices south of its southern edge are labeled the same, and there are no positive-content quadrilaterals (elements of S) south of this edge. Let E′ be the union of edges due south of the northeast vertex of our positive-content quadrilateral. Repeated applications of Lemma 5.5(b)(ii) imply that any two vertices east of E′ in the same column have the same label, and there are no positive content quadrilaterals here either. □

A little more work shows that all such D_{S} are components of D_{Q}: given any set S of good quadrilaterals, none weakly southeast of another, show that ℓ_{1} = ℓ_{3} by explicitly describing the labels dim V_{m} ∩ M_{r} for all m ∈ BS(Q_{∘}). As Cl_{BS(Q_{∘})×(X_{•}∪X_{•_{next}})} X_{∘•} is Cohen-Macaulay and D_{Q} is an effective Cartier divisor, D_{Q} has no non-maximal associated points, so D_{Q} is the scheme-theoretic union of the D_{S}. We will not need these facts, so we omit the details.

5.12. Contraction of all but one or two divisors by π. The divisors D_{∅} and D_{{northwest good quad. }} correspond to the stay and swap options respectively of the Geometric Littlewood-Richardson rule. We next show that all but possibly D_{∅} and D_{{northwest good quad. }} are contracted by π. Part (a) of the following proposition shows that all other D_{S} are contracted by π, and (b) shows that D_{∅} is contracted by π when predicted (the three entries of Table 2 where there is no “stay” option).

5.13. Proposition. —

(a) If S ≠ ∅, {northwest good quad. }, then D_{S} is contracted by π.

(b) If S = ∅ and

(i) the white checker in the critical diagonal is in the rising black checker’s square (recall we are assuming there is a white checker in the critical row), or

(ii) the white checker in the critical row is in the descending checker’s square, and there is

a checker in the critical diagonal, then D_{S} is contracted by π.

Proof. (a) The construction of an open subset of D_{S} involves starting with BS(Q_{∘})_{S} and constructing M_{·} and F_{·} using the spaces corresponding to the northeast border of BS(Q_{∘}), and those elements of the southwest border dominating a. Given a general point ((V_{m})_{m∈Q_{∘}}, M_{·}, F_{·}) of D_{S}, we will produce a one-parameter family (V′_{m})_{m∈Q_{∘}} through (V_{m})_{m∈Q_{∘}} in the stratum BS(Q_{∘})_{S}, fixing those V_{m} on the border. The corresponding family {((V′_{m})_{m∈Q_{∘}}, M_{·}, F_{·})} is contained in D_{S}, as the inclusions V_{m(M_{i})} ⊂ M_{i} and V_{m(F_{j})} ⊂ F_{j} are preserved. Also, the k-plane V_{max(Q_{∘})} is fixed, so the corresponding locus in D_{S} is contracted by π, proving the result.

Choose a quadrilateral stuv in S. Name the elements of Q_{∘} as in Figure 22(a); g_{m} is the white checker in the column of s, and f_{m−1} is the next white checker to the west. Note that g_{m} has only one edge pointing northwest, and two pointing southeast. The desired family corresponds to letting V′_{m} ≡ V_{m} for m ≠ s, g_{1}, …, g_{m}, and letting V′_{s} vary in an open set of ℙ(V_{v}/V_{e}) ≅ ℙ^{1}, such that V′_{g_{i}} := V′_{s} ∩ V_{h_{i}} has dimension dim g_{i} (1 ≤ i ≤ m). Note that V_{f_{i}} is contained in V′_{g_{i}}, as V′_{g_{i}} = V′_{s} ∩ V_{h_{i}} contains V_{e} ∩ V_{h_{i}} = V_{f_{i}} by construction.

(Note how this argument fails if S = {northwest good quad. }, so stuv is the northwest good quadrilateral. Then s = inf(a, a′′) = g_{m}. If inf(a, a′′) ≠ a′′, as in Figure 18, then s = inf(a, a′′) has a third southeastern edge, pointing due east. If inf(a, a′′) = a′′, as in Figure 19(b), then s = inf(a, a′′) is on the northeast border, so V_{s} was required to be fixed.)

g_{m−1}^{⋮}^{f_{1}}^{e}  ^{v}^{g_{m}}^{g_{1}}  ^{h_{m}}^{h_{m−1}}^{h_{1}}^{f_{m−1}}  ^{t}^{u}^{varying spaces}  ^{f_{1}}  ^{⋯}  ^{f_{m} = a′′}^{g_{1}}^{h_{1}}  ^{⋯}  ^{h_{m}}^{inf(a, a′)} ^{d}^{t}  ^{s}  ^{g_{m} = a′}  ^{row < r}^{critical row r}^{varying spaces}^{s}^{f_{m}}  (a)  (b)^{⋮}

Figure 22.

(b) (i) Name the elements of Q_{∘} as in Figure 22(b); here the white checker in the rising black checker’s square is t. Given a general point ((V_{m})_{m∈Q_{∘}}, M_{·}, F_{·}) of D_{S}, we will produce a one-parameter family (V′_{m})_{m∈Q_{∘}} in BS(Q_{∘}) through (V_{m})_{m∈Q_{∘}} preserving all spaces in BS(Q_{∘}) on the northeast and southeast borders except V′_{a′}. We will verify that V′_{a′} ⊂ M_{r} for every point in the family. Then as in (a) the corresponding family (V′_{m}, M_{·}, F_{·}) is contained in D_{S} and is contracted by π, proving the desired result.

The family corresponds to letting V′_{m} = V_{m} for m ≠ d, g_{1}, …, g_{m}, and letting V′_{d} vary in an open set of ℙ(V_{s}/V_{inf(a,a′)}) ≅ ℙ^{1}, such that V′_{g_{i}} := ⟨V′_{d}, V_{f_{i}}⟩ has dimension dim g_{i} (1 ≤ i ≤ m). Note that V_{t} ⊂ M_{r+1} ∩ F_{c−1} = M_{r} ∩ F_{c−1} (as M_{r+1} ∩ F_{c} ⊃ M_{r} ∩ F_{c−1}, and they are the same dimension by the definition of •_{next}) and V′_{d} ⊂ V_{s} = ⟨V_{d}, V_{t}⟩ ⊂ M_{r}, so V′_{a′} = V_{f_{m}} + V_{d} ⊂ M_{r} as well. (Note where the hypothesis that t was on row r + 1 was used: V_{t} ⊂ M_{r+1}.)

Case (ii) is essentially identical (with roles of rows and columns exchanged) and hence omitted. □

5.14. Multiplicity 1. We have shown that at most one or two of the D_{S} are not contracted by π, and these correspond to the divisors predicted by the Geometric Littlewood-Richardson rule. We now show that such D_{S} appear with multiplicity 1 in the Cartier divisor D_{Q}.

5.15. Proposition. — (a) The multiplicity of the Cartier divisor D_{Q} along the Weil divisor D_{∅} is 1.

(b) If there are good quadrilaterals, the multiplicity of D_{Q} along D_{{northwest good quad. }} is 1.

Proof. (a) Consider the open subset T′ of T that lies in the preimage of the dense open stratum BS(Q_{∘})_{∅}, and where V_{a} ∩ M_{r} = V_{inf(a,a′′)}. By construction, W_{•_{next}} ∩ W_{a} restricted to this locus is reduced, so the Cartier divisor W_{•_{next}} ∩ W_{a} on W_{••_{next}} ∩ W_{a} has multiplicity 1 along the corresponding Weil divisor D_{∅}.

(b) We give a test family F through a general point (V_{·}, M_{·}, F_{·}) of Cl_{BS(Q_{∘})×(X_{•}∪X_{•_{next}})} X_{∘•} meeting D_{Q} along D_{{northwest good quad. }} with multiplicity 1. Label the elements of Q_{∘} as in Figure 22(b). For example, t is the highest white checker in the critical diagonal; let r′ be the row of t. The family F = {(V′_{·}, M′_{·}, F′_{·})} is given by:

• V′_{m} = V_{m} for m ≠ d, g_{1}, …, g_{m} = a′.

• Choose e_{t} ∈ V_{t} and e_{d} ∈ V_{d} so that e_{t} is a generator of V_{t}/V_{inf(a,a′)} and e_{d} is a generator of V_{d}/V_{inf(a,a′)}. Let V′_{d} = ⟨V_{inf(a,a′)}, μe_{t} + νe_{d}⟩ (where [μ; ν] varies in ℙ^{1}), so V′_{d} varies in the pencil ℙ(V_{s}/V_{inf(a,a′)}); take V′_{g_{i}} = ⟨V_{f_{i}}, V′_{d}⟩.

• M′_{i} = M_{i} except for r ≤ i < r′.

• Let M′_{r} = ⟨M_{r−1}, V′_{d}⟩ = ⟨M_{r−1}, μe_{t} + νe_{d}⟩. Let M′_{i} (r < i < r′) vary freely (subject to M_{r} ⊂ M_{r+1} ⊂ ⋯ ⊂ M_{r′}).

• F′_{i} = F_{i} for i ≥ c.

• Let F′_{c−1} vary freely in ℙ(F_{c}/⟨V_{a}, M_{r−1}∩F_{c}⟩)^{∗}, and take F′_{j} := M_{i_{j}} ∩F′_{c−1} for j < c−1 as described in Section 2.4.

Then (V_{·}, M_{·}, F_{·}) ∈ F (take μ = 0 and M′_{i} = M_{i}), so F ⊈ D_{Q}. Also, when ν = 0, V′_{d} = V′_{t}, so (V′_{·}) ∈ BS(Q_{∘})_{{northwest good quad. }}, so F meets D_{{northwest good quad. }} at ν = 0. We will see that D_{Q} contains the divisor ν = 0 with multiplicity 1, proving the result. Keep in mind that F′_{c−1} ⊃ ⟨V_{a}, M_{r−1} ∩ F_{c}⟩ for all points of F. The divisor D_{Q} on F is given (schemetheoretically) by

(9)  ⟨V_{a}, M_{r} ∩ F_{c}⟩ ⊂ F′_{c−1}  ⟺  M_{r} ∩ F_{c} ⊂ F′_{c−1} (as V_{a} ⊂ F′_{c−1}).

As ⟨M_{r−1}, F_{c}⟩ = K^{n}, we may choose a projection σ : K^{n} → F_{c} vanishing on M_{r−1}/⟨M_{r−1}, F_{c}⟩, so (Id − σ)(K^{n}) ⊂ M_{r−1}. Then from (9), D_{Q} is given by

⟨M_{r−1}, μe_{t} + νe_{d}⟩ ∩ F_{c} ⊂ F′_{c−1}  ⟺  ⟨M_{r−1}, σ(μe_{t} + νe_{d})⟩ ∩ F_{c} ⊂ F′_{c−1}

As σ(μe_{t} + νe_{d}) ∈ F_{c}, this is equivalent to

μσ(e_{t}) + νσ(e_{d}) ∈ F′_{c−1}
⟺  μe_{t} + νσ(e_{d}) ∈ F′_{c−1} (as t is in column ≤ c, so e_{t} ∈ F_{c}, so σ(e_{t}) = e_{t})
⟺  νσ(e_{d}) ∈ F′_{c−1} (as t ≺ a, so e_{t} ∈ V_{a}; and V_{a} ⊂ F′_{c−1}).

This condition is not satisfied by all elements of F (as F ⊈ D_{Q} as stated earlier), so σ(e_{d}) ∉ ⟨V_{a}, M_{r−1} ∩ F_{c}⟩. Thus the restriction of D_{Q} to F has two components, each with multiplicity 1. One component is the hyperplane section {F′_{c−1} : σ(e_{d}) ∈ F′_{c−1}} of ℙ(F_{c}/⟨V_{a}, M_{r−1} ∩ F_{c}⟩)^{∗}; we have again verified that the multiplicity of D_{Q} along D_{∅} is 1 (in the special case where there is a northwest good quadrilateral). The fiber for ν = 0 is also a component, appearing with multiplicity 1, as desired. □

We have two loose ends to tie up to conclude the proof of the Geometric Littlewood-Richardson rule:

(i) π(D_{∅}) = \overline{X}_{∘_{stay}•_{next}} and/or π(D_{\{northwest good quad. \}}) = \overline{X}_{∘_{swap} •_{next}}.

(ii) Furthermore \overline{X}_{∘_{stay}•_{next}} appears with multiplicity 1 in Cl_{G(k,n)×(X_{•}∪X_{•_{next}})} X_{∘•} if D_{∅}

appears with multiplicity 1 in Cl_{BS(Q_{∘})×(X_{•}∪X_{•_{next}})} X_{∘•}, and similarly for \overline{X}_{∘_{swap} •_{next}} and D_{{northwest good quad. }}.

Both are a consequence of the next result ((ii) using the fact that π is birational).

5.16. Proposition. — The morphism π induces birational maps from (a) D_{∅} to \overline{X}_{∘_{stay}•_{next}} and (b) D_{\{northwest good quad. \}} to \overline{X}_{∘_{swap}•_{next}}.

Proof. (a) The inverse rational map \overline{X}_{∘_{stay}•_{next}} −−→ D_{∅} is given by the morphism X_{∘_{stay}•_{next}} → BS(Q_{∘}) × X_{•_{next}}: by definition X_{∘_{stay}•_{next}} parameterizes flags M_{·} and F_{·} in •_{next}-position, as well as a k-plane V and vector spaces V ∩ M_{i} ∩ F_{j}, which correspond to elements of Q_{∘} (and dim V ∩ M_{i} ∩ F_{j} equals the dimension of the corresponding element of Q_{∘}) .

(b) The inverse rational map \overline{X}_{∘_{swap} •_{next}} −−→ D_{\{northwest good quad. \}} is similarly given by the morphism X_{∘_{swap} •_{next}} → BS(Q_{∘}) × X_{•_{next}}, by way of the locally closed immersion BS(Q_{∘_{swap}})_{∅} ≅ BS(Q_{∘})_{{northwest good quad. }} ↪ BS(Q_{∘}). □

References

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

[BJS] S. Billey, W. Jockusch, and R. Stanley, Some combinatorial properties of Schubert polynomials, J. Algebraic Combin. 2 (1993), no. 4, 345–374.

[BV] S. Billey and R. Vakil, Intersections of Schubert varieties in Gl_{n}/B and other permutation array schemes, manuscript in preparation.

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

[B2] A. S. Buch, personal communication.

[BKT] A. S. Buch, A. Kresch, and H. Tamvakis, Gromov-Witten invariants on Grassmannians, J. Amer. Math. Soc. 16 (2003), no. 4, 901–915.

[C-F] I. Ciocan-Fontanine, On quantum cohomology rings of partial flag varieties, Duke Math. J. 98 (1999),

no. 3, 485–524.

[Co] I. Coskun, Degenerations of surface scrolls and the Gromov-Witten invariants of Grassmannians, submitted for publication.

[EG] A. Eremenko and A. Gabrielov, Rational functions with real critical points and the B. and M. Shapiro conjecture in real enumerative geometry, Ann. Math. 155 (2002), no. 1, 105–129.

[EH] D. Eisenbud and J. Harris, Divisors on general curves and cuspidal rational curves, Invent. Math. 74 (1983), no. 3, 371–418.

[F] W. Fulton, Young Tableau with Applications to Representation Theory and Geometry, Cambridge U.P., New York, 1997.

[H] W. V. D. Hodge, The intersection formulae for a Grassmannian variety, J. Lon. Math. Soc. 17, 1942, 48–64.

[Kl1] S. Kleiman, The transversality of a general translate, Compositio Math. 28 (1974), 287–297.

[Kl2] S. Kleiman, Problem 15: Rigorous foundation of Schubert’s enumerative calculus, Mathematical developments arising from Hilbert problems, Proc. Sympos. Pure Math. 28 (1976), 445–482.

[KT] A. Knutson and T. Tao, Puzzles and (equivariant) cohomology of Grassmannians, Duke Math. J. 119 (2003), no. 2, 221–260.

[KTW] A. Knutson, T. Tao, and C. Woodward, The honeycomb model of GL_{n}(ℂ) tensor products. II. Puzzles determine facets of the Littlewood-Richardson cone, J. Amer. Math. Soc. 17 (2004), no. 1, 19–48.

[KV1] A. Knutson and R. Vakil, A geometric Littlewood-Richardson rule for the two-step flag manifold and the quantum cohomology of the Grassmannian, work in progress.

[KV2] A. Knutson and R. Vakil, The equivariant K-theory of the Grassmannian, work in progress.

[KL] V. Kreiman and V. Lakshmibai, Richardson varieties in the Grassmannian, preprint 2002, math.AG/0203278.

[Mac] I. G. Macdonald, Notes on Schubert Polynomials, Publ. LaCIM, Univ. du Québec à Montréal, Montréal, 1991.

[Man] L. Manivel, Symmetric Functions, Schubert Polynomials and Degeneracy Loci, J. Swallow trans., SMF/AMS Texts and Monographs 6, Amer. Math. Soc. Providence RI; Soc. Math. de France, Paris, 2001.

[P] M. Pieri, Sul problema degli spazi secanti, Rendiconti (Reale Istituto lombardo di scienze e lettere), Vol. 26 (1893), 534–546.

[R] R. W. Richardson, Intersections of double cosets in algebraic groups, Indag. Math., (N.S.), 3 (1992), 69–77.

[S1] F. Sottile, Enumerative geometry for the real Grassmannian of lines in projective space, Duke Math. J., 87 (1997), 59–85.

[S2] F. Sottile, Pieri’s formula via explicit rational equivalence, Can. J. Math., 46 (1997), 1281–1298.

[S3] F. Sottile, Some real and unreal enumerative geometry for Flag manifolds, Michigan Math. J. 48 (2000), 573–592.

[S4] F. Sottile, personal communication.

[SVV] F. Sottile, R. Vakil, and J. Verschelde, Effective solutions to all Schubert problems, work in progress.

[St] R. Stanley, Combinatorial aspects of the Schubert calculus, Combinatoire et représentation du groupe symétrique (Actes Table Ronde CNRS, Univ. Louis-Pasteur Strasbourg, Strasbourg, 1976), 217–251. Lecture Notes in Math., Vol. 579, Springer, Berlin, 1977.

[V1] R. Vakil, The enumerative geometry of rational and elliptic curves in projective space, J. Reine Angew. Math. (Crelle) 529 (2000), 101–153.

[V2] R. Vakil, Schubert induction, preprint 2003, math.AG/0302296v1, Annals of Math., to appear.

[V3] R. Vakil, A conjectural geometric Littlewood-Richardson rule for the equivariant K-theory of the flag variety, in preparation.

Appendix A. The bijection between checkergames and puzzles (with A. Knutson)

We assume familiarity with puzzles [KT, KTW]. Fix k and n. We fill in a puzzle with given inputs, one row of triangles at a time, from left to right. Row m consists of those triangles between the m^{th} edges from the top on the sides of the triangle.

The placement of vertical rhombi may cause parts of subsequent rows to be filled; call these teeth. The m^{th} row of the puzzle corresponds to the part of the checkergame where the black checker in the m^{th} column is descending. The possible choices for filling in puzzle pieces correspond to the possible choices of next moves in the checkergame; this will give the bijection.

We now describe an injection from checkergames to puzzles; to each checkergame we will associate a different puzzle. As both count Littlewood-Richardson coefficients, this injection must be a bijection. Alternatively, to show that this is a bijection, one can instead show that there are no puzzles not accounted for here. For example, one can show easily that there are no puzzles if the checkergame predicts there shouldn’t be (i.e. if the sets are a_{1} < ⋯ < a_{k} and b_{1} < ⋯ < b_{k}, and if a_{i} + b_{k+1−i} ≤ n for some i), by focusing on a certain parallelogram-shaped region of the puzzle. More generally, one may show combinatorially that if a partially-filled-in puzzle doesn’t correspond to a valid checkergamein-progress, then there is no way to complete it. This argument is lengthy and combinatorially tedious, and hence omitted.

A.1. Bijection of starting positions. Place the partition α corresponding to the moving flag on the left side of the puzzle, and the partition β corresponding to the fixed flag on the right side of the puzzle. Fill in the top row of the puzzle in the only way possible. (As remarked earlier, the translation to checkers will give an immediate criterion for there to be no puzzles.)

A.2. The translation part-way through the checkergame. At each stage, the partially complete puzzle will look like Figure 23. Any of a, b, and c may be zero. In the checkergame, a, b, and c correspond to the the numbers shown in Figure 24. The rows of the white checkers in the game are given by the edges of Figure 25 — a “1” indicates that there is a white checker in that row. The columns are given by the edges of Figure 26. As the white checkers are mid-sort, it turns out that this specifies their position completely. See Figure 27 for a more explicit description.

c  b  a^{0}  ^{1}  ^{1}^{0} tooth  to fill in next  tooth

Figure 23. The puzzle in the process of being filled

We now go through the various cases of how to fill in the next part of the puzzle, and verify that they correspond to the possible next moves of the checkergames. Each case is depicted in Figure 28, along with the portion of Table 2 that it corresponds to (in checkers). The reader should verify that all possible puzzle piece placements, and all possible checker moves, are accounted for in the bijection.

Case 1. There is no white checker in the critical row, or in the next row. Then make one move in the checkergame.

Case 2. There is no white checker in the critical row, and there is a white checker in the next row, not on the rising black checker.

b  a  c

Figure 24. The corresponding point in the checkergame

critical row^{1}  ^{1}  row n row 1

Figure 25. The rows of the white checkers

column 1 ^{0}  ^{0}  column n column of descending checker

Figure 26. The columns of the white checkers

Case 3. There is no white checker in the critical row, and there is a white checker on the rising black checker.

Case 4. There is a white checker in the descending checker’s square. In this case, we finish the row of the puzzle, and make a series of checker moves to move the descending checker to the bottom row.

Case 5. There is a white checker in the critical row but not in the descending checker’s square, and there are no white checkers in any lower row. We finish the row of the puzzle, and make a series of checker moves to move the descending checker to the bottom row.

c 1 r no teeth 1  1  1 r  c r  c critical diagonal  critical row 0  0  1 r  c teeth, and/or 0 here

Figure 27. How to locate the white checker given the partially completed puzzle (r is the row and c is the column; see Figures 25 and 26 to interpret them as numbers)

Case 6. There is a white checker in the critical row, and there is another white checker in a lower row, but in a higher row than any white checkers on the critical diagonal (e.g. a blocker if there is a white checker on the critical diagonal). We finish the part of the row of the puzzle up to the corresponding tooth, and make a series of checker moves to move the descending checker to the blocker’s row.

Case 7. There is a white checker in the critical row but not in the descending checker’s square, and there is a white checker in the rising checker’s square. Then we place two puzzle pieces and make one checker move, as shown.

Case 8. There is a white checker in the critical row, but not on the descending checker; there is a white checker in the critical diagonal, but not on the rising checker; and there is no blocker. Then there are two cases. If the white checkers “stay”, then then we make one checker move, and place two pieces. If the white checkers “swap”, then we fill in the part of the puzzle until the “1” in the region marked a in Figure 23, and make a series of checker moves to move the descending checker to the row of the lower white checker in question.

Appendix B. Combinatorial summary of the rule

For the convenience of combinatorialists, we summarize the checker description of the Geometric Littlewood-Richardson rule here, without reference to any geometry. In this context, the rule will necessarily appear somewhat byzantine. Fix positive integers k < n.

0  ^{0} ^{0}^{0}^{1}  ^{1}^{stay:}^{1}  ^{0}  ^{0}^{⋯}  ^{1}  ^{⋯}  ^{0}^{1}  ^{0}  ^{0}^{⋯}  ^{1}  ^{⋯}^{1}^{1}^{1}^{1}^{1}^{1}  ^{0}  ^{0}^{⋯}^{or swap:}^{tooth or right side}  ^{0} 8  ^{0}^{1}  ^{0}^{0}^{⋯} 5  ^{1}  ^{1}^{0}  ^{0}  ^{0}^{⋯}  ^{0}^{⋯}^{0}  ^{0}^{⋯}^{0}^{0}  ^{1}  ^{0}  ^{0}^{1} 3  ^{1}^{0} ^{0}  ^{0} ^{0}  ^{1}^{0}^{1} 2  ^{0}  ^{0}  ^{0}^{0}  ^{0}^{0}^{0} 1  Puzzle Before  Puzzle After Checker movement Part of Table 1 Case  ^{1}  ^{1}^{no teeth}  ^{α}  ^{⋯} ^{ω}^{1}  ^{1}^{1}^{1}  ^{⋯}^{α}^{0}^{1}  ^{0}^{0}^{⋯}  ^{1}^{1}  ^{1}  ^{⋯}  ^{0}  ^{1}  ^{1}  ^{1}^{1}^{1} 4  ^{right side}  ^{(same)} 6  ^{tooth or right side} 7  ^{ω}

Figure 28. How to place the next piece in the puzzle

Fix two partitions α, β ∈ Rec_{k,n−k} (where Rec_{k,n−k} are those partitions that are contained in a k × (n − k) rectangle). We consider α and β as size k subsets of {1, …, n} via the usual bijection (Figure 1). Then a checkergame with inputs α and β is defined as follows. We have an n × n board, and n black checkers and k white checkers. We start by placing the n black checkers along the antidiagonal (in configuration •_{init}, Section 2.3), and the k white checkers in configuration ∘_{α,β} (Proposition 2.7). If the white checkers are not happy (Section 2.5), then we stop; there are no checkergames with inputs α and β. Otherwise, we perform \binom{n}{2} moves. The moves of the black checkers are predetermined, and are given by the specialization order (Section 2.3). For each move, there will be either one or two choices for how the white checkers may move (Section 2.10); after every move they will still be happy. At the end of the checkergame, the black checkers will be lined up along the diagonal (in configuration •_{final}), and the white checkers (in order to be happy) will be on a subset of the black checkers. The resulting size k subset of {1, …, n} is called the output of the checkergame.

Let I_{k,n} be the ideal in the ring of symmetric functions Λ (in countably many variables) generated by the Schur functions {s_{λ}}_{λ∉Rec_{k,n−k}}. Then Λ/I_{k,n} is isomorphic to the cohomology ring of the Grassmannian G(k, n).

B.1. Theorem (Geometric Littlewood-Richardson rule, combinatorial version). —

(i)

s_{α}s_{β} ≡ ∑_{checkergames G}s_{output(G)} (mod I_{k,n})

where the sum is over all checkergames with input α and β, and output(G)is the output of checkergame G.

(ii) Hence if γ ∈ Rec_{k,n−k}, then the integer c_{αβ}^{γ} is the number of checkergames starting with configuration ∘_{α,β}•_{init} and ending with configuration ∘_{γ}•_{final}.

For example, Figure 3 computes s_{(1)}^{2} = s_{(2)} + s_{(1,1)}. Figure 29 computes c_{(2,1),(2,1)}^{(3,2,1)} = 2 using k = 3, n = 6. (In this case, there are four games with inputs α = β = (2, 1); two of them have output (3, 2, 1).)

Theorem B.1 follows immediately from Theorem 2.15, or more explicitly from Corollary 2.17.

B.2. Remarks. (a) Like Pieri’s formula and Monk’s formula, this rule most naturally gives all terms in the product at once (part (i)), but the individual coefficients may be easily extracted (part (ii)).

(b) A derivation of Pieri’s formula from the Geometric Littlewood-Richardson rule is left as an exercise to the reader. Note that Pieri’s original proof [P] was also by degeneration methods.

(c) Some properties of Littlewood-Richardson coefficients clearly follow from the Geometric Littlewood-Richardson rule, while others do not. For example, it is not clear why c_{αβ}^{γ} = c_{βα}^{γ}. However, it can be combinatorially shown (e.g. via the link to puzzles, Appendix A) that (i) the rule is independent of the choice of n and k (i.e. the computation of c_{αβ}^{γ}

A = B = {2, 4, 6} swap steps omitted  swap swap {2, 3, 4}  {1, 3, 5}  {1, 3, 5}  {1, 2, 6} output:  input:  steps omitted

Figure 29. Computing c_{(2,1),(2,1)}^{(3,2,1)} = 2 using k = 3, n = 6; some intermediate steps are omitted

is independent of any n and k such that γ ∈ Rec_{k,n−k}), and (ii) the “triality” c_{αβ}^{γ} = c_{βγ^{∨}}^{α^{∨}} for α, β, γ ∈ Rec_{k,n−k} holds.

Dept. of Mathematics, Stanford University, Stanford CA 94305–2125

E-mail address: vakil@math.stanford.edu