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.


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.


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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: