Generalized Tur\'an problem for Complete Hypergraphs

MaRDI QIDQ6426544zbMATH OpenFDO

Authors Levente Bodnar

Publication date 15 February 2023

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65) Extremal set theory (05D05)

Abstract: Write $K_n^{(k)}$ for the complete $k$-graph on $n$ vertices. For $2leqkleqg<r$ integers, let $pileft(n,K_g^{(k)},K_r^{(k)}ight)$ be the maximum density of $K_g^{(k)}$ in $n$ vertex $K_r^{(k)}$-free $k$-graphs. The main contribution of this paper is the upper bound: $$ The graph case ($k=2$) is the first known generalized Tur'an question, investigated by ErdH{o}s. The $k=g$ case is the hypergraph Tur'an problem where the best known general upper bound is by de Caen. The result proved here matches both bounds asymptotically, while any triple $k,g,r$ with $2<k<g<r$ 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 with linear algebraic methods. Additionally a simple flag algebraic certificate will be given for $li{m}_{nightarrowinfty}pileft(n,K_4^{(3)},K_5^{(3)}ight)=3/8$.

This page was built for publication: Generalized Tur\'an problem for Complete Hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6426544)