Reduced Kronecker coefficients and counter-examples to Mulmuley's strong saturation conjecture SH
Preprint
Abstract
We provide counter-examples to Mulmuley's strong saturation conjecture (strong SH) for the Kronecker coefficients. This conjecture was proposed in the setting of Geometric Complexity Theory to show that deciding whether or not a Kronecker coefficient is zero can be done in polynomial time. We also provide a short proof of the #P-hardness of computing the Kronecker coefficients. Both results rely on the connections between the Kronecker coefficients and another family of structural constants in the representation theory of the symmetric groups: Murnaghan's reduced Kronecker coefficients. An appendix by Mulmuley introduces a relaxed form of the saturation hypothesis SH, still strong enough for the aims of Geometric Complexity Theory.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Quasipolynomial formulas for the Kronecker coefficients indexed by two two―row shapes (extended abstract)Discrete Mathematics & Theoretical Computer Science, 2009
- On the complexity of computing Kostka numbers and Littlewood-Richardson coefficientsJournal of Algebraic Combinatorics, 2006
- A polynomiality property for Littlewood–Richardson coefficientsJournal of Combinatorial Theory, Series A, 2004
- The Kronecker Product of Schur Functions Indexed by Two-Row Shapes or Hook ShapesJournal of Algebraic Combinatorics, 2001
- The honeycomb model of $GL_n(\mathbb C)$ tensor products I: Proof of the saturation conjectureJournal of the American Mathematical Society, 1999
- Stability of Kronecker Products of Irreducible Characters of the Symmetric GroupThe Electronic Journal of Combinatorics, 1999
- HOPF ALGEBRAS OF SYMMETRIC FUNCTIONS AND TENSOR PRODUCTS OF SYMMETRIC GROUP REPRESENTATIONSInternational Journal of Algebra and Computation, 1991
- Products and Plethysms of Characters with Orthogonal, Symplectic and Symmetric GroupsCanadian Journal of Mathematics, 1958