A Precise Threshold for Quasi-Ramsey Numbers

We consider the variation of Ramsey numbers introduced by Erdös 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 $\ell \ge k$ vertices with minimum degree at least $\frac12(\ell-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. Erdös 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.
© 2015, Society for Industrial and Applied Mathematics



Read More: http://epubs.siam.org/doi/10.1137/14097313X