Skip to Main content Skip to Navigation
Conference papers

A max-flow algorithm for positivity of Littlewood-Richardson coefficients

Abstract : 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.
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Thursday, August 20, 2015 - 11:10:00 AM
Last modification on : Tuesday, March 7, 2017 - 3:05:29 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 10:12:00 AM


Publisher files allowed on an open archive




Peter Bürgisser, Christian Ikenmeyer. A max-flow algorithm for positivity of Littlewood-Richardson coefficients. 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), 2009, Hagenberg, Austria. pp.265-276, ⟨10.46298/dmtcs.2749⟩. ⟨hal-01185442⟩



Record views


Files downloads