Back to Search
Start Over
Extremal density for sparse minors and subdivisions
- Source :
- International Mathematics Research Notices, Volume 2022, Issue 20
- Publication Year :
- 2020
-
Abstract
- We prove an asymptotically tight bound on the extremal density guaranteeing subdivisions of bounded-degree bipartite graphs with a mild separability condition. As corollaries, we answer several questions of Reed and Wood on embedding sparse minors. Among others, $\bullet$ $(1+o(1))t^2$ average degree is sufficient to force the $t\times t$ grid as a topological minor; $\bullet$ $(3/2+o(1))t$ average degree forces every $t$-vertex planar graph as a minor, and the constant $3/2$ is optimal, furthermore, surprisingly, the value is the same for $t$-vertex graphs embeddable on any fixed surface; $\bullet$ a universal bound of $(2+o(1))t$ on average degree forcing every $t$-vertex graph in any nontrivial minor-closed family as a minor, and the constant 2 is best possible by considering graphs with given treewidth.<br />Comment: 33 pages, 6 figures
- Subjects :
- Mathematics - Combinatorics
05C83, 05C35
Subjects
Details
- Database :
- arXiv
- Journal :
- International Mathematics Research Notices, Volume 2022, Issue 20
- Publication Type :
- Report
- Accession number :
- edsarx.2012.02159
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1093/imrn/rnab154