| Summary: | 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<sub>4</sub>. Indeed, in that case we can take δ = ε, and insist that one of G[X], G[X] has maximum degree at most ε2 |G|).
<br>
Second, we will show that every graph H that can be obtained by substitution from copies of P<sub>4</sub> 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<sub>4</sub> is viral, using a “polynomial P<sub>4</sub>-removal lemma” of Alon and Fox. We will also show that the class of viral graphs is closed under vertex-substitution.
<br>Finally, we give a different strengthening of Rödl’s theorem: we show that if G does not contain an induced copy of P<sub>4</sub>, then its vertices can be partitioned into at most 480ε −4 subsets X such that one of G[X], G[X] has maximum degree at most ε|X|.
|
|---|