Minors in Expanding Graphs

Authors
• 1 Tel Aviv University, School of Mathematical Sciences, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv, 69978, Israel , Tel Aviv (Israel)
• 2 UCLA, Department of Mathematics, Los Angeles, CA, 90095, USA , Los Angeles (United States)
• 3 Institute for Advanced Study, Princeton, USA , Princeton (United States)
Type
Published Article
Journal
Geometric and Functional Analysis
Publisher
Birkhäuser-Verlag
Publication Date
Mar 27, 2009
Volume
19
Issue
1
Pages
294–331
Identifiers
DOI: 10.1007/s00039-009-0713-z
Source
Springer Nature
Keywords
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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_{s,s^\prime}$$\end{document}-free graph G with average degree r (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2 \leq s \leq s^\prime$$\end{document} are constants) contains a minor with average degree \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$cr^{1+ {\frac{1}{2(s-1)}}}$$\end{document}, for some constant \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$c = c(s, s^\prime) > 0$$\end{document}; (b) Every C2k-free graph G with average degree r (k ≥ 2 is a constant) contains a minor with average degree \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$cr^{\frac{k+1}{2}}$$\end{document}, for some constant c = c(k) > 0. We also derive explicit lower bounds on the minor density in random, pseudo-random and expanding graphs.