Deryk Osthus<br>
<br>
Dense minors in locally sparse graphs
<br>                                                                             
<br>
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.

<br>
<br>                                                                            
Together with Daniela K&uuml;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.