Covering complete \(3\)-graphs

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\).

A problem of Erdös and Tuza [1]

Let \(f_3(n)\) denote the smallest integer for which the complete \(3\)-graph on \(n\) vertices is the union of \(f_3(n)\) \(3\)-graphs, none of which contains the complete \(3\)-graph on \(4\)-vertices. Determine \(f_3(n)\).

Of course, the general question is for any given integers \( r\) and \( k\), to determine the smallest integer \( f_r(n,k)\) for which the complete \( r\)-graph on \( n\) vertices is the union of \( f_r(n,k)\) \( k\)-graphs, none of which contains the complete \( r\)-graph on \( k\)-vertices.

For graphs, an old Ramsey-type problem which can be traced back to Schur is to partition the edges of \( K_n\) into the smallest number, denoted by \( f(n)\), of triangle-free graphs. It is easy to see that \( f(n)\) is of order \( O(\log n)\). (See also this conjecture by Erdös and Graham.)


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.