Large cliques in graphs with forbidden semi-induced structures

In 2022, Holmsen showed that any graph with at least $c\left(\genfrac{}{}{0px}{}{n}{r}\right)$ $r$-cliques but no induced complete $r$-partite graph $K_{2,\dots ,2}$ must contain a clique of order $\mathrm{\Omega }(c^{2^{r-1}}n)$. In this paper, we study graphs forbidding semi-induced substructures and show that every $n$-vertex graph $G$ containing at least $c\left(\genfrac{}{}{0px}{}{n}{r}\right)$ copies of $K_r$ (for some constant $c>0$) and forbidding semi-induced substructures, related to $K_{2,\dots ,2}$, must contain a clique of order $\mathrm{\Omega }(cn)$. Our result strengthens Holmsen’s bound by improving the dependence on $c$ from $c^{2^{r-1}}$ to linear in $c$ with bounded number of forbidden structures. Furthermore, our approach is naturally linked to the notion of VC-dimension.