A combinatorial model for computing volumes of flow polytopes

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

Research output: Contribution to journalArticlepeer-review

15 Scopus citations

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.

Original languageEnglish
Pages (from-to)3369-3404
Number of pages36
JournalTransactions of the American Mathematical Society
Volume372
Issue number5
DOIs
StatePublished - Sep 1 2019

Bibliographical note

Publisher Copyright:
© 2019 American Mathematical Society.

Keywords

  • Binomial transform
  • Caracol graph
  • Catalan numbers
  • Chan–Robbins–Yuen polytope
  • Dyck path
  • Ehrhart polynomial
  • Flow polytope
  • Gravity diagram
  • Kostant partition function
  • Lidskii formula
  • Line-dot diagram
  • Log-concave
  • Multi-labeled Dyck path
  • Parking function
  • Parking triangle
  • Pitman–Stanley polytope
  • Tesler polytope
  • Unified diagram
  • Zigzag graph

ASJC Scopus subject areas

  • General Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'A combinatorial model for computing volumes of flow polytopes'. Together they form a unique fingerprint.

Cite this