×

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)
PDF BibTeX Cite
Full Text: DOI arXiv