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}{c\log 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 $\mathrm{\Omega }(n\mathrm{/}\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$dependsonboth$\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}{c\log 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\mathrm{/}\alpha {)}^{O(\log (d\mathrm{/}\alpha ))}$. We note that similar but stronger results were independently obtained by Krivelevich and Nenadov: they show that $f(n,\alpha,d)=\Omega \left(\frac{n\alpha^2}{d^2\log 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 $O\left(\frac{n{\alpha }^2}{d^2\log 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$.