# A Combinatorial Approach to Multiplicity-Free Richardson Subvarieties of the Grassmannian

Michelle Snider¹

¹Cornell University, Ithaca, NY 14853, USA.

**Abstract.** We consider Buch's rule for K-theory of the Grassmannian, in the Schur multiplicity-free cases classified by Stembridge. Using a result of Knutson, one sees that Buch's coefficients are related to Möbius inversion. We give a direct combinatorial proof of this by considering the product expansion for Grassmannian Grothendieck polynomials. We end with an extension to the multiplicity-free cases of Thomas and Yong.

**Résumé.** On examine la règle de Buch pour la K-théorie de la variété grassmannienne dans les cas sans multiplicité de Schur, qui ont étés classifiés par Stembridge. En utilisant un résultat de Knutson, on démontre que les coefficients de Buch sont liés à l'inversion de Möbius. On en fait une preuve directe et combinatoire qui passe par le développement de produits de polynômes de Grothendieck. Pour conclure, on donne une application de cette théorie aux cas sans multiplicité de Thomas et Yong.

**Keywords:** Grassmannian, Richardson varieties, Grothendieck polynomials, Schur multiplicity free

# 1 Motivation

## 1.1 Schubert and Richardson varieties

We consider the **Grassmannian** $Gr_k\mathbb{C}^n := \{V \le \mathbb{C}^n | \dim(V) = k\}$. For a partition $\lambda$ contained in a $k \times (n-k)$ box, consider the path from the northeast corner to its southwest corner of the box that traces the partition. For the standard flag $(C_i = (*_1, \dots, *_i, 0, \dots, 0))$, we define the **Schubert variety** as

$$X_{\lambda} = \{V \in Gr_k\mathbb{C}^n | \dim(V \cap C_i) \ge \#(\text{ south steps in the first } i \text{ steps of the path })\}.$$

We denote the **Schubert class** in cohomology as $S_{\lambda} := [X_{\lambda}]_H \in H^*(Gr_k\mathbb{C}^n)$. The set

$$\{S_{\lambda} | \lambda \subset k \times (n-k) \text{ box}\}$$

forms a $\mathbb{Z}$-basis for $H^*(Gr_k\mathbb{C}^n)$, where

$$S_{\lambda}S_{\mu} = \sum c_{\lambda\mu}^{\nu}S_{\nu}$$

1365–8050 © 2009 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France
for $|\nu| = |\lambda| + |\mu|$, $\nu \subset k \times (n-k)$ box, and $c_{\lambda\mu}^{\nu}$ the Littlewood-Richardson coefficients. This follows from the surjective homomorphism

$$ \{\text{ring of symmetric polynomials}\} \to \{H^*(Gr_k\mathbb{C}^n)\} $$

$$ s_{\lambda} \mapsto \begin{cases} S_{\lambda}, & \text{if } \lambda \text{ fits in } k \times (n-k) \text{ box;} \\ 0, & \text{otherwise.} \end{cases} $$

for Schur functions $s_\lambda$.

The Möbius function $\mu_P(\nu)$ is defined recursively on a poset $\mathcal{P}$ as the unique function satisfying

$$ \sum_{\alpha \ge \mathcal{P}\nu} \mu_{\mathcal{P}}(\alpha) = 1 $$

The connection of this definition to K-classes is shown in [Kn08]. Since we are primarily interested in working in K-theory, we will use $[A]$ to denote the K-class of a subscheme of $A$, and $[A]_H$ to denote its homology class. Any subvariety $X$ of a flag manifold is rationally equivalent to a linear combination of Schubert cycles with uniquely determined non-negative integer coefficients [Br03]. We say $X$ is **multiplicity-free** if these coefficients are 0 or 1.

**Theorem 1** [Kn08] Let $X$ be a multiplicity-free irreducible subvariety of $G/P$, in the sense of [Br03], with $[X]_H = \sum_{d \in D} [X_d]_H$, $D$ a subset of the Bruhat order, and $P$ a parabolic subgroup. Let $\mathcal{P} \subseteq W/W_P$ be the set of Schubert varieties contained in $\cup_{d \in D} X_d$ (an order ideal in the Bruhat order on $W/W_P$). Then as an element of $K(G/P)$,

$$ [X] = \sum_{X_e \subseteq \cup_{d \in D} X_d} \mu_P(X_e) [X_e]. $$

We will give an independent combinatorial proof of this fact in the case that $X$ is a multiplicity-free **Richardson variety** in a Grassmannian, the intersection of a Schubert variety $X_\lambda$ with an opposite Schubert variety $w_0 \cdot X_\mu$, for $w_0$ the longest word. For any $X_\lambda \subset Gr_k\mathbb{C}^n$, let $G_\lambda := [X_\lambda]$. We have that $\{G_\lambda | \lambda \subset k \times (n-k) \text{ box}\}$ form a basis for $K(Gr_k\mathbb{C}^n)$. For certain symmetric polynomials $g_\lambda$ which we will define in the next section, we have a surjective homomorphism [Bu02]:

$$ \{\text{ring of symmetric functions}\} \to \{K(Gr_k\mathbb{C}^n)\} $$

$$ g_{\lambda} \mapsto \begin{cases} G_{\lambda}, & \text{if } \lambda \text{ fits in } k \times (n-k) \text{ box;} \\ 0, & \text{otherwise.} \end{cases} $$

Our main theorem will show that, for a poset $\mathcal{P}$ that we will define,

$$ G_{\lambda} \cdot G_{\mu} = \sum_{\nu} \mu_{\mathcal{P}}(G_{\nu}) G_{\lambda} $$

where the sum is over $\nu$ such that $\nu \subseteq (k \times n - k)$ box and $|\nu| \ge |\lambda| + |\mu|$. Our proof will proceed with sign-reversing involutions on this poset, and many reductions in the sizes of the partitions in the product.
## 1.2 Grothendieck Polynomials

For finite non-empty sets in $\mathbb{Z}^+$, $a$ and $b$, we say $a < b$ if $\max(a) < \min(b)$, and $a \le b$ if $\max(a) \le \min(b)$. For a partition $\lambda$, Buch defined a **set-valued (English) tableau (SVT)** as a filling of a Young diagram with nonempty sets in $\mathbb{Z}^+$ [Bu02]. If each box has a single entry, it is a **Young tableau**. A tableau is a **semistandard tableau (SS)** if it is weakly increasing across rows and strictly increasing down columns. The **superstandard** filling of a tableau is the one in which each box $(i, j)$ has a single entry, $i$ (its row). In all of our examples, we will use numbers smaller than 10, so we can avoid the use of set notation: we use 45 to denote the set $\{4, 5\}$.

Recall the combinatorial definition for the Schur polynomials,

$$s_{\lambda} = \sum_{T \in SSYT(\lambda)} x^T.$$

We consider the **Grothendieck polynomials** $g_{\lambda}$ of Lascoux and Schützenberger [LS82]. For $\lambda$ a partition, Buch [Bu02] gives the formula

$$g_{\lambda} = \sum_{T \in SS-SVT(\lambda)} (-1)^{|T|-|\lambda|} x^T$$

where

$$|T| = \sum_{i,j} |T(i,j)|.$$

He proves that this is a special case of the Lascoux-Schützenberger formula (which we will not need) for $g_{\pi}$ in the case when $\pi$ is a Grassmannian permutation. These are the $\{g_{\lambda}\}$ representing the $G_{\lambda}$ in section 1.1. As with the Schur polynomials, it is not obvious from the combinatorial definition that these polynomials are in fact symmetric and a basis for the symmetric polynomials [Bu02]. Linear independence follows from the fact that the lowest homogeneous component of $g_{\lambda}$ is $s_{\lambda}$.

We define the **word of a tableau** $w(T)$ to be the entries read right to left, top to bottom. Note that entries in a set are listed in increasing order, so that they occur in decreasing order in the word. A word is called a **reverse lattice word (RLW)** if for any initial string (e.g. 001 in 001110101),

$$multiplicity(i) \geq multiplicity(i+1) \quad \forall i \geq 1$$

A word that satisfies this condition is sometimes called an **election word** (or ballot sequence). For tableaux of shape $\lambda$ and $\mu$, we define the shape $\lambda \times \mu$ as the skew tableau formed by placing $\mu$ directly southwest of $\lambda$. When we refer to a filling of the shape $\lambda \times \mu$, we will call $\lambda$ the “northeast” partition, and $\mu$ the “southwest” partition. Buch [Bu02] gives a combinatorial rule for the product of two Grothendieck polynomials:

$$g_{\lambda}g_{\mu} = \sum c'_{\lambda\mu} g_{\nu}$$

where the coefficients are given by

$$c'_{\lambda\mu} = (-1)^{|\nu|-|\lambda|-|\mu|} \#(T)$$
for SS-SVT $T$ of shape $\lambda \times \mu$, content $\nu$, with $w(T)$ a RLW. We call these the K-theoretic Littlewood-Richardson numbers, since if $|\nu| = |\lambda| + |\mu|$, then $c'_{\lambda\mu}^{\nu} = c_{\lambda\mu}^{\nu}$, the usual Littlewood-Richardson number. Figure 1 shows the calculation of the expansion of $g_1 \cdot g_1$.

<figure><img src="image_1.png" /><figcaption>Fig. 1: $g_1g_1 = g_2 + g_{11} - g_{21}$</figcaption></figure>

First, we note that the reverse lattice word condition requires that the filling of the northeast tableau $\lambda$ always be superstandard. We will construct a poset out of all of the allowed fillings of the southwest tableau $\mu$, where each vertex is labeled with all tableaux of a given content, and for vertices $\nu, \nu', \nu \le_P \nu'$ if $content(\nu) \supset content(\nu')$. We are interested in a poset, since its Möbius function will allow us to compute structure constants. Note that for each tableau, the row in the poset corresponds to the number of “extra” elements in the filling (e.g. the top row has only semistandard Young tableaux, corresponding to the product $s_{\lambda} \cdot s_{\mu}$).

**Example 1** Consider the product $G_{2,1} \cdot G_{2,2}$ and its poset in Figure 2. From the second line of this poset, we can see that the coefficient of $G_{431}$ is 2 since there are two tableaux on the corresponding vertex, while $G_{422}$ has coefficient 1. Note that this product is H-multiplicity-free, but not K-multiplicity-free. The K-multiplicity-free cases are extremely rare, occurring only when both partitions $\lambda$ and $\mu$ are rectangles or one of them is a single box or empty ([Bu02, Proposition 7.2]).

<figure><img src="image_2.png" /><figcaption>Fig. 2: The poset corresponding to $G_{2,1} \cdot G_{2,2}$: the product satisfies Stembridge cases (3) and (4) from Theorem 3.</figcaption></figure>

We will consider our products as being inside an ambient box of size $k \times (n-k)$. That is, we limit the terms in the expansion to those indexed by partitions that fit inside this box. We note that this restriction
gives us a sub-poset of the full poset. The Möbius function on the remaining terms is unaffected by the removal of vertices with content exceeding the box size, since all terms above a vertex $\nu$ have content contained in the content of $\nu$. That is, for a given vertex $\nu$ with content in the ambient box, no vertex in its upwards order ideal will have content exceeding the ambient box. We are interested in cases in which the terms in the Grothendieck expansion which correspond to the Schur expansion are multiplicity-free, i.e. that their coefficients are 0 or 1.

Then Theorem 1 implies the following:

**Theorem 2** Consider partitions $\lambda = (\lambda_1^{\beta_1}, \dots, \lambda_l^{\beta_l})$ and $\mu = (\mu_1^{\alpha_1}, \dots, \mu_m^{\alpha_m})$ such that $G_\lambda \cdot G_\mu$ in a $k \times (n-k)$ box is a Schur-multiplicity-free product. In the corresponding poset, for each vertex $\nu'$, $\mu(\nu')$ gives the coefficient of $G_\nu$ in the Buch expansion of the product, where $\nu = \nu' \cup (1^{\lambda_1}, \dots, l^{\lambda_l})$.

These Schur-multiplicity-free cases have been classified by Stembridge [St01] as follows, and our proof explicitly uses his analysis. We begin by recalling Stembridge's definitions and classification of Schur-multiplicity-free cases.

**Definition 1** [St01] A partition $\mu$ with at most one part size (i.e., empty, or of the form $(c^r)$ for suitable $c, r > 0$) is said to be a **rectangle**. If it has $k$ rows or $k$ columns (i.e., $k = r$ or $k = c$), then we say $\nu$ is a **k-line rectangle**. A partition $\mu$ with exactly two part sizes (i.e., $\mu = (b^r c^s)$ for suitable $b > c > 0$ and $r, s > 0$) is said to be a **fat hook**. If it is possible to obtain a rectangle by deleting a single row or column from the fat hook $\mu$, then we say that $\mu$ is a **near rectangle**.

We will call these **top, bottom, left, or right** near rectangles, to denote the location of the extra row or column. We say that a product of Schur functions is **multiplicity-free** if all of the Littlewood-Richardson coefficients of the expansion are 0 or 1.

**Theorem 3** [St01] The product of Schur functions $s_\lambda \cdot s_\mu$ is multiplicity-free if and only if

1. $\lambda$ and $\mu$ are rectangles, or

2. (Pieri rule) $\lambda$ is arbitrary, and $\mu$ is a 1-line rectangle

3. $\lambda$ is a rectangle and $\mu$ is a near-rectangle

4. $\mu$ is a fat hook and $\lambda$ is a 2-line rectangle

We now mention some speculative geometry that motivated our combinatorial proof of Theorem 2. Buch shows that the expansion of $X_\lambda \cap (w_0 \cdot X_\mu)$ into Schubert classes has signs that alternate with dimension ([Bu02]). This suggests that there exists an exact sequence on sheaves

$$0 \to \mathcal{O}_{\bigcup_{\nu \in \mathcal{P}} X_\nu} \to \bigoplus_{T, |T|=|\nu|+1} \mathcal{O}_{X_{\text{content}(T)}} \to \dots \to \bigoplus_{T, |T|=|\nu|+k-1} \mathcal{O}_{X_{\text{content}(T)}} \to \dots \quad (1)$$

where the $k^{th}$ nonzero term sums over Buch Littlewood-Richardson tableaux with $k-1$ extra entries. This leads to a sequence for the point in the Grassmannian corresponding to each $\lambda$,

$$0 \to \mathbb{C}^1 \to \dots \to \bigoplus_{T, |T|=|\nu|+k-1, \text{content}(T) \subseteq \lambda} \mathbb{C}^1 \to \dots$$

One can hope that this sequence is in fact exact. Our main result is
**Theorem 4** There exists such an exact sequence of vector spaces, and it can be explicitly constructed as a direct sum of exact sequences with exactly two non-zero terms.

The proof requires an involution which pairs terms differing in size by one. In some cases, we provide a single rule that matches all terms required. In other cases however, we must resort to a multistage divide and conquer approach, where the involution is defined differently on several disjoint subsets. Assuming Theorem 4, we can prove Theorem 2 as a corollary.

**Proof of Theorem 2:** The exactness of the sequence (1) gives us that the alternating sum of dimensions is 0. Thus the sum of the coefficients of the pairs of Buch tableaux, with signs alternating with number of extra numbers (i.e. how many more than a single entry), is also 0. Together with the extra 1 from the single fixed point tableau, this is equivalent to the statement that the coefficient of $v'$ is given by the Möbius function. □

## 2 An Extension to the Thomas-Yong Cases

Consider partitions $\lambda$ and $\mu$ in a $(k \times (n - k))$ box. We will review the notation introduced in [TY07]. We call $R = (\lambda, \mu, k \times (n - k))$ a **Richardson quadruple**, and use the notation $\text{poset}(R)$ to denote the associated poset of allowed fillings of $\mu$. Place $\lambda$ in the upper left corner of the box, then rotate $\mu$ by $180^\circ$ (call this **rotate**($\mu$)) and place it in the lower right corner. This quadruple $(\lambda, \mu, k \times (n - k))$ is called **basic** if $\lambda \cup \text{rotate}(\mu)$ does not contain any full rows or columns. If it is not basic, we can remove all full rows and columns to get a **basic demolition** $\tilde{R} = (\tilde{\lambda}, \tilde{\mu}, \tilde{k} \times (\tilde{n} - \tilde{k}))$. We call each row (column) removal a **row (column) demolition**. Notice that if $\lambda \cap \text{rotate}(\mu) \neq \emptyset$, then $G_\lambda \cdot G_\mu = 0$, so the demolition is undefined. In order to determine whether a Richardson quadruple is multiplicity-free, we consider its basic demolition.

**Theorem 5** [TY07] A Richardson quadruple is multiplicity-free if and only if its basic Richardson quadruple is multiplicity-free. If a basic demolition of a Richardson quadruple $(\lambda, \mu, k \times n - k)$ is multiplicity-free, then it must be in the cases classified by [St01].

For example, consider the case $((4, 4, 2, 2, 1), (4, 3, 2, 1), 5 \times 5)$. This product is not multiplicity-free, but has a basic demolition of $(1, 1, 2 \times 2)$, which is multiplicity-free.

We will show that our analysis of the [St01] multiplicity-free cases extends to this larger class of products by showing that the posets of a Richardson quadruple and its basic demolition are isomorphic. Let us define the **accessible word** $w_A$ as the independent values of $\lambda$ read in increasing order, or equivalently

$$w_A(j) = 1 + \#(\text{rows of } \lambda \text{ in column } n - k - j).$$

**Lemma 1 (Column Demolition Lemma)** For $\tilde{R} = (\lambda, \mu, k \times (n - k))$, if column $c$ is full, let $\tilde{R}$ be the quadruple with column $c$ removed. Then $\text{poset}(\tilde{R})$ is isomorphic to $\text{poset}(R)$.

Let $\lambda = (\lambda_1, \dots, \lambda_l)$ and $\mu = (\mu_1, \dots, \mu_m)$. There is a full row in the diagram if and only if $\lambda_r + \mu_{k-r+1} = n - k$.

**Lemma 2** For $R = (\lambda, \mu, k \times (n - k))$, if $\lambda_1 = n - k$, let $\tilde{R}$ be the quadruple with $\lambda_1$ removed. Then $\text{poset}(R)$ is isomorphic to $\text{poset}(\tilde{R})$ for $\tilde{R} = ((\lambda_2, \dots, \lambda_l), \mu, (k - 1) \times (n - k))$.
**Lemma 3 (Row Demolition Lemma)** For $R = (\lambda, \mu, k \times (n-k))$, if row $r$ is full, then the poset($\tilde{R}$) is isomorphic to poset($R$).

We note that basic demolition is well defined, i.e. independent of the order of full column/row removal, thus so are the corresponding isomorphisms between posets.

Figure 3 is an example of a case with both a full row and column. (This product is Stembridge multiplicity-free in any ambient box, but is a good example of the row and column demolition com-mutativity.)

<figure><img src="image_3.png" /><figcaption>Fig. 3: Two demolition paths of ((2, 2), (2, 1), 3 × 3) to ((1), (1), 2 × 2).</figcaption></figure>

**Proposition 1** *Theorem 4 holds for any Richardson quadruple whose basic demolition is a Stembridge case.*

Acknowledgements

I would like to extend special thanks to Allen Knutson for both the statement of the question and contin-
ing guidance throughout the process.

References

[Br03] M. Brion, Multiplicity-free subvarieties of flag varieties, Contemporary Math. 331, 13-23, Amer. Math. Soc., Providence, 2003. math.AG/0211028

[Bu02] A. Buch, A Littlewood-Richardson rule for the $K$-theory of Grassmannians, Acta Math. 189 (2002), no. 1, 37–78. math.AG/0004137
[St01] J.R. Stembridge, Multiplicity-free products of Schur functions, Annals of Combinatorics (2001), no. 5, 113–121

[TY07] H. Thomas, A. Yong, Multiplicity-free Schubert calculus, (2007). math/0511537

[Kn08] A. Knutson, Frobenius splitting and Möbius inversion, In preparation (2008)

[LS82] A. Lascoux and M.-P. Schützenberger, Structure de Hopf de l'anneau de cohomologie et de l'anneau de Grothendieck d'une variété de drapeaux, C. R. Acad. Sci. Paris Sér. I Math. 295 (1982), no. 11, 629633. MR 84b:14030