MIT Combinatorics Seminar
Tutte Polynomial and Orbit Counting
Peter Cameron (University of London)
p.j.cameron@qmul.ac.uk
Wednesday, April 20, 2005 4:15 pm Room 2338
ABSTRACT

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.


