Large Minors in Expanders

In this paper we study expander graphs and their minors. Specifically, we attempt to answer the following question: what is the largest function $f(n,alpha,d)$, such that every $n$-vertex $alpha$-expander with maximum vertex degree at most $d$ contains {bf every} graph $H$ with at most $f(n,alpha,d)$ edges and vertices as a minor? Our main result is that there is some universal constant $c$, such that $f(n,alpha,d)geq frac{n}{clog n}cdot left(frac{alpha}{d}right )^c$. This bound achieves a tight dependence on $n$: it is well known that there are bounded-degree $n$-vertex expanders, that do not contain any grid with $Omega(n/log n)$ vertices and edges as a minor. The best previous result showed that $f(n,alpha,d) geq Omega(n/log^{kappa}n)$, where $kappa$ depends on both $alpha$ and $d$. Additionally, we provide a randomized algorithm, that, given an $n$-vertex $alpha$-expander with maximum vertex degree at most $d$, and another graph $H$ containing at most $frac{n}{clog n}cdot left(frac{alpha}{d}right )^c$ vertices and edges, with high probability finds a model of $H$ in $G$, in time poly$(n)cdot (d/alpha)^{Oleft( log(d/alpha) right)}$. We note that similar but stronger results were independently obtained by Krivelevich and Nenadov: they show that $f(n,alpha,d)=Omega left(frac{nalpha^2}{d^2log n} right)$, and provide an efficient algorithm, that, given an $n$-vertex $alpha$-expander of maximum vertex degree at most $d$, and a graph $H$ with $Oleft( frac{nalpha^2}{d^2log n} right)$ vertices and edges, finds a model of $H$ in $G$. Finally, we observe that expanders are the `most minor-rich family of graphs in the following sense: for every $n$-vertex and $m$-edge graph $G$, there exists a graph $H$ with $O left( frac{n+m}{log n} right)$ vertices and edges, such that $H$ is not a minor of $G$.