×

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.

MSC:
05C35 Extremal problems in graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Brown, W.G., On graphs that do not contain a thomsen graph, Canad. math. bull, 9, 281-285, (1966) · Zbl 0178.27302
[2] Erdös, P., Extremal problems in graph theory, Proc. symp. on graph theory, 29-36, (1964), Smolenice
[3] Erdös, P., On extremal problems of graphs and generalized graphs, Israel J. math., 2, 183-190, (1965) · Zbl 0129.39905
[4] Erdös, P., Of some new inequalities concerning extremal properties of graphs, (), 83-98
[5] Erdös, P.; Rénfi, A., On the evolution of ramdom graphs, Publ. math. inst. hung. acad., 5, 17-61, (1960)
[6] Erdös, P.; Simonovits, M., A limit theorem in graph theory, Studia sci. math. hung. acad., 1, 51-57, (1966) · Zbl 0178.27301
[7] Erdös, P.; Stone, A.H., On the structure of linear graphs, Bull. am. math. soc., 52, 1087-1091, (1946) · Zbl 0063.01277
[8] 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)
[9] Katona, Gy.; Nemetz, T.; Simonovits, M., On a graph problem of Turán, Mat. lapok, 15, 228-238, (1964), (in Hungarian) · Zbl 0138.19402
[10] 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
[11] Simonovits, M., A method for solving extremal problems in graph theory stability problems, (), 279-319
[12] Turán, P., Mat. és phys. lapok, 48, 436-452, (1941), (in Hungarian)
[13] 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.