Число ван дер Вардена

Є два випадки, в яких число ван дер Вардена ${\displaystyle W(r,\;k)}$ легко обчислити:

1. коли число кольорів ${\displaystyle r}$ дорівнює 1, очевидно ${\displaystyle W(1,\;k)=k}$ для будь-якого цілого ${\displaystyle k}$, оскільки один колір виробляє тільки тривіальні розфарбування RRRR…RRR (якщо колір позначити ${\displaystyle R}$).
2. якщо довжина ${\displaystyle K}$ необхідної арифметичної прогресії дорівнює 2, то ${\displaystyle W(r,\;2)=r+1}$, оскільки можна побудувати розфарбування, уникаючи арифметичних прогресій довжини 2, використовуючи кожен колір не більше одного разу, але використання будь-якого кольору двічі створює арифметичну прогресію довжини 2. (Наприклад, для ${\displaystyle r=3}$ найдовшим розфарбуванням, за якого не утворюється арифметична прогресія довжини 2, є RGB.)

Є тільки сім інших чисел ван дер Вардена, які відомі точно.

У таблиці наведено точні значення та межі значень ${\displaystyle W(r,\;k)}$.

Вільям Гауерс довів, що числа ван дер Вардена з ${\displaystyle R\geqslant 2}$ обмежуються зверху[1]

${\displaystyle W(r,\;k)\leqslant 2^{2^{r^{2^{2^{k+9}}}}}.}$

Елвін Берлекемп довів, що для простого числа ${\displaystyle p}$, 2-колірне число ван дер Вардена обмежене знизу[2]

${\displaystyle p\cdot 2^{p}\leqslant W(2,\;p+1).}$

Іноді також використовується позначення ${\displaystyle w(r;\;k_{1},\;k_{2},\;\ldots ,\;k_{r})}$, яке означає найменше число ${\displaystyle w}$ таке, що будь-яке розфарбування цілих чисел ${\displaystyle \{1,\;2,\;\ldots ,\;w\}}$ в ${\displaystyle r}$ кольорів містить прогресію довжини ${\displaystyle k_{i}}$ кольору ${\displaystyle i}$, для деяких ${\displaystyle i}$. Такі числа називаються недіагональними числами ван дер Вардена.

Таким чином: ${\displaystyle W(r,\;k)=w(r;\;k,\;k,\;\ldots ,\;k)}$.

• Завдання типу Ван Дер Варден
• Теорія Рамсея