TU Berlin

Fachgebiet Algorithmische AlgebraDr. Christian Ikenmeyer

Inhalt des Dokuments

zur Navigation

Ehemalige Mitarbeiter

Dr. Christian Ikenmeyer

Lupe

Kontakt
University of Liverpool
Department of Computer Science
Ashton Building, Office 311
Ashton Street, Liverpool, L69 3BX
United Kingdom
 
Persönliche Homepage
http://pcwww.liv.ac.uk/~iken/

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

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe