Generalized Turán Problem for Complete Hypergraphs

Abstract. Write [Formula: see text] for the complete [Formula: see text]-graph on [Formula: see text] vertices. For integers [Formula: see text], let [Formula: see text] be the maximum density of [Formula: see text] in [Formula: see text] vertex [Formula: see text]-free [Formula: see text]-graphs. The main contribution of this paper is the upper bound: [Formula: see text]. The graph case ([Formula: see text]) is the first known generalized Turán problem, fully answered by Erdős. The [Formula: see text] case is the hypergraph Turán problem, for which the best-known general upper bound is by de Caen. The result proved here matches both bounds asymptotically, and any triple [Formula: see text] with [Formula: see text] provides a new upper bound. The proof uses techniques from the theory of flag algebras to derive linear relations between different densities. These relations can be combined using linear algebraic methods. Additionally, a simple flag algebraic certificate will be given for [Formula: see text].