Wednesday, March 19th, 2014 | 4pm-5pm | McConnell 320 |

Monash University

Forcing a sparse minor

We consider the following question for a given graph H: what is the minimum number f(H) such that every graph with average degree at least f(H) contains H as a minor? Motivated by connections with Hadwiger's Conjecture, this question has been studied in depth when H is a complete graph. Thomason proved that f(K_t) = 0.628... t sqrt(log t). This result was generalised by Myers and Thomason for all dense graphs H. We focus on the case of sparse graphs H. Our main result says that if H has t vertices and average degree d (at least some constant) then f(K_t) <= 3.895 t sqrt(log d).