The Computational Complexity of Plethysm Coefficients

Christian Ikenmeyer (University of Liverpool, UK) Zoom talk at the Los Angeles Combinatorics and Complexity Seminar Date: Tue Oct 6, 2020, 10:15 am 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. Slides: http://pcwww.liv.ac.uk/~iken/ikenmeyer_plethysm.pdf Seminar Page: https://www.math.ucla.edu/~pak/seminars/CCSem-Fall-2020.htm #Combinatorics, #ComputationalComplexity, #RepresentationTheory