Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 236.05120
Autor: Erdös, Paul; Hajnal, András
Title: Problems and results in finite and infinite combinatorial analysis. (In English)
Source: Ann. New York Acad. Sci. 175, 115-124 (1970).
Review: In der Arbeit werden Kantenzerlegungen h = \bigcup\xi < \gamma h\xi von Graphen h betrachtet, wobei die h\xi paarwise kantendisjunkte Graphen sind. (g1, \alpha) ––> (g2, \gamma) bedeutet, daß jeder Graph h mit \alpha Ecken, der keinen zu g1 isomorphen Teilgraphen enthält, eine Kantenzerlegung h = \bigcup\xi < \gamma h\xi zuläßt, wobei kein h\xi einen zu g2 isomorphen Teilgraphen besitzt. Weiter bedeutet g ––> (g\xi)2\xi, daß für jede Kantenzerlegung g = \bigcup\xi < \gamma h\xi mindestens ein h\xi einen zu g\xi isomorphen Teilgraphen besitzt. In dieser Notation wird über einige Ergebnisse und Probleme vom Ramsey-Typ berichtet: (K\omega,\omega2) ––> (Kn, \omega) ist für n \geq 3 ungeklärt; für natürliche Zahlen k,l wird die Existenz von n mit (C2k-1,n) (not)––> (C2k+1,l) bewiesen, wobei Cm Kreis mit m Ecken; die Existenz von n mit (Kk,n) (not)––> (Kk-1,r) ist für r > 3 nicht bekannt. Eine Klasse K von Graphen hat die (uneingeschränkte) G-R-Eigenschaft, wenn zu jedem g in K (und jedem \gamma) ein h in K existiert, so daß h ––> (g,g)(h ––> (g\xi)2\gamma mit g\xi = g für alle \xi). Es werden mehrere Klassen in Bezug auf die (uneingeschränkte) G-R-Eigenschaft diskutiert und in diesem Zusammenhang weitere Probleme formuliert.
Reviewer: H.A.Jung
Classif.: * 05C99 Graph theory
05A99 Classical combinatorial problems
00A07 Problem books
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag