- This event has passed.

# Van der Warden Number and Coloring of Hypergraphs with Large Girth

## March 20, 2012 @ 11:00 am

Dmitry Shabanov (Yandex and Moscow Institute of Physics and Technology)

### Event Navigation

The talk is devoted to the classical problem of estimating the Van der Waerden number $W(n,r)$. The famous Van der Waerden theorem states that, for any integers $nge 3$, $rge 2$, there exists the smallest integer $W(n,r)$ such that, for every $Nge W(n,r)$, in any $r$-coloring of the set ${1,2,ldots,N}$ there exists a monochromatic arithmetic progression of length $n$. The best upper bound for $W(n,r)$ in the general case was obtained by W.T. Gowers in 2001 who proved thatW(n,r)≤22r22n+9.

Our talk is concentrated on the lower bounds for the Van der Waerden number. We shall show that lower estimates for $W(n,r)$ are closely connected with extremal problems concerning colorings of uniform hypergraphs with large girth. Our main result is a new lower bound for $W(n,r)$:

W(n,r)≥crn−1lnn,

where $c>0$ is an absolute constant. The proof is based on a continuous-time random recoloring process.