A combinatorial model for computing volumes of flow polytopes

Benedetti, Carolina; González D’León, Rafael; Hanusa, Christopher; Harris, Pamela; Khare, Apoorva; Morales, Alejandro; Yip, Martha

doi:10.1090/tran/7743

A combinatorial model for computing volumes of flow polytopes

Authors: Carolina Benedetti, Rafael S. González D’León, Christopher R. H. Hanusa, Pamela E. Harris, Apoorva Khare, Alejandro H. Morales and Martha Yip
Journal: Trans. Amer. Math. Soc. 372 (2019), 3369-3404
MSC (2010): Primary 05A15, 05A19, 52B05, 52A38; Secondary 05C20, 05C21, 52B11
DOI: https://doi.org/10.1090/tran/7743
Published electronically: May 23, 2019
MathSciNet review: 3988614
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We introduce new families of combinatorial objects whose enumeration computes volumes of flow polytopes. These objects provide an interpretation, based on parking functions, of Baldoni and Vergne's generalization of a volume formula originally due to Lidskii. We recover known flow polytope volume formulas and prove new volume formulas for flow polytopes. A highlight of our model is an elegant formula for the flow polytope of a graph we call the caracol graph.

As by-products of our work, we uncover a new triangle of numbers that interpolates between Catalan numbers and the number of parking functions, we prove the log-concavity of rows of this triangle along with other sequences derived from volume computations, and we introduce a new Ehrhart-like polynomial for flow polytope volume and conjecture product formulas for the polytopes we consider.

[1] A. D. Alexandrov,
To the theory of mixed volumes of convex bodies, Part IV,
Mat. Sb. 3 (1938), no. 45, 227-249.
[2] Drew Armstrong, Nicholas A. Loehr, and Gregory S. Warrington, Rational parking functions and Catalan numbers, Ann. Comb. 20 (2016), no. 1, 21–58. MR 3461934, https://doi.org/10.1007/s00026-015-0293-6
[3] V. I. Arnol′d, Snake calculus and the combinatorics of the Bernoulli, Euler and Springer numbers of Coxeter groups, Uspekhi Mat. Nauk 47 (1992), no. 1(283), 3–45, 240 (Russian); English transl., Russian Math. Surveys 47 (1992), no. 1, 1–51. MR 1171862, https://doi.org/10.1070/RM1992v047n01ABEH000861
[4] Welleda Baldoni and Michèle Vergne, Kostant partitions functions and flow polytopes, Transform. Groups 13 (2008), no. 3-4, 447–469. MR 2452600, https://doi.org/10.1007/s00031-008-9019-8
[5] Matthias Beck, Ana Berrizbeitia, Michael Dairyko, Claudia Rodriguez, Amanda Ruiz, and Schuyler Veeneman, Parking functions, Shi arrangements, and mixed graphs, Amer. Math. Monthly 122 (2015), no. 7, 660–673. MR 3383893, https://doi.org/10.4169/amer.math.monthly.122.7.660
[6] C. Ceballos and R. S. González D'León,
On -Catalan Combinatorics,
preprint, https://arxiv.org/pdf/1805.03863, 2018.
[7] Clara S. Chan, David P. Robbins, and David S. Yuen, On the volume of a certain polytope, Experiment. Math. 9 (2000), no. 1, 91–99. MR 1758803
[8] Sylvie Corteel, Jang Soo Kim, and Karola Mészáros, Flow polytopes with Catalan volumes, C. R. Math. Acad. Sci. Paris 355 (2017), no. 3, 248–259 (English, with English and French summaries). MR 3621250, https://doi.org/10.1016/j.crma.2017.01.007
[9] Dominique Foata and John Riordan, Mappings of acyclic and parking functions, Aequationes Math. 10 (1974), 10–22. MR 335294, https://doi.org/10.1007/BF01834776
[10] W. Fenchel,
Inégalités quadratiques entre les volumes mixtes des corps convexes,
C. R. Acad. Sci. Paris 203 (1936), 647-650.
[11] W. Fenchel,
Généralizations du théoréme de Brunn et Minkowski concernant les corps convexes,
C. R. Acad. Sci. Paris 203 (1936), 764-766.
[12] James Haglund, The 𝑞,𝑡-Catalan numbers and the space of diagonal harmonics, University Lecture Series, vol. 41, American Mathematical Society, Providence, RI, 2008. With an appendix on the combinatorics of Macdonald polynomials. MR 2371044
[13] Lutz Hille, Quivers, cones and polytopes, Linear Algebra Appl. 365 (2003), 215–237. Special issue on linear algebra methods in representation theory. MR 1987339, https://doi.org/10.1016/S0024-3795(02)00406-8
[14] James E. Humphreys, Introduction to Lie algebras and representation theory, Springer-Verlag, New York-Berlin, 1972. Graduate Texts in Mathematics, Vol. 9. MR 0323842
[15] A. G. Konheim and B. Weiss,
An occupancy discipline and applications,
SIAM J. Appl. Math 14 (1966), no. 6, 1266-1274.
[16] F. Liu,
On positivity of Ehrhart polynomials,
preprint, https://arxiv.org/abs/1711.09962, 2017.
[17] Karola Mészáros, Product formulas for volumes of flow polytopes, Proc. Amer. Math. Soc. 143 (2015), no. 3, 937–954. MR 3293712, https://doi.org/10.1090/S0002-9939-2014-12182-4
[18] Karola Mészáros and Alejandro H. Morales, Flow polytopes of signed graphs and the Kostant partition function, Int. Math. Res. Not. IMRN 3 (2015), 830–871. MR 3340339, https://doi.org/10.1093/imrn/rnt212
[19] K. Mészáros and A. H. Morales, Volumes and Ehrhart polynomials of flow polytopes, preprint, https://arxiv.org/abs/1710.00701, 2017, to appear in Math. Z.
[20] Karola Mészáros, Alejandro H. Morales, and Brendon Rhoades, The polytope of Tesler matrices, Selecta Math. (N.S.) 23 (2017), no. 1, 425–454. MR 3595898, https://doi.org/10.1007/s00029-016-0241-2
[21] K. Mészáros, A. H. Morales, and J. Striker. On flow polytopes, order polytopes, and certain faces of the alternating sign matrix polytope. Preprint, https://arxiv.org/abs/1510.03357. To appear in Electron. J. Combin.
[22] K. Mészáros and A. St. Dizier, From generalized permutahedra to Grothendieck polynomials via flow polytopes, preprint, https://arxiv.org/abs/1705.02418, 2017.
[23] K. Mészáros, C. Simpson, and Z. Wellner, Flow polytopes of partitions, preprint, https://arxiv.org/abs/1707.03100, 2017, to appear in Electron. J. Combin.
[24] Robert A. Proctor, New symmetric plane partition identities from invariant theory work of De Concini and Procesi, European J. Combin. 11 (1990), no. 3, 289–300. MR 1059559, https://doi.org/10.1016/S0195-6698(13)80128-X
[25] N. J. A. Sloane (ed.),
The on-line encyclopedia of integer sequences,
published electronically at https://oeis.org.
[26] Richard P. Stanley, Two combinatorial applications of the Aleksandrov-Fenchel inequalities, J. Combin. Theory Ser. A 31 (1981), no. 1, 56–65. MR 626441, https://doi.org/10.1016/0097-3165(81)90053-4
[27] Richard P. Stanley, Two poset polytopes, Discrete Comput. Geom. 1 (1986), no. 1, 9–23. MR 824105, https://doi.org/10.1007/BF02187680
[28] Richard P. Stanley, A survey of alternating permutations, Combinatorics and graphs, Contemp. Math., vol. 531, Amer. Math. Soc., Providence, RI, 2010, pp. 165–196. MR 2757798, https://doi.org/10.1090/conm/531/10466
[29] Richard P. Stanley, Catalan numbers, Cambridge University Press, New York, 2015. MR 3467982
[30] Richard P. Stanley and Jim Pitman, A polytope related to empirical distributions, plane trees, parking functions, and the associahedron, Discrete Comput. Geom. 27 (2002), no. 4, 603–634. MR 1902680, https://doi.org/10.1007/s00454-002-2776-6
[31] R. P. Stanley and A. Postnikov,
Acyclic flow polytopes and Kostant's partition function,
preprint, 2000, available at http://www-math.mit.edu/~rstan/transparencies/kostant.ps.
[32] Catherine Huafei Yan, On the enumeration of generalized parking functions, Proceedings of the Thirty-first Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 2000), 2000, pp. 201–209. MR 1818000
[33] Catherine H. Yan, Generalized parking functions, tree inversions, and multicolored graphs, Adv. in Appl. Math. 27 (2001), no. 2-3, 641–670. Special issue in honor of Dominique Foata’s 65th birthday (Philadelphia, PA, 2000). MR 1868985, https://doi.org/10.1006/aama.2001.0754
[34] Doron Zeilberger, Proof of a conjecture of Chan, Robbins, and Yuen, Electron. Trans. Numer. Anal. 9 (1999), 147–148. Orthogonal polynomials: numerical and symbolic algorithms (Leganés, 1998). MR 1749805
[35] Yue Zhou, Jia Lu, and Houshan Fu, Leading coefficients of Morris type constant term identities, Adv. in Appl. Math. 87 (2017), 24–42. MR 3629261, https://doi.org/10.1016/j.aam.2016.12.005

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05A15, 05A19, 52B05, 52A38, 05C20, 05C21, 52B11

Retrieve articles in all journals with MSC (2010): 05A15, 05A19, 52B05, 52A38, 05C20, 05C21, 52B11

Additional Information

Carolina Benedetti
Affiliation: Departamento de Matemáticas, Universidad de los Andes, Bogotá, Colombia
Email: c.benedetti@uniandes.edu.co

Rafael S. González D’León
Affiliation: Escuela de Ciencias Exactas e Ingeniería, Universidad Sergio Arboleda, Bogotá, Colombia
Email: rafael.gonzalezl@usa.edu.co

Christopher R. H. Hanusa
Affiliation: Department of Mathematics, Queens College (CUNY), 65-30 Kissena Boulevard, Flushing, New York 11367
Email: chanusa@qc.cuny.edu

Pamela E. Harris
Affiliation: Department of Mathematics and Statistics, Williams College, Bascom House, Room 106C, 33 Stetson Court, Williamstown, Massachusetts 01267
Email: peh2@williams.edu

Apoorva Khare
Affiliation: Department of Mathematics, Indian Institute of Science, Analysis and Probability Research Group, Bangalore 560012, India
Email: khare@iisc.ac.in

Alejandro H. Morales
Affiliation: Department of Mathematics and Statistics, University of Massachusetts, Amherst, Massachusetts 01003
Email: ahmorales@math.umass.edu

Martha Yip
Affiliation: Department of Mathematics, University of Kentucky, 715 Patterson Office Tower, Lexington, Kentucky 40506-0027
Email: martha.yip@uky.edu

DOI: https://doi.org/10.1090/tran/7743
Keywords: Flow polytope, parking function, Lidskii formula, Kostant partition function, caracol graph, Chan--Robbins--Yuen polytope, Tesler polytope, Pitman--Stanley polytope, zigzag graph, line-dot diagram, gravity diagram, unified diagram, log-concave, Catalan numbers, parking triangle, binomial transform, Dyck path, multi-labeled Dyck path, Ehrhart polynomial
Received by editor(s): January 30, 2018
Received by editor(s) in revised form: October 26, 2018
Published electronically: May 23, 2019
Additional Notes: The first author was supported by FAPA grant from Universidad de los Andes Faculty of Science, and by York University and the Fields Institute
The second author was supported during this project by the University of Kentucky, York University, and Universidad Sergio Arboleda, and he is grateful for their support.
The third author is grateful for the support of PSC-CUNY Award 69120-0047.
The fourth author was supported by NSF award DMS-1620202.
The fifth author was partially supported by Ramanujan Fellowship SB/S2/RJN-121/2017 and MATRICS grant MTR/2017/000295 from SERB (Government of India), by grant F.510/25/CAS-II/2018(SAP-I) from UGC (Government of India), and by a Young Investigator Award from the Infosys Foundation.
The sixth author was partially supported by an AMS-Simons Travel Grant.
The seventh author was partially supported by Simons Collaboration Grant 429920.
Dedicated: Dedicated to the memory of Griff L. Bilbro
Article copyright: © Copyright 2019 American Mathematical Society