Page Content
to Navigation
There is no English translation for this web page.
Dr. Christian Ikenmeyer
- © Christian Ikenmeyer
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
| Citation key | BI-A-Max-Flow-Algorithm-For-Positivity-Of-Littlewood-Richardson-Coefficients |
|---|---|
| Author | Peter Bürgisser and Christian Ikenmeyer |
| Title of Book | FPSAC 2009 |
| Pages | 267-278 |
| Year | 2009 |
| Address | Hagenberg, Austria |
| Series | DMTCS proc. AK |
| Abstract | 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 |