The School of Mathematical Sciences of Queen Mary University of London invite applications for a PhD project commencing either in September 2016 (funded students) or at any point in the academic year (self-funded students).
The Tutte polynomial of a graph G is a two-variable polynomial T(G;x,y) that encodes much interesting information about G. For example, T(G;1,1) is the number of spanning trees of G, T(G;-2,0) is the number of 3-colourings of G and T(G;2,0) is the number of acyclic orientations of G. There is a nice Wikipedia entry on the Tutte polynomial that gives the background to this project proposal. The aim of the project, which lies on the border between combinatorics and computational complexity, is to study generalisations of the Tutte polynomial to matroids and hypergraphs.
A matroid is one generalisation of a graph. There is really only one way to extend the definition of Tutte polynomial from graphs to matroids, and it has been well studied. However, there are several basic unanswered questions about the computational complexity of the Tutte polynomial of matroids; for example, is there an efficient algorithm for counting the number of bases T(M;1,1) of a binary matroid M? There are many open questions concerning the approximate computation of T(M;x,y) for matroids from various classes. Another generalisation of a graph is a hypergraph, and there is at least one natural definition extending the Tutte polynomial to hypergraphs.Here there is so little existing work that there are interesting straight combinatorial problems (equivalent definitions, properties, combinatorial interpretations, etc.) in addition to many complexity-theoretic questions. There may be more that one interesting way to extend the Tutte polynomial to hypergraphs and the relationships between them should be studied.
This project will be supervised by Professor Mark Jerrum.
Further details can be found in the project abstract: http://www.maths.qmul.ac.uk/sites/default/files/phd%20projects%202015/Combinatorics/hyperTutte-4.pdf
The application procedure is described on the School website. For further enquiries please contact Prof. Mark Jerrum ([email protected]
This project is eligible for several sources of full funding for the 2016/17 academic year, including support for 3.5 years’ study, additional funds for conference and research visits and funding for relevant IT needs. Applicants interested in the full funding will have to participate in a highly competitive selection process. The best candidates will be eligible to receive a prestigious Ian Macdonald Postgraduate Award of £1000, for which you will be considered alongside your application. The application deadline for full funding is January 31st 2016.
There is also 50% funding scheme available for students who are able to find the matching 50 % of the cost of their studies. Competition for these half-funded slots will be less intensive, and eligible students should mention their willingness to be considered for them in their application. The application deadline for 50 % funding is January 31st 2016.
This project can be also undertaken as a self-funded project, either through your own funds or through a body external to Queen Mary University of London. Self-funded applications are accepted year-round.