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

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

Во-первых, когда число цветов ${\displaystyle r}$ равно 1, очевидно ${\displaystyle W(1,\;k)=k}$ для любого целого ${\displaystyle k}$, так как один цвет производит только тривиальные раскраски RRRR…RRR (для одного цвета, обозначаемого ${\displaystyle R}$).

Во-вторых, если длина ${\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)}$.

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