Maximum unavoidable hypergraphs

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 \( r\)-graph \( H\) is said to be \( (n,e)\)-unavoidable if \( H\) is contained in every \( r\)-graph with \( n\) vertices and \( e\) edges. Let \( f_r(n,e)\) denote the largest integer \( m\) with the property that there exists an \( (n,e)\)-unavoidable \( r\)-graph having \( m\) edges.

A problem on unavoidable hypergraphs (proposed by Chung and Erdös [1])

Determine \(f_r(n,e)\).

For the case of \( r=2\) and \( 3\), the solutions can be found in [2], [1].

Bibliography
1 F. R. K. Chung and P. Erdös, On unavoidable hypergraphs, J. Graph Theory 11 (1987), 251-263.

2 F. R. K. Chung and P. Erdös, On unavoidable graphs, Combinatorica 3 (1983), 167-176.