• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Improved algorithms for colorings of simple hypergraphs and applications

Journal of Combinatorial Theory. Series B. 2016. Vol. 116. P. 312-332.
Shabanov D. A., Kozik J.

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 not large maximum edge degree is r-colorable. 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.