Multipass Greedy Coloring of Simple Uniform Hypergraphs

Let m*(n) be the minimum number of edges in an n-uniform simple hypergraph that is not two colorable. We prove that m*(n) = Omega (4n/ ln2 (n)). Our result generalizes to r-coloring of b-simple uniform hypergraphs. For fixed r and b we prove that a maximum vertex degree in b-simple n-uniform hypergraph that is not r-colorable must be Omega (r(n)/ ln(n)). By trimming arguments it implies that every such graph has Omega ((r(n)/ ln(n)) b+1/b) edges. For any fixed r >= 2 our techniques yield also a lower bound Omega (r(n)/ ln(n)) for van derWaerden numbersW(n, r). (c) 2015 Wiley Periodicals, Inc.