A Precise Threshold for Quasi-Ramsey Numbers

Kang, Ross J. and Pach, János and Patel, Viresh and Regts, Guus (2015) A Precise Threshold for Quasi-Ramsey Numbers. SIAM JOURNAL ON DISCRETE MATHEMATICS, 29 (3). pp. 1670-1682. ISSN 0895-4801

Preview

Text 1403.3464v2.pdf Download (167kB) | Preview

Abstract

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.

Actions (login required)

Edit Item