A GEOMETRIC LITTLEWOOD-RICHARDSON RULE

RAVI VAKIL

Abstract. We describe an explicit geometric Littlewood-Richardson rule, interpreted as deforming the intersection of two Schubert varieties so that they break into 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 a straightforward bijection 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. It has a host of geometric consequences, described in [V2]. The rule also has an interpretation in K-theory, suggested by Buch, which gives an extension of puzzles to K-theory. The rule suggests a natural approach to the open question of finding a Littlewood-Richardson rule for the flag variety, leading to a conjecture, shown to be true up to dimension 5. Finally, the rule suggests approaches to similar open problems, such as Littlewood-Richardson rules for the symplectic Grassmannian and two-flag varieties.

Contents

1. Introduction 1 2. The Geometric Littlewood-Richardson rule: Combinatorial description 4 3. Describing the geometry of the Grassmannian and flag variety with checkers 11 4. Application: Littlewood-Richardson rules 16 5. Bott-Samelson Varieties 22 6. Proof of the Geometric Littlewood-Richardson rule 27 7. Appendix: The bijection between checker games and puzzles (with A. Knutson) 41 References 44

1. Introduction

The goal of this note is to describe an explicit geometric Littlewood-Richardson rule, interpreted as deforming the intersection of two Schubert varieties (with respect to transverse flags F_{·} and M_{·}) so that they break into 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

Date: Saturday, February 22, 2003. 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.

of explicit homotopies. It has a straightforward bijection to other Littlewood-Richardson rules, such as tableaux (Sect. 2.6) and Knutson and Tao’s puzzles [KTW, KT] (Sect. 7).

This gives the first geometric proof and interpretation of the Littlewood-Richardson rule. It has a host of geometric consequences, described in [V2]. The rule also has an interpretation in K-theory, suggested by Buch (Sect. 4.3), which suggests an extension of puzzles to K-theory (Theorem 4.6), yielding a triality of K-theory Littlewood-Richardson coefficients. The rule suggests a natural approach to the open question of finding a Littlewood-Richardson rule for the flag variety, leading to a conjecture, shown to be true up to dimension 5 (Sect. 4.8). Finally, the rule suggests approaches to similar open problems, such as Littlewood-Richardson rules for the symplectic Grassmannian and two-flag varieties, and the quantum cohomology of the Grassmannian (Sect. 4.11).

The strategy is as follows. We degenerate the “Moving flag” M_{·} through a series of codimension one degenerations (in F l(n)) in a particular way (the “specialization order”) so that the cycle in G(k, n) successively breaks into varieties we can easily understand (“two-flag Schubert varieties”). At each stage, the cycle breaks into one or two pieces, and each piece appears with multiplicity one (a key fact for applications). At the end M_{·} coincides with the “Fixed flag” F_{·}, and the limit cycle is a union of Schubert varieties with respect to this flag. An explicit example is shown in Figure 6. (Caution: the theorem is stated in terms of the affine description of the Grassmannian, but all geometric descriptions are in terms of projective geometry. Hence Figure 6 shows a calculation in G(2, 4) using lines in ℙ^{3}.)

We note that degeneration methods are a very old 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 (especially [S1], dealing with G(2, n), and [S2], concerning Pieri’s formula in general) provided inspiration for this work.

The degenerations can be described combinatorially, in terms of black and white checkers on an n × n checkerboard. Thus Littlewood-Richardson coefficients count “checker games”. The input is the data of two Schubert varieties, in the form of two k-subsets of {1, …, n}; each move corresponds to moving black checkers (encoding the position of M_{·}) in a certain way (the “specialization order”), and determining then how the white checkers (encoding the position of the k-plane) move. The output is interpreted as set of k-subsets. Similarly, Schubert problems (i.e. intersecting many Schubert classes) count “checker tournaments”. The checker rule is easy to use in practice, but somewhat awkward to describe. However, at all steps, (i) its geometric meaning is clear at all steps, and (ii) there is a straightforward bijection to partially completed tableaux and puzzles. For many geometric applications [V2], the details of the combinatorial rule are unnecessary. R. Moriarty has written a program implementing this rule.

1.1. Remarks on positive characteristic. We note that the only two characteristicdependent statements in the paper are invocations of the Kleiman-Bertini theorem [Kl1] (Sections 3.7 and 3.11). Neither is used for the proof of the main theorem (Theorem 3.10).

They will be replaced by a characteristic-free generic smoothness theorem [V2, Thm. 2.6] proved using the Geometric Littlewood-Richardson rule.

1.2. Overview of paper. Section 2 is a description of the rule in combinatorial terms; it contains no geometry.

Section 3 describes the geometry related to “two-flag Schubert varieties” in the Grassmannian in the language of checkers. Black checkers correspond to the relative position of the two flags; white checkers correspond to the k-plane. The main theorem (Theorem 3.10) is stated here. Geometrically-minded readers may prefer to read some of Section 3 before Section 2.

The proof makes repeated use of smooth “Bott-Samelson varieties” BS(P) corresponding to a “planar poset” P. They are simple objects, and some basic properties are described in Section 5. Of particular importance is the Bott-Samelson variety BS(P_{□}) parametrizing two hyperplanes and a codimension two plane contained in both. Each step in the degeneration is related to BS(P_{□}) via the key construction of Section 5.6.

The proof of the Geometric Littlewood-Richardson rule is given in Section 6; the strategy is outlined in Section 6.1.

Applications are discussed in Section 4. Some are proved in detail, while others are merely sketched. Further geometric applications are discussed in [V2].

1.3. Summary of notation. If X ⊂ Y, let Cl_{Y} X denote the closure in Y of X. 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}.

We follow the notation of [F]. For example, let Ω_{w} denote the Schubert class in H^{∗}(G(k, n)) or A^{∗}(G(k, n)) (resp. H^{∗}(F l(n)) or A^{∗}(F l(k, n))), where w is a partition (resp. a permutation). Let Ω_{w}(F_{·}) (resp. Ωw^{∘}(F_{·})) be the closed (resp. open) Schubert variety with respect to the flag F_{·}. In F l(n),

Ω_{w}(F_{·}) = {[V_{·}] ∈ F l(n) : dim(V_{p} ∩ F_{q}) ≥ #{i ≤ p : w(i) > n − q} for all p, q} .

The Schur polynomials are denoted s_{·}.

Table 1 is a summary of notation introduced in the article.

1.4. 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. Any remaining misunderstandings are purely due to the author. The author also thanks L. Chen, W. Fulton, R. Moriarty, and F. Sottile.

section  notation

introduced

2.1– 2.3  configuration of checkers, specialization order, descending

and rising checkers, •, •_{init}, •_{final}, •_{next}, happy, ∘, ∘•, ∘_{A,B}, critical row, critical diagonal, Phase 1, swap, blocker, Phase 2, ∘_{stay}, ∘_{swap}, ∘_{S}

2.8  mid-sort
3.1  M_{·}, F_{·}, dominate, X_{•}
3.4  open and closed two-flag Schubert varieties Y_{∘•} and \overline{Y}_{∘•},

universal two-flag Schubert variety, X_{∘•}, \overline{X}_{∘•}

3.8  D_{X}
5.1  dimension, planar poset, P, quadrilateral, southwest and

northeast border, Bott-Samelson variety, BS(P)

5.3–5.5  strata of a Bott-Samelson variety, P_{•}, P_{∘}, BS(P → Q), p_{∘•}
5.6–5.8  P_{□}, x, y, y′, z, V_{x}, V_{y}, V_{y′}, V_{z}, D_{□}, p_{•□}, (r, c), S_{·}, T_{·}, X_{•□}, X_{•□}-position
6.1  geometrically (ir)relevant
6.3  Z
6.6–6.8  a,a′, a′′, left and right good quadrilaterals, columns, D_{S}^{Z}, D_{S}, Q_{ℓ}, P′_{∘}

Table 1. Summary of notation

2. The Geometric Littlewood-Richardson rule: Combinatorial description

2.1. Littlewood-Richardson coefficients c_{αβ}^{γ} will be counted in their guise of structure constants of the cohomology (or Chow) ring of the Grassmannian G(k, n), which in turn will be interpreted in terms of checker games, involving n black and k white checkers on an n × n board. The rows and columns of the board are numbered as in Figure 1; (r, c) will denote the square in row r and column c. A set of checkers on the board will be called a configuration of checkers.

1 n  n 1  ⋯ ⋮ Figure 1.

2.2. Black checkers. The moves of the black checkers are prescribed in advance; the Littlewood-Richardson coefficients are counted by the possible accompanying moves of the white checkers.

No two checkers of the same color are in the same row or column. Hence the positions of the black checkers correspond to permutations by the following bijection: if the black checker in column c is in row r, then the permutation sends n + 1 − c to r. For example, see Figure 2.

The initial position of the black checkers corresponds to the identity permutation in S_{n}, and the final position corresponds to the longest word w_{0}. The intermediate positions in the checker game correspond to partial factorizations from the right 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}.

For example, in Figure 2 shows the six moves of the black checkers for n = 4, along with the corresponding permutations. (The geometric interpretation will be explained in Sect. 3.3.) In essence this is a bubble-sort. Call this the specialization order in the Bruhat order. Figure 3 shows a typical checker configuration in the specialization order. Each move will involve moving one checker one row down (call this the descending checker), and another checker (call this the rising checker) one row up, as shown in the figure.

Note that this word neither begins nor ends with the corresponding word for n − 1, making induction impossible (see Sect. 3.12).

We will use the notation • to represent a configuration of black checkers. Denote the initial configuration by •_{init}, and the final configuration by •_{final}. If • is one of the configurations in the specialization order, and • ≠ •_{final}, then •_{next} will denote the next configuration in the specialization order.

2.3. White checkers. At each stage of the game, each white checker has the following property: there is a black checker in the same square or in a square above it, and there is a black checker in the same square or in a square to the left of it. A white checker satisfying this property is said to be happy. (In particular, a white checker is happy if it is in the same square as a black checker.) A configuration of white checkers will often be denoted ∘, and a configuration of white and black checkers will often be denoted ∘•.

The initial position of the white checkers depends on two subsets A = {a_{1}, …, a_{k}} and B = {b_{1}, …, b_{k}} of {1, …, n}, where a_{1} < ⋯ < a_{k} and b_{1} < ⋯ < b_{k}. The k white checkers are in the squares (a_{1}, b_{k}), (a_{2}, b_{k−1}), …, (a_{k}, b_{1}). We denote this configuration by ∘_{A,B}. If (and only if) any of these white checkers are not happy (i.e. if a_{i} + b_{k+1−i} ≤ n for some i), then there are no checker games corresponding to (A, B). (This will mean that all corresponding Littlewood-Richardson coefficients are 0. Geometrically, this means that the two Schubert varieties do not intersect.) This happens, for example, if n = 2 and A = B = {1}, computing the intersection of two general points in ℙ^{1}.

For each move of the black checkers, there will be one or two possible moves of the white checkers, which we describe next. Define the critical row and the critical diagonal as in Figure 3. The movement of the white checkers takes place in two phases.

Phase 1 depends on the answers to the 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? (There may be several white checkers in the critical diagonal.)

Based on the answer to these questions, the pair of white checkers either swap rows (i.e. if the white checkers start at (r_{1}, c_{1}) and (r_{2}, c_{2}), then they will end at (r_{2}, c_{1}) and (r_{1}, c_{2})), or they stay where they are, according to Table 2. 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

4321^{point}  ^{line}  ^{plane} 1432  2431  3421^{12}  ^{23}  ^{34}^{M·} 1234^{F·}  ^{plane}^{34}^{line}  ^{plane} 1243  1342^{23}  ^{34}

Figure 2. The specialization order for n = 4, in terms of checkers and permutations, with the geometric interpretation of Section 3

are no white checkers in the rectangle between them they can swap. Call white checkers in this rectangle blockers. See Figure 4 for an example of a blocker.

Phase 2 is a “clean-up phase”: if any white checkers are not happy, then move them by sliding them either left or up so that they become happy. This is always possible, in a unique way.

If ∘• corresponds to the configuration of black and white checkers before the move, we denote the one or two possible configurations after the move by ∘_{stay}•_{next} and/or ∘_{swap}•_{next}. Examples of the ten cases are given in Figure 5.

rising checker critical diagonal descending checker critical row

Figure 3. The critical row and the critical diagonal

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 5 for a pictorial description)

white checker in critical row

blocker

top white checker in critical diagonal

Figure 4. Example of a blocker

At the end of the checker game, the black checkers are in position •_{final}, and as the white checkers are happy, they must lie on a subset of the black checkers. The corresponding output is again a subset S of {1, …, n} of size k. Denote this final configuration of white checkers by ∘_{S}.

Hence to any two subsets A, B of {1, …, n} of size k, we can associate a formal sum of subsets of size k, corresponding to checker games. Figure 6 illustrates the two checker games starting with A = B = {2, 4} for k = 2, n = 4. The output consists of the two subsets {1, 4} and {2, 3}. Figure 7 illustrates all checker games starting with A = B = {2, 4, 6} for k = 3, n = 6. The output is {2, 3, 4} + 2{1, 3, 5} + {1, 2, 6}.

2.4. Littlewood-Richardson coefficients in terms of checker games.

†^{or}^{yes, elsewhere}^{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}

Figure 5. Examples of the nine cases (case † is discussed in Sect. 2.6)

Littlewood-Richardson rules give combinatorial descriptions of Littlewood-Richardson coefficients c_{αβ}^{γ}, defined by

s_{α}s_{β} = ∑_{γ} c_{αβ}^{γ}s_{γ}

where α and β are partitions, and s_{·} are Schur functions. The checker games will compute compute the sum on the right modulo the ideal (in the ring of symmetric functions) defining the cohomology ring of the Grassmannian G(k, n).

More precisely, let Rec_{k,n−k} be the set of subdiagrams of the rectangle with k rows and n − k columns. Throughout this article, we identify Rec_{k,n−k} with subsets of {1, …, n} of size k using the well-known bijection (see Figure 8). Fix α and β.

2.5. Theorem (Geometric Littlewood-Richardson rule, first version). —

(a) ∑_{games G}s_{output(G)}= ∑_{γ∈Rec_{k,n−k}} c_{αβ}^{γ}s_{γ}, where the left sum is over all checker games with input α

and β, and output(G)is the output of checker game G.

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

For example, Figure 6 computes s_{(1)}^{2} = s_{(2)}+s_{(1,1)}. Figure 7 computes c_{(2,1),(2,1)}^{(3,2,1)} = 2 using k = 3, n = 6.

Theorem 2.5 follows immediately from Theorem 3.9 (Geometric Littlewood-Richardson rule, second version).

input:^{(A = B = {2, 4})}^{×}  ^{output: {2, 3} =}  ^{output: {1, 4} =}^{**}^{*}  ! !

Figure 6. Two checker games with the same starting position, and the geometric interpretation of Section 3 (compare to Figure 2; checker configurations * and ** are discussed in Sect. 3.12, and the moves labeled “!” are discussed in Sect. 2.6)

2.6. Bijection to tableaux. There is a straightforward bijection to tableaux (using the tableaux description of [F, Cor. 5.1.2]). Whenever there is move described by a † in Figure 5 (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.

For example, in Figure 6, the left-most output corresponds to the (one-cell) tableau “2”, and the right-most output corresponds to the tableau “1”. The moves where the tableaux are filled are marked with “!”.

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 7. Computing c_{(2,1),(2,1)}^{(3,2,1)} = 2 using k = 3, n = 6; some intermediate steps are omitted

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

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

2.7. Remarks. (a) Like Pieri’s formula and Monk’s formula, this rule most naturally gives all terms in an intersection all at once (part (a)), but the individual coefficients can be easily extracted (part (b)).

(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 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 (most easily via the link to puzzles, Sect. 7) that (i) the rule is independent of the choice of n and k (i.e. the computation of c_{αβ}^{γ} 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.

(d) We will need the following combinatorial observation.

2.8. Lemma. — Suppose at some point in the algorithm, 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}. Then (r_{1}, …, r_{k}) is increasing for c_{i} ≤ c and decreasing for c_{i} ≥ c.

This follows from a straightforward induction showing that this property is preserved by each move. We say that configuration ∘• with this property is mid-sort. For example, the white checkers of Figures 7 and 21 are mid-sort.

3. Describing the geometry of the Grassmannian and flag variety with checkers

In this section, we interpret checker configurations geometrically, and state the main technical result of the paper, Theorem 3.10 (the Geometric Littlewood-Richardson rule, final version). Black checkers will correspond to the relative position of the two flags M_{·} and F_{·}, and white checkers will correspond to the position of the k-plane relative to the flags.

3.1. The relative position of two flags, given by black checkers; the variety X_{•}. Given two flags M_{·} and F_{·}, construct an n × n “rank” table of the numbers dim M_{i} ∩ F_{j}. Up to the action of GL(n), the two flags are specified by this table.

3^{4}^{2}  ^{2}^{1}^{1}^{1}  ⟺^{1}  ^{3}^{0}  ^{2}^{1}^{0}  ^{0}^{0}^{0}

Figure 9. The relative position of two flags, given by numbers on an n × n board, and by a configuration of black checkers

This data is equivalent to the data of n black checkers on the checkerboard such that no two are in the same row or column. The bijection is given as follows. We say a square (i_{1}, j_{1}) dominates another square (i_{2}, j_{2}) if i_{1} ≥ i_{2} and j_{1} ≥ j_{2}. Given the black checkers, dim M_{i} ∩ F_{j} is given by the number of black checkers dominated by square (i, j). An example of the bijection is given in Figure 9.

Note that each square in the table corresponds to a vector space, whose dimension is the number of black checkers dominated by that square. The vector space is the span of the vector spaces corresponding to the black checkers it dominates.

Let X_{•} be the (locally closed) subvariety of F l(n)×F l(n) corresponding to flags (M_{·}, F_{·}) in relative position given by black checker configuration •. 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 dominates b. (This is a straightforward exercise; it also follows quickly from Sect. 5.) This sort of construction is common in the literature.

3.2. Side remark: Schubert varieties of the flag variety. For a fixed F_{·} and fixed configuration • of black checkers, the set of M_{·} in F l(n) such that the relative position of M_{·} and F_{·} is given by • is an open Schubert cell Ω•^{∘} (i.e. the second projection pr_{2} : X_{•} → F l(n) is a fibration by Schubert cells). This set is a GL_{n}-orbit (what some authors call a “double Schubert cell”). Schubert cells are usually indexed by permutations; the bijection between checker configurations and permutations was given in Section 2.2. For example, the permutation corresponding to Figure 9 is 1324.

3.3. The specialization order. Given a point p of F l(n) (parametrizing M_{·}) in the dense open Schubert cell (with respect to a fixed reference flag F_{·}), the specialization order (Sect. 2.2) can be interpreted as a sequence in F l(n), consisting of a chain of \binom{n}{2} ℙ^{1}’s, starting at p and ending with the “most degenerate” point of F l(n) (corresponding to the reference flag F_{·}).

We first describe the chain informally. Each ℙ^{1} corresponds to a move of black checkers. All but one point of the ℙ^{1} lies in one open stratum X_{•}; the remaining point (where the ℙ^{1} meets the next component of the one-parameter degeneration) lies on an open stratum X_{•_{next}} of dimension one lower. If the move corresponds to the descending checker in row r dropping one row (and another checker to the left rising one row), then all components of the flags F_{·} and M_{·} except M_{r} are held fixed. For example, the geometry corresponding to the specialization order for n = 4 is shown in Figure 2.

More precisely, there is a ℙ^{1}-fibration X_{•} ∪ X_{•_{next}} → X_{•_{next}}; the ℙ^{1} corresponding to a point of X_{•} described in the previous paragraph is a fiber. A useful alternate description of X_{•} ∪ X_{•_{next}} is given in Section 5.6.

3.4. The position of a k-plane relative to two given flags, in terms of white checkers; two-flag Schubert varieties Y_{∘•} and X_{∘•}. Suppose two flags M_{·} and F_{·} are in relative position given by black checker configuration •. The position of a k-plane V relative to the two flags, up to the action of the subgroup of GL(n) fixing the two flags, is determined by the table of numbers dim V ∩ M_{i} ∩ F_{j}.

This data is equivalent to the data of k white checkers on the checkerboard that are happy (see Sect. 2.3), with no two in the same row or column. The bijection is given as follows: dim V ∩ M_{i} ∩ F_{j} is the number of white checkers in squares dominated by (i, j). See Figure 6 for example; the line ℙV is depicted as a dashed line.

If M_{·} and F_{·} are two flags whose relative position is given by •, let the open two-flag Schubert variety Y_{∘•} ⊂ 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_{∘•}. Let X_{∘•} (resp. \overline{X}_{∘•}) in G(k, n) × X_{•} be the universal open (resp. closed) two-flag Schubert variety. (Similar constructions are common in the literature.)

Note that (i) X_{∘•} → X_{•} is a Y_{∘•}-fibration; (ii) \overline{X}_{∘•} → X_{•} is an \overline{Y}_{∘•}-fibration, and proper; (iii) G(k, n) is the disjoint union of the Y_{∘•} (for fixed • and F_{·}, M_{·}); (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; Section 3.12 (a) provides a counterexample.

3.5. 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).

The proof is straightforward and hence omitted.

3.6. Proposition (Initial position of white checkers). — Suppose A = {a_{1}, …, a_{k}} and B = {b_{1}, …, b_{k}} are two subsets of {1, …, n} of size k, and M_{·} and F_{·} are two transverse (opposite) flags (i.e. with relative position given by •_{init}). Then Ω_{A}(M_{·}) ∩ Ω_{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 were also called skew Schubert varieties by Stanley [St1].

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

In positive characteristic, the same argument shows that the cycle Ω_{A}(M_{·}) ∩ Ω_{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 in Section 3.11.

3.7. The Geometric Littlewood-Richardson rule: deforming cycles in the Grassmannian. We can now give a geometric interpretation of Theorem 2.5 (which will be the first version of the Geometric Littlewood-Richardson rule). We wish to compute the class (in H_{∗}(G(k, n))) of the intersection of two Schubert cycles. By the Kleiman-Bertini theorem [Kl1] (or our Grassmannian Kleiman-Bertini theorem [V2, Thm. 2.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 3.6 is [\overline{Y}_{∘_{A,B}•_{init}}]. By a sequence of codimension 1 degenerations (corresponding to the specialization order), we degenerate the two flags until they are equal. The base of each degeneration is a ℙ^{1} in F l(n), where 𝔸^{1} ⊂ X_{•} and \{∞\} ∈ X_{•_{next}}. We have a \overline{Y}_{∘•}-fibration above 𝔸^{1}. The fiber above ∞ of the closure of this fibration (in G(k, n) × ℙ^{1}) turns out to be one of \overline{Y}_{∘_{stay}•_{next}}, \overline{Y}_{∘_{swap} •_{next}}, or \overline{Y}_{∘_{stay}•_{next}}∪\overline{Y}_{∘_{swap} •_{next}} (Theorem 3.9; ∘_{stay} and ∘_{swap} were defined in Sect. 2.3); the components appear with multiplicity 1. In other words, the two-flag Schubert variety degenerates to another two-flag Schubert variety, or to the union of two. Figure 6 illustrates the geometry behind the computation of s_{(1)}^{2} = s_{(1,1)} + s_{(2)} in G(2, 4).

3.8. More precisely, assume the black checker configuration • is in the specialization order, and the white checkers are mid-sort (in the sense of Lemma 2.8). Consider the diagram:

\overline{X}_{∘•} := Cl_{G(k,n)×X_{•}} X_{∘•} ↪ Cl_{G(k,n)×(X_{•}∪X_{•_{next}})} X_{∘•} ↩ D_{X}
↓  ↓  ↓
X_{•}  ↪  X_{•} ∪ X_{•_{next}}  ↩ X_{•_{next}}.

(1)

The Cartier divisor D_{X} is defined by fibered product. Note that the vertical morphisms are proper, the vertical morphism on the left is a \overline{Y}_{∘•}-fibration, the horizontal inclusions on the left are open immersions, and the horizontal inclusions on the right are closed immersions.

The geometric constructions described in Section 3.7 are obtained from (1) by base changing via ℙ^{1} → X_{•} ∪ X_{•_{next}} (described in Sect. 3.3), to obtain:

\begin{aligned}Y_{∘•} & ↪ & Cl_{G(k,n)×ℙ^{1}} Y_{∘•} & ↩ & D_{Y} \\ ↓ & & ↓ & & ↓ \\ 𝔸^{1} & ↪ & ℙ^{1} & ↩ & \{∞\}. \end{aligned} (2)

Here Y_{∘•}, Cl_{G(k,n)×ℙ^{1}} Y_{∘•}, and D_{Y} are defined by fibered product (or restriction) from (1). Again, the vertical morphisms are proper, the vertical morphism on the left is a \overline{Y}_{∘•}- fibration, the horizontal inclusions on the left are open immersions, and the horizontal inclusions on the right are closed immersions.

The informal statement of Section 3.7 can now be made precise:

3.9. Theorem (Geometric Littlewood-Richardson rule, second version). — D_{Y} = \overline{Y}_{∘_{stay}•_{next}}, \overline{Y}_{∘_{swap}•_{next}}, or \overline{Y}_{∘_{stay}•_{next}} ∪ \overline{Y}_{∘_{swap}•_{next}}.

By base change from (1)to (2), Theorem 3.9 is a consequence of the following, which is proved in Section 6. (The notation Y_{∘•} and D_{Y} will not be used hereafter.)

3.10. Theorem (Geometric Littlewood-Richardson rule, final version). — D_{X} = \overline{X}_{∘_{stay}•_{next}}, \overline{X}_{∘_{swap}•_{next}}, or \overline{X}_{∘_{stay}•_{next}} ∪ \overline{X}_{∘_{swap}•_{next}}.

In other words, a particular divisor D_{X} (corresponding to X_{•_{next}} ⊂ X_{•} ∪ X_{•_{next}}) on a universal two-flag Schubert variety is another such variety, or the union of two such varieties.

3.11. Enumerative problems and checker tournaments. Suppose Ω_{α_{1}}, …, Ω_{α_{ℓ}} 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

[Kl1] (or our Grassmannian Kleiman-Bertini theorem [V2, Thm. 2.6] in positive characteristic) — can clearly be inductively computed using the Geometric Littlewood-Richardson rule. Hence Schubert problems can be solved by counting checker 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 checker tournament will always be the same — the class of a point.)

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

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

3.12. Cautions. (a) The degenerations used in the Geometric Littlewood-Richardson rule follow the specialization order. An arbitrary path through the Bruhat order will not work in general. For example, if ∘• is as shown on the left of Figure 10, then X_{∘•} corresponds to 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 for example M_{3} = span(ℓ_{2}, p_{2}) and the line corresponding to the point of G(2, 4) is span(q, p_{2}). The degeneration shown in Figure 10 (to •′, 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_{•_{next}})} X_{∘•} corresponding to X_{•′} parametrizes lines through p_{1} contained in span(ℓ_{1}, ℓ_{3}); this is not of the form X_{∘′•′} for any ∘′.

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

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

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

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

4. Application: Littlewood-Richardson rules

In this section, we discuss the bijection 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 rely on Buch’s extension of the tableau rule [B1].) We then describe progress of extending this method to the flag manifold (the open question of a Littlewood-Richardson rule for Schubert polynomials). Finally, we conclude with open questions.

4.1. Checkers, puzzles, tableaux. A bijection between checker games and puzzles is given in Section 7. Combining this with Tao’s “proof-without-words” of a bijection between puzzles and tableaux (given in Figure 11) yields the bijection between checkergames and tableaux:

4.2. Theorem (bijection from checker games to tableaux). — The construction of Section 2.6 gives a bijection from checker games to tableaux.

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

Hence checker games give the first geometric interpretation of tableaux and puzzles; indeed there is a bijection between tableaux/puzzles and solutions of the corresponding triple-intersection Schubert problem, once branch paths are chosen [V2, Sect. 4.3], [SVV].

Note that to each puzzle, there are three possible checker-games, depending on the orientation of the puzzle. These correspond to three degenerations of three general flags. It would be interesting to relate these three degenerations.

4.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. 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; denote the resulting configuration ∘_{sub}•_{next}. Note that by Lemma 3.5, dim \overline{Y}_{∘_{sub}•_{next}} = dim \overline{Y}_{∘•} − 1.

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)

(−1)×

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

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

Proof. We give a bijection from K-theory checker games to Buch’s “set-valued tableaux” (certain tableaux whose entries are sets of consecutive integers, [B1]), generalizing the bijection of Section 2.6. Each white checker now has a memory of certain earlier rows. Each time there is a sub-swap, where a checker rises from being the r^{th} white checker to being the (r − 1)^{st} (counting by row), that checker adds to its memory that it had once been the r^{th} checker (by row). Whenever there is move described by a † in Figure 5, where the white checker is the r^{th} by row and the c^{th} by column, in row c of the tableau place the set consisting of r and all remembered earlier rows. Then erase the memory of that white checker. (The reader may verify that in Figure 6 (G(2, 4)), 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 straightforward and left to the reader.

This result suggests that Buch’s rule reflects a geometrically stronger fact, extending the final version of the Geometric Littlewood-Richardson rule 3.10.

4.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_{X} = \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 the degeneration is Cohen-Macaulay; this would imply the conjecture.

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

4.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

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 piece is new; it may not be rotated. Tao had earlier, independently, discovered this piece [T].

Theorem 4.6 may be proved via the K-theory Geometric Littlewood-Richardson rule 4.4, or by generalizing Tao’s proof of Figure 11. Both proofs are omitted.

As a consequence, we immediately have:

4.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(d, 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 in G(k, n)}.

More precisely, the structure sheaf for a partition λ = (λ_{1}, …, λ_{k}) is dual to t times the structure sheaf for λ^{∨} = (n − k − λ_{k}, ..., n − k − λ_{1}). (For more details, see [B1, Sect. 8]; this property is special for Grassmannians.) Hence ρ_{∗}(tO_{λ}O_{μ}O_{n}u) = C_{λμ}^{ν^{∨}} = C_{μν}^{λ^{∨}} = C_{νλ}^{μ^{∨}}.

4.8. Toward a Geometric Littlewood-Richardson rule for flag manifolds. The same methods can be applied to flag manifolds, in the hope of addressing the important open problem of finding a Littlewood-Richardson rule in this context (i.e. structure coefficients for the multiplication of Schubert polynomials), see [St2], [F, p. 180], [FP, Sect. 9.10]. This problem has already motivated a great deal of remarkable work.

We describe some partial results here, informally. Define two-flag Schubert varieties X_{δ} of flag manifolds analogously to X_{∘•}, as the locus in F l(n) × F l(n) × F l(n) parametrizing (i) two flags F_{·} and M_{·} in relative position given by •, and (ii) a third flag F_{·} such that dim F_{i} ∩ M_{j} ∩ F_{k} = δ_{ijk}. The configuration • is obtained from the rank table (δ_{ijn})i, j by the bijection of Section 3.1. The choice of the data δ_{ijk} for which this data is non-empty can be usefully summarized in two (equivalent) ways. It is not yet clear which is the more convenient notation.

First, these δ correspond to configurations of checkers on an n × n board, where there are i checkers labeled i for 1 ≤ i ≤ n. No two checkers with the same label are in the same column or the same row. An i-checker (i < n) is happy if there is an (i + 1)-checker to its left (or in the same square) and an (i+1)-checker above it (or in the same square). (See for example Figure 14.) The bijection to δ is given as follows: δ_{ijk} is the number of k-checkers dominated by (i, j). The morphism to X_{•} corresponds to forgetting all but the n-checkers.

Second, these δ correspond to “wiring diagrams”, with n wires entering the board from below and leaving the board on the right. The bijection to δ is given as follows: δ_{ijk} is the number of wires numbered at least k dominated by (i, j). See Figure 15 for an example.

δ = 54 5 54  32 5 432 1 543 ⟹^{??} δ′ = 54 54 3 54  3 2 543  2 1 5

Figure 14. Is the two-flag Schubert variety on the right in the closure of the one on the left?

1 2 5 3 4  4 5 2 1 3

Figure 15. The “wiring diagram” corresponding to the first checker configuration of Figure 14

There is an analogue of Proposition 3.6, describing the intersection of two Schubert varieties (with respect to transverse flags F_{·} and M_{·}) as \overline{X}_{δ} for an explicitly given δ; call the set of δ obtained in such a way the initial positions.

4.9. Conjecture (Existence of a Geometric Littlewood-Richardson rule for flag manifolds). — There exists a subset M of the {(δ_{ijk})_{ijk}}, where the configuration of n-checkers is in the specialization order (analogous to “mid-sort”), containing the set of initial positions, such that the divisor D_{X} on \overline{X}_{δ} corresponding to the next element of the specialization order is the union of varieties of the form \overline{X}_{δ′}, each appearing with multiplicity 1, where (δ′_{ijk})_{ijk} ∈ M.

This conjecture (which parallels Theorem 3.10) looks quite weak, as it specifies neither

(i) the “mid-sort” property M nor (ii) how to determine δ′. However, it suffices to obtain almost all of the applications described in [V2] (e.g. reality, number of solutions in positive characteristic, numerical calculation of solutions to all Schubert problems, and more). Furthermore, it implies the existence of a Littlewood-Richardson rule, and an answer to (ii) would give an explicit rule.

4.10. Proposition. — Conjecture 4.9 is true for n ≤ 5.

This is a considerable amount of evidence, involving ∑_{n=1}^{5} \binom{n}{2} ∑_{α,β,γ} c_{αβ}^{γ} degenerations. However, there are two serious reasons to remain suspicious: (a) Knutson’s puzzle variant computes Littlewood-Richardson coefficients for n < 5 but fails for n = 5 (and puzzles are related to checkers via Sect. 7), and (b) all Littlewood-Richardson coefficients are 0 or 1 for n < 6.

Sketch of proof of Proposition 4.10 for n ≤ 4. We build M inductively, starting with the set of initial positions. Successively, for each element δ of M, we find a list of possible divisors \overline{X}_{δ′} on \overline{X}_{δ} (above X_{•_{next}}) as follows. If the n-checkers of δ are in position •, the n-checkers of δ′ are in position •_{next}. Then given the positions of the k-checkers of δ and the (k + 1)-checkers of δ′ (for 1 ≤ k < n), we list the (finite number of) possibilities of the choice of positions of the choices of k-checkers of δ′ subject to two conditions: the kcheckers are happy, and δ′_{ijk} ≥ δ_{ijk}. We then discard all δ′ such that dim X_{δ′} < dim X_{δ} − 1.

Then each component of D_{X} lies in D_{δ′} for some remaining δ′. If any X_{δ′} has dimension at least dim X_{δ}, we stop, and the process fails. Otherwise, D_{X} must consist of a union of these X_{δ′}, possibility with multiplicity. We then add these δ′ to M. (This is a greedy algorithm, which sometimes includes δ′ which do not correspond to components of D_{X}.) Thus the conjecture is true for this δ (with this choice of M) with the possible exception of the multiplicity 1 claim. We now repeat the process with this enlarged M.

For n ≤ 4, one checks (most easily by computer) that this process never fails. Moreover, as all Littlewood-Richardson coefficients for n ≤ 4 are 1, the multiplicity must be 1 at each stage.

The author has a full description of the degenerations which actually appear for n ≤ 4, available upon request. However, it is not clear how to generalize this to a conjectural Littlewood-Richardson rule.

For n = 5, this process fails at six cases (where dim X_{δ′} = dim X_{δ}). However, in three of the six cases, it can be shown that \overline{X}_{δ} does not meet X_{δ′} (one is shown in Figure 14; the other two are identical except for the position of the 1-checker), and in the other three cases, δ itself can be removed from M (i.e. δ was falsely included in M by the greediness of the algorithm).

For larger n, this greedy algorithm will certainly produce even worse pathologies (i.e. arbitrarily many cases where dim X_{δ′} − dim X_{δ} is arbitrarily large).

4.11. Questions. One motivation for the Geometric Littlewood-Richardson rule is that it should generalize well to other important geometric situations (as it has in Ktheory and at least partially for the flag manifold). We now briefly describe some potential applications; some are work in progress.

(a) These methods may apply to other groups where Littlewood-Richardson rules are not known. For example, for the symplectic 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.

(b) An important intermediate stage between the Grassmannian and the full flag manifold is the two-step partial flag manifold. This case has useful applications, for example, to Grassmannians of other groups. The preprint [BKT] gives a connection to Gromov-Witten invariants (and does much more). The Littlewood-Richardson behavior of the two-step partial flag manifold is much better than for full flag manifolds. Buch, Kresch, and Tamvakis have suggested that Knutson’s proposed partial flag rule (which fails for flags in general) holds for two-step flags, and have verified this up to n = 16 [BKT, p. 6].

Is there a good (and straightforward) checker-rule for such homogeneous spaces?

(c) Can equivariant Littlewood-Richardson coefficients be understood geometrically in this way? For example, can equivariant puzzles [KT] be translated to checkers, and can partially-completed equivariant puzzles thus be given a geometric interpretation? Can this be combined with Theorem 4.4 to yield a Littlewood-Richardson rule in equivariant K-theory?

(d) The quantum cohomology of the Grassmannian can be translated into classical questions in 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) independently by I. Coskun (for rational scrolls), D. Avritzer, and M. Honsen (on Veronese surfaces).

(e) Is there any relation between the wiring diagrams of Figure 15 and rc-graphs? (We suspect not.)

(f) D. Eisenbud and J. Harris [EH] have 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 cell: 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 paths. This would provide a single path that breaks intersections of Schubert cells into their components. (Of course, the limit cycles could not have multiplicity one 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, Sect. 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 respective 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.

5. Bott-Samelson Varieties

5.1. We will associate a variety to the following data.

• n is a positive integer.

• P is a finite subset of the plane (visualized 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), with the partial order ≺ given by domination (defined in Sect. 3.1).

• dim : P → {0, 1, 2, …, n} is a morphism of posets (i.e. weakly order-preserving map), denoted dimension.

• If [a, b] is a covering relation (i.e. minimal interval) in P (i.e. a, b ∈ P, a ≺ b, and there is no c ∈ P such that a ≺ c ≺ b), then dim a = dim b − 1. (This condition is likely unnecessary.)

• P has a maximum element and a minimum element.

We call this data a planar poset, and denote it by P; the remaining data (≺, dim, n) will be implicit.

It will be convenient to represent this data as a planar graph, whose vertices are elements of P, and whose edges correspond to covering relations in P. The interior of the graph is a union of quadrilaterals; call these the quadrilaterals of P. An element of P at (i, j) is said to be on the southwest border (resp. northeast border) if there are no elements of P (i′, j′) such that i′ ≥ i and j′ ≤ j (resp. i′ ≤ i and j′ ≥ j); see Figure 16.

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

Forgetting all but the vertices on the southwest border yields a morphism to the flag manifold, and the usual Bott-Samelson variety is a fiber of this morphism.

5.2. Lemma. — The Bott-Samelson variety BS(P) is smooth.

Proof. Consider the planar graph representation of P described above. The variety parametrizing the subspaces corresponding to the southwest border of the graph is a partial flag variety (and hence smooth). The Bott-Samelson variety BS(P) can be expressed as a tower of ℙ^{1}-bundles over the partial flag variety by inductively adding the data of elements of s ∈ S corresponding to “new” vertices of quadrilaterals (where the other three vertices s_{1} ≺ s_{2} ≺ s_{3} are already parametrized, and s_{1} ≺ s ≺ s_{3}).

For example, Figure 16 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 arrows.

3^{4}^{1}  ^{2} ^{5} southwest border  northeast border

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

5.3. Strata of Bott-Samelson varieties. Any subset Q of the quadrilaterals of a planar poset determines a stratum of the Bott-Samelson variety. The closed stratum corresponds to requiring the subspaces of the opposite corners of the quadrilaterals in Q of the same dimension to be the same. The open stratum corresponds to also requiring the spaces of the opposite corners of the quadrilaterals not in Q to be distinct. By the construction in the proof of Lemma 5.2, (i) the open strata give a stratification, (ii) the closed strata are smooth, and (iii) the codimension of the stratum is the size of the subset Q. It will be convenient to depict a stratum by placing an “=” in the quadrilaterals of Q, indicating the pairs of subspaces that are required to be equal (see for example Figure 17).

5.4. Example: planar posets generated by a set of checkers. Given a checker configuration • (or ∘) and a positive integer n, we define the planar poset P_{•} (or P_{∘}) 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” above and to the left of the checkers. (The definition of happy in Sect. 2.3 can be rephrased as: the white checkers lie on elements of P_{•}.) For s ∈ P, let dim s be the number of checkers dominated by s.

For example, if • is a configuration of n checkers (as in Sect. 2.2), then the southwest border of P_{•} corresponds to F_{·}, and the northeast border corresponds to M_{·}; BS(P_{•}) is a fibration over F l(n) (where F l(n) parametrizes F_{·}), and the fiber is a Bott-Samelson resolution of Ω_{•}(F_{·}). Figure 16 describes a Bott-Samelson resolution of the double Schubert variety corresponding to 1324. Similarly, the morphism BS(P_{•}) → \overline{X}_{•} is a resolution of singularities. This morphism restricts to an isomorphism of the dense open stratum of BS(P_{•}) with X_{•}. If • is in the specialization order, then BS(P_{•_{next}}) is (isomorphic to) a codimension 1 stratum of this Bott-Samelson variety. See Figure 17 for an example.

0  =

Figure 17. The poset corresponding to • of Figure 3, with the divisorial stratum corresponding to •_{next} marked with an “=”

dim x = n − 2  dim y′ = n − 1 dim z = n dim y = n − 1

Figure 18. The planar poset P_{□}

5.5. Bott-Samelson varieties of morphisms of posets. Suppose P and Q are two planar posets (for the same n), and p : P → Q is a morphism of posets (i.e. a weakly order-preserving map of sets, with no conditions on the planar structures). Then let BS(p) = BS(P → Q) be the subvariety of BS(P) × BS(Q) such that if p(s) = t, then the subspace corresponding to s is contained in the subspace corresponding to t. For example, a configuration of black and white checkers ∘• induces a morphism of posets p_{∘•} : P_{∘} → P_{•}, and X_{∘•} is an open subset of BS(p_{∘•} : P_{∘} → P_{•}).

Caution: Unlike BS(P), the Bott-Samelson variety BS(P → Q) may be singular. For example, if P = {(x, y) : x, y ∈ {0, 1}}, Q = {(x, y) : x, y − 1 ∈ {0, 1}}, p(x, y) = (x, y + 1), and dim(x, y) = x + y, then BS(p) (with n = 3) is the triangle variety (parametrizing points p_{1}, p_{2}, p_{3} and lines ℓ_{12}, ℓ_{23}, ℓ_{31} in ℙ^{2} with p_{i}, p_{j} ∈ ℓ_{ij}) and hence singular. Also, X_{∘•} need not be dense in BS(P_{∘} → P_{•}); see Section 3.12 (b).

5.6. Relating X_{•} ∪ X_{•_{next}} to the simpler variety BS(P_{□}) via X_{•□}. Let P_{□} be the poset of Figure 18. Then BS(P_{□}) parametrizes hyperplanes V_{y} and V_{y′}, and a codimension 2 subspace V_{x} ⊂ V_{y}, V_{y′}. (Of course V_{z} = K^{n}.) The variety BS(P_{□}) has one divisorial stratum D_{□}, corresponding to V_{y} = V_{y′}. This variety will play a central role in the proof.

It will be useful to describe X_{•} ∪ X_{•_{next}} in terms of BS(P_{□}) and D_{□}. We do this by way of a variety X_{•□} which is a certain open subset of BS(p_{•□} : P_{•} → P_{□}) (defined in Sect. 5.7) whose image in BS(P_{•}) is X_{•} ∪ X_{•_{next}}, where p_{•□} is the morphism of posets depicted in Figure 19.

x  y  z y′

Figure 19. A pictorial depiction of p_{•□} : P_{•} → P_{□}; elements of p_{•□}^{−1}(x), p_{•□}^{−1}(y), p_{•□}^{−1}(y′), p_{•□}^{−1}(z) lie in regions labeled x, y, y′, z respectively.

5.7. First description of X_{•□}. Suppose the descending checker is at (r, c). Let

S_{c−1} ⊂ S_{c} ⊂ ⋯ ⊂ S_{n} (3)

be the subspaces corresponding to elements of P_{•} in the bottom row of the table (part of the flag F_{·}). (Subscripts denote dimension.) Let

T_{0} ⊂ T_{1} ⊂ ⋯ ⊂ T_{n} (4)

be the subspaces corresponding to the northeast border of P_{•} (part of the flag M_{·}). Define X_{•□} to be the locally closed subvariety of (X_{•} ∪ X_{•_{next}}) × BS(P_{□}) such that

V_{x} ∩ T_{r+1} = T_{r−1}, V_{y′} ∩ T_{r+1} = T_{r}, V_{y} ∩ S_{c} = S_{c−1}. (5)

Then the vector spaces corresponding to elements of P_{•} are determined by V_{x}, V_{y}, V_{y′}, and

S_{c} ⊂ S_{c+1} ⊂ ⋯ ⊂ S_{n}, T_{0} ⊂ T_{1} ⊂ ⋯ ⊂ T_{r−2} ⊂ T_{r+1} ⊂ ⋯ ⊂ T_{n−1} ⊂ T_{n} (6)

as shown in Figure 20. (This is because each element of P_{•} and P_{•_{next}} is of the form inf(b, b′), for some b′ on the northeast border, and b in the bottom row of the table; and V_{inf(b,b′)} = V_{b} ∩ V_{b′} for any point of X_{•} and X_{•_{next}}. Hence V_{inf(b,b′)} is determined by (3)and (4), and thus (6)and V_{x}, V_{y}, V_{y′}.)

T_{1}^{T_{2}}^{⋮}^{T_{r−2}}^{T_{r+1} ∩ Vx (= T_{r−1})}^{T_{r+1} ∩ V_{y′} (= Tr)}^{T_{r+1}}^{⋮}^{T_{n−1}}^{Sn = Tn}^{S_{n−1} ∩ T_{2}}^{S_{n−1} ∩ T_{r+1} ∩ Vx}^{Sc ∩ T_{r+1}}^{Sc ∩ T_{n−1}}  ^{S_{n−1}}^{Sc}  ^{⋯}^{Sc ∩ T_{r+1} ∩ Vx}^{0}  ^{Sc ∩ T_{r+1} ∩ Vy}  ^{Sc ∩ T_{n−1} ∩ Vy}  ^{S_{n−1} ∩ T_{r−2}}^{S_{n−1} ∩ T_{r+1} ∩ V_{y′}}^{S_{n−1} ∩ T_{r+1}}^{S_{n−1} ∩ T_{n−1}}^{Sc ∩ T_{r+1} ∩ V_{y′}} ?^{Sc ∩ T_{r−2}}  ^{Sc ∩ Vy (= S_{c−1})}

Figure 20. Pictorial description of the morphism X_{•□} → X_{•} ∪ X_{•_{next}} (in the guise of the morphism X_{•□} → BS(P_{•}))

5.8. Second description of X_{•□}. Equivalently, X_{•□} parametrizes V_{x}, V_{y}, V_{y′}, and the partial flags S_{·} and T_{·} of (6)(not (3)and (4)), such that

• the partial flags S_{·} and T_{·} are transverse,

• T_{r−2} ⊂ T_{r+1} ∩ V_{x},

• V_{x} ⊂ V_{y}, V_{y′}, and

• V_{x} is transverse to S_{c} ∩ T_{r+1}. (As r + c ≥ n + 1, dim S_{c} ∩ T_{r+1} ≥ 2, so V_{y} and V_{y′} are also transverse to S_{c} ∩ T_{r+1}.)

If these conditions hold, we say that V_{x}, V_{y}, V_{y′}, S_{·}, T_{·}, are in X_{•□}-position.

The projection f_{••_{next}} : X_{•□} → X_{•} ∪ X_{•_{next}} is smooth and surjective: given an element of X_{•} ∪ X_{•_{next}}, where S_{·} and T_{·} are the partial flags of (3) and (4), the fiber corresponds to a choice of (V_{x}, V_{y}, V_{y′}) satisfying (5). More precisely, (i) let V_{y} = T_{r−1} + S_{c−1}, (ii) then choose V_{x} in V_{y} such that V_{x} ∩ T_{r+1} = T_{r−1} (or equivalently such that V_{x} ⊃ T_{r−1}), (iii) then let V_{y′} = V_{x} + T_{r}.

Similarly, the morphism f_{□} : X_{•□} → BS(P_{□}) is smooth and surjective; by the definition of X_{•□}-position, f_{□} expresses X_{•□} as an open subset of a tower of projective bundles over BS(P_{□}).

5.9. Note that f_{••_{next}}^{−1}X_{•_{next}} = f_{□}^{−1}D_{□} (see Figure 20 — V_{y} = V_{y′} iff S_{c} ∩T_{r+1} ∩V_{y} = S_{c} ∩T_{r+1} ∩ V_{y′}). This will allow us to translate questions about codimension one degenerations in the specialization order (involving X_{•_{next}} ⊂ X_{•} ∪X_{•_{next}}) to simpler facts about codimension one degenerations relating to D_{□} ⊂ BS(P_{□}). The notation f_{••_{next}} and f_{□} will not be used hereafter.

6. Proof of the Geometric Littlewood-Richardson rule

We now prove (the final version of) the Geometric Littlewood-Richardson rule, Theorem 3.10.

6.1. Strategy of proof. The strategy is as follows. Instead of considering the “divisor at ∞” of the closure of X_{∘•} in G(k, n) × (X_{•} ∪ X_{•_{next}}), we consider the corresponding divisor on closures of other sets in different sets in different spaces, shown in (7). (The varieties X_{∘•□} and X_{∘□} will be defined in Sect. 6.3, and the smoothness and surjectivity of the morphisms of the top row will be established. For convenience, let Z be Cl_{BS(P_{∘})×BS(P_{□} )} X_{∘□}.) There is a “divisor at ∞” on each of these varieties that behaves well with respect to pullback by these morphisms; it corresponds to X_{•_{next}} ⊂ X_{•} ∪ X_{•_{next}} on the left and D_{□} ⊂ BS(P_{□}) on the right.

Cl_{BS(P_{∘})×(X_{•}∪X_{•_{next}})} X_{∘•} ⟵^{sm. surj.} Cl_{BS(P_{∘})×(X_{•}∪X_{•_{next}})} X_{∘•□} ⟶^{sm. surj.} Z := Cl_{BS(P_{∘})×BS(P_{□} )} X_{∘□}
↓ proper birat’l  ↓ closed imm.
Cl_{G(k,n)×(X_{•}∪X_{•_{next}})} X_{∘•}  BS(P_{∘} → P_{□})

(7)

We first identify the components of Cl_{BS(P_{∘})×(X_{•}∪X_{•_{next}})} X_{∘•} as follows. The components of “the divisor at ∞” of BS(P_{∘} → P_{□}) of dimension at least dim X_{∘□} − 1 are identified by Theorem 6.7. They are denoted D_{S}^{Z}, where S is a certain set of “good quadrilaterals” in the poset P_{∘}. This gives a list containing the components of the “divisor at ∞” of Z = Cl_{BS(P_{∘})×BS(P_{□} )} X_{∘□}. Via the smooth surjective morphisms of the top row of (7), this immediately gives a list containing the components, denoted D_{S}, of the “divisor at ∞” of Cl_{BS(P_{∘})×(X_{•}∪X_{•_{next}})} X_{∘•}.

We say D_{S} is geometrically irrelevant if its image in G(k, n) × X_{•_{next}} is of smaller dimension (and geometrically relevant otherwise). In Section 6.11, it is shown that all but one or two D_{S} (corresponding to those described in the Geometric Littlewood-Richardson rule) are geometrically irrelevant. We do this by exhibiting a one-parameter family through a general point of D_{S} contracted by the morphism to G(k, n) × X_{•_{next}}.

Next, in Section 6.14, we show that in the one or two geometrically relevant cases D_{S} appears with multiplicity one in the “divisor at ∞”, by showing that D_{S}^{Z} appears with multiplicity one in the corresponding divisor on Z.

Finally, these one or two D_{S}’s map are birational to (and hence map with degree 1 to) X_{∘_{stay}•_{next}} or X_{∘_{swap} •_{next}} (Proposition 6.16).

6.2. Remark. The bijection to puzzles of Section 7 gives a second proof; here is a very quick sketch. Fix a mid-sort configuration ∘•. First show that D_{X} contains both X_{∘_{stay}•_{next}} and/or X_{∘_{swap} •_{next}} (Sect. 6.14). By an easy induction, ∘• arises in the course of a checker game starting with some subsets α and β. Then D_{X} can have no more components, and these one or two must appear with multiplicity one. Otherwise, choose any γ such that the non-zero effective cycle D_{X} − \overline{X}_{∘_{stay}•_{next}}, D_{X} − \overline{X}_{∘_{swap} •_{next}}, or D_{X} − \overline{X}_{∘_{stay}•_{next}} − \overline{X}_{∘_{swap} •_{next}} has a non-zero coefficient of the basis element corresponding to γ. Then the number of puzzles with inputs α and β and output γ is strictly less than the Littlewood-Richardson coefficient c_{αβ}^{γ}, giving a contradiction.

One advantage of the proof presented in Section 6 is that in order to generalize the Geometric Littlewood-Richardson rule to other geometric situations (see for example [V2] and Conjecture 4.5), one needs the geometry behind it.

6.3. Reduction to BS(P_{□}). We first reduce much of the argument to statements involving the poset P_{□} (Figure 18) rather than the more complicated P_{•} as follows.

The composition of p_{∘•} : P_{∘} → P_{•} and p_{•□} : P_{•} → P_{□} is the morphism p_{∘□} : P_{∘} → P_{□} depicted in Figure 21. Let X_{∘□} be the open subset of BS(p_{∘□} : P_{∘} → P_{□}) such that if b ∈ P_{∘} and c ∈ P_{□}, then V_{b} ⊂ V_{c} if and only if p_{∘□}(b) ≺ c. (One could call this a “precise Bott-Samelson variety” of the morphism of posets, P BS(p_{∘□}). Then X_{∘•} = P BS(p_{∘•})|_{X_{•}}, X_{•□} = P BS(p_{•□})|_{X_{•}∪X_{•_{next}}}, and P BS(p) ⊂ BS(p) is an open immersion for all p. However, to minimize notation, we will not use this terminology.)

Define X_{∘•□} as a “triple fibered product” as in Figure 22, i.e. as the indirect limit of the lower part of the figure. Equivalently, X_{∘•□} is the open subset of X_{∘•} ×_{BS(P_{∘})} X_{∘□} whose image in BS(P_{•}) × BS(P_{□}) is in X_{•□}. Note that X_{∘•□} is an open subset of both X_{∘•} ×_{X_{•}∪X_{•_{next}}} X_{•□} and X_{∘□} ×_{BS(P_{□} )} X_{•□} (although not in general equal to either), so the projections from X_{∘•□} to X_{∘•} and X_{∘□} are both smooth (by base change from X_{•□} → X_{•} ∪ X_{•_{next}} and X_{•□} → BS(P_{□})). In addition, X_{∘•□} → X_{∘•} is surjective; the fiber corresponds to a certain (non-empty, open) choice of V_{x}, V_{y}, V_{y′}. Similarly, X_{∘•□} → X_{∘□} is surjective. This

= right good quadrilaterals = left good quadrilaterals y  y′ z  a′′ a′ x inf(a, a′)  Remove these to obtain P′_{∘} Remove these to obtain P′_{∘} a  0

Figure 21. p_{∘□} : P_{∘} → P_{□}, a, a′, a′′, P′_{∘}

smooth surj. smooth surj.

X_{∘•} X_{∘□}

X_{∘•□}

X_{•□}

BS(P_{∘})

BS(P_{□} )

smooth surj.

smooth

X_{•} ∪ X_{•_{next}}

surj.

Figure 22. The definition of X_{∘•□}

information is summarized in the top and bottom rows of (8).

X_{∘•}  ⟵_{surjective}^{smooth}  X_{∘•□}  ⟶_{surjective}^{smooth}  X_{∘□}
open ↓^{imm.}  ^{open} ↓^{imm.}  ^{open} ↓^{imm.}
Cl_{BS(P_{∘})×(X_{•}∪X_{•_{next}})} X_{∘•} ⟵_{surjective}^{smooth} Cl_{BS(P_{∘})×X_{•□}} X_{∘•□} ⟶_{surjective}^{smooth} Z = Cl_{BS(P_{∘})×BS(P_{□} )} X_{∘□}
proper ↓  ^{proper} ↓  ^{proper} ↓
X_{•} ∪ X_{•_{next}}  ⟵_{surjective}^{smooth}  X_{•□}  ⟶_{surjective}^{smooth}  BS(P_{□})

(8)

As remarked earlier, Cl_{BS(P_{∘})×BS(P_{□} )} X_{∘□} is denoted by Z. The morphism Cl_{BS(P_{∘})×X_{•□}} X_{∘•□} → Cl_{BS(P_{∘})×(X_{•}∪X_{•_{next}})} X_{∘•} is smooth and surjective for the same reason that X_{∘•□} → X_{∘•} and X_{•□} → X_{•} ∪X_{•_{next}} were: the fiber corresponds to choosing V_{x}, V_{y}, V_{y′}, satisfying the requirements of X_{•□}-position, except the transversality conditions with the spaces corresponding to elements of P_{•}, so this morphism is a tower of projective bundles.

6.4. The morphism Cl_{BS(P_{∘})×X_{•□}} X_{∘•□} → Z is smooth for the same reason that X_{∘•□} → X_{∘□} and X_{•□} → BS(P_{□}) were. More precisely, this morphism is constructed by choosing the S_{·}’s and T_{·}’s in (6):

(i) inductively choosing S_{i} (starting with i = n and decrementing) so that S_{i} contains (the subspace corresponding to) the maximum element of P_{∘} in column up to i, then

(ii) inductively choosing T_{i} (starting with i = n and decrementing) so that T_{i} contains

(the subspace corresponding to) the maximum element of P_{∘} in row up to i, then (iii) discarding the closed subset not in X_{•□}-position, and defining T_{r−1}, T_{r}, S_{c−1} by (5).

Note that (i) involves only the southwest border of P_{∘} (and not the element a shown in Figure 21), and (ii) involves only the northeast border (and not the elements a′ and a′′ shown in Figure 21).

6.5. Proof of the Geometric Littlewood-Richardson rule in the cases where p_{∘□}^{−1}(y) or p_{∘□}^{−1}(y′) is empty. This corresponds to the cases where there are no white checkers in the critical diagonal or the critical row, respectively (five of the nine cases of Table 2).

In the case p_{∘□}^{−1}(y′) = {}, the family Z → BS(P_{□}) is pulled back from a family over BS(P_{□} − {y′}), the partial flag parametrizing V_{x} ⊂ V_{y} ⊂ K^{n}. In particular, the pullback of D_{□} = {V_{y} = V_{y′}} to Z consists of one component, appearing with multiplicity 1. The corresponding divisor on Cl_{BS(P_{∘})×(X_{•}∪X_{•_{next}})} X_{∘•} also appears with multiplicity 1 by the

top row of (7) or the middle row of (8), and it is isomorphic to its image \overline{X}_{∘_{stay}•_{next}} in \overline{X}_{∘•}.

The same argument holds for the case p_{∘□}^{−1}(y) = {}, with the roles of y and y′ switched.

6.6. Proof in the remaining cases. For the rest of Section 6, we assume that both p_{∘□}^{−1}(y) (the critical diagonal) and p_{∘□}^{−1}(y′) (the critical row) are non-empty. The white checkers are in mid-sort, by Lemma 2.8. Let a (resp. a′, a′′) be the maximum of p_{∘□}^{−1}(y) (resp. p_{∘□}^{−1}(y′), p_{∘□}^{−1}(x)), so V_{a}, V_{a′}, V_{a′′} are the corresponding subspaces. (See Figure 21.)

In lieu of studying the components of the preimage of D_{□} on Z, we find the components of the pullback of D_{□} to the (a priori larger) variety BS(P_{∘} → P_{□}), and show that they all have dimension at most dim X_{∘□} − 1.

The pullback of D_{□} to BS(P_{∘} → P_{□}) is best described in terms of the stratification of BS(P_{∘}). Define the good quadrilaterals of P_{∘} to be those quadrilaterals whose minimal element does not dominate a, and either (a) whose minimal element dominates the white checker min(p_{∘□}^{−1}(y′)) in the critical row p_{∘□}^{−1}(y′), or (b) with two vertices dominating min(p_{∘□}^{−1}(y′)), and two vertices in p_{∘□}^{−1}({x, y}). Call those in case (a) right good quadrilaterals and those in case (b) left good quadrilaterals; see Figure 21. Note that the good quadrilaterals appear in columns, and that, if there is a blocker, there is no column to the left of the white checker in the critical row min(p_{∘□}^{−1}(y′)) (i.e. no left good quadrilaterals).

The following theorem describes the pullback of D_{□} to BS(P_{∘} → P_{□}).

6.7. Theorem. — The components of the pullback of D_{□} to BS(P_{∘} → P_{□}) of dimension at least dim X_{∘□} − 1 correspond to sets of good quadrilaterals, with at most one quadrilateral in each column, as follows. If S is such a set of good quadrilaterals, the corresponding component is the closure of the pullback to BS(P_{∘} → P_{□}) of the open stratum on BS(P_{∘}) corresponding to S. Its dimension is exactly dim X_{∘□} − 1.

Let D_{S}^{Z} be the component corresponding to S. Let D_{S} be the corresponding subvariety of BS(P_{∘}) × X_{•_{next}} (obtained via the top row of (7) or the middle row of (8)).

Proof. We note first that X_{∘□} can be constructed by starting with the dense open stratum of BS(P_{∘}), then choosing V_{y} containing V_{a} and V_{a′′} (giving a dimensional contribution of n − (dim a + dim a′′ − dim inf(a, a′)), as V_{a} ∩ V_{a′′} = V_{inf(a,a′)} for an element of the dense open stratum), then choosing V_{y′} containing V_{a′} (giving a dimensional contribution of n − dim a′). Then V_{x} = V_{y} ∩ V_{y′} is determined. Hence

(9) dim X_{∘□} = 2n − dim a − dim a′ − dim a′′ + dim inf(a, a′).

Next, consider an irreducible component of the pullback of D_{□} to BS(P_{∘} → P_{□}) of dimension at least dim X_{∘□} − 1. We will show that its dimension is precisely this, and that the component is of the form described in Theorem 6.7.

Let ℓ = dim(V_{a} ∩ V_{a′}) − dim inf(a, a′) for a general point of this component. (Note that ℓ ≥ 0, as V_{a} ∩ V_{a′} contains V_{inf(a,a′)}.) Let Q_{ℓ} ⊂ BS(P_{∘}) be the locus where dim(V ∩ V′) = ℓ + dim inf(a, a′). Then a dense open subset U of the component with a morphism to Q_{ℓ}, and U is an open set of the fibration over Q_{ℓ} parametrizing choices of V_{y} = V_{y′} containing V_{a} and V_{a′} (giving a dimensional contribution of n−(dim V_{a}+dim V_{a′} −dim(V_{a}∩V_{a′}))), and V_{x} contained in V_{y} = V_{y′} containing V_{a′′} (giving a dimensional contribution of n − 1 − dim V_{a′′} once V_{y} = V_{y′} is chosen). Thus by Proposition 6.8 below,

dim U ≤ dim Q_{ℓ} + (n − dim a − dim a′ + (ℓ + dim inf(a, a′))) + (n − 1 − dim a′′)
= (dim Q_{ℓ} + ℓ) + 2n − dim a − dim a′ − dim a′′ + dim inf(a, a′) − 1
≤ dim X_{∘□} − 1  (by (9)),

and if equality holds, then the the component is of the form desired (also by Proposition 6.8).

6.8. Proposition. — The irreducible components of Q_{ℓ} have codimension at least ℓ in BS(P_{∘}), and those components of codimension exactly ℓ are strata of the form described in Theorem 6.7.

Proof. Suppose P′_{∘} is defined by removing from P_{∘} all rows below a, and all elements of p_{∘□}^{−1}(x) except inf(a, a′) (see Figure 21). As in the proof of Lemma 5.2, the natural morphism BS(P_{∘}) → BS(P′_{∘}) is a tower of projective bundles , and the components of Q_{ℓ} on BS(P_{∘}) are precisely the pullback of components of the analogous Q_{ℓ} on BS(P′_{∘}). Hence the Proposition follows from the analogous result for BS(P′_{∘}), Proposition 6.9.

More precisely, it suffices to prove the result for P′_{∘} of the following form. Fix r_{1} < ⋯ < r_{y} and c_{1} < ⋯ < c_{x} where x, y > 1, and r_{1} < R_{1} < ⋯ < R_{z} < r_{y} and c_{2} > C_{1} > ⋯ > C_{z} > c_{1} ((R_{i}, C_{i}) will be location of white checkers not contained in the grid {(r_{i}, c_{j})}, for example a blocker). Then P′_{∘} is the poset generated by the set {(r_{1}, c_{i})}_{1≤i≤x} ∪ {(r_{i}, c_{1})}_{1≤i≤y} ∪ {(R_{i}, C_{i})}_{1≤i≤z} (see Sect. 5.4, and Figure 23 for an example). Note that the critical row corresponds to {(r_{1}, c_{2}), …, (r_{1}, c_{x})}, the critical diagonal corresponds to {(r_{2}, c_{1}), …, (r_{y}, c_{1})}, a = (r_{y}, c_{1}), a′ = (r_{1}, c_{x}), and inf(a, a′) = (r_{1}, c_{1}).

= right good quadrilaterals = left good quadrilaterals^{⋯} ^{(r1, cx) = a′}^{⋮}  top bottom^{(r1, c2)}^{(r2, c1)} left  ^{(R1, C1)}^{(Rz , Cz)}^{(r1, c1) = inf(a, a′)}^{(ry , c1) = a}  ^{(ry , cx)} right

Figure 23. An example of P′_{∘}

6.9. Proposition. — The irreducible components of Q_{ℓ} on BS(P′_{∘}) (described in the previous paragraph) have codimension at least ℓ in BS(P′_{∘}), and those components of codimension exactly ℓ are strata of the form described in Theorem 6.7 (corresponding to sets of good quadrilaterals, at most one per column).

Proof. For convenience, we assume dim inf(a, a′) = 0. (Geometrically, this corresponds to considering instead the quotient of all subspaces by V_{inf(a,a′)}.)

Fix an irreducible component of Q_{ℓ} of codimension at most ℓ, and choose a general point of this component; this corresponds to some configuration of subspaces {V_{c} ⊂ K^{m} : c ∈ P′_{∘}}. Label each element c of P′_{∘} with dim(V_{c} ∩ V_{a}). Hence the label on any vertex dominating a is dim a, and the label on a′ is ℓ. The label on any c ∈ P′_{∘} is at most dim c.

This point lies in some open stratum of BS(P′_{∘}); mark the quadrilaterals corresponding to that stratum with “=”. Then each labeled quadrilateral looks like one of the examples in Figure 24.

We argue by induction on the number of good quadrilaterals. The base case is given in

(c) and (d) below, and the inductive step is given in (a) and (b).

m mm  m m m m  m m  m m m  m m  m + 1 m + 1  m + 1 m + 1  m + 1 m  m m m  m m + 1  m + 1 m + 1 m + 1  m m  m + 1 m + 1 m + 1 m + 1  m + 2 m + 2

Figure 24. Possible quadrilaterals in proof of Proposition 6.9 (where c is labeled with dim(V_{c} ∩ V_{a}))

(a) First, if x > 2, consider the right-most column of good quadrilaterals (see Figure 25). The two vertices in the bottom row are labeled dim a, and the vertex in the upper right is labeled ℓ. The vertex in the upper left of the column is labeled either ℓ − 1 or ℓ. If it is labeled ℓ, then the resulting poset with the right-most column of vertices removed also satisfies the hypothesis of the Proposition, and hence by the inductive hypothesis there must be at least ℓ equal signs further to the left, of the desired form (all good quadrilaterals, at most one per column). Hence the Proposition holds in this case.

ℓ − 1 or ℓ dim a  ℓ dim a

Figure 25. The right-most column of quadrilaterals (in case (a) of the proof of Proposition 6.9)

If otherwise the vertex in the upper left corner of the right-most column of quadrilaterals is labeled ℓ−1, then by the inductive hypothesis there must be at least ℓ−1 equal signs further to the left, of the desired form. Furthermore, by inspection of Figure 24, there must be another equal sign in the right-most column as well, and again the Proposition holds. See Figure 26 for an example.

(b) Next suppose x = 2 (so there are no right good quadrilaterals), and there is at least one left good quadrilateral (hence there is no blocker). Let w = (r_{1}, c_{2}) (the rightmost element of the top row; this corresponds to the white checker in the critical row of ∘). The label on w must be 0 or 1, as dim w = 1. If w has label 0, then the Proposition follows immediately. If w has label 1, then the top left quadrilateral must be of one of the forms shown in Figure 27. In each case, we can remove the top two vertices of the good

1 2 2 3 4 5 5  2 3 3 3 4 5 5

Figure 26. Sample labeling of the right-most column of quadrilaterals (in case (a) of the proof of Proposition 6.9)

quadrilateral, and in all but the first case subtract 1 from each of the other vertices (as shown in Figure 27), and reduce to the case with one fewer good quadrilaterals. Hence by the inductive hypothesis, the last case cannot happen (there must be a second “=” in a good quadrilateral further below, yet we are allowed only ℓ = 1). The other cases may occur, and by our inductive hypothesis the Proposition holds.

0 1  1 0  1 0  ⟹ 0 1  0 1  1 0  ⟹  0 2  1 1  1 0  ⟹ 0 2  1 1  1 0  ⟹ w w  w w

Figure 27. The top (left) good quadrilateral (in case (b) of the proof of Proposition 6.9)

(c) Next, if there are no good quadrilaterals, and no blockers, then the labeled poset is the one shown in Figure 28, and the result is immediate.

0  0

Figure 28. The trivial case (i)(c) of the proof of Proposition 6.9

(d) Finally, suppose there are no good quadrilaterals (implying x = 2), and there is a blocker. As in (b), ℓ = 0 or 1. If ℓ = 0, the Proposition is immediate.

Assume now that ℓ = 1; we will obtain a contradiction. Re-label the poset by labeling element c with the dimension of the intersection of its corresponding vector space with V_{a′} (rather than V_{a}). Hence all labels are 0 or 1, and the elements on the right side and the bottom of the graph are labeled 1. Any quadrilateral with minimal element labeled 0 and other three elements labeled 1 must be marked with an “=” (see Figure 29). By hypothesis, as the component of Q_{1} has codimension at most 1 in BS(P′_{∘}), there can be at most one such quadrilateral. As the subset of elements labeled 0 has a maximum, which doesn’t lie on the right side or the bottom of the graph, there is at least one such quadrilateral, so there is exactly one. The component of Q_{1} lies in the (irreducible) divisorial stratum corresponding to this quadrilateral, so these two loci are equal. Thus a general point of this divisorial stratum lies in Q_{1}.

1 0 1 1 Figure 29.

We construct the divisorial stratum as a tower of ℙ^{1}-bundles over the partial flag variety parametrizing the subspaces corresponding to the vertices on the northeast border (as in the proof of Lemma 5.2, where the southwest border was used). There can be no quadrilateral labeled as in Figure 30 (with no “=”): V_{e} is a general subspace (of dim e) containing V_{c} and contained in V_{f}; as dim V_{d} ∩ V_{a′} = 0, we have dim V_{e} ∩ V_{a′} = 0 as well, so the label on the lower left vertex must be 0, not 1.

d 1  1 0  0 c  f e

Figure 30.

Now consider the part of the graph above row r_{2}, as in Figure 31. As there are no quadrilaterals marked as in Figure 30, all unlabeled vertices in Figure 31 must have label 1 (work inductively bottom to top, and left to right in each row), contradicting the fact that there is precisely one quadrilateral marked as in Figure 29.

6.10. Remark. The irreducible components of Q_{ℓ} correspond to sets of good quadrilaterals, at most one per column, such that each is in a higher row than any to its left. This describes the components of the pullback of D_{□} in Theorem 6.7 completely. To prove this, one must slightly refine case (a) of the proof of Proposition 6.9. However, this fact will not be needed.

0  1 1 1 1 1 1  1 Figure 31.

6.11. Geometric irrelevance of all but one or two divisors. We next show that all but one or two of the D_{S} ⊂ BS(P_{∘}) × X_{•_{next}} (defined immediately after the statement of Theorem 6.7) are geometrically irrelevant. Note that D_{{}} corresponds to the entry “stay” in Table 2, and D_{{top left good quad. }} corresponds to “swap”.

Proposition 6.12 shows that all other components are geometrically irrelevant, and Proposition 6.13 shows that D_{{}} is geometrically irrelevant as well when required to be by Table 2.

The following example may motivate the argument. Suppose ∘• is the configuration of black and white checkers shown in Figure 32, corresponding to planes in ℙ^{3}. Then a general point of X_{∘•} is depicted in Figure 33. The four points parametrized by black checkers are denoted b_{1}, b_{2}, b_{3}, b_{4}, and the three points parametrized by the white checkers are denoted p_{1}, p_{2}, p_{3}. The other subspaces parametrized by BS(P_{∘}) are two lines l_{12} and l_{23} (containing {p_{1}, p_{2}} and {p_{2}, p_{3}} respectively), and a plane f_{123}. For a fixed point of X_{•}, this locus clearly has dimension 2, (generically) one for the choice of p_{2} on the line b_{2}b_{3} and one for the choice of p_{3} on the line b_{3}b_{4}.

In the degeneration corresponding to X_{•_{next}}, b_{2} tends to b_{1} (and the line of approach ℓ is remembered). Note that there are two good quadrilaterals in P′_{∘}, one “left” and one “right”; denote them L and R. There are then three possible degenerations of Figure 33 (i.e. three components of D′_{X}), depicted in Figure 34.

ℓ_{23}^{p_{1}}  ^{f_{123}}^{p_{2}}^{b_{2}}  ^{b_{3}}  ^{p_{3}}^{b_{4}}^{ℓ_{23}}^{b_{1}} Figure 32.

b_{2}  b_{3} p_{2}  ℓ_{23} p_{3}b_{4} b^{1} = p^{2} ℓ_{12} f_{123}

Figure 33. A general point of X_{∘•} (where ∘• is given in Figure 32)

p_{1} = p_{2}  ^{f_{123}}  ^{p_{3}}^{ℓ_{23}}  ^{p_{1}}  ^{p_{1}}  ^{p_{3}}^{p_{3}} D_{{L}}  D_{{}}  D_{{R}}^{geometrically irrelevant}^{ℓ_{12}}^{ℓ}  ^{f_{123}}^{ℓ_{12}}^{p_{2}}  ^{ℓ_{23}}  ^{f_{123}}^{ℓ_{12} = ℓ_{23}}^{p_{2}}

Figure 34. Degenerations of Figure 33 (planes are denoted by arcs; a plane contains a line if the arc meets the line)

The first corresponds to the subset S = {L}, and is geometrically relevant. For a fixed point of X_{•_{next}}, this locus visibly has dimension 2, one for the choice of l_{12} through p_{1} = p_{2} = b_{1} = b_{2} in the plane spanned by ℓ and b_{3}, and one for the choice of p_{3} on the line b_{3}b_{4}.

The second corresponds to the subset S = {}, and is geometrically irrelevant. For a fixed point of X_{•_{next}}, this locus visibly has dimension 2, one for the choice of p_{2} on the line b_{1}b_{3}, and one for the choice of p_{3} on the line b_{3}b_{4}. However, the image in G(3, 4) = 𝔾(2, 3) has dimension 1, as the plane f_{123} depends only on the choice of p_{3}. This observation is a special case of Proposition 6.13.

The third corresponds to the subset {R}, and is also geometrically irrelevant. For a fixed point of X_{•_{next}}, this locus visibly has dimension 2, one for the choice of p_{2} on the line b_{1}b_{3}, and one for the choice of the plane f_{123} containing the line b_{1}b_{3}. Again, the image in G(3, 4) has dimension 1. This observation is a special case of Proposition 6.12.

Note that there is no component corresponding to S = {L, R}, as as the locus Q_{ℓ=2} on BS(P_{∘}) is empty (as dim a = dim a′ = 1, so ℓ := dim V_{a} ∩ V_{a′} − dim V_{inf(a,a′)} ≤ 1 − 0 = 1).

6.12. Proposition. — If S ≠ {}, {top left good quad. }, then D_{S} is geometrically irrelevant.

Proof. Note that the projection

Cl_{BS(P_{∘})×(X_{•}∪X_{•_{next}})} X_{∘•} → Cl_{G(k,n)×(X_{•}∪X_{•_{next}})} X_{∘•}

involves forgetting all elements of P_{∘} but the maximum, and that its construction (given in Sect. 6.4) depends only on the vector spaces on the northeast and southeast borders of P_{∘}. Fix a general point of D_{S}^{Z} (corresponding to a configuration of subspaces {V_{c} ⊂ K^{n} : c ∈ P_{∘}}). It will suffice to produce a one-parameter family through this point that preserves the spaces in the northeast and southwest borders. All possibilities for S fall into at least one of the following three cases.

Case 1: S contains a left good quadrilateral that is not the top left good quadrilateral. Name the elements of P_{∘} as in Figure 35 (showing the quadrilateral in question). Then a oneparameter family corresponds to fixing all V_{m} (m ∈ P_{∘}) except V_{d}, and letting V_{d} move freely in ℙ(V_{b}/V_{e}) ≅ ℙ^{1}.

(Note that this would fail if the left good quadrilateral were at the top. In this case, p_{∘□}(d) = x, but the V_{d} corresponding to a general element of ℙ(V_{b}/V_{e}) would lie in V_{y} = V_{y′}, and not necessarily in V_{x}.)

c p_{∘□} (b) = p_{∘□} (d) = y p_{∘□} (e) = x or y  p_{∘□} (c) = z b d e

Figure 35. Case 1 of Proposition 6.12

Case 2: S contains a right good quadrilateral q, and no quadrilaterals in the column directly to the left of q, and at least as high as q. Name the elements of P_{∘} as in Figure 36. The desired one-parameter family corresponds to fixing all the vector spaces V_{m} (m ∈ P_{∘}) except for V_{d}, V_{g_{1}}, …, V_{g_{m}}, and choosing V_{d} from an open set of ℙ(V_{b}/V_{e}) ≅ ℙ^{1}, such that V_{g_{i}} := V_{d} ∩ V_{h_{i}} has dimension dim g_{i} (1 ≤ i ≤ m). Note that V_{f_{i}} is automatically contained in V_{g_{i}} as V_{g_{i}} = V_{d} ∩ V_{h_{i}} contains V_{e} ∩ V_{h_{i}} = V_{f_{i}} by construction.

Case 3: S contains a right good quadrilateral q, and another good quadrilateral in the column directly to the left of q, at least as high as q. Name the elements of P_{∘} as in Figure 37. Then the argument from the Case 2 applies verbatim.

6.13. Proposition. — If S = {} and (i) the white checker in the critical row is in the descending checker’s square, or (ii) the white checker in the critical diagonal is in the rising checker’s square, then D_{S} is geometrically irrelevant.

q^{g_{m−1}}^{⋮}^{f_{1}}^{e}  ^{b}^{d}^{g_{m}}^{f_{m}}  ^{g_{1}}  ^{h_{m}}^{h_{m−1}}^{h_{1}}^{c}^{f_{m−1}}  ^{⋮}  y′ z

Figure 36. Case 2 of Proposition 6.12

q f_{m}  g_{1} e f_{1} ⋮  g_{m} b  c h_{1} ⋮ h_{m} d

Figure 37. Case 3 of Proposition 6.12

Proof. We deal with case (ii); case (i) is essentially identical and hence omitted.

As in the proof of Proposition 6.12, we note that the construction of Section 6.4 depended only on the vector spaces on the northeast and southeast borders of P_{∘}, but not the vector space on the northeast border in the critical row. Hence it will suffice to produce a one-parameter family through a general point of D_{S}^{Z} that preserves the spaces in the northeast and southwest borders, except the element of the critical row.

f_{1}  ^{⋯}  ^{f_{m}}^{g_{m}}^{g_{1}} x y  y′ z^{h_{1}}^{b}  ^{⋯}  ^{h_{m}}^{c} ^{e}  ^{d}

Figure 38.

Name the elements of P_{∘} as in Figure 38. As the point of D_{S}^{Z} maps to the dense open stratum of BS(P_{∘}), we have V_{h_{i}} = V_{c} + V_{g_{i}}; as V_{c} ⊂ V_{y} = V_{y′} and V_{g_{i}} ⊂ V_{y′}, we have V_{h_{i}} ⊂ V_{y} as well. The desired one-parameter family corresponds to fixing all the vector spaces V_{l} (l ∈ P_{∘}) except for V_{d}, V_{g_{1}}, …, V_{g_{m}}, and choosing V_{d} from an open set of ℙ(V_{b}/V_{e}) ≅ ℙ^{1}, such that V_{g_{i}} := V_{d} + V_{f_{i}} has dimension dim g_{i} (1 ≤ i ≤ m).

6.14. Multiplicity 1. We have shown that at most one or two of the components of D′_{X} are geometrically relevant. We now show that these one or two components appear with multiplicity 1 in Cl_{BS(P_{∘})×(X_{•}∪X_{•_{next}})} X_{∘•}. By the top row of (7) or the middle row of (8), it suffices to prove that the analogous divisors on Z appear with multiplicity 1.

6.15. Proposition. —

(a) The divisor D_{{}}^{Z} is contained in the pullback of D_{□} with multiplicity 1.

(b) The divisor D_{{top left good quad. }}^{Z} is contained in the pullback of D_{□} with multiplicity 1 if there is no blocker (i.e. there is a top left good quadrilateral).

Proof. (a) It suffices to verify the result in the preimage of the dense open stratum of BS(P_{∘}); it then suffices to verify the result for a fixed point of BS(P_{∘}). Here

V_{a} ∩ V_{a′} = V_{a} ∩ V_{a′′} = V_{inf(a,a′)}.

The Proposition then reduces to a straightforward (hence omitted) local calculation about the locus in BS(P_{□}) such that V_{x} contains V_{a′′}, V_{y} contains V_{a}, and V_{y′} contains V_{a′} (where V_{a}, V_{a′}, V_{a′′} are fixed).

(b) It suffices to verify the result in the preimage of the union of the dense open stratum of BS(P_{∘}) and the (divisorial) open stratum of BS(P_{∘}) corresponding to {top left good quad. }. This union admits a ℙ^{1}-fibration to the divisorial stratum of BS(P_{∘}), and it suffices to verify the result for a fixed fiber as follows. Name the elements of P_{∘} as in Figure 38. (Note that a′ = g_{m}, a′′ = f_{m}, e = inf(a, a′).) Hold fixed all the spaces of P_{∘} except those in the critical row {V_{d}, V_{g_{1}}, …, V_{g_{m}}}. The space V_{d} corresponding to the white checker varies in ℙ(V_{b}/V_{e}), and V_{g_{i}} is defined to be V_{d} + V_{f_{i}}. The Proposition then reduces to a straightforward (hence omitted) local calculation about the space parametrizing (V_{x}, V_{y}, V_{y′}, V_{d}) such that V_{d} varies in the pencil, V_{x} contains the fixed space V_{f_{m}}, V_{y} contains the fixed space V_{a}, and V_{y′} contains V_{g_{m}} = V_{d} + V_{f_{m}}.

Finally, we show that the map from D_{S} to Cl_{G(k,n)×(X_{•}∪X_{•_{next}})} X_{∘•} is birational to \overline{X}_{∘_{stay}•_{next}}

or \overline{X}_{∘_{swap} •_{next}}; this will conclude the proof of the Geometric Littlewood-Richardson rule.

6.16. Proposition. — (a) D_{\{\}} is birational to \overline{X}_{∘_{stay}•_{next}}. (b) D_{\{top left good quad. \}} is birational to \overline{X}_{∘_{swap}•_{next}}.

Proof. (a) The open subset of D_{{}} contained in the preimage of the dense open stratum of BS(P_{∘}) is isomorphic to X_{∘_{stay}•_{next}}. Sketch of reason: The subspaces parametrized by the dense open stratum are determined by the subspaces corresponding to the white checkers. (For c ∈ P_{∘}, V_{c} = span(V_{w}), where w runs over the white checkers dominated by c.) As in the construction of Section 6.4, choose (i) S_{i} to contain those V_{w} where w is a white checker in column at most i, and to contain no V_{w} where w is a white checker in column greater than i, and (ii) T_{i} analogously. This gives a subset of the “divisor at ∞” of Cl_{BS(P_{∘})×(X_{•}∪X_{•_{next}})} X_{∘•□} whose image in Cl_{BS(P_{∘})×(X_{•}∪X_{•_{next}})} X_{∘•} is X_{∘_{stay}•_{next}}.

(b) The open subset of D_{{top left good quad. }} contained in the preimage of the divisorial open stratum of BS(P_{∘}) corresponding to {top left good quad. } is isomorphic to X_{∘_{swap} •_{next}}. Sketch of reason: The subspaces parametrized by the divisorial open stratum are determined by the subspaces corresponding to

(i) the white checkers of ∘, except the white checkers at the opposite corners of the top left good quadrilateral (call them w_{1} = (r_{1}, c_{1}), w_{2} = (r_{2}, c_{2}), with r_{1} > r_{2}, c_{1} < c_{2}),

(ii) the vector space V_{w_{1}} = V_{w_{2}}, and (iii) V_{sup(w_{1},w_{2})} (corresponding to the lower right corner of the top left good quadrilateral).

We can interpret these subspaces as follows. Identify w_{1} and w_{2} of P_{∘} to obtain the poset P_{∘_{swap}}. The spaces described above correspond to those elements of P_{∘_{swap}} with exactly one edge to a lower-dimensional element (i.e. those w such that there is a unique covering relation w′ ≺ w). They also correspond to the white checkers of ∘_{swap}. As in (a), the image in Cl_{BS(P_{∘})×(X_{•}∪X_{•_{next}})} X_{∘•} is (naturally isomorphic to) X_{∘_{swap} •_{next}}. (The white checker of ∘_{swap} corresponding V_{w_{1}} = V_{w_{2}} must lie in the intersection of the spaces where V_{w_{1}} and V_{w_{2}} were required to lie, in the definition of X_{∘•}. Hence this checker lies in (r_{2}, c_{1}). The white checker of ∘_{swap}•_{next} corresponding to V_{sup(w_{1},w_{2})} is required to lie in (r_{1}, c_{2}), as it was in X_{∘•}.)

7. Appendix: The bijection between checker games and puzzles (with A. Knutson)

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 (1 < m ≤ n) corresponds to the part of the checker game 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 checker game; this will give the bijection.

We now describe an injection from checker games to puzzles; to each checker game we will associate a 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 checker game 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 should be able to show combinatorially that if a partially-filled-in puzzle doesn’t correspond to a valid checker game (in progress), then there is no way to complete it.

7.1. Bijection of starting positions. 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.)

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

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

Figure 39. The puzzle in the process of being filled

b  a  c

Figure 40. The corresponding point in the checker game

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 checker games. Each case is depicted in Figure 44, 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.

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

Figure 41. The rows of the white checkers

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

Figure 42. The columns of the white checkers

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 43. How to locate the white checker given the partially completed puzzle (r is the row and c is the column; see Figures 40 and 42 to interpret them as numbers)

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

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.

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.

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 blacker 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 39, and make a series of checker moves to move the descending checker to the row of the lower white checker in question.

References

[B1] A. S. Buch, A Littlewood-Richardson rule for the K-theory of Grassmannians, preprint 2000, math.AG/0004137, Acta Math., to appear.

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

[BKT] A. S. Buch, A. Kresch, and H. Tamvakis, Gromov-Witten invariants on Grassmannians, preprint 2003,

        http://home.imf.au.dk/abuch/papers/.

[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.

[FP] W. Fulton and P. Pragacz, Schubert varieties and degeneracy loci, Lecture Notes in Math., 1689, Springer-Verlag, Berlin, 1998.

[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, preprint 2001, math.AT/0112150, Duke Math. J., to appear.

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 2 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 44. How to place the next piece in the puzzle?

[KTW] A. Knutson, T. Tao, and C. Woodward, The honeycomb model of GL(n) tensor products II: Puzzles give facets of the L-R cone, preprint 2001, math.CO/0107011, J. Amer. Math. Soc., to appear.

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

[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), pp. 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.

[St1] 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.

[St2] R. Stanley, Positivity problems and conjectures in algebraic combinatorics, Mathematics: Frontiers and perspectives, 295–319, Amer. Math. Soc., Providence, RI, 2000.

[T] T. Tao, personal communication.

[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.

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

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