Induced Subgraphs of K_r-Free Graphs and the Erdos-Rogers Problem

For two graphs F, H and a positive integer n, the function fF,H (n) denotes the largest m such that every H-free graph on n vertices contains an F-free induced subgraph on m vertices. This function has been extensively studied in the last 60 years when F and H are cliques and became known as the Erdos-Rogers function. Recently, Balogh, Chen and Luo, and Mubayi and Verstra & euml;te initiated the systematic study of this function in the case where F is a general graph. Answering, in a strong form, a question of Mubayi and Verstra & euml;te, we prove that for every positive integer r and every Kr-1-free graph F, there exists some epsilon F > 0 such that fF,Kr (n) = O(n1/2-epsilon F ). This result is tight in two ways. Firstly, it is no longer true if F contains Kr-1 as a subgraph. Secondly, we show that for all r >= 4 and epsilon > 0, there exists a Kr-1-free graph F for which fF,Kr (n) = ETX(n1/2-epsilon). Along the way of proving this, we show in particular that for every graph F with minimum degree t, we have fF,K4 (n) = ETX(n1/2-6/ root t ). This answers (in a strong form) another question ofMubayi and Verstra & euml;te. Finally, we prove that there exist absolute constants 0 < c < C such that for each r >= 4, if F is a bipartite graph with sufficiently large minimum degree, then ETX(n c log r )