On the maximum F-free induced subgraphs in Kₜ-free graphs

For graphs F and H, let fF,H(n) be the minimum possible size of a maximum F-free induced subgraph in an n-vertex H-free graph. This notion generalizes the Ramsey function and the Erd{o}s--Rogers function. Establishing a container lemma for the F-free subgraphs, we give a general upper bound on fF,H(n), assuming the existence of certain locally dense H-free graphs. In particular, we prove that for every graph F with ex(m,F) = O(m1+α), where α ∈ [0,1/2), we have \[ fF, K_3(n) = O(n1/2-α(log n)3/2- α) and fF, K_4(n) = O(n1/3-2α(log n)6/3-2α). \] For the cases where F is a complete multipartite graph, letting s = ∑ᵢ₌₁ʳ sᵢ, we prove that \[ f_{Ks_1,…,s_r, Kᵣ₊₂}(n) = O ( n2s -3/4s -5 (log n)³ ). \] We also make an observation which improves the bounds of ex(G(n,p),C₄) by a polylogarithmic factor.