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.