A step towards the Erdős-Rogers problem

Abstract

For $2\le k\le t<s$, the Erdős-Rogers function $f_{t,s}^{(k)}(N)$ denotes the largest $m$ such that every $K_s^{(k)}$-free $k$-graph on $N$ vertices contains a $K_t^{(k)}$-free induced subgraph on $m$ vertices. Mubayi and Suk (J. London Math. Soc. 2018) conjectured that $f_{k+1,k+2}^{(k)}(N)=({\log }_{(k-2)}N{)}^{\hat{I}˜(1)}$ for $k\ge 4$, where ${\log }_{(i)}$ denotes the $i$-fold iterated logarithm. This is equivalent to the statement that $f_{k+1,s}^{(k)}(N)=({\log }_{(k-2)}N{)}^{\hat{I}˜(1)}$ for every $s\ge k+2$. In this paper, we introduce multi-color patterns into a random construction of a $2$-graph to build a $4$-graph, and for the first time, combine them with multi-layer extremum structures to prove that $f_{5,s}^{(4)}(N)=(\log \log N{)}^{\hat{I}˜(1)}$ for every $s\ge 11$. More generally, using a variant of the Erdős-Hajnal stepping-up lemma, we also establish that $f_{k+1,s}^{(k)}(N)=({\log }_{(k-2)}N{)}^{\hat{I}˜(1)}$ for every $s\ge k+7$.