On the order of Erdős-Rogers functions

Abstract

For an integer $n\ge 1$, the Erdős-Rogers function $f_s(n)$ is the maximum integer $m$ such that every $n$-vertex $K_{s+1}$-free graph has a $K_s$-free subgraph with $m$ vertices. It is known that for all $s\ge 3$, $f_s(n)=\Omega (\sqrt{n\log n}/\log \log n)$ as $n\to \infty$. In this paper, we show that for all $s\ge 3$, \begin{equation*} f_{s}(n) = O(\sqrt{n}\, \log n). \end{equation*} This improves previous bounds of order $\sqrt{n}(\log n{)}^{2(s+1{)}^2}$ by Dudek, Retter and Rödl.

8 pages, 2 figures