×

zbMATH — the first resource for mathematics

A combinatorial model for computing volumes of flow polytopes. (English) Zbl 1420.05011
Summary: We introduce new families of combinatorial objects whose enumeration computes volumes of flow polytopes. These objects provide an interpretation, based on parking functions, of W. Baldoni and M. Vergne’s generalization of a volume formula [Transform. Groups 13, No. 3–4, 447–469 (2008; Zbl 1200.52008)] 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.

MSC:
05A15 Exact enumeration problems, generating functions
05A19 Combinatorial identities, bijective combinatorics
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
52A38 Length, area, volume and convex sets (aspects of convex geometry)
05C20 Directed graphs (digraphs), tournaments
05C21 Flows in graphs
52B11 \(n\)-dimensional polytopes
Software:
OEIS
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Alexandrov A. D. Alexandrov, To the theory of mixed volumes of convex bodies, Part IV, Mat. Sb. 3 (1938), no. 45, 227-249.
[2] Armstrong, Drew; Loehr, Nicholas A.; Warrington, Gregory S., Rational parking functions and Catalan numbers, Ann. Comb., 20, 1, 21-58 (2016) · Zbl 1332.05146
[3] Arnol\cprime d, V. I., Snake calculus and the combinatorics of the Bernoulli, Euler and Springer numbers of Coxeter groups, Uspekhi Mat. Nauk. Russian Math. Surveys, 47 47, 1, 1-51 (1992) · Zbl 0791.05001
[4] Baldoni, Welleda; Vergne, Mich\`ele, Kostant partitions functions and flow polytopes, Transform. Groups, 13, 3-4, 447-469 (2008) · Zbl 1200.52008
[5] Beck, Matthias; Berrizbeitia, Ana; Dairyko, Michael; Rodriguez, Claudia; Ruiz, Amanda; Veeneman, Schuyler, Parking functions, Shi arrangements, and mixed graphs, Amer. Math. Monthly, 122, 7, 660-673 (2015) · Zbl 1332.05016
[6] CeballosDleon2018 C. Ceballos and R. S. Gonz\'alez D’Le\'on, On \(s\)-Catalan Combinatorics, preprint, https://arxiv.org/pdf/1805.03863, 2018.
[7] Chan, Clara S.; Robbins, David P.; Yuen, David S., On the volume of a certain polytope, Experiment. Math., 9, 1, 91-99 (2000) · Zbl 0960.05004
[8] Corteel, Sylvie; Kim, Jang Soo; M\'{e}sz\'{a}ros, Karola, Flow polytopes with Catalan volumes, C. R. Math. Acad. Sci. Paris, 355, 3, 248-259 (2017) · Zbl 1358.05129
[9] Foata, Dominique; Riordan, John, Mappings of acyclic and parking functions, Aequationes Math., 10, 10-22 (1974) · Zbl 0274.05005
[10] Fe1 W. Fenchel, In\'egalit\'es quadratiques entre les volumes mixtes des corps convexes, C. R. Acad. Sci. Paris 203 (1936), 647-650. · JFM 62.0833.02
[11] Fe2 W. Fenchel, G\'en\'eralizations du th\'eor\'eme de Brunn et Minkowski concernant les corps convexes, C. R. Acad. Sci. Paris 203 (1936), 764-766. · JFM 62.0833.03
[12] Haglund, James, The \(q,t\)-Catalan numbers and the space of diagonal harmonics, University Lecture Series 41, viii+167 pp. (2008), American Mathematical Society, Providence, RI · Zbl 1142.05074
[13] Hille, Lutz, Quivers, cones and polytopes, Linear Algebra Appl., 365, 215-237 (2003) · Zbl 1034.52011
[14] Humphreys, James E., Introduction to Lie algebras and representation theory, xii+169 pp. (1972), Springer-Verlag, New York-Berlin
[15] KonheimWeiss1966 A. G. Konheim and B. Weiss, An occupancy discipline and applications, http://dx.doi.org/10.1137/0114101SIAM J. Appl. Math 14 (1966), no. 6, 1266-1274. · Zbl 0201.50204
[16] LiuSurvey F. Liu, On positivity of Ehrhart polynomials, preprint, https://arxiv.org/abs/1711.09962, 2017.
[17] M\'{e}sz\'{a}ros, Karola, Product formulas for volumes of flow polytopes, Proc. Amer. Math. Soc., 143, 3, 937-954 (2015) · Zbl 1310.51024
[18] M\'{e}sz\'{a}ros, Karola; Morales, Alejandro H., Flow polytopes of signed graphs and the Kostant partition function, Int. Math. Res. Not. IMRN, 3, 830-871 (2015) · Zbl 1307.05097
[19] MM2 K. M\'esz\'aros 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] M\'{e}sz\'{a}ros, Karola; Morales, Alejandro H.; Rhoades, Brendon, The polytope of Tesler matrices, Selecta Math. (N.S.), 23, 1, 425-454 (2017) · Zbl 1355.05271
[21] MMS K. M\'esz\'aros, 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. · Zbl 1414.05029
[22] MSt K. M\'esz\'aros and A. St. Dizier, From generalized permutahedra to Grothendieck polynomials via flow polytopes, preprint, https://arxiv.org/abs/1705.02418, 2017. · Zbl 1448.05096
[23] MSW K. M\'esz\'aros, C. Simpson, and Z. Wellner, Flow polytopes of partitions, preprint, https://arxiv.org/abs/1707.03100, 2017, to appear in Electron. J. Combin.
[24] Proctor, Robert A., New symmetric plane partition identities from invariant theory work of De Concini and Procesi, European J. Combin., 11, 3, 289-300 (1990) · Zbl 0726.05008
[25] OEIS N. J. A. Sloane (ed.), The on-line encyclopedia of integer sequences, published electronically at https://oeis.org. · Zbl 1044.11108
[26] Stanley, Richard P., Two combinatorial applications of the Aleksandrov-Fenchel inequalities, J. Combin. Theory Ser. A, 31, 1, 56-65 (1981) · Zbl 0484.05012
[27] Stanley, Richard P., Two poset polytopes, Discrete Comput. Geom., 1, 1, 9-23 (1986) · Zbl 0595.52008
[28] Stanley, Richard P., A survey of alternating permutations. Combinatorics and graphs, Contemp. Math. 531, 165-196 (2010), Amer. Math. Soc., Providence, RI · Zbl 1231.05288
[29] Stanley, Richard P., Catalan numbers, viii+215 pp. (2015), Cambridge University Press, New York · Zbl 1317.05010
[30] Stanley, Richard P.; Pitman, Jim, A polytope related to empirical distributions, plane trees, parking functions, and the associahedron, Discrete Comput. Geom., 27, 4, 603-634 (2002) · Zbl 1012.52019
[31] Stanley_slides 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] Yan, Catherine Huafei, On the enumeration of generalized parking functions, Congr. Numer.. Proceedings of the Thirty-first Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 2000), 147, 201-209 (2000) · Zbl 0971.05003
[33] Yan, Catherine H., Generalized parking functions, tree inversions, and multicolored graphs, Adv. in Appl. Math., 27, 2-3, 641-670 (2001) · Zbl 0992.05016
[34] Zeilberger, Doron, Proof of a conjecture of Chan, Robbins, and Yuen, Electron. Trans. Numer. Anal., 9, 147-148 (1999) · Zbl 0941.05006
[35] Zhou, Yue; Lu, Jia; Fu, Houshan, Leading coefficients of Morris type constant term identities, Adv. in Appl. Math., 87, 24-42 (2017) · Zbl 1364.05015
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.