Graphs with no induced \(K_{2,t}\) (Q2223473)

Summary: Consider a graph \(G\) on \(n\) vertices with \(\alpha \binom{n}{2}\) edges which does not contain an induced \(K_{2, t}\) \((t \geqslant 2)\). How large must \(\alpha\) be to ensure that \(G\) contains, say, a large clique or some fixed subgraph \(H\)? We give results for two regimes: for \(\alpha\) bounded away from zero and for \(\alpha = o(1)\). Our results for \(\alpha = o(1)\) are strongly related to the Induced Turán numbers which were recently introduced by \textit{P.-S. Loh} et al. [Comb. Probab. Comput. 27, No. 2, 274--288 (2018; Zbl 1387.05123)]. For \(\alpha\) bounded away from zero, our results can be seen as a generalisation of a result of \textit{A. Gyárfás} et al. [Combinatorica 22, No. 2, 269--274 (2002; Zbl 0996.05094)] and more recently \textit{A. F. Holmsen} [Combinatorica 40, No. 4, 527--537 (2020; Zbl 1474.05211)] (whose argument inspired ours).