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.