Professor Catherine Greenhill has been invited to give a plenary talk at the 28th British Combinatorial Conference (BCC).
She is among nine plenary speakers at the biennial conference, which is being delivered online by Durham University this week.
This year's conference boasts a registration of over 420 participants, and is comprised of plenary and contributed talks, mini-symposia and open problem sessions.
Professor Greenhill's talk "Generating Graphs Randomly" will be presented on Friday 9 July.
Several other School members will be participating in the conference. Dr Anita Liebenau will be involved in the mini-symposia for Extremal Combinatorics, while Yudhi Bunjamin, Zhi Yee Chng and Thomas Lesgourgues will deliver contributed talks.
BCC, which has run since 1969, is one of the world's largest combinatorics conferences.
Generating Graphs Randomly
Graphs are used in many disciplines to model the relationships that exist between objects in a complex discrete system. Researchers often wish to compare their particular graph to a "typical” graph from a family (or ensemble) of graphs which are similar to theirs in some way. Such a family might be the set of all graphs with a given number of vertices and edges, or the set of all graphs with a particular degree sequence.
One way to do this is to take several random samples from the family, to gather information about what is "typical”. This motivates the search for an algorithm which can generate graphs uniformly (or approximately uniformly) at random from the given family. Since many random samples may be required, the algorithm should also be efficient. Rigorous analysis of such algorithms is often challenging, involving both combinatorial and probabilistic arguments. I will discuss some algorithms for sampling graphs, and the methods used to analyse them.