2014/09/24 by Jakub Kozik, Kozik, Jakub, D. A. Shabanov +1 · 1 citation
Computer Science · Mathematics · #05C15 #05C65 #05D40 #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #G.2.2 #G.3 #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1409.6921
openalex publication_date 2014/09/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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, is r-colorable, where c>0 is an absolute constant. %We prove also that similar result holds for b-simple hypergraphs. 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)gt;c⋅ rn-1, for some absolute constant c>0.