A Proof of the $(n,k,t)$-Conjectures

Abstract

An \emph{$(n,k,t)$-graph} is a graph on $n$ vertices in which every set of $k$ vertices contains a clique on $t$ vertices. Turán's Theorem, rephrased in terms of graph complements, states that the unique minimum $(n,k,2)$-graph is an equitable disjoint union of cliques. We prove that minimum $(n,k,t)$-graphs are always disjoint unions of cliques for any $t$ (despite \allowbreak nonuniqueness of extremal examples), thereby generalizing Turán's Theorem and confirming two conjectures of Hoffman et al.