On the asymptotics of the Erdős-Rogers function

Abstract

The Erdős-Rogers function $f_{\ell ,s}(n)$ is the largest order of a $K_{\ell }$-free induced subgraph guaranteed to exist in every $K_s$-free graph on $n$ vertices. While this function is well understood for $s=\ell +1$, the case where $s$ is much larger than $\ell$ has remained wide open. A long-standing lower bound of Sudakov states that $f_{\ell ,s}(n)\ge n^{\frac{\ell }{2s}+O_{\ell }(s^{-2})}$, while a recent result of Bradač shows that $f_{\ell ,s}(n)\le n^{\frac{\ell -1}{s-1}+o(1)}$. In this paper, we close this gap asymptotically by proving that $f_{\ell ,s}(n)=n^{\frac{\ell }{2s}+O_{\ell }(s^{-2})}$. More precisely, we prove that for all $2\le \ell <s$, we have $f_{\ell ,s}(n)\le n^{\frac{\ell }{2s-\ell }+o(1)}$. Our proof builds on Bradač's recent tight construction for off-diagonal Ramsey numbers, which can be viewed as the $\ell =2$ case of our result.

28 pages