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
HTML articles powered by AMS MathViewer

by Carolina Benedetti, Rafael S. González D’León, Christopher R. H. Hanusa, Pamela E. Harris, Apoorva Khare, Alejandro H. Morales and Martha Yip PDF

Trans. Amer. Math. Soc. 372 (2019), 3369-3404 Request permission

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.

References

A. D. Alexandrov, To the theory of mixed volumes of convex bodies, Part IV, Mat. Sb. 3 (1938), no. 45, 227–249.
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, DOI 10.1007/s00026-015-0293-6
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, DOI 10.1070/RM1992v047n01ABEH000861
Welleda Baldoni and Michèle Vergne, Kostant partitions functions and flow polytopes, Transform. Groups 13 (2008), no. 3-4, 447–469. MR 2452600, DOI 10.1007/s00031-008-9019-8
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, DOI 10.4169/amer.math.monthly.122.7.660
C. Ceballos and R. S. González D’León, On $s$-Catalan Combinatorics, preprint, https://arxiv.org/pdf/1805.03863, 2018.
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
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, DOI 10.1016/j.crma.2017.01.007
Dominique Foata and John Riordan, Mappings of acyclic and parking functions, Aequationes Math. 10 (1974), 10–22. MR 335294, DOI 10.1007/BF01834776
W. Fenchel, Inégalités quadratiques entre les volumes mixtes des corps convexes, C. R. Acad. Sci. Paris 203 (1936), 647–650.
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.
James Haglund, The $q$,$t$-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, DOI 10.1007/s10711-008-9270-0
Lutz Hille, Quivers, cones and polytopes, Linear Algebra Appl. 365 (2003), 215–237. Special issue on linear algebra methods in representation theory. MR 1987339, DOI 10.1016/S0024-3795(02)00406-8
James E. Humphreys, Introduction to Lie algebras and representation theory, Graduate Texts in Mathematics, Vol. 9, Springer-Verlag, New York-Berlin, 1972. MR 0323842
A. G. Konheim and B. Weiss, An occupancy discipline and applications, SIAM J. Appl. Math 14 (1966), no. 6, 1266–1274.
F. Liu, On positivity of Ehrhart polynomials, preprint, https://arxiv.org/abs/1711.09962, 2017.
Karola Mészáros, Product formulas for volumes of flow polytopes, Proc. Amer. Math. Soc. 143 (2015), no. 3, 937–954. MR 3293712, DOI 10.1090/S0002-9939-2014-12182-4
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, DOI 10.1093/imrn/rnt212
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.
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, DOI 10.1007/s00029-016-0241-2
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.
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.
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.
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, DOI 10.1016/S0195-6698(13)80128-X
N. J. A. Sloane (ed.), The on-line encyclopedia of integer sequences, published electronically at https://oeis.org.
Richard P. Stanley, Two combinatorial applications of the Aleksandrov-Fenchel inequalities, J. Combin. Theory Ser. A 31 (1981), no. 1, 56–65. MR 626441, DOI 10.1016/0097-3165(81)90053-4
Richard P. Stanley, Two poset polytopes, Discrete Comput. Geom. 1 (1986), no. 1, 9–23. MR 824105, DOI 10.1007/BF02187680
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, DOI 10.1090/conm/531/10466
Richard P. Stanley, Catalan numbers, Cambridge University Press, New York, 2015. MR 3467982, DOI 10.1017/CBO9781139871495
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, DOI 10.1007/s00454-002-2776-6
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.
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
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, DOI 10.1006/aama.2001.0754
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
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, DOI 10.1016/j.aam.2016.12.005