On some extremal problems on \(r\)-graphs (Q2544168): Difference between revisions

Denote by \(G^{(r)}(n;k)\) an \(r\)-graph of \(n\) vertices and \(k\) \(r\)-tuples. Turán's classical problem states: Determine the smallest integer \(f(n;r,l)\) so that every \(G^{(r)}(n;f(n;r,l))\) contains a \(K^{(r)}(l)\). Turán determined \(f(n;r,l)\) for \(r=2\), but nothing is known for \(r>2\). Put \(\lim_{n \to \infty} f(n;r,l)/\binom{n}{r}=c_{r,l}\). The values of \(c_{r,l}\) are not known for \(r>2\). I prove that to every \(\epsilon >0\) and integer \(t\) there is an \(n_0=n_0(t, \epsilon)\) so that every \(G^{(r)}(n;[(c_{r,l}+ \epsilon)(\binom{n}{r}])\) has \(lt\) vertices \(x^{(j)}_i\), \(1 \leq i \leq t\), \(1 \leq j \leq l\), so that all the \(r\)-tuples \(\left\{X^{(j_1)}_{i_1}, \ldots ,X^{(j_r)}_{i_r} \right\}\), \(1 \leq i_s \leq t\), \(1 \leq j_1< \ldots <j_r \leq l\), occur in our \(G^{(r)}\). Several unsolved problems are posed.