##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 211.27003

**Autor: ** Erdös, Paul

**Title: ** On some extremal problems on r-graphs (In English)

**Source: ** Discrete Math. 1, 1-6 (1971).

**Review: ** 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 ––> oo} 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^{(j1)}_{i1}, ... ,X^{(jr)}_{ir} \right**}**, 1 \leq i_{s} \leq t, 1 \leq j_{1} < ... < j_{r} \leq l, occur in our G^{(r)}. Several unsolved problems are posed.

**Classif.: ** * 05C35 Extremal problems (graph theory)

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag