Extremal density for sparse minors and subdivisions

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.

arXiv comment33 pages, 6 figures

References in corpus (6)

• Characterisations and Examples of Graph Classes with Bounded Expansion
• A proof of Mader's conjecture on large clique subdivisions in $C_4$-free graphs
• Packing minor-closed families of graphs into complete graphs
• Breaking the degeneracy barrier for coloring graphs with no $K_t$ minor
• Proof of Komlós's conjecture on Hamiltonian subsets
• Forcing a sparse minor

Cited by in corpus (4)

• Ramsey numbers of cycles versus general graphs
• Well-mixing vertices and almost expanders
• Extremal functions for sparse minors
• Limits of degeneracy for colouring graphs with forbidden minors