Induced subgraph density. II. Sparse and dense sets in cographs

A well-known theorem of Rödl says that for every graph H, and every ɛ>0, there exists δ>0 such that if G does not contain an induced copy of H, then there exists X⊆V(G) with |X|≥δ|G| such that one of G[X],G¯[X] has edge-density at most ɛ. But how does δ depend on ϵ? Fox and Sudakov conjectured that the dependence is at most polynomial: that for all H there exists c>0 such that for all ɛ with 0<ɛ≤1/2, Rödl's theorem holds with δ=ɛ^c. This conjecture implies the Erdős–Hajnal conjecture, and until now it had not been verified for any non-trivial graphs H. Our first result shows that it is true when H=P₄. Indeed, in that case we can take δ=ɛ, and insist that one of G[X],G¯[X] has maximum degree at most ɛ²|G|). Second, we will show that every graph H that can be obtained by substitution from copies of P₄ satisfies the Fox–Sudakov conjecture. To prove this, we need to work with a stronger property. Let us say H is viral if there exists c>0 such that for all ɛ with 0<ɛ≤1/2, if G contains at most ɛ^c|G|^|H| copies of H as induced subgraphs, then there exists X⊆V(G) with |X|≥ɛ^c|G| such that one of G[X],G¯[X] has edge-density at most ɛ. We will show that P₄ is viral, using a “polynomial P₄-removal lemma” of Alon and Fox. We will also show that the class of viral graphs is closed under vertex-substitution. Finally, we give a different strengthening of Rödl's theorem: we show that if G does not contain an induced copy of P₄, then its vertices can be partitioned into at most 480ɛ⁻⁴ subsets X such that one of G[X],G¯[X] has maximum degree at most ɛ|X|.