Vanishing of Littlewood-Richardson polynomials is in P

Preprint English OPEN
Adve, Anshul; Robichaux, Colleen; Yong, Alexander;
  • Subject: Mathematics - Combinatorics | Computer Science - Computational Complexity | Mathematics - Representation Theory
    arxiv: Mathematics::Combinatorics

J. DeLoera-T. McAllister and K. D. Mulmuley-H. Narayanan-M. Sohoni independently proved that determining the vanishing of Littlewood-Richardson coefficients has strongly polynomial time computational complexity. Viewing these as Schubert calculus numbers, we prove the g... View more
  • References (27)
    27 references, page 1 of 3

    [1] D. Anderson, E. Richmond, and A. Yong, Eigenvalues of Hermitian matrices and equivariant cohomology of Grassmannians, Compositio Math. vol 149 (2013), 1569-1582.

    [2] P. Belkale, Quantum generalization of the Horn conjecture, J. Amer. Math. Soc. 21 (2008), no. 2, 365-408.

    [3] A. S. Buch, A. Kresch and H. Tamvakis, Gromov-Witten invariants on Grassmannians, J. Amer. Math. Soc., 16 (2003), 901-915.

    [4] A. S. Buch, A. Kresch, K. Purbhoo, Kevin, H. Tamvakis, The puzzle conjecture for the cohomology of twostep flag manifolds, J. Algebraic Combin. 44 (2016), no. 4, 973-1007.

    [5] A. S. Buch, A Littlewood-Richardson rule for the K-theory of Grassmannians, Acta Math. 189 (2002), no. 1, 37-78

    [6] P. B u¨rgisser and C. Ikenmeyer, The complexity of computing Kronecker coefficients, in Discrete Math. Theor. Comput. Sci. Proc., Assoc. DMTCS, Nancy, 2008, 357-368.

    [7] J. A. De Loera and T. B. McAllister, On the computation of Clebsch-Gordan coefficients and the dilation effect, Experiment. Math., 15(1):7-19, 2006.

    [8] W. Graham, Positivity in equivariant Schubert calculus, Duke Math. J., 109 (2001), no. 3, 599-614.

    [9] M. Grotschel, L. Lovasz and A. Schrijver, Geometric algorithms and combinatorial optimization, Springer Verlag, 1993.

    [10] C. Ikenmeyer, K. D. Mulmuley and M. Walter, On vanishing of Kronecker coefficients, Computational complexity, to appear, 2017.

  • Metrics
Share - Bookmark