School Seminars and Colloquia

An introduction to the Tutte polynomial of a graph

Discrete Structures and Algorithms (Seminar)
The speaker is a DECRA Fellow who recently commenced work in our department.

by Dr Arun Mani

Institution: The University of Melbourne
Date: Wed 28th March 2012
Time: 10:00 AM
Location: Room 215, Richard Berry Building

Abstract: The Tutte polynomial of a graph is a two variable polynomial that is of central importance in many counting problems. For example, if $T(G;x,y)$ is the Tutte polynomial of a connected graph $G$, then $T(G;1,1)$ and $T(G;1,2)$ give its number of spanning trees and connected subgraphs, respectively, while $k|T(G;1-k,0)|$ is its number of proper $k$-colourings.

In this first introductory half of a two part talk, I will give an overview of the Tutte polynomial with particular focus on the following three topics:
i) its combinatorial significance,
ii) its role in Statistical Mechanics, and
iii) the computational complexity of computing its coefficients or evaluating it at various points.

These form the background material for my talk the following week, where I will introduce a family of inequalities for the Tutte polynomial and discuss its implications on all three of the above topics.