Ehrhart theory, Modular flow reciprocity, and the Tutte polynomial

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.

14 pages, 5 figures

Cited by in corpus (8)

• Existence of unimodular triangulations - positive results
• Combinatorial positivity of translation-invariant valuations and a discrete Hadwiger theorem
• Mobius Conjugation and Convolution Formulae
• The geometry and combinatorics of cographic toric face rings
• Euler characteristic reciprocity for chromatic, flow and order polynomials
• On some polynomials enumerating Fully Packed Loop configurations
• Nowhere-Zero $\vec{k}$-Flows on Graphs
• Orientations, lattice polytopes, and group arrangements II: Modular and integral flow polynomials of graphs