## Abstract

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

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}-minor (proved by Mader). Improving on results of Shapira and Sudakov, we prove the conjecture of Fiorini, Joret, Theis and Wood that any graph with n vertices and average degree at least c(t)+ε must contain a K_{t}-minor consisting of at most C(ε,t)logn vertices.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+ε)s(t) contain a K_{t}-topological minor consisting of at most C(ε,t)logn vertices. Finally, we show that, for sufficiently large t , graphs with average degree at least (1+ε)c(t) contain either a K_{t}-minor consisting of at most C(ε,t) vertices or a K_{t}-topological minor consisting of at most C(ε,t)logn vertices.Original language | English |
---|---|

Pages (from-to) | 71-88 |

Number of pages | 18 |

Journal | Journal of the London Mathematical Society |

Volume | 91 |

Issue number | 1 |

Early online date | 5 Nov 2014 |

DOIs | |

Publication status | Published - 1 Feb 2015 |