Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 289.04002
Autor: Erdös, Paul; Hajnal, András; Rothchild, B.
Title: On chromatic number of graphs and set systems. (In English)
Source: Cambridge Summer School math. Logic, Cambridge 1971, Lecture Notes Math. 337, 531-538 (1973).
Review: [For the entire collection see Zbl 261.00006.]
Für Kardinalzahlen \alpha,\beta,\gamma,k,i mit 2 \leq k < \omega, 1 \leq i < k gilt per definitionem R(\alpha,\beta,\gamma,k,i), wenn zu jedem Mengensystem H = (h,H) mit |h| = \alpha, Chr(H) > \beta und |S| = k für alle S in H ein H' \subseteq H mit |H'| = \gamma und |\cap H'| \geq i existiert; dabei bedeutet Chr(H) die kleinste Kardinalzahl \delta, so daß eine Zerlegung h = \bigcup\sigma < \deltah\sigma existiert mit S \not\subseteq h\sigma für alle S in H und \sigma < \delta. P. Erdös und A. Hajnal hatten fälschlicherweise R(\alpha,\beta,\beta ^+,k,k-1) behauptet [Acta Math. Acad. Sci. Hungar. 17, 61-99 (1966; Zbl 151.33701)].
Theorem 1: Für \beta = \omega\xi und 3 \leq k < \omega gilt R(\beta ^+, \beta,\beta ^+,k,k-1), weiter R(\alpha , \beta , \beta ^+,k,2) für \alpha \leq \omega\xi+k-2. Theorem 2: Für \beta = \omega\xi, 3 \leq k < \omega, 2 \leq i \leq k-1 und \alpha = (\expk-1(\beta))^+ gilt R(\alpha, \beta ,2,k,i) nicht; dabei \exp0(\beta) = \beta und \expj+1(\beta) = 2\expj(\beta). Unter Voraussetzung der allgemeinen Kontinuumshypothese ist damit der Gültigkeitsbereich von R(\alpha,\beta,\gamma,k,k-1) und R(\alpha,\beta,\gamma,k,2) bekannt.
In Theorem 3 wird gezeigt, daß die sich aus Satz 2 ergebenden Schranken nicht in allen Fällen scharf sind. Der kleinste ungeklärte Fall ist R(\omega2,\omega ,2,5,3).
Reviewer: H.A.Jung
Classif.: * 04A20 Combinatorial set theory
05C15 Chromatic theory of graphs and maps
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag