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

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.


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


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