×

An efficient algorithm for deciding vanishing of Schubert polynomial coefficients. (English) Zbl 1508.14062

Summary: 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.

MSC:

14N15 Classical problems, Schubert calculus
05E05 Symmetric functions and generalizations
05E10 Combinatorial aspects of representation theory
14M15 Grassmannians, Schubert varieties, flag manifolds
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
68W30 Symbolic computation and algebraic computation
14Q15 Computational aspects of higher-dimensional varieties
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Adve, A.; Robichaux, C.; Yong, A., Computational complexity, Newton polytopes, and Schubert polynomials, (Proceedings of the 31st Conference on Formal Power Series and Algebraic Combinatorics (Ljubljana). Proceedings of the 31st Conference on Formal Power Series and Algebraic Combinatorics (Ljubljana), Sem. Lothar. Combin., vol. 82B (2020)), Art. 52, 12 pp · Zbl 1436.05115
[2] Adve, A.; Robichaux, C.; Yong, A., Complexity, combinatorial positivity, and Newton polytopes (2018), preprint
[3] Billey, S.; Jockusch, W.; Stanley, R. P., Some combinatorial properties of Schubert polynomials, J. Algebraic Comb., 2, 4, 345-374 (1993) · Zbl 0790.05093
[4] Fink, A.; Mészáros, K.; Dizier, A. St., Schubert polynomials as integer point transforms of generalized permutahedra, Adv. Math., 332, 465-475 (2018) · Zbl 1443.05179
[5] Fomin, S.; Greene, C.; Reiner, V.; Shimozono, M., Balanced labellings and Schubert polynomials, Eur. J. Comb., 18, 4, 373-389 (1997) · Zbl 0871.05059
[6] Fulton, W., Young Tableaux. With Applications to Representation Theory and Geometry, London Mathematical Society Student Texts, vol. 35 (1997), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0878.14034
[7] Knutson, A.; Yong, A., A formula for K-theory truncation Schubert calculus, Int. Math. Res. Not., 70, 3741-3756 (2004) · Zbl 1072.14071
[8] Lascoux, A.; Schützenberger, M.-P., Schubert polynomials and the Littlewood-Richardson rule, Lett. Math. Phys., 10, 111-124 (1985) · Zbl 0586.20007
[9] Lascoux, A.; Schützenberger, M.-P., Polynômes de Schubert, C. R. Acad. Sci., Sér. 1 Math., 294, 447-450 (1982) · Zbl 0495.14031
[10] Manivel, L., Symmetric Functions, Schubert Polynomials and Degeneracy Loci, SMF/AMS Texts and Monographs (2001), American Mathematical Society: American Mathematical Society Providence, translated from the 1998 French original by John R. Swallow · Zbl 0998.14023
[11] Monical, C.; Tokcan, N.; Yong, A., Newton polytopes in algebraic combinatorics, Sel. Math., 25, 5, Article 66 pp. (2019), 37 pp. · Zbl 1426.05175
[12] Narayanan, H., On the complexity of computing Kostka numbers and Littlewood-Richardson coefficients, J. Algebraic Comb., 24, 3, 347-354 (2006) · Zbl 1101.05066
[13] Papadimitriou, C. H.; Steiglitz, K., Combinatorial Optimization: Algorithms and Complexity (1998), Dover Publications, Inc.: Dover Publications, Inc. Mineola, NY, xvi+496 pp., corrected reprint of the 1982 original · Zbl 0944.90066
[14] Schrijver, A., Theory of Linear and Integer Programming (1998), John Wiley & Sons · Zbl 0970.90052
[15] Stanley, R. P., Some Schubert shenanigans (2017), preprint
[16] Valiant, L. G., The complexity of computing the permanent, Theor. Comput. Sci., 8, 2, 189-201 (1979) · Zbl 0415.68008
[17] Weigandt, A., Schubert polynomials, 132-patterns, and Stanley’s conjecture, Algebraic Combin., 1, 4, 415-423 (2018) · Zbl 1397.05205
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.