MIT Combinatorics Seminar

Tutte Polynomial and Orbit Counting

Peter Cameron (University of London)

Wednesday, April 20, 2005   4:15 pm    Room 2-338


Many counting problems for graphs, codes, etc. are solved by appropriate specialisations of the Tutte polynomial. Suppose that we have a group of automorphisms of the structure in question, and we want to count orbits of this group acting on the appropriate objects. Is there a polynomial which does this? Two such polynomials have been proposed; the first combines the cycle index of the group with the Tutte polynomial, the second directly generalises the Tutte polynomial itself. The second example works only for matroids representable over a principal ideal domain, and is a multivariate generating function for the invariant factors of certain matrices.