Search

The paper deals with extremal problems concerning colorings of hypergraphs. By using a random recoloring algorithm we show that any n -uniform simple (i.e. every two distinct edges share at most one vertex) hypergraph H with maximum edge degree at most Δ ( H ) ⩽ c ⋅ n r n − 1 is r -colorable, where c > 0 is an absolute constant. As an application of our proof technique we establish a new lower bound for Van der Waerden number W ( n , r ) , the minimum N such that in any r -coloring of the set { 1 , … , N } there exists a monochromatic arithmetic progression of length n . We show that W ( n , r ) > c ⋅ r n − 1 , for some absolute constant c > 0 . [ABSTRACT FROM AUTHOR]