Title: The Tutte Polynomial, Bipartite Representations of Graphs, and Grid Walking
|University of Waterloo
Abstract: The Tutte Polynomial has many equivalent definitions. It can be defined by a deletion-contraction relation with the terms determined by the sequence of contractions, deletions, loops, and isthmi. This definition is independent of edge order. Another definition relies on a fixed edge ordering and examines the edge activities over maximal spanning forests. There is a direct relationship between edge activity and deletion/contraction for a given edge ordering. Furthermore, the monomials of the Tutte polynomial can be interpreted as grid walks. This allows for an approach to the Tutte polynomial on hypergraphs by examining the grid walks of the bipartite representation of the graph.