The extremal function for structured sparse minors

Abstract

Let $c(H)$ be the smallest value for which $e(G)/|G|\ge c(H)$ implies $H$ is a minor of $G$. We show a new upper bound on $c(H)$, which improves previous bounds for graphs with a vertex partition where some pairs of parts have many more edges than others -- for instance a complete bipartite graph with a small number of edges placed inside one class. We also show a tight matching lower bound for almost all such graphs. We apply these results to show $c(K_{ft/\log t,t})=(0.638\dots +o_f(1))t\sqrt{f}$, for $f=o(\log t)=\omega (1)$.