##
**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 G_{1} is said to embed into the graph G_{1} if G_{0} is isomorphic to a spanned subgraph of G_{1}. 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 G_{0}\cup G_{1} with |G_{0}| = |G_{1}| = \kappa and there are one-to-one enumerations G_{0} = **{**x_{\alpha}; \alpha < \kappa**}**, G_{1} = **{**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 \triangle_{0}, \triangle_{1} be symbols of these types: The graph G is said to establish the negative partition relation \kappa (not)––> (\triangle_{0},\triangle_{1})^{2} if G is a graph on \kappa vertices such that G contains no subgraph of type \triangle_{0} and the complement of G contains no subgraph of type \triangle_{1}. The main aim of this paper is to characterize the class of all countable graphs which embed into all graphs G establishing \aleph_{1} (not)––> (\triangle_{0},\triangle_{1})^{2} when \triangle_{0}, \triangle_{1} are any of [\aleph_{1}], [\aleph_{1},\aleph_{1}], [\aleph_{1}/\aleph_{1}], [\aleph_{0},\aleph_{1}], 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