ABSTRACT Let be the largest size of an induced ‐free subgraph that every ‐vertex ‐free graph is guaranteed to contain. We prove that for any triangle‐free graph , Along the way we give a slight improvement of a construction of Erdős‐Frankl‐Rödl for the Brown‐Erdős‐Sós ‐problem when is large. In contrast to our result for , for any ‐free graph containing a cycle, we prove there exists such that For every graph , we prove that there exists such that whenever is a non‐empty graph such that is not contained in any blowup of , then . On the other hand, for graph that is not a clique, and every , we exhibit a ‐free graph such that .
Mubayi et al. (Fri,) studied this question.