@article{aa48c76357fc461c9df81f8a1be6d2fc,

title = "An efficient algorithm for deciding vanishing of Schubert polynomial coefficients",

abstract = "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.",

keywords = "Computational complexity, Generalized permutahedra, Schubert polynomial",

author = "Anshul Adve and Colleen Robichaux and Alexander Yong",

note = "Funding Information: AY was supported by NSF grant DMS 1500691 , a Simons Collaboration grant 582242 and a UIUC Campus Research Board grant RB18101 . CR was supported by the NSF Graduate Research Fellowship Program under Grant No. DGE - 1746047 . We acknowledge Mathoverflow, S. Kintali's blog “My brain is open” and R. O'Donnell's Youtube videos (from his class at Carnegie Mellon) for background. We thank Philipp Hieronymi, Alexandr Kostochka, Cara Monical, Erik Walsberg, Douglas West, Alexander Woo, for helpful comments and conversations. We also thank the anonymous referee for their insightful suggestions that improved the clarity of this paper. Publisher Copyright: {\textcopyright} 2021 Elsevier Inc.",

year = "2021",

month = jun,

day = "4",

doi = "10.1016/j.aim.2021.107669",

language = "English (US)",

volume = "383",

journal = "Advances in Mathematics",

issn = "0001-8708",

publisher = "Academic Press Inc.",

}