Deryk Osthus

Dense minors in locally sparse graphs

In 1983 Thomassen proved that if the girth of a graph G is large and its minimum degree is at least 3, then G contains large complete minors. Here the girth of a graph G is the length of its shortest cycle. So if a graph G has large girth then it looks locally like a tree. Thus Thomassen's observation is the surprising fact that if the minimum degree of such a "locally sparse" graph is at least 3, i.e. if its large girth is not merely obtained by subdividing edges, then it must contain a large dense substructure, namely a large complete minor.

Together with Daniela Kühn I proved more precise asymptotic bounds on the girth required to force a complete graph of given order as minor. The proofs rely on the probabilistic method. Our results imply Hadwiger's conjecture (which states that every graph of chromatic number at least r contains a K_r minor) for all graphs whose chromatic number is sufficiently large and which do not contain a cycle of length four. In my talk, I will sketch the proof for some special cases and also mention some related results on topological minors.