Summary: A theorem of Rödl states that for every fixed \(F\) and \(\varepsilon>0\) there is \(\delta=\delta_F(\varepsilon)\) so that every induced \(F\)-free graph contains a vertex set of size \(\delta n\) whose edge density is either at most \(\varepsilon\) or at least \(1-\varepsilon\). Rödl's proof relied on the regularity lemma, hence it supplied only a tower-type bound for \(\delta \). \textit{J. Fox} and \textit{B. Sudakov} [Adv. Math. 219, No. 6, 1771--1800 (2008; Zbl 1152.05054)] conjectured that \(\delta\) can be made polynomial in \(\varepsilon\), and a recent result of \textit{J. Fox} et al. [``Induced subgraph density. II. Sparse and dense sets in cographs, Preprint, \url{arXiv:2307.00801}] shows that this conjecture holds when \(F=P_4\). In fact, they show that the same conclusion holds even if \(G\) contains few copies of \(P_4\). In this note we give a short proof of a more general statement.
This page was built for publication: On Rödl's theorem for cographs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6197319)
