Minors in Expanding Graphs期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

Minors in Expanding Graphs

Authors:	Michael Krivelevich Benjamin Sudakov

Institution:	(1) School of Mathematical Sciences, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, 69978, Israel;(2) Department of Mathematics, UCLA, Los Angeles, CA 90095, USA;(3) Institute for Advanced Study, Princeton, USA

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 C_2k-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. Received: March 2008, Accepted: May 2008

Keywords:	and phrases:" target="_blank"> and phrases: Graph minors random graphs pseudo-random graphs expanding graphs
本文献已被 SpringerLink 等数据库收录！