• University of Glasgow Featured PhD Programmes
  • University of Leeds Featured PhD Programmes
  • University of Mannheim Featured PhD Programmes
  • London School of Economics and Political Science Featured PhD Programmes
  • University of Cambridge Featured PhD Programmes
  • Carlos III Health Institute Featured PhD Programmes
  • University of Leeds Featured PhD Programmes
  • University of Leeds Featured PhD Programmes
University College London Featured PhD Programmes
University of Kent Featured PhD Programmes
University of Bristol Featured PhD Programmes
University of Sussex Featured PhD Programmes
University of Bristol Featured PhD Programmes

The Tutte polynomial of matroids and hypergraphs

This project is no longer listed in the FindAPhD
database and may not be available.

Click here to search the FindAPhD database
for PhD studentship opportunities
  • Full or part time
    Prof Jerrum
  • Application Deadline
    Applications accepted all year round

Project Description

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.

Funding Notes

If you wish to apply for the above funding slots, please visit the application website and mention that you wish to work on the “Tutte polynomial of matroids and hypergraphs” project.

School website: http://www.qmul.ac.uk/postgraduate/research/subjects/mathematical-sciences/index.html

Related Subjects

How good is research at Queen Mary University of London in Mathematical Sciences?

FTE Category A staff submitted: 34.80

Research output data provided by the Research Excellence Framework (REF)

Click here to see the results for all UK universities
Share this page:

Cookie Policy    X