Is there a short proof that the Kostka number $K_{\lambda \mu}$ is non-zero whenever $\lambda$ dominates $\mu$?

Question

This is maybe a little basic for MathOverflow, but I'm hoping it will get some interesting answers.

Let $\unrhd$ be the dominance order on partitions of $n \in \mathbb{N}$. For partitions $\lambda$ and $\mu$ of $n$, the Kostka Number $K_{\lambda\mu}$ is the number of semistandard Young tableaux of shape $\lambda$ and content $\mu$.

If $t$ is such a tableau then the $\mu_1+\cdots +\mu_r$ entries $k$ of $t$ such that $k \le r$ all lie in the first $r$ rows of $t$. Hence $\lambda_1 + \cdots + \lambda_r \ge \mu_1 + \cdots + \mu_r$ for each $r$ and so $\lambda \unrhd \mu$.

Is there a short combinatorial proof of the converse: if $\lambda \unrhd \mu$ then $K_{\lambda\mu} > 0$?

A constructive proof, maybe using the characterization of neighbours in the dominance order by single box moves on Young diagrams, would be especially welcome.

Edit. Using some representation theory it's possible to make this strategy work. The following is the symmetric functions version of Theorem 2.2.20 in the textbook by James and Kerber. Obviously $K_{\lambda\lambda} = 1$. Let $\mu$ and $\mu^\star$ be neighbours in the dominance order, with $\mu \rhd \mu^\star$, so $\mu^\star_i=\mu_i-1$, $\mu^\star_j = \mu_j+1$ for some $i < j$, and $\mu^\star_k = \mu_k$ if $k\not=i,j$. Since $h_{(a,b)} = h_{(a+1,b-1)} + s_{(a,b)}$ whenever $a \ge b$, we have

$$h_{\mu^\star} = \bigl(\prod_{k\not=i,j} h_{\mu_k} \bigr) h_{\mu_i-1}h_{\mu_j+1}= \bigl(\prod_{k\not=i,j}h_{\mu_k}\bigr) \bigl( h_{\mu_i}h_{\mu_j} + s_{(\mu_i-1,\mu_j+1)} \bigr) $$

and so if $f = \prod_{k\not=i,j}h_{\mu_k}$ then

$$K_{\lambda\mu^\star} = \langle s_\lambda, h_{\mu^\star} \rangle = \langle s_\lambda, h_\mu \rangle + \langle s_\lambda, f s_{(\mu_i-1,\mu_j+1)} \rangle = K_{\lambda\mu} + \langle s_\lambda, f s_{(\mu_i-1,\mu_j+1)} \rangle \ge K_{\lambda\mu}.$$

Answer 1

I think the following is a simple combinatorial argument which constructs the most dominant semistandard $\lambda$-tableau of content $\mu$ whenever $\lambda\trianglerighteq\mu$. (n.b. I haven't followed the reference given in Richard Stanley's comment, so I don't know whether I'm duplicating what's done there.)

In a nutshell, the idea is "put the largest numbers as low as possible". So let $l$ be the length of $\mu$, and start the tableau by putting the $\mu_l$ $l$s in the bottom boxes of columns as far to the left as possible subject to the condition that if any box has an $l$ and there is a box directly to the right, then that box must also have an $l$ in it. (Another way of saying this is: put $l$s at the bottom of the first $\mu_l$ columns, and then slide these $l$s to the ends of their rows.) If we let $j$ be maximal such that $\lambda_j\geq\mu_l$, this means that we are putting $\lambda_x-\lambda_{x+1}$ $l$s at the end of row $x$ for each $x>j$, and $\mu_l-\lambda_{j+1}$ $l$s at the end of row $j$.

To fill in the rest of the tableau, we work recursively. Let $\hat\lambda$ denote the partition whose Young diagram comprises the boxes that are still empty, and let $\hat\mu$ be the partition $(\mu_1,\dots,\mu_{l-1})$. Then as long as $\hat\lambda\trianglerighteq\hat\mu$, we can fill in the rest of the tableau with a semistandard $\hat\lambda$-tableau of content $\hat\mu$, which gives us what we need.

So we need to show that $\hat\lambda_1+\dots+\hat\lambda_x\geq\hat\mu_1+\dots+\hat\mu_x$ for every $x$. For $x<j$ or $x\geq l$ this is immediate from the fact that $\lambda\trianglerighteq\mu$, so take $j\leq x<l$. Observe that $$\lambda_1+\dots+\lambda_x=n-(\lambda_{x+1}+\dots+\lambda_l)\geqslant n-(l-x)\lambda_{x+1}$$while $$\mu_1+\dots+\mu_x=n-(\mu_{x+1}+\dots+\mu_l)\leqslant n-(l-x)\mu_l.$$ So $$(\hat\lambda_1+\dots+\hat\lambda_x)-(\hat\mu_1+\dots+\hat\mu_x)=(\lambda_1+\dots+\lambda_{x+1}-\mu_l)-(\mu_1+\dots+\mu_x)\geqslant(l-x-1)(\mu_l-\lambda_{x+1})\geqslant0$$ as required.

Answer 2

The following argument is reproduced from the proof of Lemma 3.7.3 in the book Representation Theory of the Symmetric Groups: The Okounkov–Vershik Approach, Character Formulas, and the Partition Algebras, by Tullio Ceccherini-Silberstein, Fabio Scarabotti, and Filippo Tolli (Cambridge University Press, 2010).

The proof is by induction on $n$. Suppose that $\lambda$ has $k$ parts and $\mu$ has $h$ parts, and that $\lambda\ge \mu$. Say that the positive integer $i$ is removable for the pair $(\lambda,\mu)$ if, after setting $$\tilde\lambda := (\lambda_1, \lambda_2, \ldots, \lambda_{i-1}, \lambda_i-1, \lambda_{i+1}, \ldots, \lambda_k)$$ and $$\tilde\mu := (\mu_1, \mu_2, \ldots, \mu_{h-1}, \mu_h-1),$$ $\tilde\lambda$ is still a partition (i.e., $\lambda_i > \lambda_{i+1}$) and $\tilde\lambda \ge \tilde\mu$. In particular, if the $i$th row of a SSYT of shape $\lambda$ and content $\mu$ contains the number $h$, then $i$ is removable for $(\lambda,\mu)$. Also, $k$ is always removable for the pair $(\lambda,\mu)$.

Let $i$ be the smallest removable integer for the pair $(\lambda,\mu)$, and let $\tilde\lambda$ and $\tilde\mu$ be as above. By the inductive hypothesis, we may construct a SSYT $\tilde T$ of shape $\tilde\lambda$ and content $\tilde\mu$. Moreover, by minimality of $i$, $\tilde T$ does not contain an entry $h$ in any row $j<i$. So if we add to $\tilde T$ a box at the end row $i$ with entry $h$, then we get a SSYT $T$ of shape $\lambda$ and content $\mu$.

Answer 3

The proof I know is more representation-theoretic than combinatorial; the condition $\lambda \unrhd \mu$ is replaced by the type-independent $\mu \in hull(W\cdot \lambda) \cap (\lambda +$ root lattice$)$. It goes as follows, inducting on the rank of the semisimple part of the group $G$. The rank $1$ case is standard $SL_2$ rep theory.

Pick a simple root $\alpha$, with $L_\alpha = T \cdot (SL_2)_\alpha$ the corresponding Levi subgroup, and consider the weights $\mu + \mathbb Z\alpha$. There will be a largest and a smallest $k$ such that $\lambda \unrhd \mu + k\alpha$; call them $k_\pm$. They satisfy the same condition as $\mu$, so we hope them to be weights of $V_\lambda$. Once we know they are, then we can use the $L_\alpha$ rep theory to say that $\mu$ is a weight, too.

So we've reduced to dealing with $\mu + k_\pm \alpha$. We need to argue that they are actually on the facets of $hull(W\cdot\lambda)$ (i.e. even had we considered $\mu+\mathbb R\alpha$ these would still be the right $k_\pm$) and I don't quite remember how that's done but would claim it's easy in the type $A$ case that motivates you. Then, we observe that the weight multiplicities on a facet are those of an irrep of a corank $1$ Levi subgroup (as is easily seen by Weyl invariance + the Kostant multiplicity formula), and use induction on rank.

In the SSYT situation this all goes as follows. Take $\alpha$ to be the first simple root. Then $k_+ = \lambda_1-\mu_1$, and $\mu + k_+ \alpha = (\lambda_1, \mu_2-k_+, \mu_3, \ldots)$. Any SSYT with that weight will have to have a first row of all $1$s. Filling in the rest of the SSYT is possible by induction. Now apply the $-\alpha$ crystal operator $k_+$ times to get an SSYT of weight $\mu$.

Answer 4

Here is a representation theoretic argument. I hope it is correct.

Consider the weight diagram of the irreducible representation $V_\lambda$ (of highest weight $\lambda$) of $\mathfrak{sl}_n(\mathbb{C})$. The weight space associated to $\mu$ in this weight diagram has dimension $K_{\lambda\mu}$. So it is enough to show that each weight associated to $\mu$ appears in the weight diagram of $V_\lambda$ when $\lambda\geq\mu$. This should follow from the symmetry of the weight diagram.

For example, in $\mathfrak{sl}_3(\mathbb{C})$ case, directly by inspection one can see that the weights that appear in the weight diagram of $V_\lambda$ correspond to the partitions of the form $\mu = (\lambda_1-k,\lambda_2+k)$ and these are the partitions such that $\mu\leq\lambda$.

Answer 5

Here is a simple constructive argument:

If $K_{\lambda \mu} \neq 0 $, then there is a semistandard tableau on $\lambda$ of type $\mu$. In a semistandard tableau, a box with $i$ can occur in atmost the $i^{th}$ row (as columns are strictly increasing). There are $\mu_1 \,1's, \mu_2 \,2's,\ldots \mu_i \,i's, $ which can atmost occur upto the $i^{th}$ row of $\lambda$ which immediately gives us the inequality $$\mu_1 +\mu_2 + \cdots +\mu_i \leq \lambda_1 +\lambda_2 +\cdots + \lambda_i.$$

For the converse, given the inequality, we just need to produce a semistandard tableau on $\lambda$ of type $\mu$. Let $\nu_i = \min (\lambda_i,\mu_i)$, and we fill $\nu_i \, i's$ in the $i^{th}$ row of $\lambda$. We exhaust all the $1's$ as $\mu_1\leq \lambda_1 (\implies \nu_1=\mu_1)$. Lets us say that we exhaust all the $(i-1)'s$, and the tableau is still semistandard. If $\mu_i = \nu_i$, then the $i's$ have also been exhausted, otherwise we have $\mu_i - \lambda_i$ many $i's$ left to be filled inside the boxes till the $i^{th}$ row, which we start to fill sequentially in the left over boxes in the first $i$ rows, going down a row only when one is completely filled ( this can be done as we have that $\mu_1 +\mu_2 + \cdots +\mu_i \leq \lambda_1 +\lambda_2 +\cdots + \lambda_i$). This need not give us a semistandard tableau, so we stop when we have $j$ such that $i$ occurs in the same column of the $(j-1)^{th}$ and $j^{th}$ rows. In the $j^{th}$ row, we find the first element on the left of the box with $i$ which is filled with the largest $k$ such that $k<i$, and for this $k$, we find the smallest $k'$ in the $(j-1)^{th}$ row such that $k \leq k'$, and we do a cyclic exchange of boxes, sending $k$ to the box of $k'$, and shifting everything in the $(j-1)^{th}$ row starting from $k'$ to its right, which leaves us with the box with $i$. We shift the boxes in the column that initially contained $k$ one up till atmost the $i^{th}$ row or a row containing a box with entry $>i$, and the last empty box in the column gets the leftover $i$. This shift keeps the table semistandard, and one can apply this shift repeatedly to bring a non semistandard tableau to a semistandard tableau.