A probabilistic method for graphs of large girth
by Dr Nick Wormald
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