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