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

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}.$$

• Does not the most primitive filling of the diagram obviously work? I mean, fill all rows in succession using first $\mu_1$ ones, then $\mu_2$ twos, etc. Then the $r$th row will start with at most $\mu_1+...+\mu_r-\lambda_1-...-\lambda_{r-1}$ $r$s followed by larger numbers, and strict increase in the columns will be guaranteed: if say $s$ is written at the same position $p$ in the $r$th and the $r+1$st row, then $s$ occupies all positions starting from $p$ in the $r$th row and all positions up to $p$ in the $r+1$st row, which would imply $\mu_s>\lambda_r$ for $s>r$, contradicting domination. – მამუკა ჯიბლაძე Dec 19 '15 at 23:11
• This does not work for $\lambda=(4,1,1)$ and $\mu=(2,2,2)$. – Richard Stanley Dec 20 '15 at 3:51
• Continuing my previous comment, you also cannot fill in the shape by columns, at each step inserting the smallest number possible. E.g., $\lambda=(3,3)$, $\mu=(2,2,2)$. – Richard Stanley Dec 20 '15 at 4:10
• Is there a simple proof of this fact using representation theory? – Sam Hopkins Dec 20 '15 at 6:04
• The first proofs of this result are by Lam and Leibler-Vitale. See sciencedirect.com/science/article/pii/0022404977900305. – Richard Stanley Dec 20 '15 at 14:55

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.

• Beautiful. I wonder whether relationship between $\lambda\unrhd\mu$ and $\hat\lambda\unrhd\hat\mu$ has any representation-theoretic meaning. – მამუკა ჯიბლაძე Dec 22 '15 at 17:58
• Dear Matt, I just came across your paper which shows, in type $A$, that if $\mu \geq \nu$ then $K_{\lambda \mu} \leq K_{\lambda \nu}$. Do you know if the corresponding statement is true in all types? See mathoverflow.net/questions/275740/… for context. – David E Speyer Jul 20 '17 at 14:01

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. 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$$.

• Alex Yong has pointed out to me that this proof is wrong. The step "Moreover, by minimality of $i$, $\tilde T$ does not contain an entry $h$ in any row $j<i$" is incorrect. For a counterexample, take $\lambda=(5,5)$ and $\mu=(4,2,2,2)$. Then $\tilde\lambda = (5,4)$ and $\tilde\mu=(4,2,2,1)$, and there is an SSYT $\tilde T$ of shape $\tilde\lambda$ and content $\tilde\mu$ with a $4$ at the end of the first row, which cannot be extended to an SSYT of shape $\lambda$ and content $\mu$. I am not going to delete this post, however, as I think it's useful to record the fact that this proof is wrong. – Timothy Chow Feb 26 '20 at 3:40

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$.

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$.