Small Minors in Dense Graphs

Abstract

A fundamental result in structural graph theory states that every graph with large average degree contains a large complete graph as a minor. We prove this result with the extra property that the minor is small with respect to the order of the whole graph. More precisely, we describe functions $f$ and $h$ such that every graph with $n$ vertices and average degree at least $f(t)$ contains a $K_t$-model with at most $h(t)\cdot \log n$ vertices. The logarithmic dependence on $n$ is best possible (for fixed $t$). In general, we prove that $f(t)\leq 2^{t-1}+\eps$. For $t\le 4$, we determine the least value of $f(t)$; in particular $f(3)=2+\eps$ and $f(4)=4+\eps$. For $t\le 4$, we establish similar results for graphs embedded on surfaces, where the size of the $K_t$-model is bounded (for fixed $t$).

References in corpus (1)

• Hitting Diamonds and Growing Cacti

Cited by in corpus (6)

• Logarithmically-small Minors and Topological Minors
• Hitting and Harvesting Pumpkins
• Tree densities in sparse graph classes
• Rainbow Turán number of clique subdivisions
• A tight Erdős-Pósa function for wheel minors
• Automorphisms of the k-curve graph