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

Abstract

A well-known theorem of Rödl says that for every graph $H$, and every $\hat{I}\mu >0$, there exists $\hat{I}´>0$ such that if $G$ does not contain an induced copy of $H$, then there exists $X\subseteq V(G)$ with $|X|\ge \hat{I}´|G|$ such that one of $G[X],\overline{G}[X]$ has edge-density at most $\hat{I}\mu$. But how does $\hat{I}´$ depend on $\hat{I}\mu$? Fox and Sudakov conjectured that the dependence is at most polynomial: that for all $H$ there exists $c>0$ such that for all $\hat{I}\mu$ with $0<\hat{I}\mu \le 1/2$, Rödl's theorem holds with $\hat{I}´=\hat{I}{\mu }^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_4$. Indeed, in that case we can take $\hat{I}´=\hat{I}\mu$, and insist that one of $G[X],\overline{G}[X]$ has maximum degree at most $\hat{I}{\mu }^2|G|$). Second, we will show that every graph $H$ that can be obtained by substitution from copies of $P_4$ satisfies the Fox-Sudakov conjecture. To prove this, we need to work with a stronger property. Let us say $H$ is {\em viral} if there exists $c>0$ such that for all $\hat{I}\mu$ with $0<\hat{I}\mu \le 1/2$, if $G$ contains at most $\hat{I}{\mu }^c|G{|}^{|H|}$ copies of $H$ as induced subgraphs, then there exists $X\subseteq V(G)$ with $|X|\ge \hat{I}{\mu }^c|G|$ such that one of $G[X],\overline{G}[X]$ has edge-density at most $\hat{I}\mu$. We will show that $P_4$ is viral, using a ``polynomial $P_4$-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_4$, then its vertices can be partitioned into at most $480\hat{I}{\mu }^{-4}$ subsets $X$ such that one of $G[X],\overline{G}[X]$ has maximum degree at most $\hat{I}\mu |X|$.