Small Littlewood-Richardson coefficients

We develop structural insights into the Littlewood-Richardson graph, whose number of vertices equals the Littlewood-Richardson coefficient for given partitions , , and . This graph was first introduced in Burgisser and Ikenmeyer (SIAM J Discrete Math 27(4):1639-1681, 2013), where its connectedness was proved. Our insights are useful for the design of algorithms for computing the Littlewood-Richardson coefficient: We design an algorithm for the exact computation of with running time , where , , and are partitions of length at most n. Moreover, we introduce an algorithm for deciding whether whose running time is . Even the existence of a polynomial-time algorithm for deciding whether is a nontrivial new result on its own. Our insights also lead to the proof of a conjecture by King et al. (Symmetry in physics. American Mathematical Society, Providence, 2004), stating that implies for all . Here, the stretching of partitions is defined componentwise.