Multipass greedy coloring of simple uniform hypergraphs

Letm * ( n ) be the minimum number of edges in an n ‐uniform simple hypergraph that is not two colorable. We prove thatm * ( n ) = Ω ( 4 n / ln 2 ( 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 Ω ( r n / ln ( n ) ) . By trimming arguments it implies that every such graph has Ω ( ( r n / ln ( n ) ) b + 1 / b ) edges. For any fixed r   ⩾   2 our techniques yield also a lower bound Ω ( r n / ln ( n ) ) for van der Waerden numbers W ( n, r ). © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 125–146, 2016