Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 151.33702
Autor: Erdös, Pál; Hajnal, András; Milner, E.C.
Title: On the complete subgraphs of graphs defined by systems of sets (In English)
Source: Acta Math. Acad. Sci. Hung. 17, 159-229 (1966).
Review: Ein Mengensystem F = (F,M,S) (F Abbildung von M in die Potenzmenge von S) heißt (m,\alpha)-System, wenn |M| = m und S wohlgeordnet vom Typ tpS = \alpha; B \subseteq S heißt (F,k)-vollständig), wenn zu jedem A \subseteq B mit |A| = k (bzw. |A| < k) ein \mu in M mit A \subseteq F\mu existiert; C \subseteq S heißt (F,n)-frei, wenn |{\mu in M | F\mu \cap C = Ø } | \geq n. Die Verff. untersuchen Relationen von folgender oder ähnlicher Art: (1) \alpha ––> [\beta,\gamma]km; (2) \alpha ––> [\beta,\gamma]m. (1), (2) besagen, daß zu jedem (m,\alpha)-System F = (F,M,S) ein (F,m)-freies C \subseteq S mit tpC = \gamma existiert oder im Fall (1) ein (F,k)-vollständiges B \subseteq S mit tpB = \beta, im Fall (2) ein F\mu mit tpF\mu \geq \beta. (1), (2) gehen in Relationen analogen Inhalts über, wenn \alpha,\beta,\gamma durch Kardinalzahlen ersetzt werden. \alpha ––> [\beta,\gamma]m < k wird ähnlich wie (1) interpretiert (... oder ein (F, < k)-vollständiges B \subseteq S mit tpB = \beta).
Ein Hauptergebnis [unter Benutzung der G. C. H. (generalized continuum hypothesis)]: m ––> [m,m]n < \aleph0 (m,n > \aleph0), schärfer m ==> [m,m]n falls m,n > \aleph0 und m' \ne n' (m' = \alephcf(\alpha), wenn m = \aleph\alpha). Weiter wird \alpha ––> [\beta,\gamma]\aleph0 < \aleph0 für \alpha , \beta , \gamma < \omega1 vollständig diskutiert. In der Folge werden höhere Fälle von (1) bewiesen, z.B.: \omega1\omega ––> [\omega1\omega,\omega1n ]\aleph1 < \aleph0 (n < \omega) und \omega1\lambda ––> [\omega1\lambda,\omega1\omega]2\aleph0 (\omega \leq \lambda < \omega2). Die Relation (3) von der Form (a,m,n,c)k ––> s beinhaltet, daß zu jedem (m,a)-System F = (F,M,S) ein (F,n)-freies C \subseteq S mit |C| = c oder eine Darstellung S = A \cup \bigcupi in I Bi mit |I| < s, |A| < a und (F,k)-vollständigen Bi (i in I) existiert. Für k,m,n,s < \aleph0 wird die Äquivalenz von (3) mit einem endlichen Problem gezeigt und z. B. bewiesen: (a,m,n,c)k ––> s, falls n \geq s, m \geq k(n-s+1)+s-1, a \geq \aleph0 und a \geq c \geq 1.
Weitere Ergebnisse zu (3): (\aleph0,\aleph0,\aleph0,\aleph0)k ––> 3 (k < \aleph0) und (a,m,m,m)2 ––> m ( m \geq \aleph0, m Nachfolgerzahl oder m' = \aleph0).
In der Arbeit werden außerdem viele negative Resultate, z.B. m^+\not ––> [m^+,m]mm^+ (m \geq \aleph0) bewiesen, einige Fragen auf den Partitionskalkül zurückgeführt und 15 Probleme explizite formuliert.
Reviewer: H.A.Jung
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag