direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Search for Publication

Suche nach Publikationen




All Publications

Small Littlewood-Richardson coefficients
Zitatschlüssel I-Small-Littlewood-Richardson-Coefficients
Autor Christian Ikenmeyer
Seiten 1–29
Jahr 2016
ISSN 1572-9192
DOI 10.1007/s10801-015-0658-2
Journal Journal of Algebraic Combinatorics
Jahrgang 44
Nummer 1
Monat 02
Notiz Java-Applet: http://www3.math.tu-berlin.de/algebra/flowapplet/
Zusammenfassung 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 zur Publikation Link zur Originalpublikation Download Bibtex Eintrag

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe