A precise threshold for quasi-Ramsey numbers

Abstract

We consider a variation of Ramsey numbers introduced by Erdős and Pach (1983), 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 $\frac{1}{2}(\ell -1)+\nu$ provided that $G$ has at least $k^{\Omega ({\nu }^2)}$ vertices. We also show this to be best possible in a sense. This may be viewed as correction to a result claimed in Erdős and Pach (1983). 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.

17 pages, 1 figure

References in corpus (1)

• The t-improper chromatic number of random graphs

Cited by in corpus (1)

• On a Ramsey-type problem of Erdős and Pach