Past Honours/4th Year CSE project students
- Cris Koch (2006) wrote an Honours thesis on Term rewriting approach to polycyclic group collection.
- Byron Ng (2005/2006) did his 4th year CSE project on Computer simulation for bounding the mixing time of Markov chains.
- Le Anh Vinh (2005) did an Honours-level project on Ramsey theory.
- Ka-shu Wong (2004) wrote an Honours thesis on The complexity of counting.
- Michael Leeming (2004) did his 4th year CSE project on Analyzing a Markov chain for 7-colourings of 4-regular graphs.
Topics for Honours projects
Here is an outline of a couple of possible topics for Honours projects which I could supervise in 2008. If you like the sound of one of them, then please come and talk to me about it. In each case a fairly broad, survey-style project has been described. But this is just a jumping-off point -- a student may find, over the course of the Honours year, that they have a particular interest in one part of the project and choose to focus on that.
(If you're worried that you don't have enough background in graph theory or in probability, then stop worrying. You can pick it up as you go along. That's the beauty of combinatorics, and for the most part the probability used is fairly basic.)
Of course if you have your own idea for a topic, feel free to run it by me.
Random graphs and random graph processes
The first random graph model was introduced by Erdös in 1947. The idea is as follows: to produce a random graph on n vertices, flip a fair coin (one that comes up heads with probability exactly 1/2) independently for each of the n(n-1)/2 potential edges. If the coin comes up heads, then the edge is chosen for the graph, and otherwise the (potential) edge is rejected. A generalisation of this is the binomial model G(n,p). This time we use a coin which comes up heads with probability exactly p, for a given value of p between 0 and 1 (which may depend on n). This model has been extremely well studied.
Other models are for random graphs with a fixed number of edges, or random regular graphs where every vertex has the same number of neighbours. The most recent models to emerge are the so-called Web graphs, which aim to model the growth and structure of the World Wide Web. A related area is that of random graph processes, where a discrete-time stochastic process is used to ``grow'' a random graph, typically by adding an edge (or set of edges) at each step, according to some rule.
In all cases, we are interested in asymptotic behaviour, which gives an idea of how these graphs behave as the number of vertices n tends to infinity. The properties which are studied include the connectivity, independence number, chromatic number and diameter, to name a few. The methods used are a mixture of combinatorial and probabilistic. The aim of the project is to survey the topic, learning about some of the results which have been proved and the methods used to prove them.
A couple of references:
[1] Svante Janson, Tomasz Luczak, Andrzej Rucinski, Random Graphs, Wiley, New York, 2000.
[2] Bela Bollobás, Random Graphs (2nd edn.), Cambridge University Press, Cambridge, 2001.
[3] Nicholas C. Wormald, Random Regular Graphs, in Surveys in Combinatorics 1999 (J. D. Lamb and D A. Preece, eds.), London Mathematical Society Lecture Note Series vol. 267, Cambridge University Press, Cambridge, 1999, pp. 239--298.
The differential equations method for analysing combinatorial algorithms
The differential equations method is a way of analysing a discrete-time combinatorial process. For instance, consider the following graph process which is used to form graphs with maximum degree d. The process starts at time 0 with n vertices and no edges. At each time step a pair of non-neighbouring vertices which both have current degree less than d is chosen uniformly at random, and this new edge is added to the graph. When analysing this process it is very useful to know the number Y of vertices of degree d at each step. (So Y is a non-negative integer valued random variable.) By finding the equation for the expected value of the change of Y over one time step, and treating this as the derivative of a related continuous function, we can approximate Y by the solution of a differential equation. (Similarly, a system of random variables can be approximated by the solution to a system of differential equations.)
Wormald (1995, 1999) has presented theorems which give conditions under which this approximation is guaranteed to be close. (Often there is no need to actually solve the differential equations, or else it is sufficient to solve them numerically.) The method has been applied to algorithms for random graphs and random SAT instances.
The aim of the project is to survey this area, learning about the method and how it has been applied. The history of the differential equations method (which goes back to Kurtz in 1970) could also be looked into. The focus is not on calculus, but on the interplay between discrete and continuous mathematics.
A couple of references:
[1] Nicholas C. Wormald, The differential equation method for random graph processes and greedy algorithms, in Lectures on Approximation and Randomization Algorithms (M. Karonski and H.-J. Prömel, eds.), PWN, Warsaw, 1999.
[2] Dimitris Achlioptas, Lower bounds for random 3-SAT via differential equations, Theoretical Computer Science 265 (2001), 159--185.