Finding dense minors using average degree

Abstract

Motivated by Hadwiger&apos;s conjecture, we study theproblem of finding the densest possiblet-vertex minorin graphs of average degree at least t-1. We show thatifGhas average degree at least t-1, it contains a minor on t vertices with at least (root 2-1-(1))t2) edges. We show that this cannot be improved beyond (3/4 )o(1)(t 2)+. Finally, for t <= 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.