A max-flow algorithm for positivity of Littlewood-Richardson coefficients
Abstrak
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.
Topik & Kata Kunci
Penulis (2)
Peter Bürgisser
Christian Ikenmeyer
Akses Cepat
- Tahun Terbit
- 2009
- Sumber Database
- DOAJ
- DOI
- 10.46298/dmtcs.2749
- Akses
- Open Access ✓