Tutte colloquium - Carlos Hoppen

Local algorithms: a bridge between probabilistic and deterministic results about graphs

Abstract:

We shall report on properties of regular graphs with large girth that may be derived from the analysis of a class of randomised algorithms. For instance, we shall consider independent and dominating sets, cuts and bisections. Our results are obtained by tying the performance of such algorithms on regular graphs with large girth to their performance on random regular graphs, a setting to which powerful methods may be applied. (This is joint work with Nick Wormald.)