Loading Events
  • This event has passed.
Stochastics and Statistics Seminar

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)

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)$:
where $c>0$ is an absolute constant. The proof is based on a continuous-time random recoloring process.

MIT Statistics + Data Science Center
Massachusetts Institute of Technology
77 Massachusetts Avenue
Cambridge, MA 02139-4307