Induced Turán numbers

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 nontrivial angle from which to generalize Turán theory to induced forbidden subgraphs, which this paper explores. Along the way, we derive a nontrivial 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 analog of a recent theorem of Alon and Shikhelman and is of independent interest.

This version has minor changes from the referee and is to appear in Combinatorics, Probability, and Computing. An alternate proof of the main theorem using dependent random choice has been added as well as the fourth author