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

Запрос «теорема ван дер Вардена»?! перенаправляется сюда. На эту тему нужно создать отдельную статью.

Теорема ван дер Вардена из теории Рамсея утверждает, что для любых натуральных чисел $r$ и $k$ существует такое положительное целое число $N$, что если целые числа $\{1,2,...,N\}$ окрашены, каждый в один из $r$ различных цветов, то найдётся по крайней мере $k$ целых чисел в арифметической прогрессии того же цвета. Наименьшее такое $N$ называется числом ван дер Вардена $W(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\geq 2$ ограничиваются сверху

$W(r,k)\leq 2^{2^{r^{2^{2^{k+9}}}}}$

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

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

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

Задача типа Ван дер Вардена:

Определение: Числом Ван дер Вардена W(k,r) называется минимальное такое n, что при любой раскраске первых n чисел натурального ряда в r цветов найдется одноцветная арифметическая прогрессия длины k.

Чему равно W(2,r)?
а) Доказать конечность W(3,2),W(3,3). 
б) Доказать, что W(3,2) = 9.

Решение.

Для W(3,2), во втором случае просто перебор. Более концептуальное доказательство - взять n = 65 × 5, разбить множество на 65 групп по 5 элементов. Далее, среди первых 33 5-элементных подмножеств будет два одинаково раскрашенных. Пусть это 1-е и 23-е подмножества. Внутри каждого из них среди первых трех элементов есть одноцветная арифметическая прогрессия длины 2, пусть это элементы 1 и 3, и пусть они окрашены в красный цвет. Тогда элемент 5 в обоих подмножествах (1-м и 23-м) покрашен в синий цвет, и тогда, если рассмотреть элемент 5 в 45-м 5-элементном подмножестве, он не может быть ни красным, ни синим. 

Ссылки

• Ссылка на задачу: https://mipt.ru/upload/481/seminar_3_2013_fivt-arpheeq7o8f.pdf
• Теория Рамсея