Abstract
We consider the problem of finding ex (n; G), defined as the maximal number of edges anr-graph onn vertices can have that contains no subgraph isomorphic toG. We construct certainr-graphsG for which we find the coefficientτ(G) of the asymptotic expansion ex(n;G)==\((\tau (G) + o(1))\left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)\) asn→∞.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
B. Bollobás, Tree-graphs without two triples whose symmetric difference is contained in a third,Discrete Math.,8 (1974), 21–24.
W. G. Brown andM. Simonovits, Digraph extremal problems, hypergraph extremal problems, and the densities of graph structures,Discrete Math.,48 (1984), 147–162.
D.de Caen, On Turan's hypergraph problem,Ph. D. Thesis, Univ. Toronto, 1982.
P. Erdős andT. Gallai, On maximal paths and circuits of graphs,Acta Math. Hung.,10 (1959), 337–356.
P.Erdős, Extremal problems in graph theory, In:Theory of graphs and its applications, Proc. Sympos. Smolenice, Prague, 1964, 29–36.
P. Erdős andM. Simonovits, A limit theorem in graph theory,Studia Math. Hung.,1 (1966), 51–57.
P. Frankl andV. Rödl, Hypergraphs do not jump,Combinatorica,4 (1984), 149–159.
G. Katona, T. Nemetz andM. Simonovits, On a graph problem of Turan,Mat. Lapok,XV. 1–3 (1964), 228–238, (in Hungarian).
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.
A. F. Sidorenko, The method of quadratic forms and Turán's combinatorial problem,Moscow. Univ. Math. Bull.,37 (1982), 3–6.
A. F. Sidorenko, On the maximal number of edges in a uniform hypergraph without forbidden subgraphs,Math. Notes,41 (1987), 247–259.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Sidorenko, A.F. Asymptotic solution for a new class of forbiddenr-graphs. Combinatorica 9, 207–215 (1989). https://doi.org/10.1007/BF02124681
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02124681