School Seminars and Colloquia

A probabilistic method for graphs of large girth

Geometry/Topology Seminar

by Dr Nick Wormald


Institution: University of Waterloo
Date: Mon 30th July 2007
Time: 3:15 PM
Location: Room 213, Richard Berry Building, Uni of Melbourne

Abstract: To use the "probabilistic method", one typically constructs a probability space P in order to prove something about a given structure S. Normally P is built by considering some random variables defined in terms of S. I will give some examples of this, and then describe a new kind of probabilistic method. It works in an unlikely-sounding way: we can find typical properties of random structures in a large set C, and then show separately that the properties "transfer" to all structures in C. Of course, this is only applicable under special circumstances.

Present applications involve regular graphs of large girth. (The girth is the length of the shortest cycle.) Results obtained include lower bounds on the largest independent set (set of vertices no two of which are adjacent). These bounds significantly improve Shearer's bounds, which have stood since 1991. Another application gives new upper bounds on the minimum size of dominating sets in graphs with given maximum degree and large girth.

For More Information: Lawrence Reeves L.Reeves@ms.unimelb.edu.au