Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 381.04004
Autor: Erdös, Paul; Hajnal, András
Title: Embedding theorems for graphs establishing negative partition relations. (In English)
Source: Period. Math. Hung. 9, 205-230 (1978).
Review: The graph G1 is said to embed into the graph G1 if G0 is isomorphic to a spanned subgraph of G1. Given cardinal numbers \kappa and \lambda, the symbol [\kappa] denotes the complete graph on \kappa vertices, [\kappa\lambda] the complete (\kappa\lambda)-bipartite graph and , [\kappa/\kappa] the half (\kappa/\kappa)-bipartite graph (where the set of vertices is a disjoint union G0\cup G1 with |G0| = |G1| = \kappa and there are one-to-one enumerations G0 = {x\alpha; \alpha < \kappa}, G1 = {y\beta; \beta < \kappa} such that for each x\alpha, the set of vertices adjacent to x\alpha is {y\beta; \alpha < \beta < \kappa}). Let \triangle0, \triangle1 be symbols of these types: The graph G is said to establish the negative partition relation \kappa (not)––> (\triangle0,\triangle1)2 if G is a graph on \kappa vertices such that G contains no subgraph of type \triangle0 and the complement of G contains no subgraph of type \triangle1. The main aim of this paper is to characterize the class of all countable graphs which embed into all graphs G establishing \aleph1 (not)––> (\triangle0,\triangle1)2 when \triangle0, \triangle1 are any of [\aleph1], [\aleph1,\aleph1], [\aleph1/\aleph1], [\aleph0,\aleph1], The authors prove their theorems in ZFC, and then try to show that they are ''best possible'' assuming the continuum hypothesis or the existence of a Souslin tree. Occasionally Souslin's axiom is invoked instead.
Reviewer: N.H.Williams
Classif.: * 04A20 Combinatorial set theory
03E05 Combinatorial set theory (logic)
03E30 Axiomatics of classical set theory and its fragments
05C99 Graph theory
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag