Abstract. The paper deals with extremal problems concerning colorings of hypergraphs. By using a random recoloring algorithm we show that any nuniform simple (i.e. every two distinct edges share at most one vertex) hypergraph H with maximum edge degree at most 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.
Kozik and Shabanov REF proved that any n-uniform simple hypergraph H with
Improved algorithms for colorings of simple hypergraphs and applications
ArXiv
ArXiv
Mathematics Computer Science