We study a family of dissections of flow polytopes arising from the subdivision algebra. To each dissection of a flow polytope, we associate a polynomial, called the left-degree polynomial, which we show is invariant of the dissection considered (proven independently by Grinberg). We prove that left-degree polynomials encode integer points of generalized permutahedra. Using that certain left-degree polynomials are related to Grothendieck polynomials, we resolve special cases of conjectures by Monical, Tokcan, and Yong regarding the saturated Newton polytope property of Grothendieck polynomials.
Revised:
Accepted:
Published online:
Classification: 05E05, 05C21, 52B12
Keywords: Flow polytopes, Grothendieck polynomials, generalized permutahedra.
Author's affiliations:
@article{ALCO_2020__3_5_1197_0, author = {M\'esz\'aros, Karola and St.~Dizier, Avery}, title = {From generalized permutahedra to {Grothendieck} polynomials via flow polytopes}, journal = {Algebraic Combinatorics}, pages = {1197--1229}, publisher = {MathOA foundation}, volume = {3}, number = {5}, year = {2020}, doi = {10.5802/alco.136}, language = {en}, url = {https://alco.centre-mersenne.org/articles/10.5802/alco.136/} }
TY - JOUR TI - From generalized permutahedra to Grothendieck polynomials via flow polytopes JO - Algebraic Combinatorics PY - 2020 DA - 2020/// SP - 1197 EP - 1229 VL - 3 IS - 5 PB - MathOA foundation UR - https://alco.centre-mersenne.org/articles/10.5802/alco.136/ UR - https://doi.org/10.5802/alco.136 DO - 10.5802/alco.136 LA - en ID - ALCO_2020__3_5_1197_0 ER -
Mészáros, Karola; St. Dizier, Avery. From generalized permutahedra to Grothendieck polynomials via flow polytopes. Algebraic Combinatorics, Volume 3 (2020) no. 5, pp. 1197-1229. doi : 10.5802/alco.136. https://alco.centre-mersenne.org/articles/10.5802/alco.136/
[1] Kostant partitions functions and flow polytopes, Transform. Groups, Volume 13 (2008) no. 3-4, pp. 447-469 | Article | MR: 2452600 | Zbl: 1200.52008
[2] Counting integer flows in networks, Found. Comput. Math., Volume 4 (2004) no. 3, pp. 277-314 | Article | MR: 2078665 | Zbl: 1083.68640
[3] Computing the continuous discretely. Integer-point enumeration in polyhedra, Undergraduate Texts in Mathematics, Springer, New York, 2007, xviii+226 pages | Article | MR: 2271992 | Zbl: 1114.52013
[4] Toric matrix Schubert varieties and their polytopes, Proc. Amer. Math. Soc., Volume 144 (2016) no. 12, pp. 5081-5096 | Article | MR: 3556254 | Zbl: 1357.14064
[5] Subword complexes via triangulations of root polytopes, Algebr. Comb., Volume 1 (2018) no. 3, pp. 395-414 | Article | MR: 3856530 | Zbl: 1393.52010
[6] Schubert polynomials as integer point transforms of generalized permutahedra, Adv. Math., Volume 332 (2018), pp. 465-475 | Article | MR: 3810259 | Zbl: 06887354
[7] -unique reductions for Mészáros’s subdivision algebra, SIGMA Symmetry Integrability Geom. Methods Appl., Volume 14 (2018), Paper no. Paper No. 078, 34 pages | Article | MR: 3832979 | Zbl: 1395.05191
[8] Flow polytopes and the space of diagonal harmonics, Canad. J. Math., Volume 71 (2019) no. 6, pp. 1495-1521 | Article | MR: 4028467 | Zbl: 1427.05234
[9] Root polytopes, triangulations, and the subdivision algebra I, Trans. Amer. Math. Soc., Volume 363 (2011) no. 8, pp. 4359-4382 | Article | MR: 2792991 | Zbl: 1233.05215
[10] Root polytopes, triangulations, and the subdivision algebra II, Trans. Amer. Math. Soc., Volume 363 (2011) no. 11, pp. 6111-6141 | Article | MR: 2817421 | Zbl: 1233.05216
[11] Product formulas for volumes of flow polytopes, Proc. Amer. Math. Soc., Volume 143 (2015) no. 3, pp. 937-954 | Article | MR: 3293712 | Zbl: 1310.51024
[12] Flow polytopes of signed graphs and the Kostant partition function, Int. Math. Res. Not. IMRN (2015) no. 3, pp. 830-871 | Article | MR: 3340339 | Zbl: 1307.05097
[13] The polytope of Tesler matrices, Selecta Math. (N.S.), Volume 23 (2017) no. 1, pp. 425-454 | Article | MR: 3595898 | Zbl: 1355.05271
[14] Newton polytopes in algebraic combinatorics, Selecta Math. (N.S.), Volume 25 (2019) no. 5, Paper no. Paper No. 66, 37 pages | Article | MR: 4021852 | Zbl: 1426.05175
[15] Faces of generalized permutohedra, Doc. Math., Volume 13 (2008), pp. 207-273 | MR: 2520477 | Zbl: 1167.05005
[16] Permutohedra, associahedra, and beyond, Int. Math. Res. Not. IMRN (2009) no. 6, pp. 1026-1106 | Article | MR: 2487491 | Zbl: 1162.52007
[17] Combinatorial optimization. Polyhedra and efficiency. Vol. B, Algorithms and Combinatorics, 24, Springer-Verlag, Berlin, 2003, p. i-xxxiv and 649–1217 (Matroids, trees, stable sets, Chapters 39–69) | MR: 1956925 | Zbl: 1041.90001
[18] A polytope related to empirical distributions, plane trees, parking functions, and the associahedron, Discrete Comput. Geom., Volume 27 (2002) no. 4, pp. 603-634 | Article | MR: 1902680 | Zbl: 1012.52019
Cited by Sources: