** Next:** The Dual Ramsey Theorem
** Up:** Ramsey Theory
** Previous:** Hindman's Theorem

###

Szemerédi's Theorem

Another well known result of Ramsey theory is *Van der Waerden's
theorem*:

If
is colored with finitely many colors, then one of the
colors contains arithmetic progressions of arbitrary finite length.

Using a method of Shelah, Van der Waerden's theorem is known to be
provable in
.
The so-called ``density version'' of Van der
Waerden's theorem is due to Szemerédi:
If
is such that

then *A* contains arithmetic progressions of arbitrary finite
length.

Essentially nothing is known about the strength of Szemerédi's
theorem. In particular it is unknown whether Szemerédi's theorem is
provable in
.

*Stephen G Simpson*

*1999-12-15*