# Genomic Tableaux and Combinatorial K-Theory

Oliver Pechenik<fnref n="1" />† and Alexander Yong<fnref n="1" />‡

**Abstract.** We introduce genomic tableaux, with applications to Schubert calculus. We report a combinatorial rule for structure coefficients in the torus-equivariant *K*-theory of Grassmannians for the basis of Schubert structure sheaves. This rule is positive in the sense of [Anderson-Griffeth-Miller '11]. We thereby deduce an earlier conjecture of [Thomas-Yong '13] for the coefficients. Moreover, our rule specializes to give a new Schubert calculus rule in the (non-equivariant) *K*-theory of Grassmannians. From this perspective, we also obtain a new rule for *K*-theoretic Schubert structure constants of maximal orthogonal Grassmannians, and give conjectural bounds on such constants for Lagrangian Grassmannians.

**Résumé.** Nous introduisons la notion de tableau génomique, pour l'appliquer au calcul de Schubert. Nous énonçons une règle combinatoire pour les coefficients de structure de la *K*-théorie tore-équivariante des grassmanniennes, dans la base définie par les classes des faisceaux structuraux des variétés de Schubert. Cette règle est positive au sens de [Anderson-Griffeth-Miller '11]. Nous en déduisons une conjecture de [Thomas-Yong '13]. De plus, notre règle se spécialise en une règle nouvelle pour le calcul de Schubert dans la *K*-théorie (non équivariante) des grassmanniennes. Nous obtenons également une nouvelle règle pour les coefficients de structure de la *K*-théorie des grassmanniennes orthogonales maximales dans la base de Schubert, et nous conjecturons certaines bornes pour ces coefficients dans le cas des grassmanniennes lagrangiennes.

**Keywords:** Schubert calculus, equivariant *K*-theory, Grassmannians, genomic tableaux

# 1 Introduction

## 1.1 Main Result: Equivariant *K*-theory of Grassmannians

Let $X = \text{Gr}_k(\mathbb{C}^n)$ denote the Grassmannian of $k$-dimensional planes in $\mathbb{C}^n$. The natural action of $\text{GL}_n(\mathbb{C})$ on $X$ restricts to an action of the Borel subgroup $B$ of invertible upper triangular matrices and its subgroup $T$ of invertible diagonal matrices. The $T$-fixed points $e_\lambda \in X$ are naturally indexed by Young diagrams $\lambda$ contained in the rectangle $\Omega := k \times (n-k)$. The **Schubert varieties** are defined as the orbit

<footnote n="1">¹Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA</footnote>

<footnote>†Email: pecheni2@illinois.edu. Supported by an NSF Graduate Research Fellowship, and Illinois Distinguished Fellowship from the University of Illinois, and NSF MCTP grant DMS 0838434.</footnote>

<footnote>‡Email: ayong@uiuc.edu. Supported by NSF grants and a Helen Corley Petit fellowship at UIUC.</footnote>
closures $X_λ = \overline{B_e}_e$. The classes $\{[X_λ]\}$ of their Poincaré duals form a $\mathbb{Z}$-basis of the cohomology ring $H^*(X, \mathbb{Z})$.

The (classical) **Schubert structure constants** $c_{\lambda, \mu}^{\nu}$ are defined by

$$[X_λ] \cdot [X_μ] = \sum_{ν \subseteq Ω} c_{λ,μ}^{ν}[X_ν].$$

The fact $c_{\lambda, \mu}^{\nu} \in \mathbb{Z}_{\ge 0}$ is geometrically interpreted in Schubert calculus as the statement that this number counts the number of points (when finite) in a generic triple intersection of Schubert varieties. Combinatorially, $c_{\lambda, \mu}^{\nu}$ is computed, in a manifestly nonnegative manner, by any of the Littlewood-Richardson rules. The first such rule was stated (with partial proof) by D. Littlewood-A. Richardson in the 1930s [LiRi34] in their study of the representation theory of symmetric groups. However, the first rigorous proof of a rule was given by M.-P. Schützenberger [Sc77] only in the 1970s.

In the modern Schubert calculus, substantial attention has turned to the problem of generalizing the above described work to richer cohomology theories. Early last decade, two problems of this type were solved. A. Buch [Bu02] found the first rule for the multiplication of the Schubert structure sheaves in the $K$-theory of Grassmannians. His rule was nonnegative, at least once one takes into account a predictable alternation of sign. Separately, in [KnTa03], *puzzles* (as opposed to Young tableaux) were introduced to give the first rule for equivariant Schubert calculus of Grassmannians that was positive in the sense of [Gr01].

We turn to the common unification of these problems, i.e., to combinatorially compute the Laurent polynomial $K_{\lambda, \mu}^{\nu} \in \mathbb{Z}[t_1^{\pm 1}, \dots, t_n^{\pm 1}]$ defined by

$$[\mathcal{O}_{X_λ}] \cdot [\mathcal{O}_{X_μ}] = \sum_{ν \subseteq Ω} K_{λ,μ}^{ν} [\mathcal{O}_{X_ν}]$$

where $[\mathcal{O}_{X_λ}]$ is the class of the Schubert structure sheaf in the $T$-equivariant $K$-theory ring $K_T(X)$. This problem may also be stated in terms of multiplication of *double Grothendieck polynomials* [LaSc82]. A partial summary of earlier contributions to this problem follows: A. Knutson–R. Vakil (reported in [CoVa05]) described a still-open conjectural formula for $K_{\lambda, \mu}^{\nu}$ in terms of puzzles. Later, “positivity” of $K_{\lambda, \mu}^{\nu}$ (in a more general context) was geometrically established by D. Anderson-S. Griffeth-E. Miller [AnGrMi11]. More recently, A. Knutson [Kn10] obtained a puzzle rule for a different Schubert calculus problem in $K_T(X)$, that of multiplying the class of a Schubert structure sheaf by that of an *opposite* Schubert structure sheaf. Also, H. Thomas and the second author conjectured the first Young tableau rule for $K_{\lambda, \mu}^{\nu}$ [ThYo13]. The latter rule is positive in the sense of [AnGrMi11].

We announce a proof of a new [AnGrMi11]-positive rule for $K_{\lambda, \mu}^{\nu}$ that allows us to deduce the conjectural rule of [ThYo13]. Indeed, our approach completes the strategy set out in [ThYo13]. The principal development of this paper towards this strategy is the introduction of *genomic tableaux*. (This paper does not use or contribute to mathematical biology in any way.)

## 1.2 Genomic edge-labeled tableaux

A **genomic tableau** is a Young diagram filled with (subscripted) labels $i_j$ where $i \in \mathbb{Z}_{>0}$ and the $j$'s that appear for each $i$ form an initial segment of $\mathbb{Z}_{>0}$. Such a tableau is **edge-labeled** of shape $\nu/\lambda$ if each horizontal edge of a box weakly below the southern border of $\lambda$ (interpreted as a ballot path from $(0, 0)$ to $(k, n-k)$) is filled with a subset of $\{i_j\}$.
We write $\mathbf{family}(i_j) = i$. Distinguish two orders on subscripted labels: $i_j < k_\ell$ if $i < k$; also $i_j \prec k_\ell$ if $i < k$ or $i = k$ with $j < \ell$. Note that $\prec$ is a total order, while many pairs are incomparable under $<$. For a box $\times$, let $\bar{\times}$ denote the upper horizontal edge of $\times$ and $\times$ denote the lower horizontal edge.

A genomic tableau $S$ is **semistandard** if the following hold: (1) every box-label is $\prec$-strictly smaller than any label to its right in its row; (2) every label is $<\prec$-strictly smaller than any label below in its column; (3) if $i_j, k_\ell$ appear on the same edge then $i \neq k$; (4) if $i_a$ is west of $i_b$, then $a \le b$. Let us refer to the labels $i_j$ (for fixed $i$ and $j$) collectively as a **gene**. The **content** of $T$ is the vector $(c_1, c_2, c_3, \dots)$ where $c_i$ is the number of genes of family $i$.

**Example 1.1** For $\lambda = (4, 2, 2, 1)$ and $\nu = (6, 5, 4, 3, 2)$, consider the genomic tableau $T$:

<figure><img src="image_1.png" /></figure>

The content of $T$ is $(3, 2, 2, 2)$. $T$ is not semistandard since the second column from the left fails condition (2) by having two labels of family 3. If we deleted the $3_2$ from the edge, the result would be semistandard.

## 1.3 Ballotness of genomic tableaux

A **genotype** $G$ of $T$ is a choice of one label from each gene of $T$. (The remainder of the genomic analogy is that each label of a gene is an *allele* and the other genes of the same family are *paralogs*.) Let $\text{word}(G)$ be obtained by reading family labels of $G$ down columns from right to left. (For multiple labels on an edge, read them from smallest to largest.) $G$ is **ballot** if in every initial segment of $\text{word}(G)$, there are (for each $i$) at least as many $i$'s as $i+1$'s. $T$ is **ballot** if all its genotypes are ballot.

**Example 1.2** Consider $T = \begin{array}{|c|c|} \hline 1_2 \\ \hline 1_1 & 2_1 \\ \hline \end{array}$ and $U = \begin{array}{|c|c|} \hline 1_1 \\ \hline 1_1 & 2_1 \\ \hline \end{array}$. Then $T$ is ballot since there is only one genotype (namely itself), and the reading word is the ballot sequence 121. On the other hand, $U$ is not ballot. It has two genotypes $\begin{array}{|c|c|} \hline 1_1 & 2_1 \\ \hline \end{array}$ and $\begin{array}{|c|c|} \hline 1_1 \\ \hline 2_1 \\ \hline \end{array}$ and the word for the former is 21, which is not ballot. The reader can check that the tableau of Example 1.1 is also not ballot. $\square$

## 1.4 Tableau weights and the $K_{\lambda, \mu}^{\nu}$ rule

For a box $\times$ define $\text{Man}(\times)$ to be the “Manhattan distance” from the southwest corner (point) of $\Omega$ to the northwest corner (point) of $\times$ (i.e., the length of any north and east lattice path between the corners).

For a gene $G$, define $N_G$ to be the number of genes $G'$ with $\mathbf{family}(G') = \mathbf{family}(G)$ and $G' \succ G$. For instance, in Example 1.1, $N_{1_1} = 2$ since the genes $1_2$ and $1_3$ are of the same family as $1_1$ (namely family 1) but $1_1 \prec 1_2, 1_3$. (Note that $N_G$ depends on the content of the tableau.)

Suppose $\ell \in \underline{\times}$ is an instance of $i_j$ and $\times$ is in row $r$. If $i > r$ then set $\text{edgefactor}(\ell) := 0$. Otherwise

$$ \text{edgefactor}(\ell) := 1 - \frac{t_{\text{Man}(\times)}}{t_{r-i+N_{i,j}+1+\text{Man}(\times)}}. $$
The **edge weight** edgewt(T) of T is $\prod_{\ell} \text{edgefactor}(\ell)$; the product is over all edge-labels of T.

A nonempty box x in row r is **productive** if family(label(x)) < r and family(label(x)) < family(label(x⁻)). (Here x⁻ is the box immediately right of x.) For a nonempty productive box x in row r with label iⱼ define

$$ \text{boxfactor}(x) := \frac{t_{\text{Man}(x)+1}}{t_{r-i+N_{i_j}+1+\text{Man}(x)}}. $$

If x is not productive, we set boxfactor(x) := 1. The **box weight** of T is 0 if any label of family i is in a box strictly north of row i. Otherwise, it is boxwt(T) := $\prod_{x} \text{boxfactor}(x)$, where the product is over all boxes of T. The **weight** of T is wt(T) := $(-1)^{d(T)} \times \text{boxwt}(T) \times \text{edgewt}(T)$. Here d(T) = (# genes counted with multiplicity) - (# genes counted without multiplicity).

Let

$$ L_{\lambda, \mu}^{\nu} := \sum_{T} \text{wt}(T), $$

where the sum is over all ballot semistandard genomic tableaux T of shape $\nu/\lambda$ and content $\mu$. The following provides the first theorem for an Anderson–Griffeth–Miller positive rule for $K_{\lambda, \mu}^{\nu}$:

**Theorem 1.3** $K_{\lambda, \mu}^{\nu} = L_{\lambda, \mu}^{\nu}$.

**Example 1.4** To compute $K_{(2),(2,1)}^{(2,2)}$ for $\text{Gr}_2(\mathbb{C}^4)$, the required tableaux are

$$ T_1 = \begin{array}{|c|c|} \hline \boxed{1} & \boxed{1} \\ \boxed{2} & \boxed{1} \\ \hline \end{array}, \quad T_2 = \begin{array}{|c|c|} \hline \boxed{1} & \boxed{1} \\ \boxed{2} & \boxed{1} \\ \hline \end{array}, \quad T_3 = \begin{array}{|c|c|} \hline \boxed{1} & \boxed{1} \\ \boxed{2} & \boxed{1} \\ \hline \end{array}, \quad T_4 = \begin{array}{|c|c|} \hline \boxed{1} & \boxed{1} \\ \boxed{1} & \boxed{2} \\ \hline \end{array}, \quad T_5 = \begin{array}{|c|c|} \hline \boxed{1} & \boxed{1} \\ \boxed{2} & \boxed{1} \\ \hline \end{array}. \quad \text{Then} $$

* edgewt(T₁) = 1 - t₁/t₂, boxwt(T₁) = t₃/t₄ and d(T₁) = 0

* edgewt(T₂) = 1 - t₂/t₃, boxwt(T₂) = t₃/t₄ and d(T₂) = 0

* edgewt(T₃) = (1 - t₁/t₂)(1 - t₂/t₃), boxwt(T₃) = t₃/t₄ and d(T₃) = 1

* edgewt(T₄) = (1 - t₃/t₄), boxwt(T₄) = t₂/t₄ and d(T₄) = 0

* edgewt(T₅) = (1 - t₁/t₂)(1 - t₃/t₄), boxwt(T₅) = t₂/t₄ and d(T₅) = 1

$$ \text{Hence } K_{(2),(2,1)}^{(2,2)} = \left(1 - \frac{t_1}{t_2}\right) \frac{t_3}{t_4} + \left(1 - \frac{t_2}{t_3}\right) \frac{t_3}{t_4} - \left(1 - \frac{t_1}{t_2}\right) \left(1 - \frac{t_2}{t_3}\right) \frac{t_3}{t_4} + \left(1 - \frac{t_3}{t_4}\right) \frac{t_2}{t_4} \\ - \left(1 - \frac{t_1}{t_2}\right) \left(1 - \frac{t_3}{t_4}\right) \frac{t_2}{t_4}. \quad \square $$

If one drops the edge labels and weights, Theorem 1.3 reduces to a rule for non-equivariant K-theory of Grassmannians. This indicates a different semistandard theory than the set-valued approach of A. Buch [Bu02]; see Section 3.1. If instead one assumes each gene G has (multiset) cardinality 1 in Theorem 1.3,
one essentially recovers the rule of [ThYo13] for equivariant cohomology of Grassmannians. For discussion of the algebraic relations among these generalized cohomology rings, we refer the reader to [GrRa04].

In Section 2, we sketch how Theorem 1.3 is used to prove the conjecture of [ThYo13]. Section 3 concerns applications to non-equivariant K-theory of (maximal orthogonal, Lagrangian) Grassmannians. Section 4 briefly outlines our proof of Theorem 1.3.

## 2 The conjectural $K_T$ rule from [ThYo13]

We briefly recap the conjectural rule for $K_{\lambda, \mu}^{\nu}$ from [ThYo13, §8]. We refer the reader to loc. cit. for further elaboration and references.

An **equivariant increasing tableau** is an edge-labeled filling of $\nu/\lambda$ by the labels $1, 2, \dots, \ell$ such that each label in a box is: (1) strictly smaller than the label in the box immediately to its right; (2) strictly smaller than the label in its southern edge, and the label in the box immediately below it; and (3) strictly larger than the label in the northern edge. Any subset of the boxes of $\nu/\lambda$ may be marked by $*$s, except that if the labels $i$ and $i+1$ appear as box labels in the same row, then only the box containing $i+1$ may be $*$-ed. Let $\text{EqInc}(\nu/\lambda, \ell)$ denote the set of all equivariant increasing tableaux.

A **short ribbon** $R$ is a connected skew shape without a $2 \times 2$ subshape and where each row and column contains at most two boxes. An **alternating ribbon** is a filling of $R$ by two symbols, say $\alpha$ and $\beta$, such that adjacent boxes are filled differently; all edges except the southwestmost edge are empty; and if this southwestmost edge is filled, it is filled with a different symbol than the box above it is. Let $\text{switch}(R)$ be the alternating ribbon of the same shape but where each box is instead filled with the other symbol. If the southwestmost edge contained one of these symbols, that symbol is deleted. If $R$ is a ribbon consisting of a single box with only one symbol used, then $\text{switch}$ does nothing to it. Define $\text{switch}$ to act on a disjoint union of alternating ribbons by acting on each separately.

Given $T \in \text{EqInc}(\nu/\lambda, \ell)$, consider an inner corner $x \in \lambda$ which we label $\bullet$. Erase all $*$s appearing in $T$. Apply $\text{switch}$ to the alternating ribbon made of $\bullet$ and 1. Now let $R_2$ be the union of ribbons consisting of $\bullet$ and 2, and proceed as before. Repeat this process until the $\bullet$s are at outer corners; the final placement of the numerical labels gives $\text{KEqjdt}_x^<(T)$. Define $\text{KEqrect}^<(T)$ by successively applying $\text{KEqjdt}^<$ in the column rectification order.

A label $s \in T$ is a **special label** if it is an edge-label or if its box is $*$-ed. Given a box $x$ define a weight $\hat{\beta}(x) = t_m/t_{m+1}$ where $m$ is the “Manhattan distance” as defined in Section 1.4. Each step of the rectification moves an $s$ at most one step north (keeping it in the same column). A special label $s$ **passes** through a box $x$ if it occupies $x$ during rectification of the column that $s$ initially occupies and if $s$ did not initially begin in $x$. Let $x_1, \dots, x_s$ be the boxes passed through by $s$ and $y_1, \dots, y_t$ be the numerically labeled boxes strictly right of $x_s$ and in the same row. Set

$$ \text{factor}_K(s) = 1 - \prod_{i=1}^{s} \hat{\beta}(x_i) \prod_{j=1}^{t} \hat{\beta}(y_j). $$

If a special label $s$ does not move during the rectification of the column that it initially sits in, then $\text{factor}_K(s) = 0$. Now set $\text{wt}_K(T) = \prod_s \text{factor}_K(s)$, where the product is over all special labels $s$. Lastly, given $T$ we define $\text{sgn}(T) = (-1)^{\#*s}$ in $T + \#\text{labels in } T - |\mu|$.

Let $T_\mu$ be the **superstandard tableau** of shape $\mu$, i.e., the first row has entries $1, 2, 3, \dots, \mu_1$, the second row has entries $\mu_1 + 1, \mu_1 + 2, \dots, \mu_1 + \mu_2$, etc. The following is the main conjecture of [ThYo13]. We deduce it via a weight preserving bijection with the rule of Theorem 1.3:
**Theorem 2.1** The equivariant K-theory Schubert structure coefficient is

$$K_{\lambda, \mu}^{\nu} = \sum_{T} \operatorname{sgn}(T) \cdot \operatorname{wt}_{K}(T)$$

where the sum is over all $T \in \operatorname{EqInc}(\nu/\lambda, |\mu|)$ such that $\operatorname{KEqrect}^{<}(T) = T_{\mu}$.

**Proof (sketch):** Say two equivariant increasing tableaux are equivalent if they differ only in the location of $\star$s. Let $X_{\lambda, \mu}^{\nu}$ be the set of equivalence class of witnessing tableaux for the rule asserted in the theorem. Let $Y_{\lambda, \mu}^{\nu}$ be the set of witnessing tableaux for the rule of Theorem 1.3. We need a “semistandardization” map $\phi: X_{\lambda, \mu}^{\nu} \to Y_{\lambda, \mu}^{\nu}$. Given $[T] \in X_{\lambda, \mu}^{\nu}$, replace the labels $1, 2, \dots, \mu_1$ in $T$ with $\mu_1, \mu_2, \dots, \mu_1$ respectively. Next, replace $\mu_1 + 1, \mu_1 + 2, \dots, \mu_1 + \mu_2$ by $2_1, 2_2, \dots, 2_{\mu_2}$ respectively, etc. The result is $\phi([T])$. Define a “standardization” map $\psi: Y_{\lambda, \mu}^{\nu} \to X_{\lambda, \mu}^{\nu}$ by reversing the above process in the obvious way. We prove that the maps $\phi$ and $\psi$ are weight-preserving mutually inverse bijections, which implies the theorem. We omit the details in this announcement. $\square$

**Example 2.2** We repeat the computation from Example 1.4 of $K_{(2),(2,1)}^{(2,2)}$ for $\operatorname{Gr}_2(\mathbb{C}^4)$, this time using the tableaux of [ThYo13]. There are 14 such tableaux. We illustrate only those without $\star$s, and merely describe where the $\star$s can go:

$$U_1 = \begin{tikzpicture}[baseline=(current bounding box.center), scale=0.5, every node/.style={scale=0.5}]
  \node[fill=gray, rectangle, minimum size=2mm, inner sep=1mm] at (0,0) {};
  \node[fill=gray, rectangle, minimum size=2mm, inner sep=1mm] at (1,0) {};
  \node at (0.5,0.5) {1};
  \node at (1.5,0.5) {2};
\end{tikzpicture},
U_2 = \begin{tikzpicture}[baseline=(current bounding box.center), scale=0.5, every node/.style={scale=0.5}]
  \node[fill=gray, rectangle, minimum size=2mm, inner sep=1mm] at (0,0) {};
  \node[fill=gray, rectangle, minimum size=2mm, inner sep=1mm] at (1,0) {};
  \node at (0.5,0.5) {1};
  \node at (1.5,0.5) {2};
\end{tikzpicture},
U_3 = \begin{tikzpicture}[baseline=(current bounding box.center), scale=0.5, every node/.style={scale=0.5}]
  \node[fill=gray, rectangle, minimum size=2mm, inner sep=1mm] at (0,0) {};
  \node[fill=gray, rectangle, minimum size=2mm, inner sep=1mm] at (1,0) {};
  \node at (0.5,0.5) {1};
  \node at (1.5,0.5) {2};
\end{tikzpicture},
U_4 = \begin{tikzpicture}[baseline=(current bounding box.center), scale=0.5, every node/.style={scale=0.5}]
  \node[fill=gray, rectangle, minimum size=2mm, inner sep=1mm] at (0,0) {};
  \node[fill=gray, rectangle, minimum size=2mm, inner sep=1mm] at (1,0) {};
  \node at (0.5,0.5) {1};
  \node at (1.5,0.5) {2};
\end{tikzpicture},
U_5 = \begin{tikzpicture}[baseline=(current bounding box.center), scale=0.5, every node/.style={scale=0.5}]
  \node[fill=gray, rectangle, minimum size=2mm, inner sep=1mm] at (0,0) {};
  \node[fill=gray, rectangle, minimum size=2mm, inner sep=1mm] at (1,0) {};
  \node at (0.5,0.5) {1};
  \node at (1.5,0.5) {2};
\end{tikzpicture}$$

The remaining 9 tableaux are: analogues of $U_1, U_2, U_3$ with $\star$s on the boxes containing 2, and analogues of $U_4, U_5$ with $\star$s on the boxes containing 1, 3, or both.

It is left to the reader to confirm that for each $i$, $\operatorname{wt}(T_i) = \sum \operatorname{sgn}(U) \cdot \operatorname{wt}_K(U)$, where the sum is over all equivariant increasing tableaux that differ from $U_i$ only in location of $\star$s.

## 3 Applications to (non-equivariant) K-theory

In this section we describe applications of genomic tableaux to non-equivariant K-theory. Let $G/P$ be a generalized flag variety, where $G$ is a complex connected reductive Lie group and $P$ is a parabolic subgroup. The classes $[\mathcal{O}_{X_{\lambda}}]$ of the structure sheaves of the Schubert varieties $X_{\lambda}$ form a $\mathbb{Z}$-linear basis of the Grothendieck ring $K^0(G/P)$ of algebraic vector bundles over $G/P$. Here $\lambda$ ranges over $W/W_P$, where $W$ is the Weyl group of $G$ and $W_P$ is the subgroup of $W$ associated to $P$. Define structure constants by

$$[\mathcal{O}_{X_{\lambda}}] \cdot [\mathcal{O}_{X_{\mu}}] = \sum_{\nu} k_{\lambda, \mu}^{\nu} (G/P) [\mathcal{O}_{X_{\nu}}].$$

It is known that $(-1)^{|\lambda|+|\mu|-|\nu|}k_{\lambda, \mu}^{\nu}(G/P) \ge 0$, where $|\lambda|$ is the codimension of $X_{\lambda}$ (see [Br05] and references therein). We now discuss $k_{\lambda, \mu}^{\nu}(G/P)$ when $G/P$ is a Grassmannian, maximal orthogonal Grassmannian or Lagrangian Grassmannian.

Recently, C. Monical (private communication) has found another application of genomic tableaux to combinatorial K-theory. This is in the study of Lascoux polynomials (see [RoYo13] and references therein) and K-theoretic analogues of Demazure atoms, extending results of [HLMvW11].
## 3.1 Gr<sub>k</sub>(C<sup>n</sup>)

Our rule for $K_{\lambda,\mu}^{\nu}(\mathrm{Gr}_k(\mathbb{C}^n))$ reduces to one for $k_{\lambda,\mu}^{\nu}(\mathrm{Gr}_k(\mathbb{C}^n))$. That is we define genomic tableaux, their genes, content and genotype the same way except we do not allow edge-labels. For example:

**Example 3.1** The genomic tableau $T = \begin{array}{|c|c|c|} \hline & 1_2 & 2_1 \\ \hline 1_1 & 1_2 & 2_1 \\ \hline 2_1 & & \\ \hline \end{array}$ has content $(2, 1)$ and six genotypes:

<figure><img src="image_2.png" /></figure>

The above genotypes respectively have reading words: 112, 112, 211, 121, 211 and 211. Since 211 is not a ballot sequence, the genomic tableau $T$ is not a ballot.

**Theorem 3.2** $k_{\lambda,\mu}^{\nu}(\mathrm{Gr}_k(\mathbb{C}^n))$ equals $(-1)^{|\nu|-|\lambda|-|\mu|}$ times the number of ballot genomic tableaux of shape $\nu/\lambda$ and content $\mu$.

**Example 3.3** The structure constant $k_{(2,1),(2,1)}^{(4,2,1)}(\mathrm{Gr}_3(\mathbb{C}^7)) = -3$ is computed by the tableaux

<figure><img src="image_3.png" /></figure>

A rule for $k_{\lambda,\mu}^{\nu}(\mathrm{Gr}_k(\mathbb{C}^n))$ was first given by A. Buch [Bu02] in terms of set-valued tableaux. [ThYo09b] introduced an alternative model, extending the classical *jeu de taquin* algorithm to increasing tableaux. This latter rule had applications to maximal orthogonal Grassmannians, a point we wish to now revisit.

## 3.2 OG(n, 2n + 1)

The Schubert varieties of the odd orthogonal Grassmannian OG(n, 2n + 1) are indexed by shifted Young diagrams $\lambda$ contained in the shifted staircase $\delta_n$ whose ith row is of length $i$ for $1 \le i \le n$. Equivalently, $\lambda = (\lambda_1 > \lambda_2 > \dots > \lambda_k > 0)$ where $k \le n$ and $\lambda_1 \le n$. Let $\bar{\lambda}$ be the self-conjugate Ferrers diagram $\lambda \cup \lambda^\dagger$, where $\lambda^\dagger$ is the diagram obtained by reflecting $\lambda$ across the main diagonal and folding along that diagonal. For example,

$$ \lambda = (3, 1) \subset \delta_4 = \left( \begin{array}{c|c} \bullet & \bullet \\ \bullet & \bullet \\ \bullet & \bullet \\ \bullet & \bullet \\ \bullet & \bullet \\ \bullet & \bullet \end{array} \right) \mapsto \bar{\lambda} = \left( \begin{array}{c|c} \bullet & \bullet \\ \bullet & \bullet \\ \bullet & \bullet \\ \bullet & \bullet \\ \bullet & \bullet \\ \bullet & \bullet \end{array} \right) $$

Using standard matrix coordinates to describe the boxes of $\lambda$, the **upper part** of $\bar{\lambda}$ is the set of boxes in positions $(i, j)$ with $i \le j$ (the boxes labeled $\bullet$ in our example above). A **symmetric pair** is either a pair of boxes with one in position $(i, j)$ and the other in position $(j, i)$, or else a single box in position $(i, i)$.

Let $\mathcal{D}$ be the doubled alphabet $1' < 1 < 2' < 2 < \dots$. For $i \in \mathcal{D}$, we say $|i| = n$, if either $i = n$ or $i = n'$. A **gene** is a set of subscripted entries from $\mathcal{D}$ with a given subscript. A gene is of **family** $i$ if all unprimed labels in the gene are of the form $i_a$ for some $a$. A **OG-genomic tableau** is a filling of $\bar{\lambda}$ with subscripted entries from $\mathcal{D}$ (the subscripts should form an initial segment of $\mathbb{Z}_{>0}$) such that:
1. subscripts strictly increase along rows and columns (left to right, top to bottom);

2. there is at most one unprimed label of a given family in any column;

3. if $k'_\ell$ appears in position $(i, j)$ with $i < j$, then $k_\ell$ appears in position $(j, i)$;

4. if $k_\ell$ appears in position $(i, j)$ with $i < j$, then $(k+1)_\ell$ appears in position $(j, i)$;

5. if (unprimed) $k_\alpha$ appears west of $k_\beta$, then $a \le b$;

6. if $h_\alpha$ and $k_\beta$ are (unprimed) labels with $h < k$, then $a < b$;

7. for every primed label $h'_\alpha$ in the upper part of $T$, there is an label $h_\beta$ weakly southwest in the upper part with $a \neq b$;

8. no primed labels appear on the main diagonal.

For example, if $\lambda = (3, 1)$, then an OG-genomic tableau of shape $\bar{\lambda}$ is given by
$$ \begin{bmatrix} 1_1 & 2'_2 & 3_4 \\ 2_2 & 2_3 \\ 4'_4 \end{bmatrix} $$

We now give OG-analogues of the notions from Section 1.2. The **content** of $T$ is the number of genes of each family. A **genotype** $G$ of $T$ is a choice of a single symmetric pair from each gene.

**Example 3.4** Let $n = 6, \nu = (6, 4, 1)$, $\lambda = (4, 2)$. Then a genomic tableau $T$ of shape $\bar{\nu}/\bar{\lambda}$ and one of its two genotypes $G$ are given by

$$ T = \begin{bmatrix} \bullet & \bullet & \bullet & \bullet & 1'_1 & 2_3 \\ \circ & \bullet & \bullet & 1_2 & 2_3 \\ \circ & \circ & 3_4 \\ \circ & 2'_2 \\ 1_1 & 3'_3 \\ 3'_3 \end{bmatrix}, \quad G = \begin{bmatrix} \bullet & \bullet & \bullet & \bullet & 1'_1 & 2_3 \\ \circ & \bullet & \bullet & 1_2 \\ \circ & \circ & 3_4 \\ \circ & 2'_2 \\ 1_1 \\ 3'_3 \end{bmatrix} $$

The content of $T$ is $\mu = (2, 1, 1)$.

The **reading word** $\text{word}(G)$ of a genotype $G$ is obtained by reading the families of its entries along rows from right to left and from top to bottom. Suppose $i \in \mathcal{D}$ is the $j$th letter of $\text{word}(G)$. Say $\text{word}(G)$ is **locally ballot** in the $j$th position, if $|i| = 1$ or the number of $|i|$'s among the first $j-1$ letters of $\text{word}(G)$ is strictly less than the number of $(|i| - 1)$'s among the first $j-1$ letters. $G$ is **ballot** if $\text{word}(G)$ is locally ballot in every position and the genomic tableau $T$ is **ballot** if every genotype of $T$ is ballot.

**Theorem 3.5** $k_{\lambda, \mu}^{\nu}$ ($\text{OG}(n, 2n+1)$) equals $(-1)^{|\nu|-|\lambda|-|\mu|}$ times the number of ballot genomic tableaux of shape $\bar{\nu}/\bar{\lambda}$ and content $\mu$.

One can also give a variant of this theorem, using a reading word that more closely resembles earlier work (e.g. [St89]). Earlier a conjecture for $k_{\lambda, \mu}^{\nu}$ ($\text{OG}(n, 2n+1)$) was given in [ThYo09b] and proved by the combination of [BuRa12, CIThYo14]. See also related work of T. Ikeda–H. Naruse [IkNa13]. Note that since $\text{OG}(n, 2n+1)$ is isomorphic to a component of $\text{OG}(n+1, 2n+2)$, Theorem 3.5 also applies in the latter context.
**Example 3.6** (cf. [ClThYo14, Example 1.3]) That $k_{(3,1),(3,1)}^{(5,3,1)}(\text{OG}(n, 2n + 1)) = -6$ is witnessed by:

<figure><img src="image_4.png" /></figure>

### 3.3 LG(n, 2n)

The Schubert varieties of the Lagrangian Grassmannian LG(n, 2n) are indexed by the same shifted Young diagrams $\lambda$ as in the OG case. We do not as yet have an exact rule in this case, but we present some conjectures in this direction. We define LG-genomic tableaux exactly like OG-genomic tableaux except:

* We delete condition 7. on OG-genomic tableaux; and

* we relax condition 1., allowing $i_a$ left of $j_a$ in the same row or above $j_a$ in the same column, when $i < j \in \mathcal{D}$.

**Conjecture 3.7** $|k_{\lambda, \mu}^{\nu}(\text{LG}(n, 2n))| \le \#\{\text{ballot LG-genomic tableaux of shape } \bar{\nu}/\bar{\lambda} \text{ and content } \mu\}$.

In the “cohomological case”, i.e., when $|\lambda| + |\mu| = |\nu|$, we have

$$k_{\lambda, \mu}^{\nu}(\text{LG}(n, 2n)) = 2^{l(\lambda)+l(\mu)-l(\nu)} k_{\lambda, \mu}^{\nu}(\text{OG}(n, 2n+1)),$$

where $l(\pi)$ denotes the number of nonzero parts of $\pi$. However, we are not aware of any such simple relationship between the coefficients in general. However, we have:

**Conjecture 3.8** For any strict partitions $\lambda, \mu, \nu$, $|k_{\lambda, \mu}^{\nu}(\text{OG}(n, 2n + 1))| \le |k_{\lambda, \mu}^{\nu}(\text{LG}(n, 2n))|$.

By [BuRa12], this conjecture holds whenever $\mu$ has a single part. The above two conjectures have been checked extensively by computer.

Concluding, we have given combinatorially related upper and lower bounds for $|k_{\lambda, \mu}^{\nu}(\text{LG}(n, 2n))|$. Meanwhile, Conjecture 3.8 presents an inequality for which a geometric explanation is desired.

## 4 Structure of the proof of Theorem 1.3

Let $\lambda^+$ denote the set of partitions $\rho$ such that $\lambda \subsetneq \rho$ and $\rho/\lambda$ has no two boxes in the same row or column. Similarly, let $\lambda^-$ denote the set of partitions $\delta$ such that $\delta \subsetneq \lambda$ and $\lambda/\delta$ has no two boxes in the same row or column.
**Proposition 4.1**

$$ \sum_{\rho \in \lambda^+} (-1)^{|\rho/\lambda|+1} K_{\rho\mu}^{\nu} = K_{\lambda\mu}^{\nu} (1 - \mathbf{wt}(\nu/\lambda)) + \sum_{\delta \in \nu^{-}} (-1)^{|\nu/\delta|+1} K_{\lambda\mu}^{\delta} \mathbf{wt}(\delta/\lambda). \quad (1) $$

**Proof:** The Chevalley formula in equivariant K-theory (see, e.g., [LePo07]) implies:

$$ \sigma_{\lambda}\sigma_{\square} = \sigma_{\lambda}(1 - \mathbf{wt}(\lambda)) + \sum_{\rho \in \lambda^{+}} (-1)^{|\rho/\lambda|+1}\sigma_{\rho}\mathbf{wt}(\lambda) $$

Thus, the coefficient of $\sigma_{\nu}$ in $(\sigma_{\lambda}\sigma_{\square})\sigma_{\mu}$ is

$$ [\sigma_{\nu}](\sigma_{\lambda}\sigma_{\square})\sigma_{\mu} = K_{\lambda\mu}^{\nu}(1 - \mathbf{wt}(\lambda)) + \sum_{\rho \in \lambda^{+}} (-1)^{|\rho/\lambda|+1} K_{\rho\mu}^{\nu}\mathbf{wt}(\lambda). $$

On the other hand,

$$ [\sigma_{\nu}](\sigma_{\lambda}\sigma_{\mu})\sigma_{\square} = K_{\lambda\mu}^{\nu}(1 - \mathbf{wt}(\nu)) + \sum_{\delta \in \nu^{-}} (-1)^{|\nu/\delta|+1} K_{\lambda\mu}^{\delta}\mathbf{wt}(\delta). $$

The conclusion follows from associativity and commutativity: $(\sigma_{\lambda}\sigma_{\square})\sigma_{\mu} = (\sigma_{\lambda}\sigma_{\mu})\sigma_{\square}$. $\square$

To prove $K_{\lambda,\mu}^{\nu} = L_{\lambda,\mu}^{\nu}$ we induct on $|\nu/\lambda|$. This inductive approach is inspired by that of [MoSa99] and [KnTa03]. Assume $K_{\theta,\mu}^{\tau} = L_{\theta,\mu}^{\tau}$ when $|\tau/\theta| \le h$. Now suppose we are given $\lambda, \nu$ with $|\nu/\lambda| = h+1$. We will later show that $L_{\lambda,\mu}^{\nu}$ satisfies (1). This relates $L_{\lambda,\mu}^{\nu}$ to $L_{\theta,\mu}^{\tau} = K_{\theta,\mu}^{\tau}$ (the equality being the inductive hypothesis). Since Proposition 4.1 asserts $K_{\lambda,\mu}^{\nu}$ also satisfies (1) we are done, except that we must check the base case of the induction:

**Proposition 4.2** $K_{\lambda,\mu}^{\lambda} = L_{\lambda,\mu}^{\lambda}$.

**Proof (sketch):** For $\lambda \subseteq \Omega = k \times (n-k)$, the **Grassmannian permutation** associated to $\lambda$ is the permutation $\pi_{\lambda} \in S_n$ uniquely defined by $\pi_{\lambda}(i) = i + \lambda_{k-i+1}$ for $1 \le i \le k$ and which has at most one descent, which (if it exists) appears at position $k$.

Let $w', v' \in S_n$ be the Grassmannian permutations for the conjugate shapes $\lambda', \mu' \subseteq (n-k) \times k$. The following identity (well-known to experts) relates $K_{\lambda,\mu}^{\lambda}$ to the localization at $e_{\mu}$ of the class $\sigma_{\lambda}$, as expressed in terms of a specialization of the double Grothendieck polynomial:

**Lemma 4.3** $K_{\lambda,\mu}^{\lambda}(\mathrm{Gr}_k(\mathbb{C}^n)) = \mathfrak{G}_{v'}(t_{w'(1)}, \dots, t_{w'(n)}; t_1, \dots, t_n)$. Here $\overline{f}(t_1, \dots, t_n)$ is obtained from $f(t_1, \dots, t_n)$ by the substitution $t_j \mapsto t_{n-j+1}$.

The remainder of the proof uses a tableau formula for $\mathfrak{G}_{v'}(t_{w'(1)}, \dots, t_{w'(n)}; t_1, \dots, t_n)$ [KnMiYo09, Theorem 5.8] which is valid when $v'$ is Grassmannian. We biject the tableaux of this formula with the tableaux given by our rule. $\square$

To show that $L_{\lambda,\mu}^{\nu}$ satisfies the recurrence of Proposition 4.1, we need to reformulate our rule in terms of what we call ‘bundled tableaux.’ These may be thought of as certain equivalence classes of ballot semi-standard genomic tableaux. This rule is more difficult to formulate (which is why we do not give it here),
but is the correct form to work with for our proof. Let $B_{\lambda, \mu}^{\nu} = \{B \in \text{Bundled}(\nu/\lambda) \text{ with content } \mu\}$, be the set of such tableaux. Fix $\lambda, \mu, \nu$ with $\lambda \subsetneq \nu$. Define the formal sums

$$ \Lambda^{+} = \sum_{\rho \in \lambda^{+}} (-1)^{|\rho/\lambda|+1} \sum_{T \in B_{\rho, \mu}^{\nu}} T, $$

$$ \Lambda = (1 - \mathrm{wt}(\nu/\lambda)) \sum_{T \in B_{\lambda, \mu}^{\nu}} T \quad \text{and} \quad \Lambda^{-} = \sum_{\delta \in \nu^{-}} (-1)^{|\nu/\delta|+1} \mathrm{wt}(\delta/\lambda) \sum_{T \in B_{\lambda, \mu}^{\delta}} T. $$

We define jeu de taquin swaps for bundled tableaux. We show that using these swaps to slide $\Lambda^+$ at the inner corners $\rho/\lambda$ gives $\Lambda + \Lambda^-$. We then show this process is weight-preserving in an appropriate sense, concluding the proof. This proof of weight-preservation and moreover that our slides are well-defined is the vast majority of the effort in our forthcoming work.

## Acknowledgements

AY thanks Hugh Thomas for his collaboration during [ThYo13]. Both authors thank him for his role during the early stages of this project. This report was partially completed during the workshop “Combinatorics and Complexity of Kronecker Coefficients” at the American Institute of Mathematics; we thank the organizers and the institute for their hospitality. We thank Laurent Manivel for providing a French translation of our abstract.

## References

[AnGrMi11] D. Anderson, S. Griffeth and E. Miller, Positivity and Kleiman transversality in equivariant K-theory of homogeneous spaces, J. Eur. Math. Soc., **13**(2011), 57–84.

[Br05] M. Brion, Lectures on the geometry of flag varieties, Topics in cohomological studies of algebraic varieties, 33–85, Trends Math., Birkhäuser, Basel, 2005.

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

[BuRa12] A. Buch and V. Ravikumar, Pieri rules for the K-theory of cominuscule Grassmannians, J. Reine Angew. Math., **668**(2012), 109–132.

[CIThYo14] E. Clifford, H. Thomas and A. Yong, K-theoretic Schubert calculus for $\mathrm{OG}(n, 2n+1)$ and jeu de taquin for shifted increasing tableaux, J. Reine Angew. Math., **690**(2014), 51–63.

[CoVa05] I. Coskun and R. Vakil, Geometric positivity in the cohomology of homogeneous spaces and generalized Schubert calculus, in “Algebraic Geometry — Seattle 2005” Part 1, 77–124, Proc. Sympos. Pure Math., 80, Amer. Math. Soc., Providence, RI, 2009.

[Gr01] W. Graham, Positivity in equivariant Schubert calculus, Duke Math. J., **109** (2001), no. 3, 599–614.

[GrRa04] S. Griffeth and A. Ram. Affine Hecke algebras and the Schubert calculus, European J. Combin., **25** (2004), 1263–1283.
[HLMvW11] J. Haglund, K. Luoto, S. Mason and S. van Willigenburg. *Refinements of the Littlewood-Richardson rule*, Trans. Amer. Math. Soc., **363** (2011), 1665–1686.

[IkNa13] T. Ikeda and H. Naruse. *K-theoretic analogues of factorial Schur P-and Q-functions*, Adv. Math. **243** (2013), 22–66.

[Kn10] A. Knutson, *Puzzles, positroid varieties, and equivariant K-theory of Grassmannians*, arXiv:1008.4302, 2010.

[KnMiYo09] A. Knutson, E. Miller and A. Yong, *Gröbner geometry of vertex decompositions and of flagged tableaux*, J. Reine Angew. Math. **630** (2009), 1–31.

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

[LaSc82] 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, **295** (1982), 629–633.

[LePo07] C. Lenart and A. Postnikov, *Affine Weyl groups in K-theory and representation theory*, Int. Math. Res. Not., 2007, no. 12, Art. ID rnm038, 65 pp.

[LiRi34] D. E. Littlewood and A. R. Richardson, *Group Characters and Algebra*, Philos. Trans. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci. **233** (1934), no. 721–730, 99–141.

[MoSa99] A. Molev and B. Sagan, *A Littlewood-Richardson rule for factorial Schur functions*, Trans. Amer. Math. Soc. **351** (1999), no. 11, 4429–4443.

[RoYo13] C. Ross and A. Yong, *Combinatorial rules for three bases of polynomials*, accepted to Sém. Lothar. Combin., 2013.

[Sc77] M.-P. Schützenberger, *Combinatoire et représentation du groupe symétrique* (Actes Ta-ble Ronde CNRS, Univ. Louis-Pasteur Strasbourg, Strasbourg, 1976), pp. 59–113. Lecture Notes in Math., Vol. 579, Springer, Berlin, 1977.

[St89] J. Stembridge, *Shifted tableaux and the projective representations of symmetric groups*, Adv. Math. **74.1** (1989): 87–134.

[ThYo09b] H. Thomas and A. Yong, *A jeu de taquin theory for increasing tableaux, with applications to K-theoretic Schubert calculus*, Algebra Number Theory **3** (2009), no. 2, 121–148.

[ThYo13] H. Thomas and A. Yong, *Equivariant Schubert calculus and jeu de taquin*, Ann. Inst. Fourier (Grenoble), to appear, 2013.