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 physics, partition functions are used to encapsulate statistical properties of large-particle systems (for example, gas molecules in a box; dipole configurations in a ferromagnetic solid). It turns out that the Tuttle polynomial is essentially equivalent to the partition function for the so-called Ising model of ferromagnetism.
In this project you can learn more about graph polynomials, their interesting properties, applications and connections to statistical mechanics..
There are a wide number of further 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 some Markov chain simulations of the related probabilistic models.
Discrete Mathematics is essential.
Either 2H Probability or 2H Markov Chains is recommended for the connections to statistical mechanics models.
A nice introduction to graph polynomials is the short chapter Chromatic polynomials by Bill Jackson. There is plenty of information in 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", "Ising model" 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!