Induced subgraph density. II. Sparse and dense sets in cographs - Fox, J; Nguyen, T; Scott, A; Seymour, P (Elsevier, 2024)
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 = P4. Indeed, in that case we can take δ = ε, and insist that one of G[X], G[X] has maximum degree at most ε2 |G|). Second, we will show that every graph H that can be obtained by substitution from copies of P4 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 P4 is viral, using a “polynomial P4-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 P4, 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|.