TU Berlin

Fachgebiet Algorithmische AlgebraPublications

Page Content

to Navigation

There is no English translation for this web page.

Search for Publication

Search for publications




All Publications

Small Littlewood-Richardson coefficients
Citation key I-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(ł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.
Link to publication Link to original publication Download Bibtex entry

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe