
























For $2\leq 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)\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^{\frac{2s-3}{4s-5}+o(1)}$ holds for every $s\geq 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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。