Why is a general formula for Kostka numbers "unlikely" to exist?A general formula for K λ μ exists, where K λ μ is the number of semistandard Young tableaux of shape λ and type μ with λ ⊢ n and μ a weak composition of n.

Question

Why is a general formula for Kostka numbers &quot;unlikely&quot; to exist?A general formula for       K          λ      μ       exists, where        K          λ      μ        is the number of semistandard Young tableaux of shape   λ and type   μ with   λ  ⊢  n and   μ a weak composition of   n.

Aurora Hutchinson · Accepted Answer

1) By a &quot;general formula&quot; you mean a product of some kind of factorials. This is rather uninteresting, since it&#039;s unclear what those factorials would be. Kostka numbers tend to be chaotic, so I am sure you can find relatively small partitions with annoying large prime factors. What do you do next? One can also ask about asymptotic results which don&#039;t allow this, in the flavor of de Bruijn. But again there are too many choices to consider, and none are really enlightening.2) There is a formal notion of #P-completness, a computational complexity class, loosely corresponding to hard counting problems. It is known that Kostka numbers are #P-complete. This means that computing Kostka numbers in full generality is just as hard as computing the number of 3-colorings in graphs.3) Continuing with the theme &quot;formula&quot; as a polynomial algorithm. Such &quot;formulas&quot; do exist in special cases then. For example, if the number of rows in both partitions is fixed, Kostka numbers become the number of integer points in a finite dimensional polytope, which can be computed in polynomial time.4) Alternatively, there is a rather weak notion of &quot;formula&quot; due to Wilf. Roughly, he asks for the algorithm which is asymptotically faster than trivial enumeration. But then one can use the &quot;inverse Kostka numbers&quot; which have their own combinatorial interpretation, which are similar but perhaps slightly faster to compute. Since Wilf only asks for a little better than trivial bound, one can compute the whole matrix of Kostka numbers which has sub-exponential size p(n), while Kostka numbers are exponential under mild conditions.

Why is a general formula for Kostka numbers "unlikely" to exist? A general formula for Kλμ exists, where Kλμ is the number of semistandard Young tableaux of shape λ and type μ with λ⊢n and μ a weak composition of n.

Answered question

Answer & Explanation

New Questions in Advanced Physics