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 $f$ and $h$ such that every graph with $n$ vertices and average degree at least $f(t)$ contains a $K_t$-model with at most $h(t)\cdot \log n$ vertices. The logarithmic dependence on $n$ is best possible (for fixed $t$). In general, we prove that $f(t)\le 2^{t-1}+\text{eps}$. For $t\le 4$, we determine the least value of $f(t)$; in particular $f(3)=2+\text{eps}$ and $f(4)=4+\text{eps}$. For $t\le 4$, we establish similar results for graphs embedded on surfaces, where the size of the $K_t$-model is bounded (for fixed $t$).