Improved bounds for the Erdős-Rogers function

Abstract

The Erdős-Rogers function $f_{s,t}$ measures how large a $K_s$-free induced subgraph there must be in a $K_t$-free graph on $n$ vertices. While good estimates for $f_{s,t}$ are known for some pairs $(s,t)$, notably when $t=s+1$, in general there are significant gaps between the best known upper and lower bounds. We improve the upper bounds when $s+2\le t\le 2s-1$. For each such pair we obtain for the first time a proof that $f_{s,t}\le n^{{\alpha }_{s,t}+o(1)}$ with an exponent ${\alpha }_{s,t}<1/2$, answering a question of Dudek, Retter and Rödl.

Revised and reformatted for publication