DEPARTMENT OF PURE MATHEMATICS

Date: 

Wednesday, 9th March 2005

Large girth regular graphs versus random regular graphs

Speaker: Prof. Nick Wormald (University of Waterloo)

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.