2016/10/20 by Loh, Po-Shen, Tait, Michael, Timmons, Craig +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1610.06521
The classical Kővári-Sós-Turán theorem states that if G is an n-vertex graph with no copy of Ks,t as a subgraph, then the number of edges in G is at most O(n2-1/s). We prove that if one forbids Ks,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 Kr-free graph with no induced copy of Ks,t. This result is an induced analog of a recent theorem of Alon and Shikhelman and is of independent interest.