Orientations, lattice polytopes, and group arrangements III: Cartesian product arrangements and applications to Tutte type polynomials

摘要

We study tension-flows (f, g) on a graph G (where f is a tension and g is a flow) of the following types: nowhere-zero, product-zero everywhere, and complementary. Counting the number of tension flows of the three types over modulo integer pairs (p, q) results in polynomial functions of two variables p and q. It turns out that the two-variable polynomial of the complementary case is dual to the Tutte polynomial, in the sense that the former counts the number of lattice points inside certain open lattice polytopes while the latter counts the number of lattice points inside the corresponding closed lattice polytopes. Other than counting over modulo integer pairs, we further consider enumeration of tension-flows over finitely generated abelian groups and over the field of real numbers by valuations (= finitely additive measures) on the corresponding tension-flow spaces of the three types with weights. We produce a number of Tutte type polynomials of two and of four variables associated with the graph G; some are old or generalizations, some are completely new. The present paper is to introduce the Cartesian product arrangement and multivariable characteristic polynomial, then to examine the aforementioned two-variable and four-variable polynomials. We obtain expansion formulas of these polynomials and the reciprocity laws holding among them. Moreover, the reciprocity law for one-variable characteristic polynomial is treated geometrically so that the combinatorial interpretations are obtained uniformly for the absolute values of the chromatic polynomial, tension polynomial, and flow polynomial of graphs.(C) 2018 Elsevier Ltd. All rights reserved.