You are here

 An Efficient Algorithm for Deciding the Vanishing of Schubert Polynomial Coefficients

Colleen Robichaux, UIUC
Wednesday, April 28, 2021 - 3:30pm to 5:00pm
via Zoom

Note: This talk begins with a pre-seminar (aimed at graduate students) at 3:30–4:00. The main talk starts at 4:10.

Join Zoom Meeting:
Meeting ID: 915 4733 5974

Schubert polynomials form a basis of all polynomials and appear in the study of cohomology rings of flag manifolds. The vanishing problem for Schubert polynomials asks if a coefficient of a Schubert polynomial is zero. We give a tableau criterion to solve this problem, from which we deduce the first polynomial time algorithm. These results are obtained from new characterizations of the Schubitope, a generalization of the permutahedron defined for any subset of the \$n \times n\$ grid. In contrast, we show that computing these coefficients explicitly is #P-complete. This is joint work with Anshul Adve and Alexander Yong.