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 coefficientsConference paper
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 GL(n,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.
Brett Collins, 2020, Generalized Littlewood–Richardson coefficients for branching rules of GL(n)and extremal weight crystals, Algebraic Combinatorics, 3, 6, pp. 1365-1400, 10.5802/alco.143, https://doi.org/10.5802/alco.143.
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, pp. 845-861, 2019, Baltimore, MD, USA, 10.1109/focs.2019.00055, http://arxiv.org/abs/1910.12375.