Logarithmically-small minors and topological minors

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 (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.