A combinatorial model for computing volumes of flow polytopes
From MaRDI portal
binomial transformcaracol graphCatalan numbersChan-Robbins-Yuen polytopeDyck pathEhrhart polynomialflow polytopegravity diagramkostant partition functionLidskii formulaline-dot diagramlog-concavemulti-labeled Dyck pathparking functionparking trianglePitman-Stanley polytopeTesler polytopeunified diagramzigzag graph
Exact enumeration problems, generating functions (05A15) Combinatorial identities, bijective combinatorics (05A19) Directed graphs (digraphs), tournaments (05C20) Flows in graphs (05C21) 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)
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.
Recommendations
Cites work
- A polytope related to empirical distributions, plane trees, parking functions, and the associahedron
- A survey of alternating permutations
- An Occupancy Discipline and Applications
- Catalan Numbers
- Flow polytopes of signed graphs and the Kostant partition function
- Flow polytopes with Catalan volumes
- From generalized permutahedra to Grothendieck polynomials via flow polytopes
- Generalized parking functions, tree inversions, and multicolored graphs
- scientific article; zbMATH DE number 2024859 (Why is no real title available?)
- Introduction to Lie Algebras and Representation Theory
- Kostant partitions functions and flow polytopes
- Leading coefficients of Morris type constant term identities
- Mappings of acyclic and parking functions
- 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
- On the enumeration of generalized parking functions
- On the Volume of a Certain Polytope
- Parking functions, Shi arrangements, and mixed graphs
- Product formulas for volumes of flow polytopes
- Proof of a conjecture of Chan, Robbins, and Yuen
- Quivers, cones and polytopes.
- Rational parking functions and Catalan numbers
- The q,t-Catalan numbers and the space of diagonal harmonics. With an appendix on the combinatorics of Macdonald polynomials
- The calculus of snakes and the combinatorics of Bernoulli, Euler and Springer numbers of Coxeter groups
- The polytope of Tesler matrices
- Two combinatorial applications of the Aleksandrov-Fenchel inequalities
- Two poset polytopes
Cited in
(27)- Computing volumes of adjacency polytopes via Draconian sequences
- Volumes of flow polytopes related to caracol graphs
- Kostant's partition function and magic multiplex juggling sequences
- On volume functions of special flow polytopes associated to the root system of type \(A\)
- Volumes and Ehrhart polynomials of flow polytopes
- The volume of the caracol polytope
- On framed triangulations of flow polytopes, the \(\nu\)-Tamari lattice and Young's lattice
- Flow-oriented perturbation theory
- Lower bounds for contingency tables via Lorentzian polynomials
- Volume of graph polytopes for the path-star type graphs
- On product formulas for volumes of flow polytopes
- Triangulations, order polytopes, and generalized snake posets
- Parking Functions: Choose Your Own Adventure
- Flow polytopes with Catalan volumes
- Column-convex matrices, G-cyclic orders, and flow polytopes
- Deformation cones of Tesler polytopes
- Log-concave poset inequalities
- Correlation inequalities for linear extensions
- Permutation invariant parking assortments
- Capacity bounds on integral flows and the Kostant partition function
- Interval and -interval rational parking functions
- Volume inequalities for flow polytopes of full directed acyclic graphs
- Equatorial flow triangulations of Gorenstein flow polytopes
- Metered parking functions
- On faces of partial alternating sign matrix polytopes
- Refinements and symmetries of the Morris identity for volumes of flow polytopes
- Polyhedral results on single node variable upper-bound flow models with allowed configurations
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)
