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