A combinatorial model for computing volumes of flow polytopes

DOI10.1090/TRAN/7743zbMATH Open1420.05011arXiv1801.07684OpenAlexW2963019724WikidataQ128737646 ScholiaQ128737646MaRDI QIDQ5227989FDOQ5227989

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

Publication date: 7 August 2019

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

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 that were seemingly unapproachable. 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.

Full work available at URL: https://arxiv.org/abs/1801.07684

Recommendations

• The volume of the caracol polytope
• Volumes of flow polytopes related to caracol graphs
• Volumes and Ehrhart polynomials of flow polytopes
• Flow polytopes with Catalan volumes
• On product formulas for volumes of flow polytopes

zbMATH Keywords

Catalan numbersDyck pathEhrhart polynomiallog-concavebinomial transformparking functionTesler polytopeChan-Robbins-Yuen polytopeflow polytopeLidskii formulazigzag graphcaracol graphgravity diagramkostant partition functionline-dot diagrammulti-labeled Dyck pathparking trianglePitman-Stanley polytopeunified diagram

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Exact enumeration problems, generating functions (05A15) Length, area, volume and convex sets (aspects of convex geometry) (52A38) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) (n)-dimensional polytopes (52B11) Combinatorial identities, bijective combinatorics (05A19) Flows in graphs (05C21)

Cites Work

• Title not available (Why is that?)
• Proof of a conjecture of Chan, Robbins, and Yuen
• On the Volume of a Certain Polytope
• Two poset polytopes
• The \(q,t\)-Catalan numbers and the space of diagonal harmonics. With an appendix on the combinatorics of Macdonald polynomials
• Rational parking functions and Catalan numbers
• An Occupancy Discipline and Applications
• Introduction to Lie Algebras and Representation Theory
• A polytope related to empirical distributions, plane trees, parking functions, and the associahedron
• A Survey of Alternating Permutations
• Generalized parking functions, tree inversions, and multicolored graphs
• Mappings of acyclic and parking functions
• On the enumeration of generalized parking functions
• Catalan Numbers
• Two combinatorial applications of the Aleksandrov-Fenchel inequalities
• From generalized permutahedra to Grothendieck polynomials via flow polytopes
• The calculus of snakes and the combinatorics of Bernoulli, Euler and Springer numbers of Coxeter groups
• Kostant partitions functions and flow polytopes
• Quivers, cones and polytopes.
• The polytope of Tesler matrices
• Flow polytopes with Catalan volumes
• Flow Polytopes of Signed Graphs and the Kostant Partition Function
• Product formulas for volumes of flow polytopes
• New symmetric plane partition identities from invariant theory work of De Concini and Procesi
• On flow polytopes, order polytopes, and certain faces of the alternating sign matrix polytope
• Parking Functions, Shi Arrangements, and Mixed Graphs
• Leading coefficients of Morris type constant term identities

Cited In (17)

• Refinements and symmetries of the Morris identity for volumes of flow polytopes
• Volumes and Ehrhart polynomials of flow polytopes
• Parking Functions: Choose Your Own Adventure
• Column-convex matrices, \(G\)-cyclic orders, and flow polytopes
• On volume functions of special flow polytopes associated to the root system of type \(A\)
• Polyhedral results on single node variable upper-bound flow models with allowed configurations
• Volumes of flow polytopes related to caracol graphs
• The volume of the caracol polytope
• Log-concave poset inequalities
• Correlation inequalities for linear extensions
• Kostant's partition function and magic multiplex juggling sequences
• Triangulations, Order Polytopes, and Generalized Snake Posets
• On framed triangulations of flow polytopes, the \(\nu\)-Tamari lattice and Young's lattice
• Deformation cones of Tesler polytopes
• Permutation invariant parking assortments
• Flow-oriented perturbation theory
• Lower bounds for contingency tables via Lorentzian polynomials

Uses Software

• OEIS

This page was built for publication: A combinatorial model for computing volumes of flow polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5227989)