Extremal density for sparse minors and subdivisions
Hong Liu (Warwick)
Abstract: How dense a graph has to be to necessarily contain (topological) minors of a given graph $H$? When $H$ is a complete graph, this question is well understood by result of Kostochka/Thomason for clique minor, and result of Bollobas-Thomason/Komlos-Szemeredi for topological minor. The situation is a lot less clear when $H$ is a sparse graph. We will present a general result on optimal density condition forcing (topological) minors of a wide range of sparse graphs. As corollaries, we resolve several questions of Reed and Wood on embedding sparse minors. Among others,
- $(1+o(1))t^2$ average degree is sufficient to force the $t\times t$ 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.
Joint work with John Haslegrave and Jaehoon Kim.
combinatorics
Audience: researchers in the topic
Series comments: This is the online combinatorics seminar at Warwick.
Organizers: | Jan Grebik, Oleg Pikhurko |
Curator: | Hong Liu* |
*contact for this listing |