Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 084.19701
Autor: Erdös, Pál; Rado, R.
Title: Partition relations connected with the chromatic number of graphs. (In English)
Source: J. London Math. Soc. 34, 63-72 (1959).
Review: G sei ein Graph, \Phi(G) die Anzahl seiner Punkte, X(G) seine chromatische Zahl, d.h. Mindestzahl an Farben, um seine Punkte zu färben, daß durch Kanten verbundene Punkte verschiedenfarbig sind. Nach einem Satz von J. B. Kelly und L. M. Kelly (Zbl 056.16902) gibt es zu jeder endlichen Zahl a dreiecksfreie endliche Graphen G mit X(G) = a. Dieser Satz wird erweitert für a \geq \aleph0. Unter der Annahme, daß die verallgemeinerte Kontinuums-Hypothese 2\aleph\nu = \aleph\nu+1 gilt, gibt es sogar Graphen mit X(G) = \Phi(G) = a.
Im 2. Teil wird in Analogie zu Verteilungs-Relationen in einer früheren Arbeit (Zbl 071.05105) ein neuer Typ von Verteilungs-Relationen und eine Verallgemeinerung der Baireschen Kategorien eingeführt. |M| sei die Mächtigkeit der Menge M. Ist \Omega eine Menge von Mengen, so heißt die Menge M von 1. \Omega-Kategorie, wenn M \subset sumX in \Omega' X und \Omega' \subset \Omega mit |\Omega'| < |\Omega|, andernfalls von 2. \Omega-Kategorie. Die unendliche Kardinalzahl a heißt "regulär", wenn sie nicht Summe von Kardinalzahlen < a ist. [M]2 bedeute die Menge aller Elementepaare von M. Es gilt folgender Satz: Ist \Omega eine Menge von Mengen, |\Omega| unendlich regulär, A eine Menge von 2. \Omega-Kategorie, \Lambda die Menge aller Teilmengen von A, die von 2. \Omega-Kategorie sind, und K0+K1, irgendeine Verteilung der Menge [A]2, so gibt es eine Teilmenge X von A, so daß entweder [X]2 \subset K0 und |X| = \aleph0 oder [X]2 \subset K1 und X in \Lambda. Daß die Regularität von |\Omega| notwendig ist, wird an einem Beispiel gezeigt.
Reviewer: H.Künneth
Classif.: * 05D10 Ramsey theory
05C15 Chromatic theory of graphs and maps
04A20 Combinatorial set theory
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag