Extremal density for sparse minors and subdivisions

DOI10.1093/IMRN/RNAB154MaRDI QIDQ5046072zbMATH OpenOpenAlexFDO

Authors John Haslegrave, Hong Liu, Jaehoon Kim

Publication date 27 October 2022

Published in IMRN. International Mathematics Research Notices (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2012.02159

zbMATH Keywords

\(t\)-vertex graphbounded average degreebounded-degree bipartite graphs

Mathematics Subject Classification ID

Graphical indices (Wiener index, Zagreb index, Randi? index, etc.) (05C09) Distance in graphs (05C12) Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42) Combinatorial aspects of simplicial complexes (05E45)

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, $$ $(1+o(1))t^2$ average degree is sufficient to force the $timest$ grid as a topological minor; $$ $(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; $$ 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.

Recommendations

• A lower bound on the average degree forcing a minor
• Forcing a sparse minor
• Average degree conditions forcing a minor
• Extremal functions for sparse minors
• Small minors in dense graphs

Cited in

(29)

• The density of a maximum minimal cut in the subset lattice of a finite set is almost one
• Sparse obstructions for minor-covering parameters
• A lower bound on the average degree forcing a minor
• Extremal connectivity for topological cliques in bipartite graphs
• Average degree conditions forcing a minor
• Phase transition of degeneracy in minor-closed families
• Nested cycles with no geometric crossings
• Well-mixing vertices and almost expanders
• Crux and Long Cycles in Graphs
• Forcing a sparse minor
• Extremal functions for sparse minors
• Ramsey numbers of cycles versus general graphs
• Disjoint isomorphic balanced clique subdivisions
• How to build a pillar: a proof of Thomassen's conjecture
• Recent progress towards Hadwiger's conjecture
• Towards the Erdős-Gallai cycle decomposition conjecture
• Immersion of complete digraphs in Eulerian digraphs
• Separating path systems of almost linear size
• Many Hamiltonian subsets in large graphs with given density
• Crux, space constraints and subdivisions
• Minors in small-set expanders
• Nearly Hamilton cycles in sublinear expanders and applications
• Extremal density for subdivisions with length or sparsity constraints
• Graph theory. Abstracts from the workshop held January 5--10, 2025
• Limits of degeneracy for colouring graphs with forbidden minors
• Essentially tight bounds for rainbow cycles in proper edge-colourings
• Edge-disjoint cycles with the same vertex set
• Embedding clique subdivisions via crux
• Packing subdivisions into regular graphs

This page was built for publication: Extremal density for sparse minors and subdivisions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5046072)