Improved algorithms for colorings of simple hypergraphs and applications

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⋅nrn−1Δ(H)⩽c⋅nrn−1 is r  -colorable, where c>0c>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)W(n,r), the minimum N such that in any r  -coloring of the set {1,…,N}{1,…,N} there exists a monochromatic arithmetic progression of length n. We show thatW(n,r)>c⋅rn−1,W(n,r)>c⋅rn−1, for some absolute constant c>0c>0.