Erdős-Rogers functions for arbitrary pairs of graphs

Abstract

Let $f_{F,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$, \[ f_{F,K_3}(n) = f_{K_2,K_3}(n)^{1 + o(1)} = n^{\frac{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 $K_3$, for any $K_4$-free graph $F$ containing a cycle, we prove there exists $c_F>0$ such that $$f_{F,K_4}(n)>f_{K_2,K_4}(n{)}^{1+c_F}=n^{\frac{1}{3}+c_F+o(1)}.$$ \iffalse We also observe that our earlier proof for $F=K_3$ generalizes to $f_{F,K_4}(n)=O(\sqrt{n}\log n)$ for all $F$ containing a cycle. \fi For every graph $G$, we prove that there exists ${\epsilon }_G>0$ such that whenever $F$ is a non-empty graph such that $G$ is not contained in any blowup of $F$, then $f_{F,G}(n)=O(n^{1-{\epsilon }_G})$. On the other hand, for graph $G$ that is not a clique, and every $\epsilon >0$, we exhibit a $G$-free graph $F$ such that $f_{F,G}(n)=\Omega (n^{1-\epsilon })$.