Volumes and Ehrhart polynomials of flow polytopes

DOI10.1007/S00209-019-02283-ZzbMATH Open1453.52012arXiv1710.00701OpenAlexW2963773706MaRDI QIDQ2332880FDOQ2332880

Alejandro H. Morales, Karola Mészáros

Publication date: 5 November 2019

Published in: Mathematische Zeitschrift (Search for Journal in Brave)

Abstract: The Lidskii formula for the type $A_n$ root system expresses the volume and Ehrhart polynomial of the flow polytope of the complete graph with nonnegative integer netflows in terms of Kostant partition functions. For every integer polytope the volume is the leading coefficient of the Ehrhart polynomial. The beauty of the Lidskii formula is the revelation that for these polytopes its Ehrhart polynomial function can be deduced from its volume function! Baldoni and Vergne generalized Lidskii's result for flow polytopes of arbitrary graphs $G$ and nonnegative integer netflows. While their formulas are combinatorial in nature, their proofs are based on residue computations. In this paper we construct canonical polytopal subdivisions of flow polytopes which we use to prove the Baldoni-Vergne-Lidskii formulas. In contrast with the original computational proof of these formulas, our proof reveal their geometry and combinatorics. We conclude by exhibiting enumerative properties of the Lidskii formulas via our canonical polytopal subdivisions.

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

Recommendations

• Counting integer points of flow polytopes
• Kostant partitions functions and flow polytopes
• A combinatorial model for computing volumes of flow polytopes
• Volumes of flow polytopes related to caracol graphs
• On volume functions of special flow polytopes associated to the root system of type \(A\)

zbMATH Keywords

volumeEhrhart polynomialflow polytopeLidskii formula

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Combinatorial aspects of partitions of integers (05A17) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Counting solutions of Diophantine equations (11D45)

Cites Work

• The on-line encyclopedia of integer sequences
• Proof of a conjecture of Chan, Robbins, and Yuen
• Computing the Continuous Discretely
• On the Volume of a Certain Polytope
• Permutohedra, Associahedra, and Beyond
• The Cayley trick, lifting subdivisions and the Bohne-Dress theorem on zonotopal tilings
• A polytope related to empirical distributions, plane trees, parking functions, and the associahedron
• Generalized parking functions, tree inversions, and multicolored graphs
• On the Newton polytope of the resultant
• On the enumeration of generalized parking functions
• From generalized permutahedra to Grothendieck polynomials via flow polytopes (extended abstract)
• A polynomial expression for the Hilbert series of the quotient ring of diagonal coinvariants
• 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
• On positivity of Ehrhart polynomials
• Counting integer flows in networks
• Flow polytopes of partitions
• Kostant function of the root system \(A_ n\)
• On flow polytopes, order polytopes, and certain faces of the alternating sign matrix polytope
• A combinatorial model for computing volumes of flow polytopes
• Extreme points and adjacency relationship in the flow polytope
• Berline-Vergne valuation and generalized permutohedra
• Leading coefficients of Morris type constant term identities

Cited In (19)

• Triangulations of flow polytopes, ample framings, and gentle algebras
• Column-convex matrices, \(G\)-cyclic orders, and flow polytopes
• On volume functions of special flow polytopes associated to the root system of type \(A\)
• Stanley's non-Ehrhart-positive order polytopes
• Lorentzian polynomials from polytope projections
• Counting integer points of flow polytopes
• Volumes of flow polytopes related to caracol graphs
• The volume of the caracol polytope
• Integer point enumeration on independence polytopes and half-open hypersimplices
• A billiards-like dynamical system for attacking chess pieces
• Volume polynomials and duality algebras of multi-fans
• A subdivision algebra for a product of two simplices via flow polytopes
• 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
• Ehrhart positivity of Tesler polytopes and Berline-Vergne's valuation
• Low dimensional flow polytopes and their toric ideals
• Gelfand--Tsetlin Polytopes: A Story of Flow and Order Polytopes
• Lower bounds for contingency tables via Lorentzian polynomials

Uses Software

• OEIS

This page was built for publication: Volumes and Ehrhart polynomials of flow polytopes

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