Abstract |
We develop structural insights into the Littlewood-Richardson graph, whose number of vertices equals the Littlewood-Richardson coefficient $c(łambda,\mu,\nu)$ for given partitions λ, μ and ν. This graph was first introduced by Bürgisser 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(łambda,\mu,\nu)^2\mathrmpoly(n))$, where λ, μ, and ν are partitions of length at most $n$. Moreover, we introduce an algorithm for deciding whether $c(łambda,\mu,\nu)\ge t$ whose running time is $O(t^2\mathrmpoly(n))$. Even the existence of a polynomial-time algorithm for deciding whether $c(łambda,\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(łambda,\mu,\nu) = 2$ implies $c(Młambda,M\mu,M\nu) = M + 1$ for all $M$. Here, the stretching of partitions is defined componentwise. |