A New Lower Bound For A Ramsey-Type Problem

Let 3 ≤ r < s be fixed integers and let G be a graph on n vertices not containing a complete graph on s vertices. The main aim of this paper is to provide a new lower bound on the size of the maximum subset of G without a copy of complete graph K_r. Our results substantially improve previous bounds of Krivelevich and Bollobás and Hind. * Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey. Part of this research was done while visiting Microsoft Research.