Abstract: An $(n,k,t)$-graph is a graph on $n$ vertices in which every set of $k$ vertices contain a clique on $t$ vertices. Turán's Theorem (complemented) states that the unique minimum $(n,k,2)$-graph is a disjoint union of cliques. We prove that minimum $(n,k,t)$-graphs are always disjoint unions of cliques for any $t$ (despite nonuniqueness of extremal examples), thereby generalizing Turán's Theorem and confirming two conjectures of Hoffman et al. 

 

This is joint work with Joseph Briggs.