Peter Bürgisser ; Christian Ikenmeyer
-
A max-flow algorithm for positivity of Littlewood-Richardson coefficients
dmtcs:2749 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2009,
DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)
-
https://doi.org/10.46298/dmtcs.2749
A max-flow algorithm for positivity of Littlewood-Richardson coefficientsArticle
Authors: Peter Bürgisser 1; Christian Ikenmeyer 1
NULL##NULL
Peter Bürgisser;Christian Ikenmeyer
1 Mathematisches Institut der Universität Paderborn
Littlewood-Richardson coefficients are the multiplicities in the tensor product decomposition of two irreducible representations of the general linear group $\mathrm{GL}(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 $\textit{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.
Peter Burgisser;Cole Franks;Ankit Garg;Rafael Oliveira;Michael Walter;et al., arXiv (Cornell University), Towards a Theory of Non-Commutative Optimization: Geodesic 1st and 2nd Order Methods for Moment Maps and Polytopes, 2019, Baltimore, MD, USA, 10.1109/focs.2019.00055, http://arxiv.org/abs/1910.12375.