ON THE DENSITY OF SUBGRAPHS IN A GRAPH WITH BOUNDED INDEPENDENCE NUMBER

Let sigma(n, m, k) be the largest number sigma is an element of [0, 1] such that any graph on n vertices with independence number at most m has a subgraph on k vertices with at lest sigma.((k)(2)) edges. Up to a constant multiplicative factor, we determine sigma(n, m, k) for all n, m, k. For log n less than or equal to m=k less than or equal to n, our result gives sigma(n, m, m)= Theta(log(n/m)/m), which was conjectu red by Alon (Random Structures Algorithms 9 (1996), 271-278). (C) 1998 Academic Press.