Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 178.27301
Autor: Erdös, Pál; Simonovits, M.
Title: A limit theorem in graph theory (In English)
Source: Stud. Sci. Math. Hungar. 1, 51-57 (1966).
Review: Sei f = f(n; Gi,...,Gl) die kleinste ganze Zahl, so daß jeder Graph mit n Punkten und f Kanten mindestens einen der Graphen Gi,...,Gl als Teilgraphen enthält. Die Verff. zeigen limn ––> oo (f(n; Gi,...,Gl)/\binom{n}{2}) = l-1/(r-1), wo r das Minimum der chromatischen Zahlen der Graphen Gi,...,Gl ist. Sie verallgemeinern damit die entsprechende Aussage für l = 1, G1 = Kp = der vollständige Graph mit p Punkten, die man aus den Ergebnissen von P.Turán [Mat. Fiz. Lapok 48, 436-452 (1941; Zbl 026.26903), vgl. Colloq. Math. 3, 19-30 (1954; Zbl 055.17004)] gewinnt.
Interessant ist auch die Abschätzung f(n; G0) \leq g(n; Kp) für \binom{p}{2} \leq l \leq \binom{p+1}{2} (l die Zahl der Kanten von G0) und hinreichend großes n. Einen ähnlichen Grenzwertsatz wie oben gewinnen die Verff. für die kleinste ganze Zahl h = h(n; G1,...,Gl; k), für die es einen Graphen G mit n Punkten und h Kanten gibt, so daß jeder durch k Punkte von G aufgespannte Teilgraph von G mindestens einen der Graphen G1,...,Gl als Teilgraphen enthält. Für l = 1 und spezielle Wahl von G1 gewinnen die Verff. exakte Ergebnisse für h. An verschiedenen Stellen werden offene Probleme aufgezeigt, so daß die Arbeit trotz des teilweise schwierigen Sachverhalts anregend ist.
Druckfehler: \pi(Hj) \leq k statt \nu(Hj) \leq k in Theorem 1'.
Reviewer: W.Wessel (Berlin)
Classif.: * 05C35 Extremal problems (graph theory)
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag