Research


My research looks at fundamental combinatorial objects, such as graphs and hypergraphs, and aims to answer very basic questions, such as "How many graphs are there in this family?", or "how can I sample a random graph from this family?", or "what are the typical properties of a random graph from this family?". Questions like this are very simple to state, but can be extremely difficult to answer. Solutions involve methods from combinatorics, probability, theoretical computer science and, occasionally, ideas from statistical physics. The answers we obtain are asymptotic, meaning that they hold in the limit as the size of the problem tends to infinity.

In particular, I have studied the structure of random graphs and hypergraphs, obtained asymptotic enumeration formulae for various combinatorial objects, and analysed the performance of Markov chain algorithms for approximate sampling and counting. I have also worked in the complexity of exact counting and approximate counting (but not for quite a while).

In many areas, including chemistry, physics, sociology and biology, complex discrete systems arise which can be modelled using graphs and hypergraphs. My research provides tools, such as algorithms and formulae, which can be used to better understand and work with these complex discrete systems.

Publications

For more details see my publications list.

Presentations

A list of talks I have given.

Research students

  • Yudhistira Bunjamin started his PhD in Term 3, 2019. Yudhi is working on existence and enumeration of group-divisible designs. Yudhi is supervised by myself, Diana Combe and Julian Abel, often in collaboration with Thomas Britz.
  • James Ross submitted his Masters by Research thesis in June 2022. James worked on algorithms for sampling uniform hypergraphs with given degrees.
  • Haya Aldosari was awarded her PhD in October 2020. Haya worked on enumeration problems for sparse uniform hypergraphs with given degree sequences, under various conditions (including forbidden edges, or restricted to linear hypergraphs).
  • Peter Ayre was awarded his PhD in 2019. Peter proved bounds on the chromatic number of a random hypergraph with a linear number of edges, encorporating arguments from statistical physics. His calculations supported the values predicted by the statistical physics community for the condensation threshold and rigidity threshold of hypergraph colourings.
  • Matteo Sfragara visited UNSW for a semester in 2015 as a Practicum student, on exchange from his Masters program at the University of Padua. He worked with me on The switch Markov chain for sampling irregular directed graphs.
  • 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.