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
Additional Information
- Carolina Benedetti
- Affiliation: Departamento de Matemáticas, Universidad de los Andes, Bogotá, Colombia
- MR Author ID: 898089
- 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
- MR Author ID: 723495
- 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
- MR Author ID: 953833
- ORCID: 0000-0002-3049-991X
- Email: peh2@williams.edu
- Apoorva Khare
- Affiliation: Department of Mathematics, Indian Institute of Science, Analysis and Probability Research Group, Bangalore 560012, India
- MR Author ID: 750359
- ORCID: 0000-0002-1577-9171
- Email: khare@iisc.ac.in
- Alejandro H. Morales
- Affiliation: Department of Mathematics and Statistics, University of Massachusetts, Amherst, Massachusetts 01003
- MR Author ID: 819004
- Email: ahmorales@math.umass.edu
- Martha Yip
- Affiliation: Department of Mathematics, University of Kentucky, 715 Patterson Office Tower, Lexington, Kentucky 40506-0027
- MR Author ID: 805658
- Email: martha.yip@uky.edu
- 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. - © Copyright 2019 American Mathematical Society
- 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
- MathSciNet review: 3988614
Dedicated: Dedicated to the memory of Griff L. Bilbro