The extremal function for noncomplete minors

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.

Recommendations

Cited in

(41)

This page was built for publication: The extremal function for noncomplete minors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2368599)