2024/07/03 by Dhruv Mubayi, Jacques Verstraëte, Mubayi, Dhruv +1
Mathematics · #05C55 #05D10 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #advanced mathematical theories
paper · pdf · doi:10.48550/arxiv.2407.03121
openalex publication_date 2024/07/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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,K3(n) = fK2,K3(n)1 + o(1) = n(1)/(2) + o(1). Along the way we give a slight improvement of a construction of Erd\H os-Frankl-Rödl for the Brown-Erd\H os-Sós (3r-3,3)-problem when r is large. In contrast to our result for K3, for any K4-free graph F containing a cycle, we prove there exists cF > 0 such that fF,K4(n) gt; fK2,K4(n)1 + cF = n(1)/(3)+cF+o(1). \iffalse We also observe that our earlier proof for F=K3 generalizes to fF,K4(n) = O(√(n)log n) for all F containing a cycle. \fi 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-ε).