Improved bounds for the Erdős-Rogers $(s,s+2)$-problem

Abstract

For $2\le s<t$, the Erdős-Rogers function $f_{s,t}(n)$ measures how large a $K_s$-free induced subgraph there must be in a $K_t$-free graph on $n$ vertices. There has been an extensive amount of work towards estimating this function, but until very recently only the case $t=s+1$ was well understood. A recent breakthrough of Mattheus and Verstraëte on the Ramsey number $r(4,k)$ states that $f_{2,4}(n)\le n^{1/3+o(1)}$, which matches the known lower bound up to the $o(1)$ term. In this paper we build on their approach and generalize this result by proving that $f_{s,s+2}(n)\le n^{\frac{2s-3}{4s-5}+o(1)}$ holds for every $s\ge 2$. This comes close to the best known lower bound, improves a substantial body of work and is the best that any construction of similar kind can give.

8 pages