DEPARTMENT OF PURE MATHEMATICS

Large girth regular graphs versus random regular graphs

Speaker: Prof. Nick Wormald (University of Waterloo)

Title: Large girth regular graphs versus random regular graphs

Date: Tuesday, 8 March 2005
Time: 2:00 pm
Venue:RC-4082, The Red Centre, UNSW

This talk is on the relation between random graphs with
bounded degrees, and their nonrandom counterparts with
large girth. The passing of a property of all "d"-regular
graphs with large girth to random "d"-regular graphs
(without girth restriction) is fairly well understood.

A completely new development is that we can prove something
about all regular graphs (or, sometimes, graphs of bounded
degree) with large girth by adapting methods using randomised
algorithms which were tailor-made for random regular graphs.
Although only one case has been fully investigated, it would
appear that many results obtained for random regular graphs
may translate back to the nonrandom, large girth case in a
similar way.

This provides some kind of intuitive explanation
of the origin of (some/many of?) the properties of random
regular graphs. The new result to be discussed in detail is
on the size of independent sets, obtained with Joe Lauer.
It raises some questions about many other properties such as
colouring.

Enquiries to Catherine Greenhill, 9385 7105, csg@unsw.edu.au