The Tutte polynomial, named for British codebreaker and mathematician William Tutte who was one of the first people to study it, is a graph polynomial that contains lots of information about a graph, and how it is connected. It is an integer polynomial in two variables that can be used to count many properties of a graph. Some of the many things include the number of spanning trees, the number acyclic subgraphs, the number of acyclic orientations of the edges, the number of proper colourings, and the number of "nowhere-zero flows".
For example, for a triangle (the graph with 3 vertices and 3 edges) the Tutte polynomial is T(x,y) = x2 + x + y, and the number of spanning trees is T(1,1) = 3, the number of acyclic subgraphs is T(2,1) = 7 and the number of acyclic orientations of the edges is T(2,0) = 6. Even the number of edges is encoded, since T(2,2) = 8 = 2|E|.
In addition to these particular evaluations, the Tutte polynomial also specialises to other graph polynomials of interest, for example the chromatic polynomial (which counts the number of proper colourings of a graph), the reliability polynomial (which gives the probability a graph remains connected after having edges deleted at random), and the flow polynomial (a flow being an assignment of numbers and directions to the edges so that the total flow entering matches the total flow leaving each vertex). The Tutte polynomial also has connections with the Jones polynomial from knot theory.
In this project you can learn more about the Tutte polynomial and other graph polynomials, how they are defined and how they can be calculated, and some of their interesting properties.
There are a wide number of directions to explore, including but not limited to:
For those keen on doing some computation there is also the possibility to code up some algorithms and run simulations of the related probabilistic models.
Discrete Mathematics is essential.
2H Probability is not necessary but may be helpful for the connections to statistical mechanics models.
A good starting point is the pair of survey articles Graph Polynomials and Their Applications I: The Tutte Polynomial and Graph Polynomials and Their Applications II: Interrelations and Interpretations by Ellis-Monaghan and Merino, 2008, available on arXiv: (Part I, Part II).
You can also search online for "Tutte polynomial" or some of the phrases above for more information.
If you need a reminder of some of the graph-theoretic concepts from Discrete Mathematics have a look at Modern Graph Theory, B. Bollobás, 1998, or Graph Theory, R. Diestel, 2016, free preview version available online.
Get in touch if you have any questions!