An efficient algorithm for deciding vanishing of Schubert polynomial coefficients

Anshul Adve, Colleen Robichaux, Alexander Yong

Research output: Contribution to journalArticlepeer-review


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×n grid. In contrast, we show that computing these coefficients explicitly is #P-complete.

Original languageEnglish (US)
Article number107669
JournalAdvances in Mathematics
StatePublished - Jun 4 2021


  • Computational complexity
  • Generalized permutahedra
  • Schubert polynomial

ASJC Scopus subject areas

  • General Mathematics


Dive into the research topics of 'An efficient algorithm for deciding vanishing of Schubert polynomial coefficients'. Together they form a unique fingerprint.

Cite this