Exact values for \(t_3(n, 4) \)

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

The case of \( r=3\) and \( k=4\) is of special interest.

Turán's conjecture for \(3\)-graphs, $500 (proposed by Turán[4], 1941)

\[ t_3(n,4) = \left\{ \begin{array}{c l} k^2(5k-3)/2 & \mbox{ if \(n=3k\),} \\ k(5k^2+2k-1)/2 & \mbox{ if \(n=3k+1\) }\\ k(k+1)(5k+2) & \mbox{ if \(n=3k+2\). } \end{array} \right. \]

Many constructions are known which achieve this value [1], [3]. For example, in [3], Kostochka showed that there are \( 2^{k-2}\) non-isomorphic extremal \( 3\)-graphs on \( 3k\) vertices. The above conjecture, if true, will give

\(\displaystyle \lim_{n \rightarrow \infty} \frac{t_3(n,4)}{\binom{n}{3}} = \frac{5}{ 9}. \)

The best current upper bound for the ratio is \( (-1+\sqrt{21})/6=.5971 \dots\) due to Giraud (unpublished, mentioned in [2]).


Bibliography
1 W. G. Brown, On an open problem of Paul Turán concerning \( 3\)-graphs, Studies in Pure Math., 91-93, Birkhäuser, Basel-Boston, MA, 1983.

2 D. de Caen, The current status of Turán's problem on hypergraphs, Extremal Problems for Finite Sets, Visegrád, 1991, Bolyai Soc. Math. Studies 3, 187-197.

3 A. V. Kostochka, A class of constructions for Turán's \( (3,4)\)-problem, Combinatorica 2 (1982), 187-192.

4 P. Turán, On an extremal problem in graph theory (in Hungarian), Mat. Fiz. Lapok. 48 (1941), 436-452. English translation in Collected Papers of Paul Turán (P. Erdös, ed.), 231-240, Akadémiai Kiadó, Budapest, 1990.