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
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.