##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 299.02083

**Autor: ** Erdös, Paul; Hajnal, András; Shelah, Saharon

**Title: ** On some general properties of chromatic numbers. (In English)

**Source: ** Topics in Topol., Colloqu. Keszthely 1972, Colloquia Math. Soc. Janos Bolyai 8, 243-255 (1974).

**Review: ** [For the entire collection see Zbl 278.00018.]

The starting point is the following Taylor problem [*W. Taylor*, Fundamenta Math. 71, 103-112 (1971; Zbl 238.02044); p. 106, problem 1.14]: What is the minimal cardinal number \lambda such that for every graph G with chromatic number \chi G \geq \lambda and every cardinal \sigma \geq \lambda there exists a graph G' such that \chi (G') \geq \sigma and that G,G' have the same finite graphs? According to Taylor, \lambda \geq \omega_{1}, conjecturing \lambda = \omega_{1}. The authors formulate 7 other problems, prove 3 theorems and several lemmas. E.g., if \chi (G) > \omega, then for some n < \omega the graph G contains odd circuits of length 2j+1 for every n < j < \omega (theorem 3). For any ordered set (R, \prec) and any i < \omega the authors define two sorts of graphs G^{0}(R,i) for i > 1 and G^{1}(R,i,t) for i > 2, 1 \leq t < i-1 as \prec-increasing i-sequences of points of R such that G^{0}(R,i) = **{**(\phi , \phi') | \phi (j+1) = \phi'(j) for j < i-1 **}** for i \geq 2 and

G^{1}(R,i,t) = **{**\phi , \phi') | \phi (j+t) < \phi'(t) < \phi (j+t+1) < \phi'(j+1) for j < i-1-t **}** for t \geq 3; they put

S^{0}(i) = \psi (G^{0}(\omega ,i), \omega) = \psi (G^{0}(R,i), \omega) for |R| \geq \omega and

S^{1}(i,t) = \psi (G^{1}(\omega ,i,t), \omega) = \psi (G^{1}(R,i,t), \omega) for |R| \geq \omega; the graphs S^{0},S^{1} are called ``edge graphs'' and Specker graphs respectively. Notations: For any cardinality \tau \geq \omega let B(\tau) be the system of all subgraphs of cardinality < \tau of some complete graph with \tau vertices; put A(\tau) = P(B(\tau)). If G is a given graph let

\psi (G, \tau): = **{**G' | G' in B(\tau), G' being isomorphic to a subgraph of G **}** . For S in A(\tau) let G(S, \tau) be the class of graphs G satisfying \psi (G, \tau) \subset S in A(\tau); S is said \tau-unbounded if for every cardinal \lambda there is some G in G(S, \tau) satisfying \chi (G) > \lambda. For a given operation F on cardinals satisfying Fx \geq x^+, the authors say that S in A(\omega) is \omega-unbounded with the restriction F, if for every \sigma there is some \lambda \geq \sigma and a graph G such that \psi (G, \omega) \subset S, \chi (G) > \lambda and |G| \leq F(\lambda). In particular, S is \omega-unbounded with restriction \xi if S is so with the restriction F_{\xi} where

F_{\xi} (\lambda) = \kappa <==> \lambda = \omega_{\alpha} , \kappa = \omega_{\alpha+1+\xi}. Theorem 1: (\alpha) S^{1}(i,t) is \omega-unbounded with restriction 0 for 2 \leq i < \omega; (\beta) S^{0}(i) is \omega-unbounded with restriction \exp_{i-1} (\lambda)^+ for 2 \leq i < \omega; (\gamma) S^{0}(i) is not \omega-unbounded with the restriction \exp_{i-1} (\lambda) for 2 \leq i < \omega.

**Reviewer: ** D.Kurepa

**Classif.: ** * 03E55 Large cardinals

03C68 Other classical first-order model theory

05C15 Chromatic theory of graphs and maps

05-02 Research monographs (combinatorics)

**Citations: ** Zbl 278.00018; Zbl 238.02044

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag