Abstract
Geometric complexity theory suggests intriguing connections between positivity problems in algebraic combinatorics and complexity theory. I will discuss a general algebraic technique for finding positive combinatorial formula for the Schur expansion of symmetric functions. This technique has its origins in the \emph{plactic algebra}, the free associative algebra in the alphabet of positive integers modulo Knuth equivalence. It has been known since the work of Sch\""utzenberger and Lascoux from the 1980's that the plactic algebra contains a subalgebra isomorphic to the ring of symmetric functions, equipped with a basis of noncommutative versions of Schur functions.
More recently, Fomin and Greene showed that the plactic algebra can be modified by replacing certain pairs of Knuth relations by weaker four-term relations. By studying the noncommutative Schur functions in this algebra, they obtain Schur expansions for a large class of symmetric functions including Stanley symmetric functions and stable Grothendieck polynomials.
Several years ago, Assaf defined variants of Knuth equivalence to prove Schur positivity of Macdonald polynomials. Using this work as a starting point, Sergey Fomin and I extend the Fomin-Greene setup to give Assaf's equivalences an algebraic framework and thereby obtain an approach to finding positive combinatorial formulae for the Schur expansions of an even larger class of symmetric functions. One application is a positive combinatorial formula for the Schur expansion of 3-column Macdonald polynomials.