A Note on Generalized Erdős-Rogers Problems

Abstract

For a $k$-uniform hypergraph $F$ and positive integers $s$ and $N$, the generalized Erdős-Rogers function $f_{F,s}^{(k)}(N)$ denotes the largest integer $m$ such that every $K_s^{(k)}$-free $k$-graph on $N$ vertices contains an $F$-free induced subgraph on $m$ vertices. In particular, if $F=K_t^{(k)}$, then we write $f_{t,s}^{(k)}(N)$ for $f_{F,s}^{(k)}(N)$. Mubayi and Suk (\emph{J. London. Math. Soc. 2018}) conjectured that $f_{5,6}^{(4)}(N)=(\log \log N{)}^{\hat{I}˜(1)}$. Motivated by this conjecture, we prove that $f_{5^{-},6}^{(4)}(N)=(\log \log N{)}^{\hat{I}˜(1)}$, where $5^{-}$ denotes the $4$-graph obtained from $K_5^{(4)}$ by deleting one edge. Our proof combines a probabilistic construction of a $2$-coloring of pairs with a stepping-up construction and an analysis of multi-layer local extremum structures. Furthermore, we derive an upper bound for a more general Erdős-Rogers function, which implies the lower bound $r_4(6,n)\ge 2^{2^{c{n}^{1/2}}}$. By applying a variant of the Erdős-Hajnal stepping-up lemma due to Mubayi and Suk, we also slightly improve the lower bound for $r_k(k+2,n)$.