Ehrhart theory, modular flow reciprocity, and the Tutte polynomial

DOI10.1007/S00209-010-0782-6MaRDI QIDQ663242zbMATH OpenOpenAlexFDO

Authors Felix Breuer, Raman Sanyal

Publication date 14 February 2012

Published in Mathematische Zeitschrift (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

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

zbMATH Keywords

Ehrhart theoryLattice-point countingModular flow polynomialNowhere-zero flowsReciprocity theoremsTutte polynomial

Mathematics Subject Classification ID

Flows in graphs (05C21) Graph polynomials (05C31) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35)

Abstract: Given an oriented graph G, the modular flow polynomial counts the number of nowhere-zero Z_k-flows of G. We give a description of the modular flow polynomial in terms of (open) Ehrhart polynomials of lattice polytopes. Using Ehrhart-Macdonald reciprocity we give a combinatorial interpretation for the values of the modular flow polynomial at negative arguments which answers a question of Beck and Zaslavsky (2006). Our construction extends to Z_l-tensions and we recover Stanley's reciprocity theorem for the chromatic polynomial. Combining the combinatorial reciprocity statements for flows and tensions, we give an enumerative interpretation for positive evaluations of the Tutte polynomial of G.

Recommendations

• Orientations, lattice polytopes, and group arrangements. II: Modular and integral flow polynomials of graphs
• Orientations, lattice polytopes, and group arrangements I: Chromatic and tension polynomials of graphs
• Dual complementary polynomials of graphs and combinatorial-geometric interpretation on the values of Tutte polynomial at positive integers
• Orientations, lattice polytopes, and group arrangements. III: Cartesian product arrangements and applications to Tutte type polynomials
• Reciprocity and Polynomial Properties for Even Flows and Potentials on Directed Graphs

Cites work

• A Contribution to the Theory of Chromatic Polynomials
• A convolution formula for the Tutte polynomial
• Acyclic orientations of graphs
• An interpretation for the Tutte polynomial
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Combinatorial reciprocity theorems
• Computing the Continuous Discretely
• Enumerating degree sequences in digraphs and a cycle--cocycle reversing system
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 67324 (Why is no real title available?)
• scientific article; zbMATH DE number 3049182 (Why is no real title available?)
• Inside-out polytopes
• On the Interpretation of Whitney Numbers Through Arrangements of Hyperplanes, Zonotopes, Non-Radon Partitions, and Orientations of Graphs
• Orientations, lattice polytopes, and group arrangements I: Chromatic and tension polynomials of graphs
• Orientations, lattice polytopes, and group arrangements. II: Modular and integral flow polynomials of graphs
• Polynomials associated with nowhere-zero flows
• The number of nowhere-zero flows on graphs and signed graphs

Cited in

(21)

• A note on flow polynomials of graphs
• Orientations, lattice polytopes, and group arrangements. III: Cartesian product arrangements and applications to Tutte type polynomials
• Orientations, lattice polytopes, and group arrangements. II: Modular and integral flow polynomials of graphs
• Binomial inequalities for chromatic, flow, and tension polynomials
• Polynomials counting nowhere-zero chains in graphs
• Nowhere-zero \(\vec{k}\)-flows on graphs
• Enumerating colorings, tensions and flows in cell complexes
• Dual complementary polynomials of graphs and combinatorial-geometric interpretation on the values of Tutte polynomial at positive integers
• Dualities and reciprocities on graphs on surfaces
• Existence of unimodular triangulations -- positive results
• Hypergraph coloring complexes
• Viewing counting polynomials as Hilbert functions via Ehrhart theory
• Euler characteristic reciprocity for chromatic, flow and order polynomials
• scientific article; zbMATH DE number 6107212 (Why is no real title available?)
• Möbius conjugation and convolution formulae
• Bounds of characteristic polynomials of regular matroids
• Nowhere-harmonic colorings of graphs
• Polynomial algorithms for canonical forms of orientations
• Bounds on the coefficients of tension and flow polynomials
• Orientations, lattice polytopes, and group arrangements I: Chromatic and tension polynomials of graphs
• On some polynomials enumerating fully packed loop configurations

This page was built for publication: Ehrhart theory, modular flow reciprocity, and the Tutte polynomial

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