# zbMATH — the first resource for mathematics

Minors in expanding graphs. (English) Zbl 1227.05230
Summary: 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 $$C_{2k}$$-free graph $$G$$ with average degree $$r$$ ($$k \geq 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.

##### MSC:
 05C83 Graph minors 05C35 Extremal problems in graph theory 05C80 Random graphs (graph-theoretic aspects)
##### Keywords:
extremal problem; graph minors
Full Text: