## Non-zero Kostka Numbers

Let $\lambda$ and $\mu$ be partitions of the same size. The Kostka Number $K_{\lambda\mu}$ is the number of semistandard $\lambda$-tableau of type $\mu$. It is easy to see that if $K_{\lambda\mu} \not=0$ then $\lambda \unrhd \mu$, where $\unrhd$ is the dominance order on partitions. I asked on MathOverflow if there was a short combinatorial proof of the converse. Matt Fayers posted an unexpectedly beautiful constructive answer. He has since put a proof of the stronger result that if $\mu \unrhd \nu$ then $K_{\lambda\nu} \ge K_{\lambda \mu}$ on his website.

The purpose of this post is to record a small simplification of Fayers’ original MathOverflow proof and to ask a question inspired by his stronger result.

#### Claim

Let $\mu$ have $\ell$ parts. If $j$ is maximal such that $\lambda_j \ge \mu_\ell$ then there is a semistandard Young tableau of shape $\lambda$ and content $\mu$ in which the entries equal to $\ell$ lie in rows numbered $\ge j$.

#### Proof of claim

We put an $\ell$ at the end of row of $j$ of the Young diagram of $\lambda$. Continuing inductively, we are left with partitions $\lambda^-$ and $\mu^-$ obtained by deleting the boxes at the ends of row $j$ of $\lambda$ and row $\ell$ of $\mu$. Suppose, for a contradiction, that $\lambda^- \not\unrhd \mu^-$. Then

$\lambda_1 + \cdots + (\lambda_j-1) + \cdots + \lambda_k < \mu_1 + \cdots + \mu_k$

for some $k$ such that $j \le k < \ell$. (If $k=j$ then the final summand on the left is $\lambda_j-1$.) Since $\lambda \unrhd \mu$ we have

$\lambda_1 + \cdots + \lambda_j + \cdots + \lambda_k = \mu_1 + \cdots + \mu_k.$

Hence if $\lambda^\star$ and $\mu^\star$ are the partitions obtained from $\lambda$ and $\mu$ by removing the first $k$ parts of each then $\lambda^\star \unrhd \mu^\star$. But since $\lambda_{j+1} < \mu_\ell$, all the parts of $\lambda^\star$ are strictly less than the smallest part of $\mu^\star$, a contradiction.

If $\mu_\ell = 1$ then we are finished with entries equal to $\ell$. Otherwise since $\lambda^-_j = \lambda_j - 1 \ge \mu_\ell -1 = \mu^-_\ell$, the new value of $j$ is at least the old one (with equality unless $\lambda_j = \lambda_{j+1} + 1$), as required for the claim.

#### Question

Is there a nice characterization of the triples $(\lambda,\mu,\nu)$ such that $\lambda \unrhd \mu \unrhd \nu$ and $K_{\lambda\mu} = K_{\lambda\nu}$?

The pairs $(\lambda,\mu)$ such that $K_{\lambda\mu} = 1$ have been characterized.

Advertisements