Set systems with finite chromatic number

In this paper we consider the chromatic number of set systems, i.e. the minimal cardinality k for which the ground set can be colored by k colors with no monocolored member of the system. We are especially interested in the case when k is finite (but the system may be infinite). Another property widely investigated is the transversal property, i.e. when the system has a one-to-one choice function. If the system consists of finitely many finite sets, a very satisfactory characterization is known; such an \({\mathcal H}\) has the transversal property if the union of any t members of \({\mathcal H}\) has at least t elements. Compactness arguments extend this to the case when an arbitrary number of finite sets is given. For systems consisting of both finite and infinite sets a (much more complex) characterization has recently been proved by \textit{R. Aharoni, \textit{C. St. J. A. Nash-William}} and \textit{S. Shelah} [A general criterion for the existence of transversals, Proc. Lond. Math. Soc. 47, No.3, 43-68 (1983; Zbl 0522.05002)], successfully using and extending the tools elaborated by \textit{S. Shelah} [Whitehead groups may be not free even assuming Ch. II. Isr. Math. J. 35, 257-285 (1980; Zbl 0467.03049)].

Recommendations

Cites work

Cited in

(5)

This page was built for publication: Set systems with finite chromatic number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q805616)