TU Berlin

Fachgebiet Algorithmische AlgebraRefereed Contributions

Inhalt des Dokuments

zur Navigation

Refereed Contributions

A max-flow algorithm for positivity of Littlewood-Richardson coefficients
Zitatschlüssel BI-A-Max-Flow-Algorithm-For-Positivity-Of-Littlewood-Richardson-Coefficients
Autor Peter Bürgisser and Christian Ikenmeyer
Buchtitel FPSAC 2009
Seiten 267-278
Jahr 2009
Adresse Hagenberg, Austria
Serie DMTCS proc. AK
Zusammenfassung Littlewood-Richardson coefficients are the multiplicities in the tensor product decomposition of two irreducible representations of the general linear group $\mathrmGL(n,\mathbb C)$. They have a wide variety of interpretations in combinatorics, representation theory and geometry. Mulmuley and Sohoni pointed out that it is possible to decide the positivity of Littlewood-Richardson coefficients in polynomial time. This follows by combining the saturation property of Littlewood-Richardson coefficients (shown by Knutson and Tao 1999) with the well-known fact that linear optimization is solvable in polynomial time. We design an explicit combinatorial polynomial time algorithm for deciding the positivity of Littlewood-Richardson coefficients. This algorithm is highly adapted to the problem and it is based on ideas from the theory of optimizing flows in networks
Link zur Publikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe