|
|
Below is a selection of 6 possible projects for next year. In general I am happy to supervise a project in any area of discrete maths / combinatorics / graph theory so if you have an idea for a project or want to discuss one of the projects below please email me, or come and see me (M407).
In a mobile phone network, the transmitters have to be allocated frequencies so that those that are closely situated receive frequencies that are well separated. As a result of this, many problems, that are similar to vertex colouring of graphs, have acquired importance. In this project we would look at some of these colourings (including some new ones) and find optimal solutions for easily defined classes of graphs such as paths and cycles.
Many well known graph problems such as vertex colouring and finding a Hamiltonian path are "difficult" in the sense that there is no known efficient algorithm to solve them. However if the problem is restricted to working with a particular type of graph then they become much easier. Series parallel networks are one such type of graph and this project would study these graphs and graph problems which become easy when restricted to this type of graph.
Matchings are introduced briefly in MA2023S. An interesting problem is to count the number of matchings in a given graph. It turns out that the number of matchings of each size are the coefficients of a easily computed polynomial. The aim of the project would be to write some software to evaluate the matching polynomial of a graph and then to use this to test some conjectures. Similar and very successful projects have been carried out in the recent past on the chromatic polynomial, the reliability polynomial and the Tutte polynomial.
In a spinning mill, many different types of product have to be made. When production changes to a new product, waste product is produced until the set-up of the spinning line has beeen changed to the new settings. One of the most important, and also most frequenct changes, just involves a change of colour dye. This can take time because the old colour must be completely flushed out of the system. Naturally the delay involved is worse when moving from a dark colour to a light colour than when moving from a light colour to a dark colour. This project would initially involve a study of the colour change problem and attempt to estimate how long it should take to change colour, and would then move on to scheduling a sequence of jobs in the order that minimises delay. This turns out to be equivalent to the Travelling Salesman Problem, discussed in graph theory, for which there are many well-known solution methods.
Coding theory was introduced very briefly at the end of MA2124A. This project would continue the material that was discussed there and look at the construction of a wide variety of codes including non-binary codes.
With the development of new internet technologies, the use of random numbers is rapidly increasing. Random numbers are needed for cryptography, simulation and also for online gaming. This project will study methods of generating random numbers and tests that can be used to verify their distribution and will include writing some simple macros to do this in Excel.
Back to my home page.
You are (approximately) visitor number
to this page.