A combinatorial model for computing volumes of flow polytopes
From MaRDI portal
Publication:5227989
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
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)
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
- scientific article; zbMATH DE number 2024859 (Why is no real title available?)
- 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
- 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 Volume of a Certain Polytope
- On the enumeration of generalized parking functions
- 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
(21)- Refinements and symmetries of the Morris identity for volumes of flow polytopes
- On product formulas for volumes of flow polytopes
- Volumes and Ehrhart polynomials of flow polytopes
- Parking Functions: Choose Your Own Adventure
- On volume functions of special flow polytopes associated to the root system of type \(A\)
- Column-convex matrices, \(G\)-cyclic orders, and flow polytopes
- Computing volumes of adjacency polytopes via Draconian sequences
- 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
- Volume of graph polytopes for the path-star type graphs
- Correlation inequalities for linear extensions
- Kostant's partition function and magic multiplex juggling sequences
- 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
- Flow polytopes with Catalan volumes
- Triangulations, order polytopes, and generalized snake posets
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)
