Width parameters for matroids
Application process
A completed online application must be submitted by 4.30 pm 22 September 2025. Late or incomplete applications will not be accepted. Any required supporting documentation (including references) must also be received by 4.30 pm on the closing date in order for the application to be considered.
Project number
132
Project description
In general, many graph problems are computationally difficult. However, one can describe how “treelike” a graph is using the notion of treewidth, and Courcelle’s Theorem (1990) states that a wide range of graph problems can be solved efficiently for graphs with small treewidth. More generally, width parameters have now been used widely to obtain efficient algorithms for a vast array of graph problems.
Matroids are an abstraction of graphs, and are useful for identifying what aspects of a problem make it computationally difficult. However, width parameters for matroids have not been well studied. The goal of this project would be to explore the world of width parameters for matroids. Of particular interest is the notion of contraction*-depth. Goals of this project include attempting to generalise some known results about contraction*-depth for representable matroids to all matroids, and developing an analogue of contraction*-depth that is well-behaved under duality.
This project is for a single student.
Location
Either at university, or remotely/flexibly.
Supervisor
Lecturer, Mathematics
School of Mathematics and Statistics