On the extremal function for graph minors
| Autor: | Thomason, Andrew, Wales, Matthew |
|---|---|
| Rok vydání: | 2019 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1002/jgt.22811 |
| Popis: | 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. Comment: Final accepted version |
| Databáze: | arXiv |
| Externí odkaz: |
|