Deciding Positivity of Littlewood-Richardson Coefficients

Abstract

Starting with Knutson and Tao's hive model (in J. Amer. Math. Soc., 1999) we characterize the Littlewood-Richardson coefficient $c_{\lambda ,\mu }^{\nu }$ of given partitions $\lambda ,\mu ,\nu \in N^n$ as the number of capacity achieving hive flows on the honeycomb graph. Based on this, we design a polynomial time algorithm for deciding $c_{\lambda ,\mu }^{\nu }>0$. This algorithm is easy to state and takes $O(n^3\log {\nu }_1)$ arithmetic operations and comparisons. We further show that the capacity achieving hive flows can be seen as the vertices of a connected graph, which leads to new structural insights into Littlewood-Richardson coefficients.

arXiv comment38 pages

References in corpus (1)

• Small Littlewood-Richardson coefficients

Cited by in corpus (1)

• Small Littlewood-Richardson coefficients