On the complexity of computing Kronecker coefficients

2014/04/02 by Igor Pak, Greta Panova, Pak, Igor +1 · 1 citation
Mathematics · Computer Science · #Advanced Combinatorial Mathematics #Limits and Structures in Graph Theory #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.1404.0653

Abstract

We study the complexity of computing Kronecker coefficients g(λ,μ,ν). We give explicit bounds in terms of the number of parts ℓ in the partitions, their largest part size N and the smallest second part M of the three partitions. When M = O(1), i.e. one of the partitions is hook-like, the bounds are linear in log N, but depend exponentially on ℓ. Moreover, similar bounds hold even when M=e^O(ℓ). By a separate argument, we show that the positivity of Kronecker coefficients can be decided in O(log N) time for a bounded number ℓ of parts and without restriction on M. Related problems of computing Kronecker coefficients when one partition is a hook, and computing characters of S_n are also considered.

Cited by

• The Saxl Conjecture and the Dominance Order

Related

• Estimating and computing Kronecker Coefficients: a vector partition function approach
• Breaking down the reduced Kronecker coefficients
• Algebraic Obstructions and the Collapse of Elementary Structure in the Kronecker Problem
• Kronecker multiplicities in the (k,ℓ) hook are polynomially bounded
• Upper bounds on Kronecker coefficients with few rows