WikiSort.ru - Не сортированное

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

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

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

Примечания

Ссылки

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