## 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.