direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Ehemalige Mitarbeiter

Dr. Christian Ikenmeyer

Lupe [1]

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/ [2]

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)^2mathrmpoly(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^2mathrmpoly(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,Mmu,Mnu) = M + 1$ for all $M$. Here, the stretching of partitions is defined componentwise.
Link zur Publikation [3] Link zur Originalpublikation [4] Download Bibtex Eintrag [5]
------ Links: ------

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe

Diese Seite verwendet Matomo für anonymisierte Webanalysen. Mehr Informationen und Opt-Out-Möglichkeiten unter Datenschutz.
Copyright TU Berlin 2008