Research Interests

On this page I have attempted to describe my papers and what they are about, sometimes including a few stories about how I got interested in the problems. If you are thinking of doing a PhD and something sounds interesting then please get in touch.

Graph Polynomials

Much of my research has been centred around graph polynomials. Perhaps the most well-known graph polynomial is the chromatic polynomial, which counts the number of ways of properly colouring the vertices of a graph from a fixed palette of colours. I have been mostly interested in the Tutte polyomial which is a two-variable polynomial, incorporating the chromatic polynomial as a one-variable specialization. For me the Tutte polynomial has two attractions. First, it specializes to a vast range of interesting, yet otherwise apparently unconnected invariants with links to knot theory via the Jones polynomial, statistical physics via the partition functions of the Ising and Potts models, operational research via the reliability polynomial and many parts of graph theory. Second, a vast range of beautiful mathematics has already been discovered concerning the polynomial, but there is still a vast amount that is unknown and the range of unsolved problems is likely to lead to much more beautiful mathematics.
tutteplane.jpegThe diagram depicts the Tutte plane, and more precisely, the complexity of evaluating the Tutte polynomial at different points. Evaluations at green points are easy, those at blue points can be computed for planar graphs, those at red points might be approximated efficiently (it is an open problem) and those at black points cannot be approximated. The diagram was popularized by Dominic Welsh. I have yet to incorporate the more recent results due to Leslie Goldberg and Mark Jerrum - unfortunately they spoil the picture.

What does the Tutte polynomial tell us?

An interesting question is to learn more about exactly what information can be determined from the Tutte polynomial of a graph. For instance it is easy to determine whether a graph is a series-parallel network, but it is not possible to determine if it is planar.

The U-polynomial

The U-polynomial is one of my favourite topics around the Tutte polynomial, although I have not thought about it for a little while now. It generalises the Tutte polynomial by using weighted graphs. Roughly speaking it is defined using a delete-contraction relation, where when an edge is contracted the single vertex formed takes the sum of the two weights of the end-vertices of the contracted edge. It includes the Tutte polynomial as a special case, but also includes many other invariants such as the matching polynomial and is equivalent to Stanley's symmetric function generalization of the Tutte polynomial.

Tutte polynomial inspired techniques

The next section of papers is not so easy to categorize. They are usually indirectly connected with the Tutte polynomial by discussing an invariant of the Tutte polynomial, rather than the polynomial itself. This means that techniques used on the polynomial itself are often useful.

Complexity

A lot of my interest in the Tutte polynomial used to be around complexity: given a class of graphs, how difficult is it to compute the polynomial? However I have not thought about this quite so much for a little while.

Algorithms and complexity

When not thinking about graph polynomials, I generally like to think about problems with an algorithmic flavour. How easy or hard is it to solve a particular problem? Are there subcases which are easier?

Frequency Assignment

I first heard about the frequency assignment problem in 1995 from a talk given by Robert Leese in Oxford. I have returned to it a few times since. The idea is to give integer labels to the vertices of a graph, subject to certain constraints, in such a way that the difference between the largest and the smallest labels is minimized. The vertices of the graph represent transmitters, the labels represent frequencies of radio channels and the constraints are there to ensure that users in the vicinity of more than one transmitter do not suffer from interference.

Complexity of other problems

Scale-free Networks

Back to my home page.