Minors in small-set expanders

Abstract

We study large minors in small-set expanders. More precisely, we consider graphs with $n$ vertices and the property that every set of size at most $\hat{I}\pm n/t$ expands by a factor of $t$, for some (constant) $\hat{I}\pm >0$ and large $t=t(n)$. We obtain the following: * Improving results of Krivelevich and Sudakov, we show that a small-set expander contains a complete minor of order $\sqrt{nt/\log n}$. * We show that a small-set expander contains every graph $H$ with $O(n\log t/\log n)$ edges and vertices as a minor. We complement this with an upper bound showing that if an $n$-vertex graph $G$ has average degree $d$, then there exists a graph with $O(n\log d/\log n)$ edges and vertices which is not a minor of $G$. This has two consequences: (i) It implies the optimality of our result in the case $t=d^c$ for some constant $c>0$, and (ii) it shows expanders are optimal minor-universal graphs of a given average degree.

15 pages