Logarithmically-small Minors and Topological Minors

Abstract

Mader proved that for every integer $t$ there is a smallest real number $c(t)$ such that any graph with average degree at least $c(t)$ must contain a $K_t$-minor. Fiorini, Joret, Theis and Wood conjectured that any graph with $n$ vertices and average degree at least $c(t)+\epsilon$ must contain a $K_t$-minor consisting of at most $C(\epsilon ,t)\log n$ vertices. Shapira and Sudakov subsequently proved that such a graph contains a $K_t$-minor consisting of at most $C(\epsilon ,t)\log n\log \log n$ vertices. Here we build on their method using graph expansion to remove the $\log \log n$ factor and prove the conjecture. Mader also proved that for every integer $t$ there is a smallest real number $s(t)$ such that any graph with average degree larger than $s(t)$ must contain a $K_t$-topological minor. We prove that, for sufficiently large $t$, graphs with average degree at least $(1+\epsilon )s(t)$ contain a $K_t$-topological minor consisting of at most $C(\epsilon ,t)\log n$ vertices. Finally, we show that, for sufficiently large $t$, graphs with average degree at least $(1+\epsilon )c(t)$ contain either a $K_t$-minor consisting of at most $C(\epsilon ,t)$ vertices or a $K_t$-topological minor consisting of at most $C(\epsilon ,t)\log n$ vertices.

19 pages

Cited by in corpus (8)

• A proof of Mader's conjecture on large clique subdivisions in $C_4$-free graphs
• Proof of Komlós's conjecture on Hamiltonian subsets
• Tree densities in sparse graph classes
• Rainbow Turán number of clique subdivisions
• A tight Erdős-Pósa function for planar minors
• Robust (rainbow) subdivisions and simplicial cycles
• Finding large expanders in graphs: from topological minors to induced subgraphs
• A tight Erdős-Pósa function for wheel minors