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 \omega1, conjecturing \lambda = \omega1. 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 G0(R,i) for i > 1 and G1(R,i,t) for i > 2, 1 \leq t < i-1 as \prec-increasing i-sequences of points of R such that

G0(R,i) = {(\phi , \phi') | \phi (j+1) = \phi'(j) for j < i-1 }

for i \geq 2 and

G1(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

S0(i) = \psi (G0(\omega ,i), \omega) = \psi (G0(R,i), \omega)

for |R| \geq \omega and

S1(i,t) = \psi (G1(\omega ,i,t), \omega) = \psi (G1(R,i,t), \omega)

for |R| \geq \omega; the graphs S0,S1 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) S1(i,t) is \omega-unbounded with restriction 0 for 2 \leq i < \omega; (\beta) S0(i) is \omega-unbounded with restriction \expi-1 (\lambda)^+ for 2 \leq i < \omega; (\gamma) S0(i) is not \omega-unbounded with the restriction \expi-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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page