Induced Turan Numbers

The classical Kovari-Sos-Turan theorem states that if G is an n-vertex graph with no copy of K-s,K-t as a subgraph, then the number of edges in G is at most O(n(2-1/s)). We prove that if one forbids K-s,K-t as an induced subgraph, and also forbids any fixed graph H as a (not necessarily induced) subgraph, the same asymptotic upper bound still holds, with different constant factors. This introduces a non-trivial angle from which to generalize Turan theory to induced forbidden subgraphs, which this paper explores. Along the way, we derive a non-trivial upper bound on the number of cliques of fixed order in a K-r-free graph with no induced copy of K-s,K-t. This result is an induced analogue of a recent theorem of Alon and Shikhelman and is of independent interest.