In 2022, Holmsen showed that any graph with at least \( c \binom{ n}{ r} \) \(r\)-cliques but no induced complete $r$-partite graph $K_{ 2,\ldots, 2}$ must contain a clique of order \(\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\binom{ n}{ r}$ copies of $K_r$ (for some constant $c>0$) and forbidding semi-induced substructures, related to $K_{ 2,\ldots, 2}$, must contain a clique of order $\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.
Categories: math.CO