Abstract: | Let m(r, k) denote the minimum number of edges in an r‐uniform hypergraph that is not k‐colorable. We give a new lower bound on m(r, k) for fixed k and large r. Namely, we prove that if k ≥ 2n, then m(r, k) ≥ ?(k)kr(r/ln r)n/(n+1). © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2004 |