zbMATH — the first resource for mathematics

Asymptotic solution for a new class of forbidden r-graphs. (English) Zbl 0732.05031
Summary: We consider the problem of finding ex(n;G), defined as the maximal number of edges an r-graph on n vertices can have that contains no subgraph isomorphic to G. We construct certain r-graphs G for which we find the coefficient \(\tau\) (G) of the asymptotic expansion \(ex(n;G)=(\tau (G)+o(1))\left( \begin{matrix} n\\ r\end{matrix} \right)\) as \(n\to \infty\).

05C35 Extremal problems in graph theory
05C65 Hypergraphs
Full Text: DOI
[1] B. Bollobás, Tree-graphs without two triples whose symmetric difference is contained in a third,Discrete Math.,8 (1974), 21–24. · Zbl 0291.05114 · doi:10.1016/0012-365X(74)90105-8
[2] W. G. Brown andM. Simonovits, Digraph extremal problems, hypergraph extremal problems, and the densities of graph structures,Discrete Math.,48 (1984), 147–162. · Zbl 0541.05035 · doi:10.1016/0012-365X(84)90178-X
[3] D.de Caen, On Turan’s hypergraph problem,Ph. D. Thesis, Univ. Toronto, 1982.
[4] P. Erdos andT. Gallai, On maximal paths and circuits of graphs,Acta Math. Hung.,10 (1959), 337–356. · Zbl 0090.39401 · doi:10.1007/BF02024498
[5] P.Erdos, Extremal problems in graph theory, In:Theory of graphs and its applications, Proc. Sympos. Smolenice, Prague, 1964, 29–36.
[6] P. Erdos andM. Simonovits, A limit theorem in graph theory,Studia Math. Hung.,1 (1966), 51–57.
[7] P. Frankl andV. Rödl, Hypergraphs do not jump,Combinatorica,4 (1984), 149–159. · Zbl 0663.05047 · doi:10.1007/BF02579215
[8] G. Katona, T. Nemetz andM. Simonovits, On a graph problem of Turan,Mat. Lapok,XV. 1–3 (1964), 228–238, (in Hungarian).
[9] T. S. Motzkin andE. G. Strauss, Maxima of graphs and a new proof of a theorem of Turan,Canadian J. of Math.,17 (1965), 533–540. · Zbl 0129.39902 · doi:10.4153/CJM-1965-053-6
[10] A. F. Sidorenko, The method of quadratic forms and Turán’s combinatorial problem,Moscow. Univ. Math. Bull.,37 (1982), 3–6. · Zbl 0515.05037
[11] A. F. Sidorenko, On the maximal number of edges in a uniform hypergraph without forbidden subgraphs,Math. Notes,41 (1987), 247–259. · Zbl 0677.05064
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.