An Extension of Turán's Theorem, Uniqueness and Stability

Abstract

We determine the maximum number of edges of an $n$-vertex graph $G$ with the property that none of its $r$-cliques intersects a fixed set $M\subset V(G)$.  For $(r-1)|M|\ge n$, the $(r-1)$-partite Turán graph turns out to be the unique extremal graph. For $(r-1)|M|<n$, there is a whole family of extremal graphs, which we describe explicitly. In addition we provide corresponding stability results.