Improved bounds for the Erd\H{o}s-Rogers (s,s+2)-problem

MaRDI QIDQ6511012arXivFDO

Authors Oliver Janzer, Benny Sudakov

Published in arXiv

Abstract: For $2leqs<t$, the ErdH{o}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 a tremendeus 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"ete on the Ramsey number $r(4,k)$ states that $f_{2,4}(n)leq{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)leq{n}^{frac2s-34s-5+o(1)}$ holds for every $sgeq2$. 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.

This page was built for publication: Improved bounds for the Erd\H{o}s-Rogers $(s,s+2)$-problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6511012)