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

2010/07/02 by Joseph P. S. Kung, Kung, Joseph P. S.
Mathematics · #05B35 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05B35

paper · pdf · doi:10.48550/arxiv.1007.0279

arxiv created 2011/12/03 · arxiv updated 2011/12/06

Abstract

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 (λ-1,x-1) on the complex hyperbola (λ- 1)(x-1) = |A|.

Related

• On the irreducibility and monodromy of Tutte polynomials
• Orientations, lattice polytopes, and group arrangements III: Cartesian product arrangements and applications to the Tutte type polynomials of graphs
• Universal Tutte polynomial
• Linear relations for a generalized Tutte polynomial
• Matroid variant of Matiyasevich formula and its application