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

Stacie Baumann, Joseph Briggs

Published 2022-10-15Version 1

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\'an'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\'an's Theorem and confirming two conjectures of Hoffman et al.