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