Research


My research interests lie in graph theory, particularly the theory of random graphs. Here we try to discover what a "typical" graph with certain properties might look like (for instance, a given number of vertices and edges, or a given number of vertices and every vertex having a fixed degree). This work involves a mixture of combinatorial and probabilistic arguments, and the results obtained are asymptotic, meaning they hold in the limit as the number of vertices of the graph tends to infinity. Some of my work involves proving that two different random graph models are contiguous, meaning that any event which holds asymptotically almost surely in one model also holds asymptotically almost surely in the other. I have also investigated various random processes for generating random graphs.

A related area is asymptotic enumeration of various kinds of graphs. This means finding a formula for the number of graphs of interest which is closer and closer to the truth as the number of vertices tends to infinity. For sparse graphs the methods are combinatorial and often involve a probabilistic approach using switchings. For dense graphs the approach is quite different: we want to to know a particular coefficient of the generating function and proceed using complex analysis, evaluating integrals using the saddle-point method.

I am also interested in the design and analysis of randomized algorithms for graphs and other combinatorial structures, particularly Markov chain Monte Carlo algorithms for approximate sampling and/or counting. Here a Markov chain is designed with a given stationary distribution, for instance the uniform distribution on the set of all proper colourings of the input graph. The aim is to prove that the Markov chain converges rapidly (i.e. in polynomial time with respect to the number of vertices) to this distribution, for all input graphs (or for all input graphs with maximum degree bounded above by some fixed constant, say). My favourite method for doing this is path coupling, but I have also discovered the joys of multicommodity flows.

Algorithm design often leads to related questions in computational complexity: for instance, a polynomial-time algorithm to approximately count something is more impressive if it is known that exact counting is unlikely to be possible in polynomial time. I have worked in the complexity of exact counting and approximate counting (but not for quite a while).

Publications

For more details see my publications list.

Presentations

A list of talks I have given.

Research students

  • James Ross started a Masters by Research with me in Semester 2, 2017. James is looking at algorithms for sampling hypergraphs.
  • Haya Aldosri started a PhD with me in Semester 2, 2016. Haya is working on enumeration problems for hypergraphs.
  • Peter Ayre started a PhD with me in Semester 1, 2015. Peter has been working on phase transitions in hypergraph colouring problems, where the proofs are inspired by statistical physics heuristics.
  • Natalya Levenkova was awarded her Masters by Research in 2014. She looked at the use of random networks in application areas such as the modelling of infectious diseases and in the study of criminal networks. (Co-supervisor, Prof. John Murray.)
  • Stephen Howe was awarded his PhD in 2009. He extended the existing theory of the differential equations method, and applied his new theory to dominating set problems for directed regular graphs.
  • I co-supervised Helen Armstrong's PhD. Her work involved using graphical models for statistical inference (at least, that's what I think she was doing - we just talked about graph theory). Helen was awarded her PhD in 2006.

I do not offer summer internships.