Small minors in dense graphs

A fundamental result in structural graph theory states that every graph with large average degree contains a large complete graph as a minor. We prove this result with the extra property that the minor is small with respect to the order of the whole graph. More precisely, we describe functions ff and hh such that every graph with nn vertices and average degree at least f(t)f(t) contains a KtKt-model with at most h(t)⋅lognh(t)⋅logn vertices. The logarithmic dependence on nn is best possible (for fixed tt). In general, we prove that f(t)≤2t−1+εf(t)≤2t−1+ε. For t≤4t≤4, we determine the least value of f(t)f(t); in particular, f(3)=2+εf(3)=2+ε and f(4)=4+εf(4)=4+ε. For t≤4t≤4, we establish similar results for graphs embedded on surfaces, where the size of the KtKt-model is bounded (for fixed tt).