A random graph is obtained by starting with a set of n vertices (points) and adding edges (connections) between them at random. When a random graph on n vertices has enough edges, i.e. about (1/2) n log n, it almost surely has a cycle containing all of its vertices, and the circumference (length of the longest cycle) is n. What happens in the sparser case? When the graph has many fewer than n/2 edges there are few cycles and the answer is well understood. I will discuss old results on circumference as well as a new lower bound applying to the intermediate range. The new bound is joint work with Jeong Han Kim.

Colloquia are designed to be of interest to a general mathematical audience and to be accessible without specialist knowledge. There will be wine and cheese afterwards.
 

Convenor: Ian Wanless - firstname.lastname@sci.monash.edu.au