Small Littlewood-Richardson coefficients

Understand

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({\lambda},{\mu},{\nu}) with running time O(c({\lambda},{\mu},{\nu})^2 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}) >= t whose running time is O(t^2 poly(n)).