Satz von van der Waerden

Der Satz von van der Waerden (nach Bartel Leendert van der Waerden) ist ein Satz aus der Kombinatorik, genauer aus der Ramseytheorie.

Er besagt, dass für alle natürlichen Zahlen ${\displaystyle r}$ und ${\displaystyle l}$ eine natürliche Zahl ${\displaystyle N=N(r,l)}$ existiert, so dass gilt:

Färbt man die Zahlen ${\displaystyle 1,2,\ldots ,N}$ mit ${\displaystyle r}$ „Farben“, so existiert eine arithmetische Progression der Länge ${\displaystyle l}$ in ${\displaystyle 1,2,\ldots ,N}$, die gleich gefärbt (monochrom) ist.

Eine arithmetische Progression der Länge ${\displaystyle l}$ ist das Anfangsstück einer arithmetischen Folge, so ist z. B. ${\displaystyle 3,33,63,93}$ eine arithmetische Progression der Länge 4 (vier Zahlen mit gleichen Abständen, hier 30). Eine arithmetische Progression der Länge 2 ist jede zweielementige Teilfolge der natürlichen Zahlen.

Der Satz nennt nur die Existenz einer endlichen Zahl ${\displaystyle N(r,l)}$. Im Folgenden bezeichnet ${\displaystyle N(r,l)}$ die kleinste natürliche Zahl mit der obigen Eigenschaft. Eine Formel dafür, wie groß genau diese Zahl für allgemeine ${\displaystyle r,l}$ ist, ist bisher nicht bekannt.