The extremal function for noncomplete minors (Q2368599): Difference between revisions

In classical extremal graph theory the maximum number of edges of graphs avoiding certain substructures is investigated. In this paper the authors investigate the maximum number of edges that a graph \(G\) can have if it does not contain \(H\) as a minor. Let \(c(H)=\inf \{c: e(G)\geq c|G|\;\text{implies}\;G\succ H\}\); and \(\gamma (H)=\min_w {1\over t}\sum_{u\in H} w(u)\) such that \(\sum_{uv\in E(H)} t^{-w(u)w(v)}\leq t\) where the minimum is taken over all assignments \(w: V(H)\mapsto {\mathbb R}^+\). One of the important results of this paper says that if \(H\) is a graph of order \(t\), then \(c(H)=(\alpha\gamma (H)+o(1))t\sqrt{\log t}\), and the random graphs provide extremal graphs for \(c(H)\). Several other important theorems are obtained.