Extending the concept of Ramsey numbers, Erd{H o}s and Rogers introduced the following function. For given integers $2le s<t$ let $$ f_{s,t}(n)=min {max {|W| : Wsubseteq V(G) {and} G[W] {contains no} 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 $sge 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 geq s geq 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 ErdH{o}s by showing that $lim_{nto infty} frac{f_{s+1,s+2}(n)}{f_{s,s+2}(n)}=infty$ for any $sge 4$.
Download