Project option 1: Matroids and Combinatorial Optimisation

Matroids can be thought of as generalising linear dependence in linear algebra to classical combinatorial problems like the study of cycles in graphs, bipartite matchings and much more. Greedy algorithm characterisations of matroids exist and matroids have a splendid polyhedral structure which can be studied through linear programming. Like most modern mathematics, there is also a rich duality theory in matroids.

The goal of this project will be to introduce the student to combinatorial optimisation (which you can think of as combinatorial problems that can be described and studied succinctly in terms of optimisation problems) through the lens of matroids. We will concentrate on the role of greedy algorithms in matroids, the matroid polytope and matroid duality and how the ideas behind these algorithms and constructions extend (or don't extend) to other combinatorial problems.

Project option 2: Frequency of prime numbers

One of the earliest theorems of mathematics is that of Euclid, exhibiting that there are infinitely many primes by contradicting an assumption that only finitely many exist. There are (at least) 5 other proofs that are within reach of most mathematics undergraduates. But this doesn't answer the question of how frequently the primes occur in the set of positive integers. For this the prime number theorem says that the number of primes between 2 and N is approximately log(N), for large enough N.

Another way of saying this is that the identity function id(n)=n on the domain of positive integers produces primes at a rate of log(N)/N, again for large enough N. So it is natural to ask, is there another function f with the positive integers as its domain such that f produces primes at a better rate than the identity function? For example, the polynomial f(n) = n² - 79n + 1601 produces nothing but primes for n = 1,2,...,79 but fails at 80 (and many times thereafter). In this project we will explore the many proofs showing that there are infinitely many primes, the prime number theorem and why, regardless of how hard one looks, one can never find a polynomial function whose domain is the positive integers and which produces nothing but primes. We will also look at other functions.

Project option 3: Topic of mutual interest.

See my research page or my masters course for some other possibilities. Feel free to email me and propose another one.