Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 324.04005
Autor: Erdös, Paul; Galvin, Fred; Hajnal, András
Title: On set-systems having large chromatic number and not containing prescribed subsystems. (In English)
Source: Infinite finite Sets, Colloq. Honour Paul Erdös, Keszthely 1973, Colloq. Math. Soc. Janos Bolyai 10, 425-513 (1975).
Review: [For the entire collection see Zbl 293.00009.]
This lengthy paper is devoted to a variety of problems concerning the chromatic number of set systems. A ``set system'' is defined to be a family of S of sets each of at least two elements. The ``chromatic number'' of S is the smallest cardinal \kappa for which there is a partition of length \kappa of \cup S, \cup S = \cup {P\nu; \nu < \kappa }, such that A \not\subseteq P\nu whenever A in S, \nu < \kappa. The family S is said to be an (n,i)-system if it is a family of n-tuples every two of which have at most i elements in common. – In an earlier paper [Cambridge Summer School Math. Logic, Cambridge 1971, Lecture Notes Math. 337, 531-538 (1973; Zbl 289.04002)], P. Erdös, A. Hajnal and B. Rothchild have shown that if 1 \leq i \leq n < \omega \leq \kappa then there is an (n,i)-system with chromatic number > \kappa, and that the cardinality of such a system must be large. One of the aims of the present paper is to determine just how large. The following are proved: (a) Assume mi+2 \leq n < \aleph0. Let S be a system of n-tuples with |S| = \aleph\alpha+m such that every \aleph\alpha+1-size subset of S has at most i elements in its intersection. Then S has chromatic number at most \aleph\alpha. (b) Assume 2 \leq n < mi+2 < \aleph0 and that G.C.H. holds. Then there is an (n,i)-system of cardinality \aleph\alpha+m and chromatic number > \aleph\alpha. – The G.C.H. is needed in (b), for it is shown that if MA\kappa holds then every (3,1)-system of cardinality \kappa has chromatic number at {u in P |u ~ x, u ~ y, u ~ z }. Bose has proved that |tr(x,y,z)| = q+1. The triple (x,y,z), x \not ~ , y \not ~ z, z \not ~ x, is said to be regular provided each point collinear with at least three points of tr(x,y,z) is actually collinear with all points of tr(x,y,z). If for a point x each triple (x,y,z), with x \not ~ y, y \not ~ z, z \not ~ x, is regular, x is said to be regular. The following theorems are proved. a) If the 4-gonal configuration S with parameters r = q2+1 and k = q+1, where q is even and q > 2, possesses a regular point, then S is isomorphic to a 4-gonal configuration T(0) (i.e. a 4-gonal configuration arising from an ovoid 0 of PG(3,q)) of J. Tits. b) If each point of the 4-gonal configuration S with parameters r = q2+1 and k = q+1 (q > 2) is regular, then S is isomorphic to the 4-gonal configuration Q(5,q) arising from a non-singular hyperquadric Q of index 2 of PG(5,q). c) Suppose that the 4-gonal configuration S = (P,B,I), with parameters r = q2+1 and k = q+1 (q > 1), has a 4-gonal subconfiguration S' = (P' ,B' ,I), with parameters k' = r' = k, for which the following condition is satisfied: if x,y,z in P' with x \not ~ y, y \not ~ z, z \not ~ x, then the triple (x,y,z) is regular and moreover sp(x,y,z) \subset P'. Then we have (i) S has an involution with fixes P' pointwise (ii) S' is isomorphic to the 4-gonal configuration Q(4,q) arising from a non-singular hyperquadric in PG(4,q). – Remark: Recently the author has proved a) for q odd.
Reviewer: P.Erdös
Classif.: * 04A20 Combinatorial set theory
04A10 Ordinal and cardinal numbers; generalizations
05C15 Chromatic theory of graphs and maps
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag