The Computational Complexity of Plethysm Coefficients

Christian Ikenmeyer (University of Liverpool)

06-Oct-2020, 17:15-17:45 (3 years ago)

Abstract: We show that deciding positivity of plethysm coefficients is NP-hard, and that computing plethysm coefficients is #P-hard. In fact, both problems remain hard even if the inner parameter of the plethysm coefficient is fixed. In this way we obtain an inner versus outer contrast: If the outer parameter of the plethysm coefficient is fixed, then the plethysm coefficient can be computed in polynomial time. Moreover, we derive new lower and upper bounds and in special cases even combinatorial descriptions for plethysm coefficients, which is a contribution towards Stanley's 9th problem from his list from 1999.

Our technique uses discrete tomography in a more refined way than the recent work on Kronecker coefficients by Ikenmeyer, Mulmuley, and Walter (2017). This makes our work the first to apply techniques from discrete tomography to the study of plethysm coefficients. Quite surprisingly, that interpretation also leads to new equalities between certain plethysm coefficients and Kronecker coefficients.

computational complexitydiscrete mathematicscombinatoricsrepresentation theory

Audience: researchers in the topic

( paper | slides | video )


LA Combinatorics and Complexity Seminar

Series comments: Password is on the seminar page. www.math.ucla.edu/~pak/seminars/CCSem-Fall-2020.htm

Organizers: Igor Pak*, Greta Panova
*contact for this listing

Export talk to