Adding an edge to extremal \(K^{(3)}_k\)-free graph gives two copies of \(K^{(3)}_k\)

A hypergraph \( H\) consists of a vertex set \( V\) together with a family \( E\) of subsets of \( V\), which are called the edges of \( H\). A \( r\)-uniform hypergraph, or \( r\)-graph, for short, is a hypergraph whose edge set consists of \( r\)-subsets of \( V\). A graph is just a special case of an \( r\)-graph with \( r=2\).

For a finite family \( \mathcal F\) of \( r\)-graphs, one can define the Turán number \( t_r(n,{\mathcal F})\) to be the largest integer \( t\) such that there is an \( r\)-graph on \( n\) vertices with \( t\) edges which does not contain any \( F \in {\mathcal F}\) as a subgraph. We let \( K_k^{(r)}\) denote a complete \( r\)-graph on \( k\) vertices and we write \( t_r(n,K_k^{(r)})=t_r(n,k)\).

Dirac and Erdös observed that any graph on \( n\) vertices and \( t(n,k)+1\) edges contains not only a complete graph on \( k\) vertices but also a complete graph on \( k+1\) vertices with one edge missing. Rademacher observed that every graph on \( n\) vertices and \( t(n,3)+1\) edges contains \( \lfloor n/2 \rfloor \) triangles [2]. No analogous results are known for hypergraphs [1].

Conjecture [1]

Every \(3\)-graph on \(n\) vertices with \(t_3(n,k)+1\) edges must contain at least two copies of \(K_k^{(3)}\).

Bibliography
1 P. Erdös. Problems and results on set systems and hypergraphs. Extremal problems for finite sets (Visegrád, 1991), Bolyai Soc. Math. Stud., 3, pp. 217-227, János Bolyai Math. Soc., Budapest, 1994.

2 P. Erdös, On some problems in graph theory, combinatorial analysis and combinatorial number theory, Graph theory and combinatorics (Cambridge, 1983), 1-17, Academic Press, London-New York, 1984.