Abstract
Given an oriented graph G, the modular flow polynomial \({\phi_G(k)}\) counts the number of nowhere-zero \({\mathbb{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 \({\phi_G}\) at negative arguments which answers a question of Beck and Zaslavsky (Adv Math 205:134–162, 2006). Our construction extends to \({\mathbb{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 t G (x, y) of G.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Babson, E., Beck, M.: Minimal-distance chromatic and modular flow polynomials. (In preparation.)
Beck, M., Robins, S.: Computing the continuous discretely: integer-point enumeration in polyhedra. In: Undergraduate Texts in Mathematics. Springer, New York (2007)
Beck M., Zaslavsky T.: Inside-out polytopes. Adv. Math. 205, 134–162 (2006)
Beck M., Zaslavsky T.: The number of nowhere-zero flows on graphs and signed graphs. J. Comb. Theory Ser. B 96, 901–918 (2006)
Breuer, F.: Ham sandwiches, staircases and counting polynomials. PhD thesis, Freie Universität Berlin (2009)
Brylawski, T., Oxley, J.: The Tutte polynomial and its applications. In: Matroid Applications. Encyclopedia Math. Appl., vol. 40, pp. 123–225. Cambridge University Press, Cambridge (1992)
Chen B.: Orientations, lattice polytopes, and group arrangements I: chromatic and tension polynomials of graphs. Ann. Comb. 13, 425–452 (2010)
Chen, B., Stanley, R.P.: Orientations, lattice polytopes, and group arrangements II: modular and integral flow polynomials of graphs. Preprint
Ehrhart, E.: Polynômes arithmétiques et méthode des polyèdres en combinatoire. International Series of Numerical Mathematics, vol. 35. Birkhäuser Verlag, Basel (1977)
Gioan E.: Enumerating degree sequences in digraphs and a cycle-cocycle reversing system. Eur. J. Comb. 28, 1351–1366 (2007)
Greene C., Zaslavsky T.: On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs. Trans. Am. Math. Soc. 280, 97–126 (1983)
Kochol M.: Polynomials associated with nowhere-zero flows. J. Comb. Theory Ser. B 84, 260–269 (2002)
Kook W., Reiner V., Stanton D.: A convolution formula for the Tutte polynomial. J. Comb. Theory Ser. B 76, 297–300 (1999)
Matoušek, J.: Lectures on discrete geometry. In: Graduate Texts in Mathematics, vol. 212. Springer-Verlag New York (2002)
Reiner V.: An interpretation for the Tutte polynomial. Eur. J. Comb. 20, 149–161 (1999)
Schrijver, A.: Theory of linear and integer programming. In: Wiley-Interscience Series in Discrete Mathematics. Wiley, Chichester (1986)
Schrijver, A.: Combinatorial optimization. Polyhedra and efficiency. Volume A. In: Algorithms and Combinatorics, vol. 24. Springer, Berlin (2003)
Stanley R.P.: Acyclic orientations of graphs. Discrete Math. 5, 171–178 (1973)
Stanley R.P.: Combinatorial reciprocity theorems. Adv. Math. 14, 194–253 (1974)
Tutte W.T.: A ring in graph theory. Proc. Camb. Philos. Soc. 43, 26–40 (1947)
Tutte W.T.: A contribution to the theory of chromatic polynomials. Can. J. Math. 6, 80–91 (1954)
Acknowledgments
We would like to thank Matthias Beck for valuable conversations and comments on an earlier version of this paper.
Open Access
This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
Author information
Authors and Affiliations
Corresponding author
Additional information
Felix Breuer was supported by the Deutsche Forschungsgemeinschaft within the research training group ‘Methods for Discrete Structures’ (GRK 1408). Raman Sanyal was supported by the Konrad-Zuse-Zentrum für Informationstechnik Berlin and by a Miller Research Fellowship.
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Breuer, F., Sanyal, R. Ehrhart theory, modular flow reciprocity, and the Tutte polynomial. Math. Z. 270, 1–18 (2012). https://doi.org/10.1007/s00209-010-0782-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00209-010-0782-6
Keywords
- Nowhere-zero flows
- Modular flow polynomial
- Reciprocity theorems
- Lattice-point counting
- Ehrhart theory
- Tutte polynomial