Ponencia
A max-flow algorithm for positivity of Littlewood-Richardson coefficients
Autor/es | Bürgisser, Peter
Ikenmeyer, Christian |
Fecha de publicación | 2009-11 |
Fecha de depósito | 2016-02-22 |
Publicado en |
|
Resumen | Littlewood-Richardson coefficients appear as limits of certain families of Kronecker coefficients. They have a wide variety of interpretations in combinatorics, representation theory and geometry. Mulmuley and Sohoni pointed ... Littlewood-Richardson coefficients appear as limits of certain families of Kronecker coefficients. 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. |
Cita | Bürgisser, P. y Ikenmeyer, C. (2009). A max-flow algorithm for positivity of Littlewood-Richardson coefficients. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
A max-flow algorithm for positivity ... | 665.8Kb | [PDF] | Ver/ | |