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 limn ––> oo f(n; r,l)/\binom{n}{r} = cr,l. The values of cr,l are not known for r > 2. I prove that to every \epsilon > 0 and integer t there is an n0 = n0(t, \epsilon) so that every G(r)(n; [(cr,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 is \leq t, 1 \leq j1 < ... < jr \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