High average degree forces a complete graph minor
Discrete Structures and Algorithms (Reading Group): Graph Minors
by Daniel Harvey and Michael Payne
Abstract: We will prove that every graph with average degree at least c t log t contains a complete graph on t vertices as a minor. This result is almost best possible. The proof is an elegant example of the probabilistic method.