An $(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 nonuniqueness of extremal examples), thereby generalizing Turán's Theorem and confirming two conjectures of Hoffman et al.
@article{10_37236_12707,
author = {Stacie Baumann and Joseph Briggs},
title = {A proof of the \((n, k, t)\) conjectures},
journal = {The electronic journal of combinatorics},
year = {2025},
volume = {32},
number = {1},
doi = {10.37236/12707},
zbl = {1559.05081},
url = {http://geodesic.mathdoc.fr/articles/10.37236/12707/}
}
TY - JOUR
AU - Stacie Baumann
AU - Joseph Briggs
TI - A proof of the \((n, k, t)\) conjectures
JO - The electronic journal of combinatorics
PY - 2025
VL - 32
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/12707/
DO - 10.37236/12707
ID - 10_37236_12707
ER -
%0 Journal Article
%A Stacie Baumann
%A Joseph Briggs
%T A proof of the \((n, k, t)\) conjectures
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/12707/
%R 10.37236/12707
%F 10_37236_12707
Stacie Baumann; Joseph Briggs. A proof of the \((n, k, t)\) conjectures. The electronic journal of combinatorics, Tome 32 (2025) no. 1. doi: 10.37236/12707
