##### Department of Mathematics,

University of California San Diego

****************************

### Colloquium

## Greta Panova

#### University of Pennsylvania

## Kronecker coefficients in combinatorics and complexity theory

##### Abstract:

Some of the outstanding and still classical problems in Algebraic Combinatorics concern understanding the Kronecker coefficients of the symmetric group, the multiplicities describing the decomposition of tensor products of representations into irreducibles, which are nonnegative integers lacking a positive combinatorial formula for over 75 years. Recently they appeared in Geometric Complexity Theory (GCT), a program aimed to distinguish computational complexity classes (like the P vs NP problem) and prove complexity theoretic bounds using Algebraic Geometry and Representation Theory. On the combinatorial side, we \lbrack{Pak-P}\rbrack will show various bounds on Kronecker coefficients via character evaluations and partition enumeration, and use them to extend Sylvester and Stanley's theorem on the unimodality of partitions inside a rectangle and find asymptotic bounds. On the GCT side, using algebraic and combinatorial methods, we \lbrack{Burgisser-Ikenmeyer-P, Ikenmeyer-P}\rbrack show that the relevant Kronecker and plethysm coefficients of the general linear group are positive, thereby disproving a Mulmuley and Sohoni conjecture on the existence of ``occurrence obstructions" and practically showing that the 'P vs NP' problem is even more difficult. In the reverse direction, GCT arguments show that rectangular Kronecker coefficients are larger than plethysm coefficient in a stable range \lbrack{Ikenmyer-P}\rbrack, establishing a connection between apriori unrelated and greatly mysterious multiplicities.

Host: Sam Buss

### January 23, 2017

### 3:00 PM

### AP&M 6402

****************************