Random hypergraphs and asymptotic enumeration

Date: Tuesday 4 October 2022

Abstract

Hypergraphs are generalisations of graphs, where each edge is a subset of the vertex set. In a uniform hypergraph, every edge has the same size: for example, a graph is a 2-uniform hypergraph.  Asymptotic enumeration involves finding an approximate formula for the size of a combinatorial set, with a relative error that gets smaller as the size of the set grows. For example, we might be interested in the number of hypergraphs with a given number of vertices and satisfying some other nice properties.

As well as being interesting in their own right, asymptotic enumeration formulae can be very useful tools which can help us prove results about random hypergraphs, or analyse randomised algorithms for hypergraphs. I will illustrate this claim by discussing three recent results about random hypergraphs.

Short Bio

Catherine Greenhill started her academic career as an undergraduate at the University of Queensland, before obtaining a D.Phil. from the University of Oxford (1992). She held postdoctoral positions at the University of Leeds and at the University of Melbourne, then joined UNSW in 2002.  Today she is a Professor and head of the Combinatorics group in the School of Mathematics and Statistics, UNSW Sydney.  Catherine's research interests lie in asymptotic, probabilistic and algorithmic combinatorics.  She was awarded the Christopher Heyde Medal by the Australian Academy of Science (AAS) in 2015, and was elected as a Fellow of the AAS in 2022.  Her work lies at the interface between discrete mathematics, theoretical computer science and probability, and has been applied by researchers in various areas including physics and cryptography.