2024/09/10 by Lior Gishboliner, Oliver Janzer, Gishboliner, Lior +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2409.06650
openalex publication_date 2024/09/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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 Kr-1-free graph F, there exists some εF>0 such that fF,Kr(n)=O(n1/2-ε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 ε>0, there exists a Kr-1-free graph F for which fF,Kr(n)=Ω(n1/2-ε). Along the way of proving this, we show in particular that for every graph F with minimum degree t, we have fF,K4(n)=Ω(n1/2-6/√(t)). This answers (in a strong form) another question of Mubayi and Verstraëte. Finally, we prove that there exist absolute constants 0