@article{I-Small-Littlewood-Richardson-Coefficients,
Title = {Small Littlewood-Richardson coefficients},
Author = {Christian Ikenmeyer},
Pages = {1--29},
Year = {2016},
Issn = {1572-9192},
Doi = {10.1007/s10801-015-0658-2},
Journal = {Journal of Algebraic Combinatorics},
Volume = {44},
Number = {1},
Month = {02},
Note = {Java-Applet: http://www3.math.tu-berlin.de/algebra/flowapplet/},
Abstract = {We develop structural insights into the Littlewood-Richardson graph, whose number of vertices equals the Littlewood-Richardson coefficient $c(\lambda,\mu,\nu)$ for given partitions $\lambda$, $\mu$ and $\nu$. This graph was first introduced by B\"urgisser and Ikenmeyer in [arXiv:1204.2484], 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 c(λ,μ,ν) with running time $O(c(\lambda,\mu,\nu)^2\mathrm{poly}(n))$, where $\lambda$, $\mu$, and $\nu$ are partitions of length at most $n$. Moreover, we introduce an algorithm for deciding whether $c(\lambda,\mu,\nu)\ge t$ whose running time is $O(t^2\mathrm{poly}(n))$. Even the existence of a polynomial-time algorithm for deciding whether $c(\lambda,\mu,\nu)\ge 2$ is a nontrivial new result on its own. Our insights also lead to the proof of a conjecture by King, Tollu, and Toumazet posed in 2004, stating that $c(\lambda,\mu,\nu) = 2$ implies $c(M\lambda,M\mu,M\nu) = M + 1$ for all $M$. Here, the stretching of partitions is defined componentwise.},
Url = {http://arxiv.org/abs/1209.1521},
Url2 = {http://dx.doi.org/10.1007/s10801-015-0658-2}
}