Minors in Expanding Graphs.

Abstract.  We propose a unifying framework for studying extremal problems related to graph minors. This framework relates the existence of a large minor in a given graph to its expansion properties. We then apply the developed framework to several extremal problems and prove in particular that: (a) Every $$K_{s,s^\prime}$$-free graph G with average degree r ($$2 \leq s \leq s^\prime$$ are constants) contains a minor with average degree $$cr^{1+ {\frac{1}{2(s-1)}}}$$, for some constant $$c = c(s, s^\prime) > 0$$; (b) Every C2k-free graph G with average degree r (k ≥ 2 is a constant) contains a minor with average degree $$cr^{\frac{k+1}{2}}$$, for some constant c = c(k) > 0. We also derive explicit lower bounds on the minor density in random, pseudo-random and expanding graphs. [ABSTRACT FROM AUTHOR]