The Extremal Function For Noncomplete Minors

  We investigate the maximum number of edges that a graph G can have if it does not contain a given graph H as a minor (subcontraction). Let We define a parameter γ(H) of the graph H and show that, if H has t vertices, then where α = 0.319. . . is an explicit constant and o(1) denotes a term tending to zero as t→∞. The extremal graphs are unions of pseudo-random graphs. If H has t^1+τ edges then , equality holding for almost all H and for all regular H. We show how γ(H) might be evaluated for other graphs H also, such as complete multi-partite graphs. * Research supported by EPSRC studentship 99801140.