# zbMATH — the first resource for mathematics

On some extremal problems on $$r$$-graphs. (English) Zbl 0211.27003
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.
Show Scanned Page ##### MSC:
 05C35 Extremal problems in graph theory
Full Text:
##### References:
  Brown, W.G., On graphs that do not contain a thomsen graph, Canad. math. bull, 9, 281-285, (1966) · Zbl 0178.27302  Erdös, P., Extremal problems in graph theory, Proc. symp. on graph theory, 29-36, (1964), Smolenice  Erdös, P., On extremal problems of graphs and generalized graphs, Israel J. math., 2, 183-190, (1965) · Zbl 0129.39905  Erdös, P., Of some new inequalities concerning extremal properties of graphs, (), 83-98  Erdös, P.; Rénfi, A., On the evolution of ramdom graphs, Publ. math. inst. hung. acad., 5, 17-61, (1960)  Erdös, P.; Simonovits, M., A limit theorem in graph theory, Studia sci. math. hung. acad., 1, 51-57, (1966) · Zbl 0178.27301  Erdös, P.; Stone, A.H., On the structure of linear graphs, Bull. am. math. soc., 52, 1087-1091, (1946) · Zbl 0063.01277  Erdös, P.; Rénfi, A.; Sós, V.T., On a problem of graph theory, Studia sci. math. hung. acad., 1, 215-235, (1966)  Katona, Gy.; Nemetz, T.; Simonovits, M., On a graph problem of Turán, Mat. lapok, 15, 228-238, (1964), (in Hungarian) · Zbl 0138.19402  Kövári, T.; Sós, V.T.; Turán, P., On a problem of zarankiewicz, Coll. mat., 3, 50-57, (1954) · Zbl 0055.00704  Simonovits, M., A method for solving extremal problems in graph theory stability problems, (), 279-319  Turán, P., Mat. és phys. lapok, 48, 436-452, (1941), (in Hungarian)  Turán, P., On the theory of graphs, Coll. math., 3, 19-30, (1954) · Zbl 0055.17004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.