2023/07/03 by Hendrey, Kevin, Norin, Sergey, Steiner, Raphael +1 · 1 citation
#05C07 #05C35 #05C83 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2307.01184
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 (√(2)-1-o(1))\binomt2 edges. We show that this cannot be improved beyond ((3)/(4)+o(1))\binomt2. 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.