Induced Subgraphs of $$K_r$$-Free Graphs and the Erdős–Rogers Problem

Abstract For two graphs F, H and a positive integer n, the function $$f_{F,H}(n)$$ f F , 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 Erdős–Rogers function. Recently, Balogh, Chen and Luo, and Mubayi and Verstraë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ëte, we prove that for every positive integer r and every $$K_{r-1}$$ K r - 1 -free graph F, there exists some $$\varepsilon _F>0$$ ε F > 0 such that $$f_{F,K_r}(n)=O(n^{1/2-\varepsilon _F})$$ f F , K r ( n ) = O ( n 1 / 2 - ε F ) . This result is tight in two ways. Firstly, it is no longer true if F contains $$K_{r-1}$$ K r - 1 as a subgraph. Secondly, we show that for all $$r\ge 4$$ r ≥ 4 and $$\varepsilon >0$$ ε > 0 , there exists a $$K_{r-1}$$ K r - 1 -free graph F for which $$f_{F,K_r}(n)=\Omega (n^{1/2-\varepsilon })$$ f F , K r ( n ) = Ω ( n 1 / 2 - ε ) . Along the way of proving this, we show in particular that for every graph F with minimum degree t, we have $$f_{F,K_4}(n)=\Omega (n^{1/2-6/\sqrt{t}})$$ f F , K 4 ( n ) = Ω ( n 1

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.