• University of Pennsylvania Featured PhD Programmes
  • Staffordshire University Featured PhD Programmes
  • FindA University Ltd Featured PhD Programmes
  • Aberdeen University Featured PhD Programmes
  • University of Tasmania Featured PhD Programmes
  • University of Cambridge Featured PhD Programmes
University of York Featured PhD Programmes
Peter MacCallum Cancer Centre Featured PhD Programmes
Imperial College London Featured PhD Programmes
University of Leeds Featured PhD Programmes
University of Reading Featured PhD Programmes

The Tutte polynomial of matroids and hypergraphs

  • Full or part time
  • Application Deadline
    Applications accepted all year round
  • Awaiting Funding Decision/Possible External Funding
    Awaiting Funding Decision/Possible External Funding

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 ().

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: View Website

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

Email Now

Insert previous message below for editing? 
You haven’t included a message. Providing a specific message means universities will take your enquiry more seriously and helps them provide the information you need.
Why not add a message here
* required field
Send a copy to me for my own records.
Email Sent

Share this page:

Cookie Policy    X