Back to Search
Start Over
An efficient algorithm for deciding vanishing of Schubert polynomial coefficients
- Source :
- Adv. Math. 383 (2021), Paper No. 107669, 38 pp
- Publication Year :
- 2021
-
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 x n grid. In contrast, we show that computing these coefficients explicitly is #P-complete.<br />Comment: 30 pages. This paper was split off from 1810.10361v1, with a new title and abstract. That earlier preprint has been replaced by a conference proceedings version 1810.10361v2, with a different title and abstract; it contains complexity discussion and a related conjecture not found here. To appear in Advances in Math
- Subjects :
- Mathematics - Combinatorics
Subjects
Details
- Database :
- arXiv
- Journal :
- Adv. Math. 383 (2021), Paper No. 107669, 38 pp
- Publication Type :
- Report
- Accession number :
- edsarx.2103.05195
- Document Type :
- Working Paper