A max-flow algorithm for positivity of Littlewood-Richardson coefficients
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 Soh...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2009-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/2749/pdf |
| _version_ | 1797270370784378880 |
|---|---|
| author | Peter Bürgisser Christian Ikenmeyer |
| author_facet | Peter Bürgisser Christian Ikenmeyer |
| author_sort | Peter Bürgisser |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T02:03:12Z |
| format | Article |
| id | doaj.art-b142dcf6548449d79f9d013c6b85aa92 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:03:12Z |
| publishDate | 2009-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-b142dcf6548449d79f9d013c6b85aa922024-03-07T14:45:40ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502009-01-01DMTCS Proceedings vol. AK,...Proceedings10.46298/dmtcs.27492749A max-flow algorithm for positivity of Littlewood-Richardson coefficientsPeter Bürgisser0Christian Ikenmeyer1Mathematisches Institut der Universität PaderbornMathematisches Institut der Universität PaderbornLittlewood-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.https://dmtcs.episciences.org/2749/pdflittlewood-richardson coefficientssaturation conjectureflows in networkpolynomial time[math.math-co] mathematics [math]/combinatorics [math.co][info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | Peter Bürgisser Christian Ikenmeyer A max-flow algorithm for positivity of Littlewood-Richardson coefficients Discrete Mathematics & Theoretical Computer Science littlewood-richardson coefficients saturation conjecture flows in network polynomial time [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| title | A max-flow algorithm for positivity of Littlewood-Richardson coefficients |
| title_full | A max-flow algorithm for positivity of Littlewood-Richardson coefficients |
| title_fullStr | A max-flow algorithm for positivity of Littlewood-Richardson coefficients |
| title_full_unstemmed | A max-flow algorithm for positivity of Littlewood-Richardson coefficients |
| title_short | A max-flow algorithm for positivity of Littlewood-Richardson coefficients |
| title_sort | max flow algorithm for positivity of littlewood richardson coefficients |
| topic | littlewood-richardson coefficients saturation conjecture flows in network polynomial time [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| url | https://dmtcs.episciences.org/2749/pdf |
| work_keys_str_mv | AT peterburgisser amaxflowalgorithmforpositivityoflittlewoodrichardsoncoefficients AT christianikenmeyer amaxflowalgorithmforpositivityoflittlewoodrichardsoncoefficients AT peterburgisser maxflowalgorithmforpositivityoflittlewoodrichardsoncoefficients AT christianikenmeyer maxflowalgorithmforpositivityoflittlewoodrichardsoncoefficients |