Hints and tips:
  • You may need to look up some unfamiliar terms in the title or description to get more of a sense of what is involved.
  • If the project has "No" in the "Current Availability:" field, it is already taken or not being offered this academic year but may be available again in future years.
  • The supervisor name links to a contact details webpage so, if you are interested, you can arrange to discuss this project or even propose a related topic of your own.
Level: BSc, MSci, MSc
Title: The Tutte polynomial and its evaluations
Supervisor:

Prof. Mark Jerrum
Research Area: Combinatorics
Description:

The Tutte polynomial T(G;x,y) is a two-variable polynomial associated with an undirected graph G. Evaluating the polynomial at various points provides a wealth of information about G. For example, T(G;1,1) is the number of spanning trees in G and T(G,-2,0) is the number of 3-colourings of G. The project would need to survey different definitions of the Tutte polynomial (in terms of contraction/deletion, and in terms of a rank function), and survey (with proofs) several of the combinatorial interpretations of the polynomial.
Further Reading:
  • Wikipedia contributors, Tutte polynomial, Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/wiki/Tutte_polynomial.
  • D. J. A. Welsh, Complexity: Knots, Colourings and Counting. London Mathematical Society Lecture Note Series 186, Cambridge Univ. Press, 1993.
  • M. Loebl, Discrete Mathematics in Statistical Physics: Introductory Lectures. Advanced Lectures in Mathematics, Vieweg+Teubner, Wiesbaden, 2010.
Key Modules:
Other Information:

Some background knowledge in Graph Theory would be an advantage.
Current Availability: Yes