Saturation for Flagged Skew
Littlewood-Richardson coefficients

The Littlewood-Richardson (LR) coefficients are among the most celebrated numbers in algebraic combinatorics. They are the multiplicities in the decomposition into irreducibles of tensor products of irreducible polynomial representations of general linear groups. As such, they are the structure constants for the multiplication of Schur polynomials (which form a basis for the ring of symmetric polynomials). These coefficients also determine the branching of irreducible representations of symmetric groups on restriction to Young subgroups. They also come up in several other places. For example, they occur as structure constants for the multiplication of Schubert cohomology classes of Grassmanians.

Several generalizations of these coefficients can be found in the literature: e.g., [Zel81], [RS95], [KRV21]. Our broader goal is to investigate, for some of these generalizations, the analogue of the saturation theorem of Knutson-Tao for the LR coefficients. In this paper, we consider a simultaneous generalization of Zelevinsky’s skew LR coefficients [Zel81] and the flagged LR coefficients of [KRV21]. We prove that these flagged skew LR coefficients exhibit the saturation property.

In order to do this, we need to lift the main key-positivity result of [RS95] to crystals; we do this using a recent result of Assaf [ADG22]. We also give a hive-like model for the flagged skew LR coefficients. Although a skew Gelfand-Tsetlin (GT) polytope need not be isomorphic to a GT polytope, it turns out that every flagged skew hive polytope is isomorphic to some flagged hive polytope.

A partition $\lambda=(\lambda_{1},\lambda_{2},\cdots)$ is a weakly decreasing sequence of non-negative integers with finitely many non-zero terms (or parts). The length of the partition $\lambda$ is defined to be the largest integer $i$ such that $\lambda_{i}$ is non-zero and we denote it by $l(\lambda)$. The weight of $\lambda$ is the sum of its parts and we denote it by $|\lambda|$. We denote by $\mathcal{P}[n]$ the set of all partitions of length at most $n$. The Young diagram of the partition $\lambda$ is the left and top justified collection of boxes such that row $i$ contains $\lambda_{i}$ boxes. We denote it again by $\lambda$. For Young diagrams $\lambda$ and $\mu$ such that $\lambda\supset\mu$ (i.e., $\lambda_{i}\geq\mu_{i}\text{ }\forall i$), the skew diagram $\lambda/\mu$ is obtained by removing the boxes of $\mu$ from those of $\lambda$.

Given partitions $\lambda\supset\mu$, a semi-standard skew tableau of shape $\lambda/\mu$ is a filling of the skew diagram $\lambda/\mu$ that is weakly increasing along the rows (from left to right) and strictly increasing along the columns (from top to bottom). A semi-standard tableau of shape $\lambda$ is just a semi-standard skew tableau of shape $\lambda/\text{empty}$ . We denote by $\operatorname{Tab}(\lambda/\mu)$ the set of all semi-standard skew tableaux of shape $\lambda/\mu$ and $\operatorname{Tab}(\lambda/\mu,n)$ the subset of $\operatorname{Tab}(\lambda/\mu)$ where the fillings are all $\leq n$. It will be convenient to let $\operatorname{Tab}(\lambda/\mu)$ be the empty set if $\lambda,\mu$ are partitions with $\lambda\not\supset\mu$. The weight of a tableau $T\in\operatorname{Tab}(\lambda/\mu,n)$ is defined as $wt(T)=(t_{1},t_{2},\cdots,t_{n})$, where $t_{i}$ is the number of times $i$ occurs in $T$. A standard $(\text{skew})$ tableau $T$ is a semi-standard $(\text{skew})$ tableau of the same shape in which $1,2,\cdots,k$ appears exactly once, where $k$ is the number of boxes in $T$. For $T\in\operatorname{Tab}(\lambda/\mu)$, we write $b_{T}$ to denote the reverse-row reading word of $T$ which is the word obtained by reading $T$ right to left and from top to bottom.

Fix $n$ a positive integer. A flag $\Phi$ = $(\Phi_{1},\Phi_{2},\cdots,\Phi_{n})$ is a weakly increasing sequence of positive integers such that¹¹1In the literature, a flag need not have $\Phi_{n}=n$, but for our purposes it is sufficient to consider only such flags. $\Phi_{n}=n$. For $\lambda,\mu\in\mathcal{P}[n]$ and flag $\Phi$ = $(\Phi_{1},\Phi_{2},\cdots,\Phi_{n})$, $\operatorname{Tab}(\lambda/\mu,\Phi)$ is the set of all elements $T$ in $\operatorname{Tab}(\lambda/\mu)$ such that the entries in row $i$ of $T$ are at most $\Phi_{i}$ for $1\leq i\leq n$. Following Reiner-Shimozono [RS95], we define the flagged skew Schur polynomial

where $T$ varies over $\operatorname{Tab}(\lambda/\mu,\Phi)$ and for $t=(t_{1},t_{2},\cdots,t_{n})\in\mathbb{Z}^{n}_{+}$, $\mathbf{x}^{t}$ denotes the monomial $x_{1}^{t_{1}}x_{2}^{t_{2}}\cdots x_{n}^{t_{n}}$. When $\Phi=(n,n,\cdots,n)$, these reduce to the skew Schur polynomials $s_{\lambda/\mu}(x_{1},x_{2},\cdots,x_{n})$. When $\mu$ is the empty partition, they become the flagged Schur polynomials $s_{\lambda}(X_{\Phi})$, which coincide with key polynomials corresponding to $312$-avoiding permutations [PS09, theorem 14.1]. The flagged skew Schur polynomials $s_{\lambda/\mu}(X_{\Phi})$ also have a representation theoretic interpretation as characters of certain Borel modules called flagged Schur modules [RS98].

For $1\leq i\leq n-1$, define the Demazure operator $T_{i}$ on the ring of polynomials in the variables $x_{1},x_{2}\cdots,x_{n}$ as follows:

For $w\in\mathfrak{S}_{n}$ (the symmetric group), we define

where $s_{i_{1}}s_{i_{2}}\cdots s_{i_{k}}$ is a reduced expression for $w$. This is well-defined because the $T_{i}$’s satisfy the braid relations.

For $\alpha\in\mathbb{Z}^{n}_{+}$, let $\alpha^{\dagger}$ be the partition obtained by sorting the parts of $\alpha$ in descending order and let $\omega\in\mathfrak{S}_{n}$ be any permutation such that $\omega\alpha^{\dagger}=\alpha$ (here, the action of $\omega$ is the usual left action of $\mathfrak{S}_{n}$ on $n$-tuples). We recall that the key polynomial $\alpha$ is defined to be ${\alpha}=T_{\omega}(\mathbf{x}^{\alpha^{\dagger}})$, and that this is independent of the choice of $\omega$. A polynomial $f$ is said to be key-positive if it is a sum of key polynomials. If $f$ is key-positive, then $\mathbf{x}^{\lambda}\,f$ and $T_{w}(f)$ are also key-positive, for all $\lambda\in\mathcal{P}[n]$ and all $w\in\mathfrak{S_{n}}$. The former follows from a theorem of Joseph [Jos03] and the latter from the fact that a composition of Demazure operators is itself a Demazure operator. Reiner-Shimozono [RS95, Theorem 20] showed that the flagged skew Schur polynomial $s_{\lambda/\mu}(X_{\Phi})$ is key-positive.

Now, if $w_{0}$ denotes the longest element of $\mathfrak{S}_{n}$, we have

the Schur polynomial indexed by ${\alpha^{\dagger}}$. More generally, (since the key polynomials form a $\mathbb{Z}$-basis of the polynomial ring in $n$ variables [RS95, corollary 7]) given any polynomial $f=f(x_{1},x_{2},\cdots,x_{n})$, we have that $T_{w_{0}}(f)$ is a symmetric polynomial, which can therefore be expanded in the basis of Schur polynomials. If further $f$ is key-positive, then equation (1) shows that $T_{w_{0}}(f)$ is Schur-positive, i.e., a sum of Schur polynomials. This leads us to the main objects of our study.

By the remarks preceding equation (1), it follows that the LHS of (2) is Schur positive, and thus the flagged skew Littlewood-Richardson coefficients are non-negative integers. It is clear by definition that these coefficients are zero if $\mu\not\supset\gamma$. It will follow from Theorem 1 below that they are also zero if $\nu\not\supset\lambda$.

These coefficients subsume many other extensions of the Littlewood-Richardson coefficients. When $\Phi=(n,n,\cdots,n)$, these become Zelevinsky’s extension [Zel81] of the Littlewood-Richardson coefficients $c_{\lambda,\,\mu/\gamma}^{\,\nu}$ defined by $s_{\lambda}(\textbf{x})\,s_{\mu/\gamma}(\textbf{x})=\sum_{\nu\in\mathcal{P}[n]}c_{\lambda,\,\mu/\gamma}^{\,\nu}\,s_{\nu}(\textbf{x})$. These in turn reduce to the usual Littlewood-Richardson coefficients when we further take $\gamma=(0,0,\cdots,0)$.

On the other hand, if we take $\gamma=(0,0,\cdots,0)$ but let $\Phi$ remain arbitrary, we get the w-refined Littlewood-Richardson coefficients of [KRV21] for 312-avoiding permutations $w$.

If we set $\lambda=(0,\dots,0)$, we have $c_{\lambda,\,\mu/\gamma}^{\,\nu}(\Phi)=\sum_{\,\alpha}c^{\,\mu/\gamma,\Phi}_{\,\alpha}$ where the sum runs over all compositions $\alpha$ that are obtained by permuting the parts of $\nu$. The coefficients on the right are the ones which appear in the flagged Littlewood-Richardson expansion of [RS95, section 7].

Our first result provides two combinatorial models for flagged skew LR coefficients (see §3, 4 for undefined terms) that generalize those for LR coefficients:

Our proof of Theorem 1 hinges on understanding the crystal structure on the set of flagged skew tableaux $\operatorname{Tab}(\mu/\gamma,\Phi)$. We show in particular that this set is a disjoint union of Demazure crystals; this lifts the key-positivity result of Reiner-Shimozono [RS95, Theorem 20] from the level of characters to that of crystals.

The main theorem of this paper is the following saturation property of the flagged skew LR coefficients:

We remark that, as in the classical LR case, the stronger converse statement holds. Scaling $\lambda,\mu,\gamma,\nu$ by $k$ also dilates the polytope $\operatorname{SHive}(\lambda,\mu,\gamma,\nu,\Phi)$ by the factor $k$. Thus, $c_{\lambda,\,\mu/\gamma}^{\,\nu}(\Phi)>0$ implies that $c_{k\lambda,\,k\mu/k\gamma}^{\,k\nu}(\Phi)>0$ for every $k\geq 1$, by Theorem 1.

To prove Theorem 2, we construct an affine linear isomorphism between $\operatorname{SHive}(\lambda,\mu,\gamma,\nu)$ and a certain hive polytope, which preserves flags and integral points. Then we deduce theorem 2 from the corresponding theorem for hive polytopes [KRV21, Theorem 1.4].

The purpose of this section is to prove that the subset $\operatorname{Tab}(\mu/\gamma,\Phi)$ of the type $A_{n-1}$ crystal
$\operatorname{Tab}(\mu/\gamma,n)$ is a disjoint union of Demazure crystals. This is the key step in proving the first part of theorem 1 which we will see at the end of this section.

By a crystal of type $A_{n-1}$ (see section 2.2 of [BS17]), we mean a finite and non-empty set $\mathcal{B}$ together with maps

where $i\in\{1,2,\cdots,n-1\}$ and $0\not\in\mathcal{B}$ is an auxiliary element, satisfying the following conditions:

1. (1)

   If $x,y\in\mathcal{B}$ then $e_{i}(x)=y$ if and only if $f_{i}(y)=x$. In this case it is assumed that

   $$wt(y)=wt(x)+(\epsilon_{i}-\epsilon_{i+1})$$

   where $\epsilon_{1},\epsilon_{2},\cdots,\epsilon_{n}$ are the standard orthonormal vectors in $\mathbb{R}^{n}$.

2. (2)

   For all $x\in\mathcal{B}$ and $i\in\{1,2,\cdots,n-1\}$ we require that

   $$\phi_{i}(x)=wt(x)\cdot(\epsilon_{i}-\epsilon_{i+1})+\varepsilon_{i}(x)$$

   where $\varepsilon_{i}(x)$ (resp. $\phi_{i}(y)$) is the maximum number of times $e_{i}$ (resp. $f_{i}$) can be applied to $x$ (resp. $y$) without making it $0$.

The maps $e_{i}$ and $f_{i}$ are called the raising and lowering operators respectively.

The crystal graph associated to a type $A_{n-1}$ crystal $\mathcal{C}$ is an edge-coloured (the colours being $1,2,\cdots n-1$) directed graph whose vertex set is the underlying set of the crystal. An edge with colour $k$ originates from $x\in\mathcal{C}$ and terminates at $y\in\mathcal{C}$ if and only if $f_{k}(x)=y$. We say a crystal is connected if its crystal graph is connected (viewed as an undirected graph).

A subset $\mathcal{C}^{\prime}$ of a crystal $\mathcal{C}$ which is a union of connected components of $\mathcal{C}$ inherits a crystal structure from that of $\mathcal{C}$. In this case, we call $\mathcal{C}^{\prime}$ a full-subcrystal of $\mathcal{C}$.

In this section we define the skew hive polytope and its faces corresponding to flags $\Phi$. We then prove the second part of theorem 1.