A further extension of Rödl's theorem (Q6133166)

Summary: Fix \(\varepsilon>0\) and a graph \(H\) with at least one vertex. A well-known theorem of \textit{V. Rödl} from the 80s [Discrete Math. 59, 125--134 (1986; Zbl 0619.05035)] says that every graph \(G\) with no induced copy of \(H\) contains a linear-sized \(\varepsilon\)-restricted set \(S\subseteq V(G)\), which means \(S\) induces a subgraph with maximum degree at most \(\varepsilon |S|\) in \(G\) or its complement. There are two extensions of this result: \begin{itemize} \item quantitatively, \textit{V. Nikiforov} [Comb. Probab. Comput. 15, No. 6, 895--902 (2006; Zbl 1120.05072)] (and later \textit{J. Fox} and \textit{B. Sudakov} [Adv. Math. 219, No. 6, 1771--1800 (2008; Zbl 1152.05054)]) relaxed the condition ``no induced copy of \(H\)'' into ``at most \(\kappa|G|^{|H|}\) induced copies of \(H\) for some \(\kappa>0\)'' depending on \(H\) and \(\varepsilon \); and \item qualitatively, \textit{M. Chudnovsky} et al. [``Strengthening Rödl's theorem'', Preprint, \url{arXiv:2105.07370}] recently showed that there exists \(N>0\) depending on \(H\) and \(\varepsilon\) such that \(G\) is \((N,\varepsilon\)-restricted, which means \(V(G)\) has a partition into at most \(N\) subsets that are \(\varepsilon\)-restricted. \end{itemize} A natural common generalization of these two asserts that every graph \(G\) with at most \(\kappa|G|^{|H|}\) induced copies of \(H\) is \((N,\varepsilon)\)-restricted for some \(\kappa,N>0\). This is unfortunately false, but we prove that for every \(\varepsilon>0, \kappa\) and \(N\) still exist so that for every \(d\geqslant 0\), every graph with at most \(\kappa d^{\vert H\vert}\) induced copies of \(H\) has an \((N,\varepsilon)\)-restricted induced subgraph on at least \(\vert G\vert-d\) vertices. This unifies the two aforementioned theorems, and is optimal up to \(\kappa\) and \(N\) for every value of \(d\).