On the chromatic number of set systems

An ( r ,  l )‐system is an r ‐uniform hypergraph in which every set of l vertices lies in at most one edge. Let m k ( r ,  l ) be the minimum number of edges in an ( r ,  l )‐system that is not k ‐colorable. Using probabilistic techniques, we prove that$$a_{r,l}(k^{r-1}{\rm ln}k)^{l/(l-1)}\leq m_k(r,l)\leq b_{r,l}(k^{r-1}{\rm ln}k)^{l/(l-1)},$$ where b r ,  l is explicitly defined and a r ,  l is sufficiently small. We also give a different argument proving (for even k )$$m_k(r,l)\leq a'_{r,l}k^{(r-1)l/(l-1)}.$$ where a ′ r ,  l =( r − l +1)/ r (2 r −1 re ) − l /( l −1) . Our results complement earlier results of Erdős and Lovász [10] who mainly focused on the case l =2,  k fixed, and r large. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 87–98, 2001