Induced Turán Numbers

Source abstract

The classical Kővári–Sós–Turán theorem states that if G is an n -vertex graph with no copy of K s,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,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 Turán 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,t . This result is an induced analogue of a recent theorem of Alon and Shikhelman and is of independent interest.