Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4656692 | Journal of Combinatorial Theory, Series B | 2016 | 21 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Jakub Kozik, Dmitry Shabanov,