Congruence conditions, parcels, and Tutte polynomials of graphs and matroids

Joseph P. S. Kung

Published 2010-07-02, updated 2011-12-03Version 2

Let $G$ be a matrix and $M(G)$ be the matroid defined by linear dependence on the set $E$ of column vectors of $G.$ Roughly speaking, a parcel is a subset of pairs $(f,g)$ of functions defined on $E$ to an Abelian group $A$ satisfying a coboundary condition (that $f-g$ is a flow over $A$ relative to $G$) and a congruence condition (that the size of the supports of $f$ and $g$ satisfy some congruence condition modulo an integer). We prove several theorems of the form: a linear combination of sizes of parcels, with coefficients roots of unity, equals an evaluation of the Tutte polynomial of $M(G)$ at a point $(\lambda-1,x-1)$ on the complex hyperbola $(\lambda - 1)(x-1) = |A|.$