Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



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
Published electronically: May 23, 2019
MathSciNet review: 3988614
Full-text PDF

Abstract | References | Similar Articles | Additional Information


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 [Enhancements On Off] (What's this?)


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
MR Author ID: 898089

Rafael S. González D’León
Affiliation: Escuela de Ciencias Exactas e Ingeniería, Universidad Sergio Arboleda, Bogotá, Colombia

Christopher R. H. Hanusa
Affiliation: Department of Mathematics, Queens College (CUNY), 65-30 Kissena Boulevard, Flushing, New York 11367
MR Author ID: 723495

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

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

Alejandro H. Morales
Affiliation: Department of Mathematics and Statistics, University of Massachusetts, Amherst, Massachusetts 01003
MR Author ID: 819004

Martha Yip
Affiliation: Department of Mathematics, University of Kentucky, 715 Patterson Office Tower, Lexington, Kentucky 40506-0027
MR Author ID: 805658

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