Turán's conjecture: hypergraph Turán numbers: \(t_r(n, 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. Stated in this generality, the problem of determining or estimating \( t_r(n,{\mathcal F})\) represents an overwhelming cornucopia of challenging problems, almost all of which are untouched.

Although the most celebrated of these problems is not due to Erdös, but rather to his close collaborator (and next-door neighbor for many years) Paul Turán, Erdös liked it so much that he offered \(1000 for its solution [1]. (Usually, Erdös did not offer prizes for problems which he did not originate). The problem is for the case \( r=3\) where \( \mathcal F\) consists of the single complete \( 3\)-graph \( K_4^{3}\), consisting of all \( 4\) triples on \( 4\) vertices. 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)\).

Turán's conjecture for \(r\)-graphs, $1000 (proposed by Turán, 1941)

Determine, for \( 2 < r < k \) , \[ \lim_{n \rightarrow \infty} \frac{t_3(n,k)}{\binom{n}{r}} . \]

It is easy to show the limit exists.

Bibliography
1 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.