Finding dense minors using average degree

Abstract

Motivated by Hadwiger's conjecture, we study the problem of finding the densest possible $t$-vertex minor in graphs of average degree at least $t-1$. We show that if $G$ has average degree at least $t-1$, it contains a minor on $t$ vertices with at least $(\sqrt{2}-1-o(1))\left(\genfrac{}{}{0ex}{}{t}{2}\right)$ edges. We show that this cannot be improved beyond $\left(\frac{3}{4}+o(1)\right)\left(\genfrac{}{}{0ex}{}{t}{2}\right)$. Finally, for $t\le 6$ we exactly determine the number of edges we are guaranteed to find in the densest $t$-vertex minor in graphs of average degree at least $t-1$.

14 pages