##
**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 < \aleph_{0}. 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 < \aleph_{0} 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 = q^{2}+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 = q^{2}+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 = q^{2}+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