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.

Published in:
Siam Journal On Discrete Mathematics, 29, 3, 1670-1682
Philadelphia, Siam Publications

 Record created 2015-12-02, last modified 2018-01-28

Rate this document:

Rate this document:
(Not yet reviewed)