Erdős, Paul; Galvin, Fred; Hajnal, András On set-systems having large chromatic number and not containing prescribed subsystems. (English) Zbl 0324.04005 Infinite finite Sets, Colloq. Honour Paul Erdős, Keszthely 1973, Colloq. Math. Soc. János Bolyai 10, 425-513 (1975). 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 0289.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 \sim x, u \sim y, u \sim z \}\). Bose has proved that \(|tr(x,y,z)| =q+1\). The triple \((x,y,z)\), \(x \not\sim\), \(y \not\sim z\), \(z \not\sim 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\sim y\), \(y \not\sim z\), \(z \not\sim 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 \(\mathrm{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 \(\mathrm{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\sim y\), \(y \not\sim z\), \(z \not\sim 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 \(\mathrm{PG}(4,q)\). Remark: Recently the author has proved a) for \(q\) odd.[For the entire collection see Zbl 0293.00009.] Reviewer: Pál Erdős (Budapest) Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page Cited in 2 ReviewsCited in 3 Documents MSC: 03E05 Other combinatorial set theory 03E10 Ordinal and cardinal numbers 05C15 Coloring of graphs and hypergraphs Citations:Zbl 0293.00009; Zbl 0289.04002 PDFBibTeX XML