Geodesic
A max-flow algorithm for positivity of Littlewood-Richardson coefficients
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009) (2009).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2009_special_256_a71,
     author = {B\"urgisser, Peter and Ikenmeyer, Christian},
     title = {A max-flow algorithm for positivity of {Littlewood-Richardson} coefficients},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)},
     year = {2009},
     doi = {10.46298/dmtcs.2749},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2749/}
}
TY  - JOUR
AU  - Bürgisser, Peter
AU  - Ikenmeyer, Christian
TI  - A max-flow algorithm for positivity of Littlewood-Richardson coefficients
JO  - Discrete mathematics & theoretical computer science
PY  - 2009
VL  - DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2749/
DO  - 10.46298/dmtcs.2749
LA  - en
ID  - DMTCS_2009_special_256_a71
ER  - 
%0 Journal Article
%A Bürgisser, Peter
%A Ikenmeyer, Christian
%T A max-flow algorithm for positivity of Littlewood-Richardson coefficients
%J Discrete mathematics & theoretical computer science
%D 2009
%V DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2749/
%R 10.46298/dmtcs.2749
%G en
%F DMTCS_2009_special_256_a71
Bürgisser, Peter; Ikenmeyer, Christian. A max-flow algorithm for positivity of Littlewood-Richardson coefficients. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009) (2009). doi : 10.46298/dmtcs.2749. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2749/

Cité par Sources :