From generalized permutahedra to Grothendieck polynomials via flow polytopes
Algebraic Combinatorics, Volume 3 (2020) no. 5, pp. 1197-1229.

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.

Received: 2019-04-25
Revised: 2020-06-14
Accepted: 2020-06-17
Published online: 2020-10-12
DOI: https://doi.org/10.5802/alco.136
Classification: 05E05,  05C21,  52B12
Keywords: Flow polytopes, Grothendieck polynomials, generalized permutahedra.
@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},
     publisher = {MathOA foundation},
     volume = {3},
     number = {5},
     year = {2020},
     pages = {1197-1229},
     doi = {10.5802/alco.136},
     language = {en},
     url = {alco.centre-mersenne.org/item/ALCO_2020__3_5_1197_0/}
}
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/item/ALCO_2020__3_5_1197_0/

[1] Baldoni, Welleda; Vergne, Michèle Kostant partitions functions and flow polytopes, Transform. Groups, Volume 13 (2008) no. 3-4, pp. 447-469 | Article | MR 2452600 | Zbl 1200.52008

[2] Baldoni-Silva, Welleda; De Loera, Jesús A.; Vergne, Michèle Counting integer flows in networks, Found. Comput. Math., Volume 4 (2004) no. 3, pp. 277-314 | Article | MR 2078665 | Zbl 1083.68640

[3] Beck, Matthias; Robins, Sinai 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] Escobar, Laura; Mészáros, Karola 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] Escobar, Laura; Mészáros, Karola Subword complexes via triangulations of root polytopes, Algebr. Comb., Volume 1 (2018) no. 3, pp. 395-414 | Article | MR 3856530 | Zbl 1393.52010

[6] Fink, Alex; Mészáros, Karola; St. Dizier, Avery Schubert polynomials as integer point transforms of generalized permutahedra, Adv. Math., Volume 332 (2018), pp. 465-475 | Article | MR 3810259 | Zbl 06887354

[7] Grinberg, Darij t-unique reductions for Mészáros’s subdivision algebra, SIGMA Symmetry Integrability Geom. Methods Appl., Volume 14 (2018), Paper No. 078, 34 pages | Article | MR 3832979 | Zbl 1395.05191

[8] Liu, Ricky I.; Morales, Alejandro H.; Mészáros, Karola 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] Mészáros, Karola 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] Mészáros, Karola 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] Mészáros, Karola 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] Mészáros, Karola; Morales, Alejandro H. 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] Mészáros, Karola; Morales, Alejandro H.; Rhoades, Brendon The polytope of Tesler matrices, Selecta Math. (N.S.), Volume 23 (2017) no. 1, pp. 425-454 | Article | MR 3595898 | Zbl 1355.05271

[14] Monical, Cara; Tokcan, Neriman; Yong, Alexander Newton polytopes in algebraic combinatorics, Selecta Math. (N.S.), Volume 25 (2019) no. 5, Paper No. 66, 37 pages | Article | MR 4021852 | Zbl 1426.05175

[15] Postnikov, Alex; Reiner, Victor; Williams, Lauren Faces of generalized permutohedra, Doc. Math., Volume 13 (2008), pp. 207-273 | MR 2520477 | Zbl 1167.05005

[16] Postnikov, Alexander Permutohedra, associahedra, and beyond, Int. Math. Res. Not. IMRN (2009) no. 6, pp. 1026-1106 | Article | MR 2487491 | Zbl 1162.52007

[17] Schrijver, Alexander Combinatorial optimization. Polyhedra and efficiency. Vol. B, Algorithms and Combinatorics, Volume 24, Springer-Verlag, Berlin, 2003, p. i-xxxiv and 649–1217 (Matroids, trees, stable sets, Chapters 39–69) | MR 1956925 | Zbl 1041.90001

[18] Stanley, Richard P.; Pitman, Jim 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