The van der Waerden Number and Colorings of Hypergraphs

Combinatorics Seminar
Friday, November 16, 2012 - 15:05
1 hour (actually 50 minutes)
Skiles 005
Moscow State University and Yandex Corporate
 The talk is devoted to the classical problem of estimating the Van der Waerden number W(n,k). The famous Van der Waerden theorem states that, for any integers n\ge 3, k\ge 2, there exists the smallest integer W(n,k) such that in any k-coloring of the set {1,2,...,W(n,k)}, there exists a monochromatic arithmetic progression of length n.  Our talk is focused on the lower bounds for the van der Waerden number. We shall show that estimating W(n,k) from below is closely connected with extremal problems concerning colorings of uniform hypergraphs with large girth. We present a new lower bound for W(n,k), whose proof is based  on a continuous-time random recoloring process.