School Seminars and Colloquia

High average degree forces a complete graph minor

Discrete Structures and Algorithms (Reading Group): Graph Minors

by Daniel Harvey and Michael Payne

Institution: The University of Melbourne
Date: Mon 19th September 2011
Time: 11:00 AM
Location: Room 107, Richard Berry Building

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.