The extremal function for noncomplete minors (Q2368599)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The extremal function for noncomplete minors |
scientific article |
Statements
The extremal function for noncomplete minors (English)
0 references
27 June 2006
0 references
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.
0 references
subcontraction
0 references
random and pseudo-random graph
0 references
extremal graph
0 references