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

Числом ван дер Вардена $W(r,\;k)$ называется наименьшее $N$ такое, что в любой раскраске множества $\{1,\;2,\;\ldots ,\;N\}$ в $r$ цветов найдётся одноцветная арифметическая прогрессия длины $k$. Существование этих чисел гарантирует теорема ван дер Вардена из теории Рамсея.

Оценка чисел ван дер Вардена

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

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

Во-вторых, если длина $K$ требуемой арифметической прогрессии равна 2, то $W(r,\;2)=r+1$, так как можно построить раскраску, которая избегает арифметических прогрессий длины 2, используя каждый цвет не более одного раза, но используя любой цвет дважды, создает арифметическую прогрессию длины 2. (Например, для $r=3$ самой длинной раскраской, избегающей арифметической прогрессии длины 2, является RGB.)

Есть только семь других чисел ван дер Вардена, которые известны точно.

В приведенной ниже таблице приведены точные значения и границы значений $W(r,\;k)$.

k\r	2 цвета	3 цвета	4 цвета	5 цветов	6 цветов
3	9	27	76	>170	>223
4	35	293	>1048	>2254	>9778
5	178	>2173	>17 705	>98 740	>98 748
6	1132	>11 191	>91 331	>540 025	>816 981
7	>3703	>48 811	>420 217	>1 381 687	>7 465 909
8	>11 495	>238 400	>2 388 317	>10 743 258	>57 445 718
9	>41 265	>932 745	>10 898 729	>79 706 009	>458 062 329
10	>103 474	>4 173 724	>76 049 218	>542 694 970	>2 615 305 384
11	>193 941	>18 603 731	>30 551 357	>2 967 283 511	>3 004 668 671

Уильям Гауэрс доказал, что числа ван дер Вардена с $R\geqslant 2$ ограничиваются сверху

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

Элвин Берлекэмп доказал, что для простого числа $p$, 2-цветное число ван дер Вардена количество ограничено снизу

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

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

Таким образом: $W(r,\;k)=w(r;\;k,\;k,\;\ldots ,\;k)$.

Ссылки

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