A combinatorial interpretation for certain plethysm and Kronecker coefficients

Abstract

We give explicit positive combinatorial interpretations for the plethysm coefficients $⟨s_{\hat{I}}¼[s_{\hat{I}}½],s_{\hat{I}}»⟩$, when $\hat{I}»$ has at most two rows, as counting certain marked trees. In the special case $\hat{I}¼=(n)$, this also yields a combinatorial interpretation for the corresponding rectangular Kronecker coefficient $g(\hat{I}»,(n^k),(n^k))$. While it is easy to express these quantities as differences of counting problems in the complexity class $\mathrm{FP}$, putting the problem in $\#\mathrm{P}$, our interpretations give a positive counting formula over explicit marked trees.

Minor corrections, final version. 13 pages. To appear in Proceedings of the AMS