DECIDING POSITIVITY OF LITTLEWOOD-RICHARDSON COEFFICIENTS

被引：19

作者：

Buergisser, Peter ^{[1
]}

Ikenmeyer, Christian ^{[1
]}

机构：

[1] Univ Paderborn, Inst Math, D-33098 Paderborn, Germany

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2013年 / 27卷 / 04期

关键词：

Littlewood-Richardson coefficients; hive model; polynomial time algorithm; flows in networks; SCHUBERT CALCULUS; HONEYCOMB MODEL; COMPLEXITY;

D O I：

10.1137/120892532

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Starting with Knutson and Tao's hive model [J. Amer. Math. Soc., 12 (1999), pp. 1055-1090] we characterize the Littlewood-Richardson coefficient c(lambda)(nu),(mu) of given partitions lambda, mu, nu is an element of N-n as the number of capacity achieving hive flows on the honeycomb graph. Based on this, we design a polynomial time algorithm for deciding c(lambda)(nu),(mu) > 0. This algorithm is easy to state and takes O(n(3) log nu(1)) arithmetic operations and comparisons. We further show that the capacity achieving hive flows can be seen as the vertices of a connected graph, which leads to new structural insights into Littlewood-Richardson coefficients.

引用

页码：1639 / 1681

页数：43