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,α,d)$, such that every $n$-vertex $α$-expander with maximum vertex degree at most $d$ contains {\bf every} graph $H$ with at most $f(n,α,d)$ edges and vertices as a minor? Our main result is that there is some universal constant $c$, such that $f(n,α,d)\geq \frac{n}{c\log n}\cdot \left(\fracα{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 $Ω(n/\log n)$ vertices and edges as a minor. The best previous result showed that $f(n,α,d) \geq Ω(n/\log^κn)$, where $κ$ depends on both $α$ and $d$. Additionally, we provide a randomized algorithm, that, given an $n$-vertex $α$-expander with maximum vertex degree at most $d$, and another graph $H$ containing at most $\frac{n}{c\log n}\cdot \left(\fracα{d}\right )^c$ vertices and edges, with high probability finds a model of $H$ in $G$, in time poly$(n)\cdot (d/α)^{O\left( \log(d/α) \right)}$. We note that similar but stronger results were independently obtained by Krivelevich and Nenadov: they show that $f(n,α,d)=Ω\left(\frac{nα^2}{d^2\log n} \right)$, and provide an efficient algorithm, that, given an $n$-vertex $α$-expander of maximum vertex degree at most $d$, and a graph $H$ with $O\left( \frac{nα^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$.