Erd{o}s-Rogers functions for arbitrary pairs of graphs

Let fF,G(n) be the largest size of an induced F-free subgraph that every n-vertex G-free graph is guaranteed to contain. We prove that for any triangle-free graph F, \[ fF,K_3(n) = fK_2,K_3(n)1 + o(1) = n1/2 + o(1).\] Along the way we give a slight improvement of a construction of Erd os-Frankl-R\"odl for the Brown-Erd os-S\'os $(3r-3,3)$-problem when r is large. In contrast to our result for K₃, for any K₄-free graph F containing a cycle, we prove there exists cF > 0 such that fF,K₄(n) > fK₂,K₄(n)1 + cF = n1/3+cF+o(1). We also observe that our earlier proof for F=K₃ generalizes to fF,K₄(n) = O(√nlog n) for all F containing a cycle. For every graph G, we prove that there exists εG >0 such that whenever F is a non-empty graph such that G is not contained in any blowup of F, then fF,G(n) = O(n1-εG). On the other hand, for graph G that is not a clique, and every ε>0, we exhibit a G-free graph F such that fF,G(n) = Ω(n1-ε).