On the chromatic number of set systems

An (r, l)-system is an r-uniform hypergraph in which every set of l vertice s 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) ln k)(l/l(.-1)) less than or equal to m(k)(r, l) less than or equal to b(r,l)(k(r-1) ln k)(l/(l-1)), where b(r,l) is explicitly defined and a(r,l) is sufficiently small. We als o give a different argument proving (for even k) m(k)(r, l) greater than or equal to 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 Erdos and Lovasz [10] who mainly focused on the case l = 2, k fixed, and r large. (C) 2001 John Wiley & Sons , Inc.