Hints and tips:
  • You may need to look up some unfamiliar terms in the title or description to get more of a sense of what is involved.
  • If the project has "No" in the "Current Availability:" field, it is already taken or not being offered this academic year but may be available again in future years.
  • The supervisor name links to a contact details webpage so, if you are interested, you can arrange to discuss this project or even propose a related topic of your own.
Level: MSc
Title: Degree bounded graph processes
Supervisor:

Dr Dudley Stark

Research Area: Combinatorics
Description:

In a degree bounded graph process we repeatedly add edges between vertices in a graph subject to the condition that the degrees of the
vertices are less than some constant which is a parameter of the process. The degree bounded graph process is studied using the differential equations method of Wormald. We will survey the known results about the process and perhaps do some simulations of it.
Further Reading:
  • N. Wormald, The differential equation method for random graph processes and greedy algorithms, in Lectures on Approximation and Randomized Algorithms: Proceedings of the Berlin-Poznań Summer School, Edited by M. Karoński and  H. J. Pröme, Polish Scientific Publishers PWN, 1999. 73–155 [http://users.monash.edu.au/~nwormald/papers/de.pdf].
Key Modules:
Other Information:

Differential equations, probability and some knowledge of stochastic processes are required.
Current Availability: Yes