direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

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

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

This site uses Matomo for anonymized webanalysis. Visit Data Privacy for more information and opt-out options.