On the extremal function for graph minors

For a graph $H$, let $c(H)=\inf\{c\,:\,e(G)\geq c|G| \mbox{ implies } G\succ H\,\}$, where $G\succ H$ means that $H$ is a minor of $G$. We show that if $H$ has average degree $d$, then $c(H)\le (0.319\ldots+o_d(1))|H|\sqrt{\log d}$ where $0.319\ldots$ is an explicitly defined constant. This bound matches a corresponding lower bound shown to hold for almost all such $H$ by Norin, Reed, Wood and the first author.

No reviews yet.

No comments yet.