direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Ehemalige Mitarbeiter

Dr. Christian Ikenmeyer

Lupe

Kontakt
Max-Planck-Institut für Informatik
Department 1: Algorithms and Complexity
Campus E1 4, Room 311D
66123 Saarbrücken
Germany
 
Persönliche Homepage
people.mpi-inf.mpg.de/~cikenmey/

Publikationen in der Arbeitsgruppe

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