# 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.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [13 references]

https://hal.inria.fr/hal-01185442
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

### File

dmAK0122.pdf
Publisher files allowed on an open archive

### Citation

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