On generalized Ramsey numbers of Erdős and Rogers

Abstract

Extending the concept of Ramsey numbers, Erd{\H o}s and Rogers introduced the following function. For given integers $2\le s<t$ let $$f_{s,t}(n)=\min \{\max \{|W|:W\subseteq V(G)andG[W]containsno{K}_s\}\},$$ where the minimum is taken over all $K_t$-free graphs $G$ of order $n$. In this paper, we show that for every $s\ge 3$ there exist constants $c_1=c_1(s)$ and $c_2=c_2(s)$ such that $f_{s,s+1}(n)\le c_1(\log n{)}^{c_2}\sqrt{n}$. This result is best possible up to a polylogarithmic factor. We also show for all $t-2\ge s\ge 4$, there exists a constant $c_3$ such that $f_{s,t}(n)\le c_3\sqrt{n}$. In doing so, we partially answer a question of Erdős by showing that ${\lim }_{n\to \infty }\frac{f_{s+1,s+2}(n)}{f_{s,s+2}(n)}=\infty$ for any $s\ge 4$.