A Precise Threshold For Quasi-Ramsey Numbers

We consider the variation of Ramsey numbers introduced by Erdos and Pach [J. Graph Theory, 7 (1983), pp. 137-147], where instead of seeking complete or independent sets we only seek a t-homogeneous set, a vertex subset that induces a subgraph of minimum degree at least t or the complement of such a graph. For any nu > 0 and positive integer k, we show that any graph G or its complement contains as an induced subgraph some graph H on l >= k vertices with minimum degree at least 1/2 (l - 1) + nu provided that G has at least k(Omega)(nu(2)) vertices. We also show this to be the best possible in a sense. This may be viewed as correction to a result claimed in [P. Erdos and J. Pach, J. Graph Theory, 7 (1983), pp. 137-147]. For the above result, we permit H to have order at least k. In the harder problem, where we insist that H have exactly k vertices, we do not obtain sharp results, although we show a way to translate results of one form of the problem to the other.