An extremal function for digraph subcontraction

We determine, to within a constant factor, the maximum size of a digraph which has no subcontraction to the complete digraph DK_p of order p. Let d(p) be defined for positive integers p by d(p) = inf{c; e(D) ≥ c |D| implies D (FANCY MORE THAN) DK_p}, where D denotes a digraph, and (FANCY MORE THAN) denotes contraction. We show that 0.53p√log₂p < d(p) ≤ 2502p√log₂p holds if p is sufficiently large. Hence the function d(p) differs by only a constant factor from the corresponding function for undirected graphs. © 1996 John Wiley & Sons, Inc.