Improved bounds for the Erdős-Rogers function

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\leq t\leq 2s-1$. For each such pair we obtain for the first time a proof that $f_{s,t}\leq n^{α_{s,t}+o(1)}$ with an exponent $α_{s,t}<1/2$, answering a question of Dudek, Retter and Rödl.

No reviews yet.

No comments yet.